井字游戏的遗传算法

因此，我被分配的问题是使用遗传算法编写 5x5x5 井字棋玩家。我的方法是从 3x3 开始，让它发挥作用，然后扩展到 5x5，然后扩展到 5x5x5。

它的工作方式是这样的：

• 模拟一大堆游戏，并在每个游戏的每个回合中，在相应的表（作为 C++ stdlib 映射实现的 X 表或 O 表）中查找响应。如果板不存在，请将板添加到表中。否则，做出随机响应。

• 当我拥有完整的桌子后，我初始化了一群玩家（每个玩家都有一份棋盘表的副本，并使用随机响应进行初始化），并让他们互相对战。

• 使用他们的胜利/失败来评估健康状况，我保留一定比例的最佳球员，然后他们继续前进。冲洗并重复 X 代，最佳玩家就会出现。

对于 3x3，扣除其他棋盘的反射/旋转的棋盘，以及移动为“取胜”或“阻止获胜”的棋盘，我将遇到的棋盘总数为 53 或 38，具体取决于是否你先走还是后走。极好的！不到一个小时就产生了一名最佳球员。很酷！

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

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

解决这个问题的现实方法是什么？我会被卡住使用董事会功能吗？目标是对尽可能少的游戏功能进行硬编码。

我一直在做研究，但我读到的所有内容都会导致最小/最大，而 A-B 剪枝是唯一可行的选择。我当然可以这样做，但是 GA 真的很酷，我目前的方法只是有点超出现实。

EDIT问题已经基本解决了：

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

我对 GA 的了解非常有限，但是在建模板配置方面，您不是问错了问题吗？你的任务不是枚举所有可能的获胜配置——你要做的是找到导致获胜配置的一系列动作。也许您应该查看的群体不是一组棋盘，而是一组移动序列。

Edit:我并没有考虑从一块特定的板开始，而是从一块空板开始。很明显，在 3x3 棋盘上，从 (1,1) 开始的移动序列最适合 X。重要的不是最终棋盘中间有一个 X，而是 X 被放置在中间first。如果 X 有一个或多个最佳第一步，那么 X 是否也有一个最佳第二步、第三步或第四步？经过几轮适应度测试和重新组合后，我们会发现X的第二步动作通常是相同的，还是一小组值中的一个？那么第三个动作呢？

这不是极小极大，因为你不是根据棋盘的先前状态一次寻找最佳动作，而是同时寻找所有最佳动作，希望能够收敛到获胜策略。

我知道这并不能解决你的问题，但如果你的想法是制定一个获胜策略，那么你自然会想要查看移动顺序而不是棋盘状态。