Tic-Tac-Toe：如何填充决策树？
我正在制作Tic-Tac-Toe计划。 我打算用它来使用minimax。 我为所有可能的游戏序列制作了一个带有空间的树，我正在寻找一种填充它的方法。 我目前有这种类型：
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)
我想你可以想办法从这里开始。
伪代码因为递归很难进入列表：
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语句来做到这一点。
孩子的游戏。
编辑：以防上述链接中断，它是1989年10月科学美国人对Tinkertoy计算机的描述的参考，也是由同一作者作为Tinkertoy计算机和其他机械加工编辑和出版的其他SA娱乐文章。 构建这台机器的人（和gals）非常聪明，可以避免任何alpha-beta搜索以及将电路板压缩成易于计算的东西。 通过Tinkertoys。
在这里你有一个有效的解决方案 它是用Python实现的，但我认为它可能会对你有所帮助。
游戏树由build_tree函数递归构建，并实现为列表列表。
build_tree函数接受一个板（树的一个节点）和转向作为输入参数的块，并构建所有可能的新板，从而将该块应用到板上。 然后，对于这些新板中的每一块，它再次调用build_tree函数，但这次改变了转弯的棋子。 当电路板是终端（没有空方块）时，递归结束。
这是1×3板的结果树：
[（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’表示。
对于tic tac toe游戏，请将blank_board = (0,0,0)更改为blank_board = (0,0,0,0,0,0,0,0,0)以获得3×3板。
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)
这是递归的经典案例：
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 na 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); }