Java中用于TicTacToe AI的最简单的MiniMax算法 [英] simplest MiniMax algorithm for TicTacToe AI in Java

问题描述

我正试图了解MiniMax算法，并已经阅读了它。我最初的方法是实现一个简单的MiniMax算法，然后添加alpha-beta修剪。但这是我当前的代码：

I was trying to get a grasp of MiniMax algorithm, and have read up on it. My initial approach was to implement a simple MiniMax algorithm, and then to add alpha-beta pruning. However this is my current code:

public int miniMax(char[] node, int playerNum)
{
    int victor = checkWin(node); // returns 0 if game is ongoing, 1 for p1, 2 for p2, 3 for tie.
    if(victor != 0) //game over .
        return score(victor);   

    if(playerNum == 2) //AI
    {
        int bestVal = Integer.MIN_VALUE;
        int bestSpot = 0;
        for(int i = 0; i < node.length; i++)
        {
            if(node[i] != '-')
                continue;
            node[i] = getSymbol(playerNum);
            int value = miniMax(node, 1); 
            if(value > bestVal)
            {
                bestVal = value;
                bestSpot = i;
            }

            node[i] = '-';
        }
        return bestSpot;
    }
    else
    {
        int bestVal = Integer.MAX_VALUE;
        int bestSpot = 0;
        for(int i = 0; i < node.length; i++)
        {
            if(node[i] != '-')
                continue;
            node[i] = getSymbol(playerNum);
            int value = miniMax(node, 2); 
            if(value < bestVal)
            {
                bestVal = value;
                bestSpot = i;
            }
            node[i] = '-';
        }
        return bestSpot;
    }
}

我的得分函数

private int Score(int gameState)
{
    if(gameState ==2) //O wins.
        return 10;
    else if(gameState==1) //X wins
        return -10;
    return 0;
}

现在，我有一个正在运行的AI试图阻止我的行动并取得胜利，但是有时它会做出非智能的选择，例如这是我从控制台读取的输入依次为6、7、8时得到的输出。它不会试图阻止我的胜利。

Now, I have a working AI that tries to block my move and win, however sometimes it is making non-intelligent choices for instance this is the output I get if my input read from console is 6,7,8 in that order. It does not attempt to block my win. But in other cases it does.

| O | O | |

| O | O | |

| | | |

| X | X | X |

| X | X | X |

在我的第二次尝试中，我尝试了4,3，但它阻止了我的获胜举动。

In my second attempt I tried 4,3 and it blocked my winning move.

| | O | |

| | O | |

| X | X | O |

| X | X | O |

| | | |

我想知道有人能指出我的实现方式有什么问题吗？

I was wondering anyone could point out what is wrong with my implementation?

推荐答案

所示示例代码的行为是正确的！

The behavior of the code for the shown examples is correct!

那么以下内容中的威胁为什么如此？位置没有被阻止？为什么程序播放从1开始而不是6？

So why is the threat in the following position not blocked? Why does the program play move 1 instead of 6?

O . .                                    O 1 2
. . .     numbering available moves:     3 4 5
X X .                                    X X 6

这是因为如果游戏在完美玩法中输了，程序只会玩

该算法仅关心获胜或失败，而不关心多少步。

The algorithm only cares about win or loss and not in how many moves.

查看如果阻止了威胁会发生什么情况：

See what happens if the threat is blocked:

O . .     O . .
. . .     . X .     and X wins on his next move
X X O     X X O

这篇关于Java中用于TicTacToe AI的最简单的MiniMax算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！