我正在尝试构建一个井字游戏来演示和试验机器学习算法,我发现了一个有趣的问题。
例如:井字棋盘可以镜像,但对于机器学习而言,这两种状态是等价的
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
识别/计算井字游戏独特状态的最佳方法是什么?
是否有我应该研究的研究领域或数学领域?
最佳答案
数学
技巧是使用 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 来确保您的算法得到所有这些.
如建议的那样,从集合中挑选最小的人是配置模数操作的唯一表示。
关于algorithm - 计算井字游戏唯一状态的有效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6160231/