井字唯一状态计数的高效算法 [英] Efficient algorithm for counting unique states of tic tac toe
问题描述
我正在尝试构建一个tic tac toe游戏，以演示和试验机器学习算法，但我发现了一个有趣的问题.
例如:井字游戏板可以镜像，但是出于机器学习的目的，这两个状态都是等效的
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
忽略重复项，存在3个状态(x，o和-)的9个正方形，因此有3 ^ 9 = 19683个配置.您需要定义在板上提供操作的组.对于您的问题，Dehedral Group 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}等.随身携带而已.这将生成所有板.注意组动作和并置将如何转换这样的数字.可能性是有限的(将x从x移到o，反之亦然，其他根据D4组在板上的位置移动.有8种这样的变换.)您可以使用Polya来确保算法将所有问题都得到了解决.
如建议的那样，从集合中选择最小的家伙是对操作进行模运算的配置的唯一代表.
I'm trying to build a tic tac toe game to demonstrate and experiment with machine learning algorithms, and i've found an interesting problem.
eg: a tic tac toe board can be mirrored, but for a machine learning purposes both these states are equivilent
x _ o o _ x
o o x = x o o
_ _ _ _ _ _
like-wise rotations
x _ o _ _ x _ _ _ o _ _
_ _ _ = _ _ _ = _ _ _ = _ _ _
_ _ _ _ _ o o _ x x _ _
finally, juxtapositions
x _ o o _ x
_ x _ = _ o _
_ _ x _ _ o
what is the best way to identify/count the unique states for tic tac toe?
is there a field of study or mathematics that I should look into ?
Math
The trick is to use Polyas enumeration theorem:
http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem
Ignoring the duplicates, there are 9 squares of 3 states (x, o and -), so there are 3^9 = 19683 configurations. You need to define the group which provides actions on the board. For your problem the Dihedral Group D4 seems to work for everything but the juxtapositions. But the juxtapositions are easy since there are 2 whenever it is not a board full of don't cares (all -, the initial configuration).
Computation
While the math lets us count the configurations, it doesn't help identify them. The perhaps simplest solution is to define a board as a tuple: {p1, p2, p3, ..., p9} where each pn is either {0,1,2}. It requires 2 bits per square and there are 9 of them for a total of 18 bits. A board hence can be represented by a 32bit integer or less.
Indexing into boards is easily done by a hash table. There are only the 19000 configurations, so it isn't going to kill us.
Running through all board configurations is best done on radix-3 arithmetic on the 9-tuple above: {0,0,9,...,0}, {0,0,0,..., 1}, {0,0,0,...,1,0} and so on. It is just addition with carry. This generates all boards. Notice how the group action and juxtaposition will transform such a number. There is a limited amount of possibilities (juxta shifts x to o and vice versa, the others moves around positions on the board according to the D4 group. There are 8 such transformations.) You can use Polya to make sure your algorithm got them all.
As suggested, picking the smallest guy from the set is a unique representant of the configuration modulo the actions.
这篇关于井字唯一状态计数的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
