pre*_*lic 16 artificial-intelligence genetic-algorithm
所以我被赋予了使用遗传算法编写5x5x5井字游戏的问题.我的方法是从3x3开始,使其工作,然后扩展到5x5,然后扩展到5x5x5.
它的工作方式是这样的:
模拟一大堆游戏,并在每个游戏的每个回合中,在相应的表(X表或实现为c ++ stdlib映射的O表)中查找响应.如果电路板不存在,请将电路板添加到表中.否则,进行随机响应.
在我有完整的表格后,我初始化了一堆玩家(每个玩家都有一个董事会表格副本,用随机响应进行初始化),然后让他们互相对抗.
为3×3,贴现板即是反射/其它板的旋转,和电路板,其中所述移动可以是"取胜"或"阻断取胜",板的总数I会遇到要么53或38,这取决于是否你去第一或第二.太棒了!在一小时内生成了最佳玩家.很酷!
使用相同的5x5策略,我知道表的大小会增加,但没有意识到它会大幅增加.即使折扣旋转/反射和强制移动,我的表格约为360万条,看不到尽头.
好吧,这显然不会起作用,我需要一个新的计划.如果我不列举所有的电路板,只是一些电路板,该怎么办？好吧,似乎这也不会起作用,因为如果每个玩家只有一小部分他们可能看到的可能的板,那么他们将会做出很多随机动作,显然是在最优化的相反方向.
实现这一目标的现实方法是什么？我会被困在使用电路板功能吗？目标是尽可能少地编写游戏功能.
我一直在做研究,但我读到的所有内容都会导致最小/最大,AB修剪是唯一可行的选择.我当然可以这样做,但GA真的很酷,我现在的方法只是在这里超过现实.
编辑问题已经解决了:
使用结合开放空间的汉明距离的相似性函数,可能的获胜条件以及一些其他措施使得桌子降低到可管理的2500种可能性,其std::map在几分之一秒内处理.
我对 GA 的了解非常有限，但是在建模板配置方面，您是否问错了问题？你的任务不是枚举所有可能的获胜配置——你要做的是找到导致获胜配置的一系列动作。也许您应该查看的群体不是一组棋盘，而是一组移动序列。
编辑：我并没有考虑从特定的板开始，而是从空的板开始。很明显，在 3x3 棋盘上，从 (1,1) 开始的移动序列最适合 X。重要的不是最终棋盘中间有一个 X，而是 X首先放置在中间。如果 X 有一个或多个最佳第一步，那么 X 是否也有一个最佳第二步、第三步或第四步？经过几轮适应度测试和重新组合后，我们会发现X的第二步动作通常是相同的，还是一小组值中的一个？那么第三个动作呢？
这不是极小极大，因为你不是根据棋盘的先前状态一次寻找最佳动作，而是同时寻找所有最佳动作，希望能够收敛到获胜策略。
我知道这并不能解决你的问题，但如果你的想法是制定一个获胜策略，那么你自然会想要查看移动顺序而不是棋盘状态。