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

Question

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

例如:一个tic tac toe board可以被镜像,但是对于机器学习目的,这两种状态都是等效的

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独特状态的最佳方法是什么？

我应该研究一下学习或数学领域吗？

Answer 1

数学

诀窍是使用Polyas枚举定理:

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

忽略重复,有3个状态的9个方格(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确保你的算法得到它们全部.

正如所建议的那样,从集合中挑选最小的人是以动作为模的配置的唯一代表.