极小极大算法井字游戏无法正常工作(Minimax algorithm with TicTacToe

我已经发布了类似的问题在这里在这个论坛上，但因为老了后有点长，我改写了我的算法我开始这个新的职位。 旧后可以发现在这里 。

---

所以我只是想实现一个极大极小算法我井字游戏，但它被证明是相当困难，甚至试图发现其中的错误天后，我找不到它。 你可以在下面找到我的代码。 首先，我有几个定义，typedef和声明：

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

最后一个功能打印在表格中的分数以及在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:

我认为，问题在于从得分这个块的代码在您的情况下，从正确的返回值翻转：

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在这种状态下，且返回的比分获胜应该反映这个（即它应该是负的）。 由于深度达到最大值8的返回值时mode == EMaximizing总是正的，这是不是你想要的。

当情况是相反的，你的程序输出都是零，这似乎更为明智的完美球员应该总是吸引。 我还测试了代码以下行添加到顶部printScoredBoards进行硬编码第一次玩到左上角：

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

我们得到以下：

 0     10     10 
10      0     10 
10     10     10 

正确识别两个第二玩家不能选择左上角，如果他们发挥出比中心作为其开放移动其他任何事情都会失去。

文章来源: Minimax algorithm with TicTacToe not working properly