用于计算井字游戏独特状态的高效算法
我正在尝试构建一个井字游戏来演示和实验机器学习算法，并且我发现了一个有趣的问题。
例如：井字游戏板可以镜像，但出于机器学习的目的，这两种状态是等效的
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 的独特状态的最佳方法是什么？
我应该研究某个研究领域或数学吗？
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 ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
数学
诀窍是使用 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 元组上使用 radix-3 算术来完成：{0,0,9,...,0}, {0,0,0,..., 1}, {0 ,0,0,...,1,0} 等等。这只是带有进位的加法。这会生成所有板。注意集体行动和并置将如何改变这样的数字。可能性有限（juxta 将 x 转换为 o，反之亦然，其他转换根据 D4 组在棋盘上的位置移动。有 8 种这样的转换。）您可以使用 Polya 来确保您的算法获得所有这些转换。
正如所建议的，从集合中挑选最小的家伙是对动作取模的配置的唯一表示。
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.
我不知道正确的数学方法，但我会这样做。设计一种将任何状态转换为一个数字的方法。例如，将空字段指定为 0，将 O 块指定为 1，将 X 块指定为 2，并将 9 位数字视为基数为 3 的数字。现在，将状态转换为所有剩余的 7 个镜像状态。也计算一下他们的数量。从这 8 个数字中选择最小的一个。就是这样。
I don't know the proper mathematical way, but I'd do it like this. Devise a way to convert any state to one number. For instance, assign empty field to zero, O piece to 1, X piece to 2, and treat 9 digits as a number in base-3 system. Now, transform the state to all 7 remaining mirror states. Calculate their numbers too. Pick the smallest out of those 8 numbers. That's it.
如果您只关心最佳动作：
请参阅此最佳 tic-tac-toe 动作的系统图 (http://xkcd. com/832/）。您可以使用一些（列、行）索引来标识特定状态。
如果存在多个等效状态，请使用所有等效状态中的“最低”索引（您必须定义“最低”的含义；例如，值 3*col+row 最低的 (col,row) 对）。
If you care only about optimal moves:
See this systematic map of optimal tic-tac-toe moves (http://xkcd.com/832/). You can use some (col, row) indexing to identify a particular state.
If there is more than one equivalent state, use the "lowest" index (you have to define what "lowest" means; e.g. that (col,row) pair whose value 3*col+row is lowest) of all equivalent ones.
结合其他答案的一些想法......
不要将配置映射到数字。使用数字代表配置。如果您确实需要通过 x,y 位置获取/设置，请编写对表示进行操作的方法。
然后选择一种可以有效地回答问题的表示形式。这是一个想法。
您有三个操作，所以让我们给它们命名：
您想要计算这些操作的轨道下板的等价类数量。每个等价类中最多有 16 个元素。给定一块板，您可以通过按以下顺序应用操作来生成其他 15 个等效板：
R, R, R, I, R, R, R, M, R, R, R, I, R, R, R
（还有其他序列也可以工作...）
所以一个好主意是选择一种使 R 更快的表示，我有点快，并且不用太担心 M。
由于 R 不会改变中心，所以我会将其保存在其他地方，并使用 2 位数字序列来表示其他 8 个方格。我会让第一个 2 位数字代表左下角，下一个 2 位数字代表旁边的正方形，依此类推，在棋盘上逆时针移动。我会让 00 代表“O”，11 代表“X”，01 和 10 都代表“空”（因为这样操作 I 就变成了简单的位翻转）。
然后，如果您将这 8 个 2 位数字写为单个 16 位数字，则操作 R 只是对 16 位数字进行循环操作，您的 CPU 可能可以在单个指令中执行该操作。操作 I 只是与 -1 进行异或（但也不要忘记反转中心方块）。 M 操作是一堆复杂的位修改，但既然你只在 15 次中执行一次，谁在乎呢？
这应该可以让您采用任何表示形式并快速生成其他 15 个等效的表示形式。然后，正如辩证法所建议的那样，选择数字最小的表示作为等价类的规范成员并计算它们。
Combining some of the ideas from the other answers...
Do not map configurations to numbers. Use numbers to represent configurations. Write methods to operate on the representation if you really need to get/set by x,y location.
Then choose a representation that you can operate on efficiently to answer the question. Here is one idea.
You have three operations, so let's give them names:
You want to count the number of equivalence classes of boards under the orbit of these operations. There are at most 16 elements in each equivalence class. Given a board, you can generate the other 15 equivalent boards by applying the operations in the following sequence:
R, R, R, I, R, R, R, M, R, R, R, I, R, R, R
(There are other sequences that work, too...)
So a good idea would be to pick a representation that makes R fast, I somewhat fast, and not worry too much about M.
Since R does not change the center, I would hold that somewhere else, and use a sequence of 2-bit numbers to represent the other 8 squares. I would let the first 2-bit number represent the lower-left, the next 2-bit number represent the square next to that, and so on, moving counter-clockwise around the board. I would let 00 represent "O", 11 represent "X", and both 01 and 10 represent "empty" (because then operation I becomes a simple flipping of bits).
Then if you write those 8 2-bit numbers as a single 16-bit number, operation R is just a rotate operation on the 16-bit number, which your CPU can probably perform in a single instruction. Operation I is just XOR with -1 (but do not forget to invert the center square too). Operation M is a complicated bunch of bit-munging, but since you only do it one time out of 15, who cares?
This should let you take any representation and quickly generate the other 15 that are equivalent. Then as Dialecticus suggests, pick the numerically smallest representation as your canonical member of the equivalence class and count those.
我认为图论对此很有用，对于您给出的示例，您将拥有一个包含 9 个顶点的图。唯一仍然可能成为问题的是并置。
I think graph theory is good for this, you would have a graph with 9 vertices for the example you gave. The only thing that could still be a problem is juxtapositions.
井字棋与人工智能有关，特别是来自博弈论的最小最大算法，更具体地说是AB剪枝以获得良好的结果。整个主题很大，但很简单且程序化。它很容易掌握，您可以从以下页面开始：
http://en.wikipedia.org/wiki /Game_theory
http://www.cs.trincoll。 edu/~ram/cpsc352/notes/minimax.html
比上面的链接更清晰、更简单的东西：
http://www.cs.ucla.edu/~rosen/161/notes/alphabeta.html
Tic tac toe is related to AI, specifically minmax algorithm from Game theory, even more specifically AB Pruning for good results. The entire topic is huge, but is easy and procudural. It is easy to grasp and you can get started at these page:
http://en.wikipedia.org/wiki/Game_theory
http://www.cs.trincoll.edu/~ram/cpsc352/notes/minimax.html
Something lucid and easier than the above link:
http://www.cs.ucla.edu/~rosen/161/notes/alphabeta.html