生成所有独特的Tic Tac Toe板的列表

Question

我想生成一个文本文件,其中包含所有19,683个 Tic-Tac-Toe板布局,结构为0 =空白,1 = X,2 = O.不幸的是,数学不是我的强项,我似乎找不到任何例子在任何地方.

这不是我向你保证的作业.我打算通过Minimax计算器运行此数据,以生成包含RGB值的图像,RGB值表示基于电路板设置的最佳移动.我正在开发一个不支持函数的平台Tic-Tac-Toe(它是事件驱动的)所以我会将我的电路板转换为游戏中的数字,然后在图像中查找像素的RGB,以指示最佳移动是.这是一个厚颜无耻的解决方法,但不需要比145x145像素图像更多的RAM(145x145 = 21,025,因此每个像素代表基于电路板的推荐移动有效).这也意味着我不必咀嚼CPU时间,这是另一个优点.

Answer 1

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

• 根据 Tic Tac Toe 规则，棋盘状态有效，即玩家必须轮流放置 X 和 Os。即没有这样的董事会职位：

  XXX
  XXX
  XXO

• 树的所有叶子都包含根据 Tic Tac Toe 规则被视为最终游戏状态的棋盘状态（玩家 1 获胜、玩家 2 获胜或平局）。即没有像这样的树分支：

  XOX
  OXO
  X
  |
  |
  XOX
  OXO <-- 拥有此节点没有意义，因为它的父节点具有最终游戏位置（X 获胜）
  XO

• 给定的树节点可能有多个父节点（多个树节点可能有相同的子节点）。

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

我还找到了一本书，其中提到了 5477 个独特、独特、有效的 Tic Tac Toe 棋盘状态。:

Tic-Tac-Toe 有 5477 个有效状态（不包括空位置）

Answer 2

有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;
}

Answer 3

生成所有可能的游戏板（深度优先搜索效果最好）并排除轮换下的重复项并镜像 765 个板中的结果。626 场中期比赛，X 获胜 91 场，O 获胜 44 场，平局 3 场。

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

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

1. 棋盘上的每个图块都有 3 个状态，因此您可以将棋盘编码为基数为 3 的数字。为了更简单的数学，我使用基数 4（每个图块 2 位，因此我只需要移位）。然后，我有一个哈希函数，可以在所有可能的旋转和镜像（8 种情况）下为棋盘生成该数字，并返回最小值。这样我就可以查找我是否已经玩过该棋盘了。

2. 从一个空棋盘开始，在棋盘上每个可能的位置上做一个标记，检查棋盘是否已经玩过，将其标记为已玩，检查游戏是否结束并计算棋盘数，否则递归交替玩家。

3. 第一个X只能设置在3个位置（考虑旋转和镜像），后面的所有动作最多有8个选择。您可以只计算空的图块并以 3 位对其进行编码，而不是对要播放的绝对图块进行编码。

4. 使用上面的哈希函数为我们提供了 626 个棋盘，我们必须在其中进行移动（您只需反转旋转/镜像即可从数据中获取真正的移动）。可能存在一个不太大的相对素数，以便每个板都适合哈希表而不会发生冲突。假设这个数字是 696（我知道，不是相对质数）。在每盘 3 位的情况下，只需要 261 字节的数据来存储每种可能游戏的最佳走法。

5. 由于你玩得很完美，可到达的棋盘数量再次下降。构建一个用于玩 X 的数据集和一个用于玩 O 的数据集，您可以再次按这种方式进行缩减。

6. 想让它变得更小吗？只需按照一些基本规则进行编程，例如：如果有空，第一个 O 应该在中间。连续 2 个“我的颜色”完成该行。用2个“其他颜色”连续挡住该行，以此类推。维基百科列出了 8 条规则，但我认为当我这样做时，我的规则就少了。

7. 完美的井字游戏对手很无聊。你永远不可能赢。为什么不让游戏从失败中吸取教训呢？跟踪所有 626 个棋盘及其可能的走法。当某步棋导致失败时，将该步棋从棋盘上移除。如果棋盘没有更多的移动，请从所有导致该棋盘的棋盘中删除导致该棋盘的移动（如果删除了那里的最后一步，则递归地）。你的游戏永远不会以同样的方式失败两次。与导致胜利的动作类似，您从可能的动作列表中删除对手的动作，如果没有剩余，您将前一个动作标记为必胜。这样，如果你能强行获胜，那么从现在开始你就会一直强行获胜。玩X你能得到91种方式吗？玩 O 你能让它失去所有 44 种方式吗？

Answer 4

由于您需要电路板布局，因此只有一小部分（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 个电路板布局。我不确定你想要什么格式，但从输出中提取它应该相当容易。