所以我被分配了使用遗传算法编写5x5x5井字游戏的问题。我的方法是从3x3开始，然后扩展到5x5，再扩展到5x5x5。
它的工作方式是这样的:
-
模拟一大堆游戏，在每个游戏的每个回合中，查找相应的表(X表或O表实现为c++ stdlib映射)以获得响应。如果板不在那里，将板添加到表中。否则，随机响应。
-
在我有了完整的表格后，我初始化了一群玩家(每个玩家都有一个棋盘表格的副本，初始化随机反应)，让他们互相对抗。
- 用他们的胜利/失败来评估健康，我保留一定百分比的最佳球员，然后他们继续前进。重复X代，最佳玩家就会出现。
对于3x3，折扣棋盘是其他棋盘的反射/旋转，以及棋盘的移动是"获胜"或"阻止胜利"，我将遇到的棋盘总数是53或38，这取决于你是第一个还是第二个。太棒了!一个最佳玩家在一个小时内生成。非常酷!
对于5x5使用相同的策略，我知道表的大小会增加，但没有意识到它会如此急剧地增加。即使不考虑旋转/反射和强制移动，我的表也有360万个条目，看不到尽头。
好吧，那显然行不通，我需要一个新计划。如果我不列举所有的板，而只是一些板呢?好吧，这似乎也行不通，因为如果每个玩家只有一小部分可能看到的棋盘，那么他们就会做出很多随机的移动，显然是在与最优性相反的方向上。
现实的做法是什么?我是否会被困在使用棋盘功能上?我们的目标是硬编码尽可能少的游戏功能。
我一直在做研究，但我读到的所有东西都指向最小/最大，A-B修剪是唯一可行的选择。我当然可以这样做，但是遗传算法真的很酷，我现在的方法只是在这里超出了现实。
EDIT问题已经基本解决:
使用结合开放空间的汉明距离，可能的获胜条件和其他一些措施的相似性函数，将表降低到非常可管理的2500种可能性，std::map在几分之一秒内处理。
我对GA的了解非常有限，但是在建模板配置方面，您不是问错了问题吗?你的任务并不是列举所有可能的获胜配置——你要做的是找到一系列能够导致获胜配置的移动。也许你应该关注的群体不是一组棋盘，而是一组移动序列。
编辑:我没有想到从一个特定的板开始，因为从一个空板开始。很明显，在3x3棋盘上，从(1,1)开始的移动序列最适合X。重要的不是最后的棋盘中间有一个X，而是X被放置在中间第一个。如果X有一个或多个最佳第一步，那么X可能也有最佳第二，第三，第四步?经过几轮适应度测试和重组，我们会发现X的第二步通常是相同的，还是一个小的值集合?那第三步呢?
这不是极大极小，因为你不是根据棋盘的先前状态一次寻找一个最好的走法，你是同时寻找所有最好的走法，希望收敛到一个获胜的策略。
我知道这并不能解决你的问题，但是如果你的想法是进化出一个获胜的策略，那么你就会很自然地想要查看移动序列而不是棋盘状态。
这似乎是一个非常古老的谈话，但引起了我的注意。考虑到它可能有助于公众讨论，以下是我的意见。
我认为分配给你的任务的目标需要定义得更清楚。
-
你是在寻找一套获胜板吗?我不这么认为，因为对于一个3 × 3的棋盘来说这是很简单的甚至可以用手来解，而且它可以外推到更大的棋盘上。遗传算法可以用于更大的电路板，但这只是一个遗传算法练习。
-
你们是想利用GA来训练TicTacToe给AI玩家玩吗?我认为应该是这样。在这种情况下，你的GA字符串/染色体不应该代表获胜的棋盘，相反，它们应该代表玩家有序的移动序列，以赢得游戏。不过，正如预期的那样，这确实有点棘手，这将是一个真正的人工智能训练编程练习。
我希望这个观点有帮助。