algorithm - 生成所有独特井字游戏板的列表

Question

我想生成一个包含所有19,683个井字棋棋盘布局的文本文件，其结构为 0 = 空白、1 = X 和 2 = O。不幸的是，数学不是我的强项，我似乎找不到任何例子这个在任何地方。

我向你保证，这不是家庭作业。我打算通过 Minimax 计算器运行这些数据，以生成包含 RGB 值的图像，该值表示基于棋盘设置的最佳移动。我正在为一个不支持功能的平台开发井字游戏（它是事件驱动的），所以我将在我的游戏中将棋盘转换为数字，然后在图像中查找像素的 RGB，这表明什么是最好的移动是。这是一个厚颜无耻的解决方法，但它需要的 RAM 不超过 145x145 像素图像（145x145 = 21,025，因此每个像素有效地代表了基于棋盘的推荐移动）。这也意味着我不必咀嚼 CPU 时间，这是另一个优点。

score 7 · Accepted Answer

有 9 个位置和一个带有 3 个字母（X、O、空）的字母表。可能的组合总数为 3^9 = 19683。

for(int i = 0; i < 19683; ++i)
{
    int c = i;
    for (int j = 0; j < 9; ++j)
    {
        cout << (c % 3) << " ";
        c /= 3;
    }

    cout << endl;
}

score 4 · Accepted Answer

由于您需要电路板布局，因此只有少数（19683）。

你可以蛮力生成所有这些。每个盒子只有 3 种可能性。并且有 9 个盒子，只需将它们全部运行一遍。

编辑：

int c = 0;
while (c < 262144){
    bool valid = (c & 3) < 3;
    valid &= ((c >>  2) & 3) < 3;
    valid &= ((c >>  4) & 3) < 3;
    valid &= ((c >>  6) & 3) < 3;
    valid &= ((c >>  8) & 3) < 3;
    valid &= ((c >> 10) & 3) < 3;
    valid &= ((c >> 12) & 3) < 3;
    valid &= ((c >> 14) & 3) < 3;
    valid &= ((c >> 16) & 3) < 3;

    if (valid){
        int i = c;
        int j = 0;
        while (j < 9){
            cout << (i & 3) << " ";
            i >>= 2;
            j++;
        }
        cout << endl;
    }

    c++;
}

这将打印出所有 19,683 个电路板布局。我不确定您想要什么格式，但从输出中提取它应该相当容易。

score 4 · Accepted Answer

我的 Minimax for Tic Tac Toe 实现生成一棵包含 5477 个节点的树。每个节点包含一个井字棋盘状态并满足以下条件：

根据井字游戏规则，棋盘状态有效，玩家必须轮流放置 X 和 Os。即没有像这样的董事会职位：

XXX
XXX
XXO
树的所有叶子都包含棋盘状态，这些状态根据井字游戏规则（玩家 1 获胜、玩家 2 获胜或平局）被视为最终游戏状态。即没有树的分支，例如：

XOX
OXO
X
|
|
XOX
OXO <-- 有这个节点没有意义，因为它的父节点有一个结束游戏的位置（X 赢了）
XO
给定的树节点可能有多个父节点（多个树节点可能有相同的子节点）。

即，由于可以通过多个不同的移动序列获得给定的棋盘状态，因此在创建树节点时，如果已经有一个包含我要（重新）生成的棋盘状态的节点，我会重用（重新附加）现有的节点。这样，当我从下到上对树节点进行评分时（根据 Minimax 理论），我不必为某些树枝子集多次计算相同的分数（如果我不重用这将是相同的现有节点）。

我还找到了一本书，其中提到了 5477 独特、独特、有效的井字棋棋盘状态。：

Tic-Tac-Toe 有 5477 个有效状态，不包括空位

score 4 · Accepted Answer

生成所有可能的游戏板（深度优先搜索效果最好）并在 765 个板中排除旋转和镜像结果中的重复项。626场是中期，91场X赢，44场O赢，3场平局。

如果您只对最佳动作感兴趣，您可以简单地使用 https://xkcd.com/832/作为参考。做一张漂亮的海报。

但是井字游戏的所有乐趣都在于实现它。所以我把它留给读者。只是一些提示：

板上的每个图块都有 3 个状态，因此您可以将电路板编码为以 3 为底的数字。为了更简单的数学，我使用基数 4（每个图块 2 位，所以我只需要移位）。然后我有一个散列函数，它在所有可能的旋转和镜像（8 种情况）下为板生成该数字并返回最小值。这样我就可以查找我是否已经玩过那个棋盘了。
从一个空棋盘开始，在棋盘上的每个可能的位置上做一个标记，检查棋盘是否已经玩过，标记它已经玩过，检查游戏是否结束并计数棋盘，否则递归交替玩家。
第一个 X 只能设置在 3 个位置（考虑旋转和镜像），后面的所有动作最多有 8 个选择。而不是编码要播放的绝对图块，您只能计算空图块并将其编码为 3 位。
使用上述哈希函数为我们提供了 626 个棋盘，我们必须在其中移动（您只需反转旋转/镜像即可从数据中获取真正的移动）。可能没有大得多的相对质数，因此每个板都可以放入哈希表中而不会发生冲突。假设这个数字是 696（我知道，不是相对素数）。每块棋盘 3 位，只需要 261 字节的数据来存储每个可能游戏的最佳移动。
由于您玩得很完美，因此可到达的棋盘数量再次下降。建立一个用于玩 X 的数据集和一个用于玩 O 的数据集，您可以再次减少这种方式。
想让它更小吗？只需编写一些基本规则，例如：如果空闲，第一个 O 应该在中间。连续使用 2 个“我的颜色”完成该行。用 2 个“其他颜色”在一行中阻止该行，依此类推。Wikipedia 列出了 8 条规则，但我认为当我这样做时我的规则更少。
完美的井字游戏对手很无聊。你永远不可能赢。为什么不让游戏从失败中吸取教训？跟踪所有 626 个棋盘及其可能的移动。当移动导致失败时，从板上删除该移动。如果棋盘没有更多的移动，则从导致该棋盘的所有棋盘中删除导致它的移动（如果删除最后一步，则递归）。你的游戏永远不会以同样的方式输掉两次。类似地，对于导致获胜的动作，您从可能的列表中删除对手的动作，如果没有剩下的动作，您将先前的动作标记为确定的胜利。那样的话，如果你能强制获胜，那么从现在开始你将永远强制获胜。玩 X 能让它松 91 种方式吗？玩 O 能让它失去所有 44 种方式吗？

score 3 · Accepted Answer

您可以简单地暴力破解。每个正方形都是 0、1 或 2，所以...：

for (int i1 = 0; i1 <= 2; i++) {
    for (int i2 = 0; i2 <= 2; i++) {
        // ...
        // lot's of nested for loops
        // ...
    }
}

或者，如果您不介意；）那么您可以为它编写一个递归函数：

int square[9];
void place(int square_num) {
    if (square_num == 9) {
        output the current configuration
    }

    for (int i = 0; i <= 2; i++) {
        square[square_num] = i;
        place(square_num+1);
    }
}

然后做：

place(0);

魔法就会发生。

顺便说一句，这是在 c++ 中。

score 1 · Accepted Answer

可能的移动总数不是 3^9，因为它包括井字游戏中许多不允许的移动。(X's - O's) 或 (O's - X's) 必须始终等于 1。正如https://stackoverflow.com/a/25358690/13557570提到的，可能的移动总数为 5477

使用 numpy 的 Python 代码，状态减少到 5814：

import numpy as np
StatesMatrix = np.zeros((3**9,9))
for i in range(3**9):
     c = i
     for j in range(9):
       StatesMatrix[i][j] = c % 3
       c //= 3
StatesMatrix1 = np.zeros((5814,9))
k = 0
for i in range(0,StatesMatrix.shape[0]):
  if (np. count_nonzero(StatesMatrix[i] == 1) - np. count_nonzero(StatesMatrix[i] == 2)) == 1 or (np. count_nonzero(StatesMatrix[i] == 2) - np. count_nonzero(StatesMatrix[i] == 1))== 1:
    StatesMatrix1[k] = StatesMatrix[i]
    k = k + 1
    
print(StatesMatrix1)
print(k)

score 0 · Accepted Answer

像早期的解决方案一样，但更易于阅读和使用 Python。

for i in range(3**9):
     c = i
     for j in range(9):
         if j % 3 == 0:
             print("")
         print(str(c % 3) + " ", end='')
         c //= 3
     print("")

algorithm - 生成所有独特井字游戏板的列表

7 回答 7

Related

Reference