87 lines
2.1 KiB
C++
87 lines
2.1 KiB
C++
#include <iostream>
|
|
#include "Search.hpp"
|
|
#include "Move.hpp"
|
|
#include "Board.hpp"
|
|
|
|
#include <algorithm>
|
|
|
|
int Search::search(Node *node, const Board &board, unsigned depth, int alpha, int beta) {
|
|
|
|
if (depth == 0) {
|
|
return evaluate(board);
|
|
}
|
|
|
|
auto moves = Board::MoveVec();
|
|
board.pseudoLegalMoves(moves);
|
|
if (moves.empty()) {
|
|
return evaluate(board);
|
|
}
|
|
std::stable_sort(moves.begin(), moves.end());
|
|
|
|
int maxValue = kNegInfinity;
|
|
for (auto &kMove: moves) {
|
|
Board nodeBoard = board;
|
|
nodeBoard.makeMove(kMove);
|
|
|
|
Node child(kMove);
|
|
child.value = search(&child, nodeBoard, depth - 1, -beta, -alpha);
|
|
|
|
auto value = -child.value;
|
|
if (value > maxValue) {
|
|
maxValue = value;
|
|
node->next = std::make_unique<Node>(child);
|
|
}
|
|
|
|
alpha = std::max(alpha, value);
|
|
if (alpha >= beta) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
node->value = maxValue;
|
|
|
|
return maxValue;
|
|
}
|
|
|
|
int Search::evaluate(const Board &board) {
|
|
|
|
return board.evaluate();
|
|
}
|
|
|
|
|
|
PrincipalVariation Search::start(const Board &board) {
|
|
auto rootMoves = Board::MoveVec();
|
|
board.pseudoLegalMoves(rootMoves);
|
|
std::stable_sort(rootMoves.begin(), rootMoves.end());
|
|
|
|
if (rootMoves.size() <= 1) {
|
|
auto b = board;
|
|
return PrincipalVariation(rootMoves, b);
|
|
}
|
|
|
|
std::unique_ptr<RootNode> best = std::make_unique<RootNode>();
|
|
for (const auto &kMove: rootMoves) {
|
|
|
|
auto node = Node(kMove);
|
|
|
|
Board nodeBoard = board;
|
|
nodeBoard.makeMove(kMove);
|
|
|
|
auto value = -search(&node, nodeBoard, 5, kNegInfinity, kPosInfinity);
|
|
if (value > best->value) {
|
|
best->child = std::make_unique<Node>(node);
|
|
best->board = nodeBoard;
|
|
best->value = value;
|
|
}
|
|
}
|
|
|
|
auto moves = std::vector<Move>();
|
|
auto current = std::move(best->child);
|
|
do {
|
|
moves.push_back(current->move);
|
|
current = std::move(current->next);
|
|
} while (current);
|
|
|
|
return PrincipalVariation(moves, best->board);
|
|
}
|