目录

一，套娃圈叉棋

二，解空间分析

1，节点

2，解空间结构

三，复杂度分析

1，总节点数目

2，关键节点数目

四，思路分析

一，套娃圈叉棋

在圈叉棋的基础上，加上套娃的规则：

每人有9个棋子，3大3中3小，较大的可以把较小的套住。

二，解空间分析

1，节点

节点包含的信息有：

• 9个格子的状态，每个格子有7种状态（空白、双方的大中小棋子）
• 轮到谁下
• 双方手里剩下的棋子数量

双方手里剩下的棋子数量可以推算出轮到谁下。

2，解空间结构

这是一个无环的有向图，开局作为起点，到任意节点都有唯一路劲存在。

如果去掉方向，那么得到的无向图就有圈了。

三，复杂度分析

1，总节点数目

9个格子的状态有7^9=40353607种，双方手里剩下的棋子数量有（4*4*4）^ 2 = 4096种情况，一共有40353607*4096=1653亿种情况。

考虑到双方手里剩下的大棋子的数量其实也可以推算出来，那么就只有40353607*16*16=103亿种情况。

数目还是有点大，动态规划的备忘录存103亿种状态，需要的内存太大。

2，关键节点数目

所有局面最终都会走向三种局面：

• 胜负已分，但是还有空格。
• 所有棋子都用完了，平局，但是还有空格。
• 没有空格。

其中，前两种局面应该是很少的，关键是第三种，没有空格的局面。

没有空格的局面，方手里剩下的小棋子就没用了，所有只有6^9 * 4 * 4 * 2 = 3.2亿种情况。

之所以要乘2，是因为要区分轮到谁下了。

如果每种情况用4字节来表示，那么一共需要大概1G的内存。

四，思路分析

首先，我们可以先把所有的关键状态的胜负全部求出来，然后以此为基础再求其他状态的胜负。

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/125057136