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;
}
}
}

-2

Решение

Вы неоднократно модифицируете nextBoard, добавляя (возможно незаконные) ходы к нему:

nextBoard = doMove(nextBoard, move);

но вы должны попробовать каждый ход по очереди на оригинальной доске:

State nextBoard = doMove(board, move);

(Отказ от ответственности: могут быть и другие проблемы.)

2

Другие решения

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;
}
}
}
0