用于计算井字游戏独特状态的高效算法

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

例如：井字棋板可以是mirrored，但出于机器学习的目的，这两种状态是等效的

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

识别/计算 tic tac toe 的独特状态的最佳方法是什么？

我应该研究某个研究领域或数学吗？

Math

诀窍是使用 Polyas 枚举定理：

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

忽略重复项，有 9 个方格有 3 个状态（x、o 和 -），因此有 3^9 = 19683 个配置。您需要定义在板上提供操作的组。对于您的问题，二面体群 D4 似乎适用于除并置之外的所有问题。但并置很容易，因为只要它不是一个充满不在乎的板（所有 - ，初始配置），就有 2 个。

计算

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

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

运行所有电路板配置最好使用上面 9 元组的基 3 算术：{0,0,9,...,0}、{0,0,0,..., 1}、{0 ,0,0,...,1,0} 等等。这只是带有进位的加法。这会生成所有板。注意集体行动和并置将如何改变这样的数字。可能性有限（juxta 将 x 移动到 o，反之亦然，其他移动根据 D4 组在棋盘上的位置周围移动。有 8 种这样的变换。）您可以使用 Polya 来确保您的算法得到所有这些。

正如所建议的，从集合中选择最小的家伙是对动作取模的配置的唯一表示。