algorithm - 计算井字游戏唯一状态的有效算法

Question

我正在尝试构建一个井字游戏来演示和试验机器学习算法，我发现了一个有趣的问题。

例如:井字棋盘可以镜像，但对于机器学习而言，这两种状态是等价的

x _ o     o _ x
o o x  =  x o o
_ _ _     _ _ _

同样的旋转

x _ o   _ _ x   _ _ _   o _ _
_ _ _ = _ _ _ = _ _ _ = _ _ _ 
_ _ _   _ _ o   o _ x   x _ _

最后，并置

x _ o   o _ x
_ x _ = _ o _
_ _ x   _ _ o

识别/计算井字游戏独特状态的最佳方法是什么？

是否有我应该研究的研究领域或数学领域？

Answer 1

数学

技巧是使用 Polyas 枚举定理:

http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem

忽略重复项，有 9 个正方形的 3 个状态(x、o 和 -)，因此有 3^9 = 19683 个配置。您需要定义在板上提供操作的组。对于您的问题，Dihedral Group D4 似乎适用于除并列之外的所有内容。但是并列很容易，因为只要它不是一个充满无关紧要的板(所有 -，初始配置)，就会有 2 个。

计算

虽然数学可以让我们计算配置，但它无助于识别它们。最简单的解决方案可能是将棋盘定义为元组:{p1, p2, p3, ..., p9} 其中每个 pn 是 {0,1,2}。它每平方需要 2 位，共有 9 位，总共 18 位。因此，棋盘可以用 32 位或更小的整数表示。

通过哈希表可以轻松地对板进行索引。只有 19000 个配置，所以它不会杀死我们。

遍历所有电路板配置最好在上面的 9 元组的 radix-3 算法上完成:{0,0,9,...,0}, {0,0,0,..., 1} , {0,0,0,...,1,0} 等等。它只是加进位。这会生成所有板。请注意集体行动和并列将如何改变这样的数字。可能性有限(juxta 将 x 移动到 o，反之亦然，其他人根据 D4 组在棋盘上的位置移动。有 8 种这样的转换。)您可以使用 Polya 来确保您的算法得到所有这些.

如建议的那样，从集合中挑选最小的人是配置模数操作的唯一表示。