TicTacToe 的 Minimax 算法无法正常工作

Question

我已经在这个论坛中 post 提出了一个类似的问题，但是由于旧的 post 有点长，我重写了我的算法，我开始这个新的 post。旧的post可以找到here。

所以我只是想为我的 TicTacToe 游戏实现一个 minimax 算法，但事实证明它非常困难，甚至在尝试找出错误几天后，我也找不到它。你可以在下面找到我的代码。首先，我有一些定义、类型定义和声明：

typedef signed char s8;
typedef unsigned char u8;
typedef s8 score;

#define STATE_00    getBoardState(0, 0)
#define STATE_01    getBoardState(0, 1)
#define STATE_02    getBoardState(0, 2)
#define STATE_10    getBoardState(1, 0)
#define STATE_11    getBoardState(1, 1)
#define STATE_12    getBoardState(1, 2)
#define STATE_20    getBoardState(2, 0)
#define STATE_21    getBoardState(2, 1)
#define STATE_22    getBoardState(2, 2)

typedef enum {
    EPlayerX = 1,
    EPlayerO
} EPlayer;

typedef enum {
    EMinimizing = 0,
    EMaximizing
} EMinMax;

static u8 g_boardState[3][3] = {
    {0, 0, 0,},
    {0, 0, 0,},
    {0, 0, 0,},
};

后面还有一些函数：

u8 getBoardState(u8 row, u8 column);

EPlayer isWon(void)
{
    EPlayer winningBoards[8][3] = {
        {STATE_00, STATE_01, STATE_02},
        {STATE_10, STATE_11, STATE_12},
        {STATE_20, STATE_21, STATE_22},
        {STATE_00, STATE_10, STATE_20},
        {STATE_01, STATE_11, STATE_21},
        {STATE_02, STATE_12, STATE_22},
        {STATE_00, STATE_11, STATE_22},
        {STATE_20, STATE_11, STATE_02},
    };
    u8 i;
    for(i=0; i<8; i++){
        if( (winningBoards[i][0] != 0) &&
            (winningBoards[i][0] == winningBoards[i][1]) &&
            (winningBoards[i][0] == winningBoards[i][2])){
                return winningBoards[i][0];
        }
    }
    return 0;
}

u8 getBoardState(u8 row, u8 column)
{
    return g_boardState[row][column];
}

void setBoardState(u8 row, u8 column, u8 state)
{
    g_boardState[row][column] = state;
}

u8 isDraw(void)
{
    u8 i, j;
    for(i=0; i<3; i++){
        for(j=0; j<3; j++){
            if(getBoardState(i, j) == 0){
                return 0;
            }
        }
    }
    return 1;
}

void dumpTable(score table[3][3])
{
    int i, j;
    for(i=0; i<3; i++) {
        printf("\n");
        for(j=0; j<3; j++){
            printf("%6i ", table[i][j]);
        }
    }
    printf("\n");
}

EPlayer playerSwitch(EPlayer player)
{
    if(player == EPlayerO) return EPlayerX;
    if(player == EPlayerX) return EPlayerO;
    return 0;
}

EMinMax modeSwitch(EMinMax mode)
{
    if(mode == EMaximizing) return EMinimizing;
    if(mode == EMinimizing) return EMaximizing;
    return 0;
}

然后这里有真正的极小极大算法scoring:

score scoring(EMinMax mode, EPlayer player, u8 depth)
{
    score thisScore, tempScore;
    if(mode == EMaximizing){
        thisScore = -20;
        if(isWon()) return 15-depth;
    }
    if(mode == EMinimizing){
        thisScore = 20;
        if(isWon()) return depth-15;
    }
    if(isDraw()){
        return 0;
    }

    u8 i, j;
    for(i=0; i<3; i++){
        for(j=0; j<3; j++){
            if(getBoardState(i, j) == 0){
                setBoardState(i, j, player);
                tempScore = scoring(modeSwitch(mode), playerSwitch(player), depth+1);
                if((mode == EMaximizing) && (tempScore > thisScore)){
                    thisScore = tempScore;
                }
                if((mode == EMinimizing) && (tempScore < thisScore)){
                    thisScore = tempScore;
                }
                setBoardState(i, j, 0);
            }
        }
    }

    return thisScore;
}

最后一个函数在 table 和 main:

中打印分数

void printSocredBoards(EPlayer player)
{   
    score thisScore[3][3] = {
        {STATE_00, STATE_01, STATE_02},
        {STATE_10, STATE_11, STATE_12},
        {STATE_20, STATE_21, STATE_22},
    };
    int i, j;
    if((isWon() == 0) && (isDraw() == 0)){
        for(i=0; i<3; i++){
            for(j=0; j<3; j++){
                if(getBoardState(i, j) == 0){
                    setBoardState(i, j, player);
                    thisScore[i][j] = scoring(EMaximizing, playerSwitch(player), 0);
                    setBoardState(i, j, 0);
                }
            }
        }
    }
    dumpTable(thisScore);
}

int main(int argc, char **argv)
{

    printSocredBoards(EPlayerO);

    return 0;
}

据我所知，这个算法应该可以正常工作，但是它给了我一个无意义的输出：

 7      7      7 
 7      0      7 
 7      7      7

我错过了什么？在此先感谢您的帮助。

Answer 1

我认为问题出在这段代码中，在你的案例从正确的 return 值翻转的地方进行评分：

if(mode == EMaximizing){
    thisScore = -20;
    if(isWon()) return 15-depth;
}
if(mode == EMinimizing){
    thisScore = 20;
    if(isWon()) return depth-15;
}

直觉上，问题是当 scoring 到达代码中的这一点时，对 isWon 的调用正在评估 上一个 片段的结果放置，这是用 mode.

的另一个选择做出的

例如，当用 EMaximizing 调用计分并且棋盘状态已经获胜时，则意味着 EMinimizing 的玩家在此状态下获胜，而 return ed 分数应该反映这一点（即它应该是负数）。由于深度达到最大值 8，当 mode == EMaximizing 始终为正时，您的 return 值，这不是您想要的。

当大小写颠倒时，您的程序输出全为零，这似乎更明智，因为完美的玩家应该总是抽牌。我还测试了将以下行添加到 printScoredBoards 顶部的代码，以将第一个播放硬编码到左上角：

setBoardState(0, 0, playerSwitch(player));

这会产生以下结果：

 0     10     10 
10      0     10 
10     10     10

正确识别第二个玩家不能选择左上角，并且如果他们在开局时选择中间以外的任何东西都会输。

TicTacToe 的 Minimax 算法无法正常工作

Minimax algorithm with TicTacToe not working properly

c

artificial-intelligence

tic-tac-toe

minimax