Внедрение альфа-беты в минимакс

Question

Внедрение альфа-беты в минимакс

Я пытаюсь добавить обрезку альфа-беты в свой минимакс, но я не могу понять, где я иду не так.

На данный момент я прохожу 5000 итераций, где, по словам друга, мне нужно пройти около 16 000. При выборе первой позиции она возвращает -1 (убыток), тогда как в этой точке она должна быть в состоянии точно вернуть 0 (ничья), так как она должна быть в состоянии вытянуть с пустой доски, однако я не вижу где я иду не так, как я следую своему коду, кажется, все в порядке

Странно, что если я переключу возвращаемые Альфа и Бета внутри своих чеков (чтобы добиться возврата 0), компьютер будет пытаться рисовать, но никогда не инициировать выигрышные ходы, только блоки

Мой логический поток

Если мы ищем альфа:
Если счет> альфа, измените альфа. если альфа и бета перекрываются, вернуть альфа

Если мы ищем бета-версию:
Если оценка < бета, измени бета. если альфа и бета перекрываются, вернуть бета

Вот мой
Рекурсивный вызов

int MinimaxAB(TGameBoard* GameBoard, int iPlayer, bool _bFindAlpha, int _iAlpha, int _iBeta)
{

//How is the position like for player (their turn) on iGameBoard?
int iWinner = CheckForWin(GameBoard);
bool bFull = CheckForFullBoard(GameBoard);

//If the board is full or there is a winner on this board, return the winner
if(iWinner != NONE || bFull == true)
{
//Will return 1 or -1 depending on winner
return iWinner*iPlayer;
}

//Initial invalid move (just follows i in for loop)
int iMove = -1;
//Set the score to be instantly beaten
int iScore = INVALID_SCORE;

for(int i = 0; i < 9; ++i)
{
//Check if the move is possible
if(GameBoard->iBoard[i] == 0)
{
//Put the move in
GameBoard->iBoard[i] = iPlayer;

//Recall function
int iBestPositionSoFar = -MinimaxAB(GameBoard, Switch(iPlayer), !_bFindAlpha, _iAlpha, _iBeta);

//Replace Alpha and Beta variables if they fit the conditions - stops checking for situations that will never happen
if (_bFindAlpha == false)
{
if (iBestPositionSoFar < _iBeta)
{
//If the beta is larger, make the beta smaller
_iBeta = iBestPositionSoFar;
iMove = i;

if (_iAlpha >= _iBeta)
{
GameBoard->iBoard[i] = EMPTY;

//If alpha and beta are overlapping, exit the loop
++g_iIterations;
return _iBeta;

}
}
}
else
{
if (iBestPositionSoFar > _iAlpha)
{
//If the alpha is smaller, make the alpha bigger
_iAlpha = iBestPositionSoFar;
iMove = i;

if (_iAlpha >= _iBeta)
{
GameBoard->iBoard[i] = EMPTY;

//If alpha and beta are overlapping, exit the loop
++g_iIterations;
return _iAlpha;
}
}
}

//Remove the move you just placed
GameBoard->iBoard[i] = EMPTY;
}
}++g_iIterations;

if (_bFindAlpha == true)
{
return _iAlpha;
}
else
{
return _iBeta;
}
}

Первоначальный звонок (когда компьютер должен выбрать позицию)

int iMove = -1; //Invalid
int iScore = INVALID_SCORE;

for(int i = 0; i < 9; ++i)
{
if(GameBoard->iBoard[i] == EMPTY)
{
GameBoard->iBoard[i] = CROSS;
int tempScore = -MinimaxAB(GameBoard, NAUGHT, true, -1000000, 1000000);
GameBoard->iBoard[i] = EMPTY;

//Choosing best value here
if (tempScore > iScore)
{
iScore = tempScore;
iMove = i;
}
}
}
//returns a score based on Minimax tree at a given node.
GameBoard->iBoard[iMove] = CROSS;

Будем благодарны за любую помощь относительно моего логического потока, которая заставит компьютер вернуть правильные результаты и сделает разумные шаги

0

alpha-beta-pruning c++minimax

Решение

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

Других решений пока нет …

Источник

Accepted Answer

Работает ли ваш алгоритм без обрезки альфа-бета? Ваш первый звонок должен быть дан с false за _bFindAlpha поскольку корневой узел ведет себя как альфа-узел, но он не выглядит так, как это будет иметь значение:

int tempScore = -MinimaxAB(GameBoard, NAUGHT, false, -1000000, 1000000);

Таким образом я буду рекомендовать вам отказаться от этого _bFindAlpha вздор и конвертируй свой алгоритм в negamax. Он ведет себя идентично минимаксному, но делает ваш код короче и понятнее. Вместо того, чтобы проверять, максимизировать ли альфа или минимизировать бета, вы можете просто поменять местами и отрицать при рекурсивном вызове (это та же самая причина, по которой вы можете вернуть отрицательное значение функции прямо сейчас). Вот слегка отредактированная версия псевдокода Википедии:

function negamax(node, α, β, player)
if node is a terminal node
return color * the heuristic value of node
else
foreach child of node
val := -negamax(child, -β, -α, -player)
if val ≥ β
return val
if val > α
α := val
return α

Если вы не любите обходить деревья поиска, я думаю, вам будет проще просто написать чистую, правильную версию negamax, чем отлаживать текущую реализацию.

1