我被分配到一个任务，要使用遗传算法编写一个 5x5x5 的井字游戏 AI。我的方法是从 3×3 开始，先让它运行起来，然后扩展到 5×5，最后到 5x5x5。

它的工作方式如下：

• 模拟一大堆游戏，在每局游戏的每一轮中，都在相应的表（X 表或 O 表，用 C++ stdlib map 实现）中查找响应。如果棋盘不存在，则将棋盘添加到表中。否则，随机做出响应。

• 在我有完整的表格后，我初始化一大堆玩家（每个玩家都有棋盘表格的副本，并用随机响应初始化），让他们相互对战。

• 使用他们的胜/负来评估适应度，我保留一定百分比的最佳玩家，他们可以继续。重复 X 代，应该会出现一个最佳玩家。

对于 3×3，排除掉棋盘是其他棋盘的反射/旋转，以及该步棋是“直接赢”或“阻挡赢”的情况，我遇到的棋盘总数是 53 或 38，这取决于你是先手还是后手。太棒了！不到一个小时就生成了一个最佳玩家。非常酷！

对于 5×5，我使用相同的策略，我知道表格的大小会增加，但没有意识到它会增加得如此之快。即使排除旋转/反射和强制移动，我的表格也有大约 360 万个条目，而且看不到尽头。

好吧，这显然行不通，我需要一个新的计划。如果我不枚举所有的棋盘，而只是枚举一些棋盘呢？嗯，这似乎也不起作用，因为如果每个玩家只有可能看到的棋盘的一小部分，那么他们会做出很多随机移动，显然是朝着与最优相反的方向前进。

有什么现实的方法可以解决这个问题吗？我是否会被迫使用棋盘特征？目标是尽可能少地硬编码游戏功能。

我一直在做研究，但我读到的一切都表明，带有 A-B 剪枝的 min/max 是唯一可行的选择。我当然可以这样做，但遗传算法真的很酷，我目前的方法在这里有点超出实际情况了。

编辑 问题几乎已经解决：

使用一个相似性函数，结合了开放空间的汉明距离、可能的获胜条件以及其他一些度量，将表格缩小到一个非常易于管理的 2500 个可能性，std::map 可以在不到一秒的时间内处理这些可能性。

回答：

我对遗传算法的了解非常有限，但在对棋盘配置进行建模时，你是否问错了问题？你的任务不是枚举所有可能的获胜配置——你试图做的是找到一系列通往获胜配置的动作。也许你应该关注的种群不是一组棋盘，而是一组移动序列。

编辑：我考虑的更多的是从一个空棋盘开始，而不是从一个特定的棋盘开始。在 3×3 的棋盘上，很明显以 (1,1) 开头的移动序列对 X 最有利。重要的不是最终的棋盘中间有一个 X，而是 X 首先被放在中间。如果 X 有一个或多个最佳第一步，那么 X 也有最佳的第二步、第三步或第四步吗？经过几轮的适应度测试和重组，我们会发现 X 的第二步通常是相同的，还是属于一小组值中的一个？第三步呢？

这不是极小极大算法，因为你不是基于棋盘的先前状态一次寻找最佳移动，而是在同时寻找所有最佳移动，希望收敛到一种获胜策略。

我知道这不能解决你的问题，但如果目的是进化出一种获胜策略，那么你自然会想要关注移动序列而不是棋盘状态。