C ++ 4 Алфавитный алгоритм подряд не очень умный
Я делаю управляемый ИИ алгоритм альфа-бета для школьного проекта, но мой алгоритм очень противоречив. Иногда он успешно блокирует все мои движения, а иногда просто игнорирует мои 3 подряд Вот. Как это могло произойти и как я могу решить проблему?
int alphaBeta(const State board, int alpha, int beta, const Player player, int depth)
{
//Max player = Player::O
//Min player = Player::X
std::vector<Move> possibleMoves = getMoves(board);
if(eval(board)==Player::X){return 9999-depth;} //Player X wins
else if(eval(board)==Player::O){return -9999+depth;} //Player O wins
else if(possibleMoves.size()==0){return 0;} //Tie
else{ //Zoek verder
depth++;
State nextBoard = board;
int result;
if(player==Player::O){
for (Move move: possibleMoves) {
nextBoard = doMove(nextBoard, move);
result = alphaBeta(nextBoard, alpha, beta, Player::X, depth);
if (result > alpha){
alpha = result;
if (depth == 1){
choice = move; //The actual move he will do
}
}
else if (alpha >= beta){
return alpha;
}
}
return alpha;
}
else{
for (Move move: possibleMoves) {
nextBoard = doMove(nextBoard, move);
result = alphaBeta(nextBoard, alpha, beta, Player::O, depth);
if (result < beta){
beta = result;
if (depth == 1){
choice = move;
}
}
else if (beta <= alpha){
return beta;
}
}
return beta;
}
}
}
Решение
Вы неоднократно модифицируете nextBoard, добавляя (возможно незаконные) ходы к нему:
nextBoard = doMove(nextBoard, move);
но вы должны попробовать каждый ход по очереди на оригинальной доске:
State nextBoard = doMove(board, move);
(Отказ от ответственности: могут быть и другие проблемы.)
Другие решения
1) Не оценивайте каждый узел в рекурсивном вызове, это будет слишком дорого. Оцените только листовые узлы.
2) Используйте граничное условие в минимаксном рекурсивном вызове для завершения, если глубина больше определенного значения; каждая ветвь не приводит к выигрышному ходу, и поиск будет слишком большим, и программа может зависнуть.
3) Рассмотрите возможность использования многопоточности на ветках верхнего уровня, чтобы ускорить поиск.
int alphaBeta(const State board, int alpha, int beta, const Player player, int depth)
{
std::vector<Move> possibleMoves = getMoves(board);
if(CheckForWinX(board))
{
return 9999;
}
else
if(CheckForWinO(board))
{
return -9999;
}
else
if(possibleMoves.size()==0)
{
return 0;
}
else
if( depth >= 5) // without this boundary condition, the search tree will too big
{
return eval(board); // evaluate ( which is more time expensive than CheckForWin() ) only the leaf node, not every nodes
}
else{
depth++;
State nextBoard = board;
int result;
if(player==Player::O){
/**/
return alpha;
}
else{
/**/
return beta;
}
}
}