标签: tic-tac-toe

我在Java中编写了一个井字游戏,我目前确定游戏结束的方法解释了游戏结束的以下可能情况:

1. 董事会已经满员,尚未宣布获胜者:比赛是平局.
2. 克罗斯赢了.
3. Circle赢了.

不幸的是,为了做到这一点,它从表中读取了一组预定义的这些场景.考虑到电路板上只有9个空格,这并不一定是坏的,因此表格有点小,但有没有更好的算法来确定游戏是否结束？确定某人是否赢了是问题的关键,因为检查9个空格是否已满是微不足道的.

表方法可能是解决方案,但如果没有,那是什么？另外,如果电路板尺寸不大n=9怎么办？如果它是一个更大的板,比如n=16,n=25等,造成连续放置物品的数量取胜是x=4,x=5等？一种用于所有人的通用算法n = { 9, 16, 25, 36 ... }？

在一个井字游戏的实现中,我认为具有挑战性的部分是确定机器播放的最佳动作.

有哪些算法可以追求？我正在研究从简单到复杂的实现.我该如何处理这部分问题？

按字符数发布您的最短代码,以检查玩家是否赢了,如果是,那么.

假设你在变量b(board)中有一个整数数组,它包含Tic Tac Toe板,以及玩家的移动:

• 0 =没有设置
• 1 =玩家1(X)
• 2 =玩家2(O)

所以,鉴于阵列b = [ 1, 2, 1, 0, 1, 2, 1, 0, 2 ]将代表董事会

X|O|X
-+-+-
 |X|O
-+-+-
X| |O

对于这种情况,您的代码应该输出1以指示玩家1赢了.如果没有人赢了你可以输出0或false.

我自己的(Ruby)解决方案即将推出.

编辑:对不起,忘了将其标记为社区维基.您可以假设输入格式正确,不必进行错误检查.

更新:请以函数的形式发布您的解决方案.大多数人已经这样做了,但有些人没有,这不完全公平.电路板作为参数提供给您的功能.结果应该由函数返回.该函数可以具有您选择的名称.

编辑:Uploded完整的源代码,如果你想看看如果你能得到的AI表现得更好:https://www.dropbox.com/s/ous72hidygbnqv6/MCTS_TTT.rar

编辑:搜索搜索空间并找到导致丢失的移动.但由于UCT算法,不会经常访问导致损失的移动.

要了解MCTS(蒙特卡罗树搜索),我已经使用该算法为经典的井字游戏制作AI.我使用以下设计实现了算法:

树策略基于UCT,默认策略是执行随机移动直到游戏结束.我在实现中观察到的是,计算机有时会进行错误的移动,因为它无法"看到"特定的移动会直接导致丢失.

例如: 注意动作6(红色方块)的值略高于蓝色方块,因此计算机标记了这个位置.我认为这是因为游戏政策是基于随机移动,因此很有可能人类不会在蓝框中加上"2".如果玩家没有在蓝色框中放置2,那么计算机就会赢得胜利.

我的问题

1)这是MCTS的已知问题还是实施失败的结果？

2)有什么可能的解决方案？我正在考虑将这些动作限制在选择阶段,但我不确定:-)

核心MCTS的代码:

    //THE EXECUTING FUNCTION
    public unsafe byte GetBestMove(Game game, int player, TreeView tv)
    {

        //Setup root and initial variables
        Node root = new Node(null, 0, Opponent(player));
        int startPlayer = player;

        helper.CopyBytes(root.state, game.board);

        //four phases: descent, roll-out, update and growth done iteratively X times
        //-----------------------------------------------------------------------------------------------------
        for (int iteration = 0; iteration < 1000; iteration++)
        {
            Node current = Selection(root, game);
            int value = Rollout(current, game, startPlayer);
            Update(current, value);
        }

        //Restore game …

我发现这个有效的解决方案

private int[] winningPatterns = { 0b111000000, 0b000111000, 0b000000111, // rows
        0b100100100, 0b010010010, 0b001001001, // cols
        0b100010001, 0b001010100 // diagonals
};

/** Returns true if thePlayer wins */
private boolean hasWon(int thePlayer) {
    int pattern = 0b000000000; // 9-bit pattern for the 9 cells
    for (int row = 0; row < 3; ++row) {
        for (int col = 0; col < 3; ++col) {
            if (cells[row][col].content == thePlayer) {
                pattern |= (1 << (row * 3 + col));
            }
        } …

我已经在StackOverflow上阅读了许多Tic Tac Toe主题.我发现维基百科上的策略适合我的演示项目:

如果玩家在下表中选择具有最高优先级的移动,则玩家可以玩完美的井字游戏[3].

1)胜利:如果你有两个连续的比赛,打第三个连续三个.

2)阻挡:如果对手连续两次,则发挥第三个阻挡他们.

3)福克斯:创造一个可以通过两种方式获胜的机会.

4)阻挡对手的分叉:

选项1:连续创建两个以强制对手进行防守,只要它不会导致他们创建分叉或获胜.例如,如果"X"有一个角,"O"有中心,"X"也有相反的角,"O"不能为了赢得角落.(在这个场景中扮演角球会为"X"赢得一个分叉.)

选项2:如果存在对手可以分叉的配置,则阻止该分叉.

5)中心:打中锋.

6)对角:如果对手在角落,则对角.

7)空角:打空角.

8)空的一面:空洞的一面.

我按照这一步,计算机永远不会丢失.但是,它的攻击方式并不完美.因为我不知道如何做第3步.这是我在第3步中所做的:扫描每个单元格,检查是否在该单元格上放置标记创建了一个fork,然后将其放在那里.

private void step3() // Create Fork.
{
    int[] dummyField = (int[])field.Clone();
    // Try Level 1 Dummy
    for (int i = 0; i < 9; i++)
    {
        if (dummyField[i] != 0) continue;
        dummyField[i] = 2;
        if (countFork(dummyField, 2) >= 2)
        {
            nextCell = i;
            return;
        }
        dummyField[i] = 0;
    }

}

请给我一些关于这一步的建议.

EDIT1:计数叉将计算计算机有多少叉(计算机的令牌为2,玩家令牌为1,因为我也使用了该方法用于步骤4,因此在countFork功能中有令牌参数).

EDIT2:我说它不完美的原因是(CPU先行,其细胞为蓝色,人体细胞为红色). 正如您所看到的,如果我放入顶部单元格,计算机就会获胜.但是,如果我放入右侧的单元格,它就是一个平局,虽然计算机仍然可以获胜.

编辑3:不知道为什么,但我评论了第3步,计算机播放......完美!我真的很惊讶!这是我的countFork函数(我需要将此代码移植到Alice,它不支持二维数组,因此我使用getNumberFromXY将二维数组转换为一维):

private int countFork(int[] field, int token)
{ …

我浪费了一整天努力使用minimax算法来制作无与伦比的tictactoe AI.我一路上都错过了一些东西(大脑炒).

我不是在这里寻找代码,只是更好地解释我出错的地方.

这是我当前的代码(minimax方法由于某种原因总是返回0):

from copy import deepcopy


class Square(object):
    def __init__(self, player=None):
        self.player = player

    @property
    def empty(self):
        return self.player is None


class Board(object):
    winning_combos = (
        [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6],
    )

    def __init__(self, squares={}):
        self.squares = squares
        for i in range(9):
            if self.squares.get(i) is None:
                self.squares[i] = Square()

    @property
    def available_moves(self):
        return [k for k, v in self.squares.iteritems() …

在制作Tic-Tac-Toe机器人时,我正试图了解"树木".我理解这个概念,但我无法想出来实现它们.

有人能告诉我一个如何为这种情况生成树的例子吗？还是一个关于生成树木的好教程？我想难以产生部分树木.我知道如何实现生成整棵树,但不是它的一部分.

我已经想到了一些大型(更高维度)井字游戏的启发式方法.如何检查哪些实际上是一致的？

一致性意味着什么？

一点背景:作为一种在C++中学习多节点树的方法,我决定生成所有可能的TicTacToe板并将它们存储在一棵树中,这样从一个节点开始的分支都是可以跟随该节点的板,以及节点是一步到位的板.在那之后,我认为使用该树作为决策树编写AI来玩TicTacToe会很有趣.

TTT是一个可以解决的问题,一个完美的玩家永远不会丢失,所以我第一次尝试AI时编码似乎很简单.

现在,当我第一次实现AI时,我回过头来为每个节点添加两个字段:X将赢得的次数和O将在该节点下的所有子节点中获胜的次数.我认为最好的解决方案就是让我的每一步动作都选择AI,然后选择最能赢得次数的子树.然后我发现虽然它在大部分时间都是完美的,但我找到了可以击败它的方法.这对我的代码来说不是问题,只是我用AI选择它的路径的问题.

然后我决定让它选择具有计算机最大胜利或人类最大损失的树,以较多者为准.这使它表现更好,但仍然不完美.我仍然可以击败它.

所以我有两个想法,我希望得到更好的输入:

1)而不是最大化赢或输,而是我可以为胜利分配1,为平局分配0,为亏损分配-1.然后选择具有最高值的树将是最佳移动,因为下一个节点不能是导致丢失的移动.这是电路板生成中的一个简单更改,但它保留了相同的搜索空间和内存使用量.要么...

2)在棋盘生成期间,如果有一个棋盘使X或O在下一步中获胜,则只会产生阻止该胜利的孩子.不会考虑其他子节点,然后生成将在此之后正常进行.它缩小了树的大小,但后来我必须实现一个算法来确定是否有一个移动获胜,我认为这只能在线性时间内完成(我认为让板子生成慢很多？)

哪个更好,还是有更好的解决方案？