我正在制作井字游戏程序。我计划使用极小极大。我为所有可能的游戏序列制作了一个带有空间的树，我正在寻找一种填充它的方法。我目前有这种类型：
typedef struct name
{
char grid [3] [3];
struct name * child [9];
} node;
我正在寻找一种填充网格的方法，就像这里显示的那样。我将如何填充网格以确保所有可能的组合都存在？我的计划是让游戏识别玩家可以采取的每一个动作，然后决定采取哪些步骤才能获胜（我仍然需要弄清楚决策部分，但我一直坚持到我可以填满树中的网格） .
对我来说，这听起来像是递归的主要候选人......
以基数 3 编码位置。制作一个未使用的网格0；带有“X”的网格 a 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)
我想你可以想办法从这里继续下去。
编辑：以防上述链接中断，它是对1989 年 10 月《科学美国人》中对 Tinkertoy 计算机的描述的引用，该描述也由与The Tinkertoy Computer and Other Machinations相同的作者与其他 SA 娱乐文章一起编译和出版。制造这台机器的家伙（和女孩）足够聪明，可以避免任何 alpha-beta 搜索，并将电路板压缩成可以轻松计算的东西。由修补匠玩具。
伪代码，因为递归很难做成一个列表：
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语句来做到这一点。
这是递归的经典案例：
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);
}
在这里，您有一个可行的解决方案。它是用 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)