计算tic toe唯一状态的有效算法

Question

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

一个抽搐的脚趾板可以是镜像的，但就机器学习的目的而言，这两种状态都是相等的。

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

智慧型旋转

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

最后，juxtapositions

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配置。您需要定义在董事会上提供操作的组。对于您的问题，二面体组D4似乎适用于除并置之外的所有东西。但是并行处理很容易，因为当它不是一个“不关心”(所有的-，最初的配置)时，就有2种。

计算

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

索引到板是很容易完成的哈希表。只有19000的配置，所以它不会杀了我们。

在上述9元组上，以基数-3算法运行所有板的配置最好：{0,0,9，...,0}，{0,0,0，0，…，1}，{0,0,0，0，...,1,0}等等。它只是加上了进位。这就产生了所有的板。注意组操作和并置将如何转换这样一个数字。根据D4集团的说法，有一定数量的可能性(顺势移动x到o，反之亦然，其他的在董事会中的位置移动。)有8个这样的转换。)您可以使用Polya来确保您的算法都得到了它们。

正如建议的那样，从集合中选择最小的人是配置模块化操作的独特代表。

Answer 2

我不知道正确的数学方法，但我会这样做。设计一种将任何状态转换为一个数字的方法。例如，将空字段赋值为零，将O段赋值为1，将X段赋值为2，并将9位数作为基-3系统中的一个数字。现在，将状态转换为所有剩下的7个镜像状态。也算一下他们的人数。从这8个数字中选出最小的一个。就这样。

Answer 3

如果你只关心最优的动作：

请看这张最优toe移动的系统地图(http://xkcd.com/832/)。您可以使用一些(col，row)索引来标识特定的状态。

如果存在多个等效状态，则使用“最低”索引(必须定义“最低”的含义；例如，值3*col+row最低的(col，row)对)。

​

​