c/c++语言开发共享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); } 

      以上就是c/c++开发分享Tic-Tac-Toe:如何填充决策树?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注(计算机技术网)。

      本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

      如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/550047.html

      (0)
      上一篇 2021年1月14日
      下一篇 2021年1月14日

      精彩推荐