Tic Tac Toe：评估节点的启发式值

Question

请原谅我，如果这个问题已经存在，我已经搜索了很多，但我还没有得到我想问的问题的答案。所以，基本上，我正在尝试实现一个使用Minimax算法进行移动的Tic-Tac-Toe AI。

但是，我没有得到的一点是，当Minimax用于空板时，返回的值始终为0（这是有道理的，因为如果两个玩家都达到最佳状态，游戏总是以平局结束）。

因此当AI为X时，Minimax总是选择第一个tile作为最佳移动（因为所有移动都返回0作为值）。第二次移动也是如此，它总是选择第二个瓦片。我怎样才能解决这个问题，让我的AI选择获胜的概率更高？这是我使用的评估和Minimax功能（使用Alpha-Beta修剪）：

int evaluate(char board[3][3], char AI)
{
for (int row = 0; row<3; row++)
{
    if (board[row][0] != '_' && board[row][0] == board[row][1] && board[row][1] == board[row][2])
    {
        if (board[row][0]==AI)
        {
            return +10;
        }
        else
        {
            return -10;
        }
    }
}

for (int col = 0; col<3; col++)
{
    if (board[0][col] != '_' && board[0][col] == board[1][col] && board[1][col] == board[2][col])
    {
        if (board[0][col]==AI)
        {
            return +10;
        }

        else
        {
            return -10;
        }
    }
}

if (board[1][1] != '_' && ((board[0][0]==board[1][1] && board[1][1]==board[2][2]) || (board[0][2]==board[1][1] && board[1][1]==board[2][0])))
{
    if (board[1][1]==AI)
    {
        return +10;
    }
    else
    {
        return -10;
    }
}

return 0;
}

int Minimax(char board[3][3], bool AITurn, char AI, char Player, int depth, int alpha, int beta)
{
bool breakout = false;
int score = evaluate(board, AI);

if(score == 10)
{
    return score - depth;
}
else if(score == -10)
{
    return score + depth;
}
else if(NoTilesEmpty(board))
{
    return 0;
}

if(AITurn == true)
{
    int bestvalue = -1024;
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j<3; j++)
        {
            if(board[i][j] == '_')
            {
                board[i][j] = AI;
                bestvalue = max(bestvalue, Minimax(board, false, AI, Player, depth+1, alpha, beta));
                alpha = max(bestvalue, alpha);
                board[i][j] = '_';
                if(beta <= alpha)
                {
                    breakout = true;
                    break;
                }
            }
        }
        if(breakout == true)
        {
            break;
        }
    }
    return bestvalue;
}

else if(AITurn == false)
{
    int bestvalue = +1024;
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j<3; j++)
        {
            if(board[i][j] == '_')
            {
                board[i][j] = Player;
                bestvalue = min(bestvalue, Minimax(board, true, AI, Player, depth+1, alpha, beta));
                beta = min(bestvalue, beta);
                board[i][j] = '_';
                if(beta <= alpha)
                {
                    breakout = true;
                    break;
                }
            }
        }
        if(breakout == true)
        {
            break;
        }
    }
    return bestvalue;
}
}

Answer 1

Minimax假设最佳发挥，因此最大化“获胜概率”并不是一个有意义的概念：由于其他玩家可以强制平局而不能强制获胜，他们将总是强制平局。如果你想对一个不完全理性的球员进行最佳的比赛（当然，这是赢得*的唯一两种方式之一），你需要假设一些概率分布在对手的动作上并使用像ExpectMinimax这样的东西，有可能对手的移动被随机错误所取代。或者，您可以故意限制极小极大搜索的厚度，使用启发式对手超过一定深度的游戏（但仍然在搜索游戏树以获取您自己的动作。）

*另一个不玩。

Answer 2

将代码组织到较小的例程中，使其看起来更整洁，更容易调试。除了递归的minimax函数之外，一个全可能有效的移动生成函数和一个强大的评估子例程是必不可少的（这里似乎缺乏）。

例如，在游戏开始时，评估算法应该返回非零分数，每个位置应该具有相对评分指数（例如，中间位置可以具有比角稍高的权重）。

您的极小极大边界条件 - 如果没有空单元格位置则返回;即使在前一层发生输赢的动作时它也会评估是有缺陷的。这种情况会在更复杂的AI游戏中加剧。

如果您是minimax的新手，您可以在CodeReview上找到大量可以编译的示例代码