Tic-Tac-Toe：如何填充决策树？

Question

我正在制作一个井字游戏程序。我计划将 minimax 与它一起使用。我制作了一棵树，其中包含所有可能的游戏序列的空间，并且我正在寻找一种方法来填充它。我目前有这种类型：

typedef struct name
{
    char grid [3] [3];
    struct name * child [9];
} node;

我正在寻找一种填充网格的方法，就像它所示的此处。我将如何填充网格以确保所有可能的组合都存在？我的计划是让游戏识别玩家可以采取的每一步，然后决定采取哪些步骤才能获胜（我仍然需要弄清楚决策部分，但我会坚持下去，直到我可以填充树中的网格） 。

Answer 1

对我来说听起来像是递归的主要候选者......

Answer 2

对基数 3 中的位置进行编码。创建一个未使用的网格 0；带有“X”的网格 1；以及带有“O”a 2 的网格。因此，您可以拥有的完整网格的绝对最大数量是 3^9 = 19683（其中一些是无效的井字游戏表示）

因此，假设您正在处理“020112021”。它的孩子们是：

020112021 /* father */ (4759 base 10)
=========
020112022                 father + 1 (1 base 3)
0201120x1 /* invalid */   father + 3 (10 base 3)
020112121                 father + 9 (100 base 3)
02011x021 /* invalid */   father + 27 (1000 base 3)
020122021                 father + 81 (10000 base 3)
020212021                 father + 243
021112021                 father + 729
0x0112021 /* invalid */   father + 2187
120112021                 father + 6561 (100000000 base 3)

我认为你可以想出一种从这里继续下去的方法。

Answer 3

伪代码，因为递归很难放入列表中：

function descend(X_or_O, board)
    for square in board
        If square isn't empty: continue
        new_board = Fill in square with X_or_O.
        Check for a winner (if yes, return)
        newer_board = descend(opposite of X_or_O, new_board)
        tack newer_board onto the tree.
        clear out square

您应该能够通过几个 for 循环和 if 语句来做到这一点。

Answer 4

编辑

：以防万一上述情况链接中断，它引用了《科学美国人》1989 年 10 月对 Tinkertoy 计算机的描述，该文章还与《The Tinkertoy 计算机和其他机器》同一作者的其他 SA 娱乐文章一起编译和出版。 /em>.
建造这台机器的家伙（和女孩）足够聪明，可以避免任何 alpha-beta 搜索，并将棋盘压缩成易于计算的东西。由 Tinkertoys 制作。

Answer 5

这里你有一个可行的解决方案。它是用Python实现的，但我认为它可能对你有帮助。

游戏树由 build_tree 函数递归构建，并以列表的列表形式实现。

build_tree 函数将棋盘（树的一个节点）和轮到玩的棋子作为输入参数，并构建将棋子应用到棋盘后产生的所有可能的新棋盘。然后，对于每个新棋盘，它再次调用 build_tree 函数，但这次更改了轮到玩的棋子。当棋盘结束时（没有空方块），递归结束。

这是 1x3 棋盘的结果树：

[(0, 0, 0), [[('x', 0, 0), [[('x', 'o', 0), [('x' , 'o', 'x')]], [('x', 0, 'o'), [('x', 'x', 'o')]]]], [(0, 'x') ', 0), [[('o', 'x', 0), [('o', 'x', 'x')]], [(0, 'x', 'o'), [ ('x', 'x', 'o')]]]], [(0, 0, 'x'), [[('o', 0, 'x'), [('o', ' x', 'x')]], [(0, 'o', 'x'), [('x', 'o', 'x')]]]]]]

空方块用 '0 表示'。

对于井字游戏，请将 blank_board = (0,0,0) 更改为 blank_board = (0,0,0,0,0,0,0,0,0) 以便拥有 3x3 板。

def change_piece(piece):
    if piece == 'x': return 'o'
    return 'x'

def is_terminal(board):
    """Check if there are any empty square in the board"""
    for square in board:
        if square == 0:
            return False
    return True

def build_tree(node, piece):
    """Build the game tree recursively. 

    The tree is implemented as a list of lists.
    """
    child_nodes = []
    for index, value in enumerate(node):
        if value == 0:
            new_node = list(node)
            new_node[index] = piece
            new_node = tuple(new_node)
            if not is_terminal(new_node):
                child_nodes.append(build_tree(new_node,change_piece(piece)))
            else:
                child_nodes.append(new_node)
    if child_nodes:
        return [node,child_nodes]
    return

if __name__ == "__main__":
    blank_board = (0,0,0)
    game_tree = build_tree(blank_board,'x')
    print(game_tree)

Answer 6

这是递归的经典案例：

typedef struct name
{
    char grid [3] [3];
    struct name * child [9];
} node;

node * new_grid(node *parent) {
    node *n = calloc(1, sizeof(node));
    if (parent)
        memcpy(n->grid, parent->grid, sizeof(grid));
}

// is n a winner based on the move just made at x,y?
int winner(const node *n, int x, int y) {
    return (n->grid[x][0] == n->grid[x][1] == n->grid[x][2]) ||
           (n->grid[0][y] == n->grid[1][y] == n->grid[2][y]) ||
           ((x == y) && (n->grid[0][0] == n->grid[1][1] == n->grid[2][2])) ||
           ((2-x == y) && (n->grid[0][2] == n->grid[1][1] == n->grid[2][0]));
}

void fill(node *n, char c) {
    int x, y, children;
    node *child;

    for (x = 0; x < 3; x++) {
        for (y = 0; y < 3; y++) {
             if (n->grid[x][y])
                 continue;
             child = n->child[children++] = new_grid(n);
             child->grid[x][y] = c;

             // recurse unless this is a winning play
             if (!winner(child, x, y))
                 fill(child, c == 'x' ? 'y' : 'x');
        }
    }
}

int main(void) {
    node *start = new_grid(0);
    fill(start);
}