将Alpha Beta纳入Minimax
我正在尝试将Alpha Beta修剪添加到我的minimax中，但我无法理解我要出错的地方。
目前我正在经历5000次迭代，根据一位朋友的说法，我应该经历约16,000次迭代。 当选择第一个位置时，它返回-1（一个损失），但它应该能够在这一点（一个平局）肯定地返回一个0，因为它应该能够从一个空白的棋盘上抽取，但是我看不到在我按照我的代码看起来很好的时候，我会出错
奇怪的是，如果我在我的支票中切换返回Alpha和Beta（实现返回0），计算机将尝试绘制但不会启动任何获胜动作，只有块
我的逻辑流程
如果我们正在寻找阿尔法：如果分数>阿尔法，改变阿尔法。 如果alpha和beta重叠，则返回alpha
如果我们正在寻找测试版：如果分数<测试版，请更改测试版。 如果alpha和beta重叠，则返回beta
这是我的递归调用
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;
任何有关我的逻辑流程的帮助，将使计算机返回正确的结果，并作出明智的举动，将不胜感激
如果没有alpha-beta修剪，您的算法是否可以正常工作？ 对于_bFindAlpha ，您的初始调用应该为false ，因为根节点的行为类似于alpha节点，但它看起来不会有什么不同：
int tempScore = -MinimaxAB(GameBoard, NAUGHT, false, -1000000, 1000000);
因此，我会建议你放弃这个_bFindAlpha废话并将你的算法转换为negamax。 它的行为与minimax相同，但会使您的代码更短，更清晰。 而不是检查是否最大化alpha或最小化beta，可以在递归调用时进行交换和否定（这与您现在可以返回函数的否定值的原因相同）。 以下是维基百科伪代码的稍微编辑版本：
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版本比调试当前的实现更容易。
链接地址: http://www.djcxy.com/p/56339.html