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

Question

我正在制作一个Tic-Tac-Toe计划.我打算用它来使用minimax.我为所有可能的游戏序列制作了一个有空间的树,我正在寻找一种填充它的方法.我目前有这种类型:

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

我正在寻找一种填充网格的方法,就像它在这里显示的一样.我如何填充网格以确保所有可能的组合都存在？我的计划是让游戏识别玩家可以采取的每一个动作,然后决定采取什么步骤来获胜(我仍然需要弄清楚决定部分,但我一直坚持,直到我可以填充树中的网格) .

Answer 1

听起来像是递归给我的主要候选人......

Answer 2

编码基座3中的位置.制作未使用的网格0; 带有"X"a的网格1; 和一个带"O"的网格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)

我想你可以想办法从这里开始.