我怎么让我的人工智能算法玩9板抽搐脚趾？

Question

为了让别人更容易地帮助我，我已经把所有的代码都放在这里了，https://pastebin.com/WENzM41k，它将从两个代理互相竞争开始。

我正在尝试实现蒙特卡洛树搜索，在Python中玩9板tic游戏。游戏规则就像普通的抽搐脚趾，但有9块3x3的子板。最后一块的位置是决定放置你的作品的子董事会。这有点像终极的抽搐脚趾，但如果其中一个棋子赢了，游戏就结束了。

我正在努力学习MCTS，我在这里找到了一些代码：http://mcts.ai/code/python.html

我在网站上使用了节点类和UCT类，并添加了我的9块板、抽搐-脚趾游戏状态类和一些其他代码。所有代码都在这里：

from math import log, sqrt
import random
import numpy as np
from copy import deepcopy


class BigGameState:
    def __init__(self):
        self.board = np.zeros((10, 10), dtype="int8")
        self.curr = 1
        self.playerJustMoved = 2 # At the root pretend the player just moved is player 2 - player 1 has the first move

    def Clone(self):
        """ Create a deep clone of this game state.
        """
        st = BigGameState()
        st.playerJustMoved = self.playerJustMoved
        st.curr = self.curr
        st.board = deepcopy(self.board)
        return st

    def DoMove(self, move):
        """ Update a state by carrying out the given move.
            Must update playerJustMoved.
        """
        self.playerJustMoved = 3 - self.playerJustMoved
        if move >= 1 and move <= 9 and move == int(move) and self.board[self.curr][move] == 0:
            self.board[self.curr][move] = self.playerJustMoved
            self.curr = move

    def GetMoves(self):
        """ Get all possible moves from this state.
        """
        return [i for i in range(1, 10) if self.board[self.curr][i] == 0]

    def GetResult(self, playerjm):
        """ Get the game result from the viewpoint of playerjm. 
        """
        for bo in self.board:
            for (x,y,z) in [(1,2,3),(4,5,6),(7,8,9),(1,4,7),(2,5,8),(3,6,9),(1,5,9),(3,5,7)]:
                if bo[x] == [y] == bo[z]:
                    if bo[x] == playerjm:
                        return 1.0
                    else:
                        return 0.0
        if self.GetMoves() == []: return 0.5 # draw

    def drawboard(self):
        print_board_row(self.board, 1, 2, 3, 1, 2, 3)
        print_board_row(self.board, 1, 2, 3, 4, 5, 6)
        print_board_row(self.board, 1, 2, 3, 7, 8, 9)
        print(" ------+-------+------")
        print_board_row(self.board, 4, 5, 6, 1, 2, 3)
        print_board_row(self.board, 4, 5, 6, 4, 5, 6)
        print_board_row(self.board, 4, 5, 6, 7, 8, 9)
        print(" ------+-------+------")
        print_board_row(self.board, 7, 8, 9, 1, 2, 3)
        print_board_row(self.board, 7, 8, 9, 4, 5, 6)
        print_board_row(self.board, 7, 8, 9, 7, 8, 9)
        print()


def print_board_row(board, a, b, c, i, j, k):
    # The marking script doesn't seem to like this either, so just take it out to submit
    print("", board[a][i], board[a][j], board[a][k], end = " | ")
    print(board[b][i], board[b][j], board[b][k], end = " | ")
    print(board[c][i], board[c][j], board[c][k])


class Node:
    """ A node in the game tree. Note wins is always from the viewpoint of playerJustMoved.
        Crashes if state not specified.
    """
    def __init__(self, move = None, parent = None, state = None):
        self.move = move # the move that got us to this node - "None" for the root node
        self.parentNode = parent # "None" for the root node
        self.childNodes = []
        self.wins = 0
        self.visits = 0
        self.untriedMoves = state.GetMoves() # future child nodes
        self.playerJustMoved = state.playerJustMoved # the only part of the state that the Node needs later


    def UCTSelectChild(self):
        """ Use the UCB1 formula to select a child node. Often a constant UCTK is applied so we have
            lambda c: c.wins/c.visits + UCTK * sqrt(2*log(self.visits)/c.visits to vary the amount of
            exploration versus exploitation.
        """
        s = sorted(self.childNodes, key = lambda c: c.wins/c.visits + 0.2 * sqrt(2*log(self.visits)/c.visits))[-1]
        return s

    def AddChild(self, m, s):
        """ Remove m from untriedMoves and add a new child node for this move.
            Return the added child node
        """
        n = Node(move = m, parent = self, state = s)
        self.untriedMoves.remove(m)
        self.childNodes.append(n)
        return n

    def Update(self, result):
        """ Update this node - one additional visit and result additional wins. result must be from the viewpoint of playerJustmoved.
        """
        self.visits += 1
        self.wins += result

    def __repr__(self):
        return "[M:" + str(self.move) + " W/V:" + str(self.wins) + "/" + str(self.visits) + " U:" + str(self.untriedMoves) + "]"

    def TreeToString(self, indent):
        s = self.IndentString(indent) + str(self)
        for c in self.childNodes:
             s += c.TreeToString(indent+1)
        return s

    def IndentString(self,indent):
        s = "\n"
        for i in range (1,indent+1):
            s += "| "
        return s

    def ChildrenToString(self):
        s = ""
        for c in self.childNodes:
             s += str(c) + "\n"
        return s


def UCT(rootstate, itermax, verbose = False):
    """ Conduct a UCT search for itermax iterations starting from rootstate.
        Return the best move from the rootstate.
        Assumes 2 alternating players (player 1 starts), with game results in the range [0.0, 1.0]."""

    rootnode = Node(state = rootstate)

    for i in range(itermax):
        node = rootnode
        state = rootstate.Clone()

        # Select
        while node.untriedMoves == [] and node.childNodes != []: # node is fully expanded and non-terminal
            node = node.UCTSelectChild()
            state.DoMove(node.move)

        # Expand
        if node.untriedMoves != []: # if we can expand (i.e. state/node is non-terminal)
            m = random.choice(node.untriedMoves) 
            state.DoMove(m)
            node = node.AddChild(m,state) # add child and descend tree

        # Rollout - this can often be made orders of magnitude quicker using a state.GetRandomMove() function
        while state.GetMoves() != []: # while state is non-terminal
            state.DoMove(random.choice(state.GetMoves()))

        # Backpropagate
        while node != None: # backpropagate from the expanded node and work back to the root node
            node.Update(state.GetResult(node.playerJustMoved)) # state is terminal. Update node with result from POV of node.playerJustMoved
            node = node.parentNode

    # Output some information about the tree - can be omitted
    if (verbose): print(rootnode.TreeToString(0))
    else: print(rootnode.ChildrenToString())

    return sorted(rootnode.childNodes, key = lambda c: c.visits)[-1].move # return the move that was most visited

def UCTPlayGame():
    """ Play a sample game between two UCT players where each player gets a different number 
        of UCT iterations (= simulations = tree nodes).
    """

    state = BigGameState() # uncomment to play OXO

    while (state.GetMoves() != []):
        state.drawboard()
        m = UCT(rootstate = state, itermax = 1000, verbose = False) # play with values for itermax and verbose = True
        print("Best Move: " + str(m) + "\n")
        state.DoMove(m)
    if state.GetResult(state.playerJustMoved) == 1.0:
        print("Player " + str(state.playerJustMoved) + " wins!")
    elif state.GetResult(state.playerJustMoved) == 0.0:
        print("Player " + str(3 - state.playerJustMoved) + " wins!")
    else: print("Nobody wins!")

if __name__ == "__main__":
    """ Play a single game to the end using UCT for both players. 
    """
    UCTPlayGame()

运行代码，它将启动2代理之间的竞争。然而，经纪人不能很好地玩游戏。这出糟糕的戏是不能接受的。例如，如果ai在一个子董事会中连续得到2，而这又是他的时候，他就不会做出获胜的动作。我应该从哪里开始改进，如何改进？我试图更改Node类和UCT类的代码，但是没有任何效果。

更新:如果董事会在下面的状态，这是我的AI(玩X)转到第8板(第三排的中间子板)。我应该写一些特定的代码，让AI不能在1或5上玩(因为那样对手就会赢)或者我应该让AI来决定。我试着写代码告诉人工智能，但那样的话，我必须遍历所有的子板。

--O|---|---
-O-|---|---
---|---|---
-----------
---|-O-|---
---|-O-|---
---|---|---
-----------
---|---|---
---|---|---
---|---|---

Answer 1

我花了一些时间阅读有关MCTS的内容，并花了更多的时间来捕捉其余的bug：

1. 我添加了OXOState ()，这样我就可以用一个熟悉而简单的游戏进行调试了。这只是http://mcts.ai/code/python.html原始源代码的一个问题:在有人赢了游戏之后，它还会继续玩下去。所以我修好了。
2. 为了调试和乐趣添加了HumanPlayer。
3. 对于游戏级别的评估，添加了RandomPlayer和NegamaxPlayer (否定算法https://en.wikipedia.org/wiki/Negamax)。

NegamaxPlayer与UCT (蒙特卡罗树搜索)

itermax= won lost draw total_time
       1 964   0   36       172.8
      10 923   0   77       173.4
     100 577   0  423       182.1
    1000  48   0  952       328.9
   10000   0   0 1000      1950.3

UTC对完美球员的比赛令人印象深刻(minimax完成三次搜索)：与itermax=1000相比，比分和时间几乎相等--从1000开始只有48场输掉比赛。

1. 修复了BigGameState的其他(我想)问题。它现在打得很熟练，所以我赢不了。

我在NegamaxPlayer中增加了一个深度限制来玩9板toe，因为它可能需要一段时间才能找到这个游戏中最好的动作。

NegamaxPlayer(深度)与UCT (迭代最大)

depth itermax won  lost draw total_time
    4       1   9     1    0       18.4
    4      10   9     1    0       20.7
    4     100   5     5    0       36.2
    4    1000   2     8    0      188.8
    5   10000   2     8    0      318.0
    6   10000   0    10    0      996.5

现在UTC(itermax=100)和NegamaxPlayer(深度4)一样，在下一关8比2中获胜。我很惊讶！-)

我赢得了第一场比赛(itermax=100)，但在1000级输掉了第二场比赛：

Game 1, Move 40:
┏━━━━━━━┳━━━━━━━┳━━━━━━━┓
┃ X X . ┃*O O O ┃ O . . ┃
┃ . O O ┃ . . X ┃ . X O ┃
┃ O X X ┃ X . . ┃ . X . ┃
┣━━━━━━━╋━━━━━━━╋━━━━━━━┫
┃ X . . ┃ . X . ┃ O . . ┃
┃ . X . ┃ O O X ┃ O X . ┃
┃ . O . ┃ O . . ┃ X . . ┃
┣━━━━━━━╋━━━━━━━╋━━━━━━━┫
┃ X X O ┃ O . X ┃ . O X ┃
┃ X . . ┃ . . . ┃ . . . ┃
┃ . . O ┃ O . X ┃ . O . ┃
┗━━━━━━━┻━━━━━━━┻━━━━━━━┛

Player 2 wins!
won 0 lost 1 draw 0

以下是完整的代码：

from math import *
import random
import time
from copy import deepcopy


class BigGameState:
    def __init__(self):
        self.board = [[0 for i in range(10)] for j in range(10)]
        self.curr = 1
        # At the root pretend the player just moved is player 2,
        # so player 1 will have the first move
        self.playerJustMoved = 2
        self.ended = False
        # to put * in __str__
        self.last_move = None
        self.last_curr = None

    def Clone(self):
        return deepcopy(self)

    def DoMove(self, move):
        # 1 2 3
        # 4 5 6
        # 7 8 9
        winning_pairs = [[],  # 0
                         [[2, 3], [5, 9], [4, 7]],  # for 1
                         [[1, 3], [5, 8]],  # for 2
                         [[1, 2], [5, 7], [6, 9]],  # for 3
                         [[1, 7], [5, 6]],  # for 4
                         [[1, 9], [2, 8], [3, 7], [4, 6]],  # for 5
                         [[3, 9], [4, 5]],  # for 6
                         [[1, 4], [5, 3], [8, 9]],  # for 7
                         [[7, 9], [2, 5]],  # for 8
                         [[7, 8], [1, 5], [3, 6]],  # for 9
                         ]
        if not isinstance(move, int) or 1 < move > 9 or \
                self.board[self.curr][move] != 0:
            raise ValueError
        self.playerJustMoved = 3 - self.playerJustMoved
        self.board[self.curr][move] = self.playerJustMoved
        for index1, index2 in winning_pairs[move]:
            if self.playerJustMoved == self.board[self.curr][index1] == \
                    self.board[self.curr][index2]:
                self.ended = True
        self.last_move = move
        self.last_curr = self.curr
        self.curr = move

    def GetMoves(self):
        if self.ended:
            return []
        return [i for i in range(1, 10) if self.board[self.curr][i] == 0]

    def GetResult(self, playerjm):
        # Get the game result from the viewpoint of playerjm.
        for bo in self.board:
            for x, y, z in [(1, 2, 3), (4, 5, 6), (7, 8, 9),
                            (1, 4, 7), (2, 5, 8), (3, 6, 9),
                            (1, 5, 9), (3, 5, 7)]:
                if bo[x] == bo[y] == bo[z]:
                    if bo[x] == playerjm:
                        return 1.0
                    elif bo[x] != 0:
                        return 0.0
        if not self.GetMoves():
            return 0.5 # draw
        raise ValueError

    def _one_board_string(self, a, row):
        return ''.join([' ' + '.XO'[self.board[a][i+row]] for i in range(3)])

    def _three_board_line(self, index, row):
        return '┃' + ''.join([self._one_board_string(i + index, row) + ' ┃' for i in range(3)])

    def __repr__(self):
        # ┏━━━━━━━┳━━━━━━━┳━━━━━━━┓
        # ┃ . . . ┃ . . . ┃ . . . ┃
        # ┃ . . . ┃ X . X ┃ . . O ┃
        # ┃ . X . ┃ . . O ┃ . . . ┃
        # ┣━━━━━━━╋━━━━━━━╋━━━━━━━┫
        # ┃ . . . ┃ . . . ┃*X X X ┃
        # ┃ X . O ┃ . . . ┃ O . O ┃
        # ┃ . . O ┃ . . . ┃ . . . ┃
        # ┣━━━━━━━╋━━━━━━━╋━━━━━━━┫
        # ┃ . . . ┃ . O . ┃ . O . ┃
        # ┃ . . . ┃ . . . ┃ . . X ┃
        # ┃ . . . ┃ . . . ┃ . . X ┃
        # ┗━━━━━━━┻━━━━━━━┻━━━━━━━┛
        s = '┏━━━━━━━┳━━━━━━━┳━━━━━━━┓\n'
        for i in [1, 4, 7]:
            for j in [1, 4, 7]:
                s += self._three_board_line(i, j) + '\n'
            if i != 7:
                s += '┣━━━━━━━╋━━━━━━━╋━━━━━━━┫\n'
            else:
                s += '┗━━━━━━━┻━━━━━━━┻━━━━━━━┛\n'
        # Hack: by rows and colums of move and current board
        # calculate place to put '*' so it is visible
        c = self.last_curr - 1
        c_c = c % 3
        c_r = c // 3
        m_c = (self.last_move - 1) % 3
        m_r = (self.last_move - 1)// 3
        p = 26 + c_r * (26 * 4) + c_c * 8 + m_r * 26 + m_c * 2 + 1
        s = s[:p] + '*' + s[p+1:]
        return s


class OXOState:
    def __init__(self):
        self.playerJustMoved = 2
        self.ended = False
        self.board = [0, 0, 0, 0, 0, 0, 0, 0, 0]

    def Clone(self):
        return deepcopy(self)

    def DoMove(self, move):
        #  0 1 2
        #  3 4 5
        #  6 7 8
        winning_pairs = [[[1, 2], [4, 8], [3, 6]],  # for 0
                         [[0, 2], [4, 7]],  # for 1
                         [[0, 1], [4, 6], [5, 8]],  # for 2
                         [[0, 6], [4, 5]],  # for 3
                         [[0, 8], [1, 7], [2, 6], [3, 5]],  # for 4
                         [[2, 8], [3, 4]],  # for 5
                         [[0, 3], [4, 2], [7, 8]],  # for 6
                         [[6, 8], [1, 4]],  # for 7
                         [[6, 7], [0, 4], [2, 5]],  # for 6
                         ]
        if not isinstance(move, int) or 0 < move > 8 or \
                self.board[move] != 0:
            raise ValueError
        self.playerJustMoved = 3 - self.playerJustMoved
        self.board[move] = self.playerJustMoved
        for index1, index2 in winning_pairs[move]:
            if self.playerJustMoved == self.board[index1] == self.board[index2]:
                self.ended = True

    def GetMoves(self):
        return [] if self.ended else [i for i in range(9) if self.board[i] == 0]

    def GetResult(self, playerjm):
        for (x, y, z) in [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7),
                          (2, 5, 8), (0, 4, 8), (2, 4, 6)]:
            if self.board[x] == self.board[y] == self.board[z]:
                if self.board[x] == playerjm:
                    return 1.0
                elif self.board[x] != 0:
                    return 0.0
        if self.GetMoves() == []:
            return 0.5  # draw
        raise ValueError

    def __repr__(self):
        s = ""
        for i in range(9):
            s += '.XO'[self.board[i]]
            if i % 3 == 2: s += "\n"
        return s


class Node:
    """ A node in the game tree. Note wins is always from the viewpoint of playerJustMoved.
        Crashes if state not specified.
    """

    def __init__(self, move=None, parent=None, state=None):
        self.move = move  # the move that got us to this node - "None" for the root node
        self.parentNode = parent  # "None" for the root node
        self.childNodes = []
        self.wins = 0
        self.visits = 0
        self.untriedMoves = state.GetMoves()  # future child nodes
        self.playerJustMoved = state.playerJustMoved  # the only part of the state that the Node needs later

    def UCTSelectChild(self):
        """ Use the UCB1 formula to select a child node. Often a constant UCTK is applied so we have
            lambda c: c.wins/c.visits + UCTK * sqrt(2*log(self.visits)/c.visits to vary the amount of
            exploration versus exploitation.
        """
        s = sorted(self.childNodes, key=lambda c: c.wins / c.visits + sqrt(
            2 * log(self.visits) / c.visits))[-1]
        return s

    def AddChild(self, m, s):
        """ Remove m from untriedMoves and add a new child node for this move.
            Return the added child node
        """
        n = Node(move=m, parent=self, state=s)
        self.untriedMoves.remove(m)
        self.childNodes.append(n)
        return n

    def Update(self, result):
        """ Update this node - one additional visit and result additional wins. result must be from the viewpoint of playerJustmoved.
        """
        self.visits += 1
        self.wins += result

    def __repr__(self):
        return "[M:" + str(self.move) + " W/V:" + str(self.wins) + "/" + str(
            self.visits) + " U:" + str(self.untriedMoves) + "]"

    def TreeToString(self, indent):
        s = self.IndentString(indent) + str(self)
        for c in self.childNodes:
            s += c.TreeToString(indent + 1)
        return s

    def IndentString(self, indent):
        s = "\n"
        for i in range(1, indent + 1):
            s += "| "
        return s

    def ChildrenToString(self):
        s = ""
        for c in self.childNodes:
            s += str(c) + "\n"
        return s


def UCT(rootstate, itermax, verbose=False):
    """ Conduct a UCT search for itermax iterations starting from rootstate.
        Return the best move from the rootstate.
        Assumes 2 alternating players (player 1 starts), with game results in the range [0.0, 1.0]."""

    rootnode = Node(state=rootstate)

    for i in range(itermax):
        node = rootnode
        state = rootstate.Clone()

        # Select
        while node.untriedMoves == [] and node.childNodes != []:  # node is fully expanded and non-terminal
            node = node.UCTSelectChild()
            state.DoMove(node.move)

        # Expand
        if node.untriedMoves != []:  # if we can expand (i.e. state/node is non-terminal)
            m = random.choice(node.untriedMoves)
            state.DoMove(m)
            node = node.AddChild(m, state)  # add child and descend tree

        # Rollout - this can often be made orders of magnitude quicker using a state.GetRandomMove() function
        while state.GetMoves() != []:  # while state is non-terminal
            state.DoMove(random.choice(state.GetMoves()))

        # Backpropagate
        while node != None:  # backpropagate from the expanded node and work back to the root node
            node.Update(state.GetResult(
                node.playerJustMoved))  # state is terminal. Update node with result from POV of node.playerJustMoved
            node = node.parentNode

    # Output some information about the tree - can be omitted
    # if (verbose):
    #     print(rootnode.TreeToString(0))
    # else:
    #     print(rootnode.ChildrenToString())

    return sorted(rootnode.childNodes, key=lambda c: c.visits)[
        -1].move  # return the move that was most visited


def HumanPlayer(state):
    moves = state.GetMoves()
    while True:
        try:
            m = int(input("Your move " + str(moves) + " : "))
            if m in moves:
                return m
        except ValueError:
            pass


def RandomPlayer(state):
    return random.choice(state.GetMoves())


def negamax(board, color, depth):  # ##################################################
    moves = board.GetMoves()
    if not moves:
        x = board.GetResult(board.playerJustMoved)
        if x == 0.0:
            print('negamax ERROR:')
            print(board)
            print(board.playerJustMoved)
            print(board.curr, board.ended)
            print(board.GetMoves())
            raise ValueError
        if x == 0.5:
            return 0.0, None
        if color == 1 and board.playerJustMoved == 1:
            return 1.0, None
        else:
            return -1.0, None
    if depth == 0:
        return 0.0, None
    v = float("-inf")
    best_move = []
    for m in moves:
        new_board = board.Clone()
        new_board.DoMove(m)
        x, _ = negamax(new_board, -color, depth - 1)
        x = - x
        if x >= v:
            if x > v:
                best_move = []
            v = x
            best_move.append(m)
    if depth >=8:
        print(depth, v, best_move)
    return v, best_move


def NegamaxPlayer(game):
        best_moves = game.GetMoves()
        if len(best_moves) != 9:
            _, best_moves = negamax(game, 1, 4)
            print(best_moves)
        return random.choice(best_moves)


if __name__ == "__main__":
    def main():
        random.seed(123456789)
        won = 0
        lost = 0
        draw = 0
        for i in range(10):
            # state = OXOState() # uncomment to play OXO
            state = BigGameState()
            move = 0
            while (state.GetMoves() != []):
                if state.playerJustMoved == 1:
                    # m = RandomPlayer(state)
                    m = UCT(rootstate=state, itermax=100, verbose=False)
                else:
                    # m = UCT(rootstate=state, itermax=100, verbose=False)
                    # m = NegamaxPlayer(state)
                    m = HumanPlayer(state)
                    # m = RandomPlayer(state)
                state.DoMove(m)
                move += 1
                print('Game ', i + 1, ', Move ', move, ':\n', state, sep='')
            if state.GetResult(1) == 1.0:
                won += 1
                print("Player 1 wins!")
            elif state.GetResult(1) == 0.0:
                lost += 1
                print("Player 2 wins!")
            else:
                draw += 1
                print("Nobody wins!")
            print('won', won, 'lost', lost, 'draw', draw)

    start_time = time.perf_counter()
    main()
    total_time = time.perf_counter() - start_time
    print('total_time', total_time)

Answer 2

一般来说，是的，α-β剪枝(A)将改善基于转弯的搜索的性能。然而，MCTS有一种不同的方法。at通常取决于在应用点有一个合理准确的董事会评估。MCTS将随机选择的一个分支推入其结论，然后根据每个节点的决策权重向上传播结果。

如果您想在向下决策时应用剪枝，您可以这样做，但是与其添加a，不如将这两种方法混合在一起。我不知道这种改进是否值得在编写和调试方面付出额外的努力。

如果添加特定于领域的知识，您将得到巨大的改进，就像MCTS站点上的性能警告中提到的那样。对于九个板中的每一个，只考虑已知的最佳移动。对于正常的抽搐脚趾来说，优先考虑的问题是

1. 如果可用的话，做出一个获胜的举动。
2. 如果可用的话，阻挡对手的胜利。
3. 从中心广场走。
4. 取一个拐角广场(随机选择)。
5. 取一个侧方(随机选择)。

这组启发式算法永远不会输掉一场正常的游戏。它可以作为你的起点。一旦您添加代码以正确识别胜利，您的程序将加快相当大的速度。

感谢亚历山大·洛帕丁( Alexander )记住了“永不”声明中的致命缺陷。我脸红了，因为我至少在三门课程中教过这个案例：

- - - - - - - 

亚历山大写道：

由于格式限制，我无法将它放在注释中。这里有一个游戏，这个策略失去了最小化：

 0   1   2   3   4   5   6    7 
--- --- --- --- X-- X-- X-X  X-X
--- --- -X- -XO -XO -XO -XO  -XO
--- -O- -O- -O- -O- -OO -OO  OOO

在移动4中，X随机取了一个错误的角正方形。在这个移动中，算法应该使用可能的叉子。

- - - - - - - 

再次修剪：

更糟糕的是，如果你知道人工智能在玩我给出的算法，你可以强迫你赢，而不是随机选择角球：

 0   1   2   3   4   5 
--- --- --- --O X-O X-O
--- --- -X- -X- -X- -X-
--- O-- O-- O-- O-- O-O  ... and 'X' cannot block both winning moves.

在移动4，AI需要看到即将到来的叉子，并与任何侧面移动(任何一个角落失去)，这将导致平局。