我一直在认真尝试创建一个遗传程序，以便它能以可接受的方式演化出玩井字游戏的能力。我使用基因组来生成一个函数，然后该函数以棋盘作为输入并输出结果…但它不起作用。

这个程序能否在少于500行代码（包括空行和文档）的情况下编写出来？也许我的问题在于我生成的AI过于简单了。

我的研究

• 井字游戏的遗传算法（与我的方法非常不同）。
• http://www.tropicalcoder.com/GeneticAlgorithm.htm（过于抽象）。
• 在相当多的网站上都有提到“神经网络”。它们真的需要吗？

重要声明

• 这不是任何形式的家庭作业，只是一个为了学习一些有趣东西的个人项目。
• 这不是“请给我代码”的请求，我正在寻找高层次的建议。我明确地不想要现成的解决方案作为答案。

请给我一些帮助和见解，关于将这个“遗传编程”概念应用于这个特定简单问题的见解。

@OnABauer：我认为我使用的是遗传编程，因为引用维基百科的话

在人工智能中，遗传编程（GP）是一种基于进化算法的方法论，受到生物进化的启发，用于寻找执行用户定义任务的计算机程序。

而我正在尝试生成一个程序（在这种情况下是函数），以执行玩井字游戏的任务，你可以看到这一点，因为最重要的genetic_process函数的输出是一个基因组，然后它将被转换为一个函数，因此如果我理解正确的话，这是遗传编程，因为输出是一个函数。

程序自省和可能的错误/问题

代码运行时没有错误或崩溃。问题在于，最终我得到的是一个无能的AI，它会尝试做非法移动，每次都会被惩罚输掉。它并不比随机更好。

可能是因为我的AI函数过于简单：仅对存储的方块值进行计算，没有条件判断。

高层次描述

• 你的染色体代表什么？

我的染色体代表一个函数列表，这些函数将被用于对存储为三元的棋盘数组进行归约。让我举个例子：* 染色体是：amMMMdsa（染色体的长度必须为8）。1. 第一步是根据顶部的查找表LETTERS_TO_FUNCTIONS将此转换为函数，这给出了函数：[op.add,op.mul,op.mod,op.mod,op.mod,op.floordiv,op.sub,op.add]

2. 第二步是将棋盘转换为三元表示。所以假设棋盘是"OX XOX "，我们将得到 [2, 3, 1, 1, 3, 2, 3, 1, 1]

3. 第三步是使用上述获得的函数对三元表示进行归约。最好通过下面的函数来解释：

   def reduce_by_all_functions(numbers_list,functions_list):    """    将列表中的所有函数应用于数字列表。    >>> reduce_by_all_functions([3,4,6],[op.add,op.sub])    1    >>> reduce_by_all_functions([6,2,4],[op.mul,op.floordiv])    3    """    if len(functions_list) != len(numbers_list) - 1:        raise ValueError("函数必须恰好比数字少一个")    result = numbers_list[0]    for index,n in enumerate(numbers_list[1:]):        result = functions_list[index](result,n)    return result

   因此产生的结果是：0，这意味着AI决定走第一格

   • 你的适应度函数是什么？

幸运的是，这个问题很容易回答。

def ai_fitness(genome,accuracy):    """    通过让AI多次与随机AI对战，返回AI的表现好坏。    值越高，AI表现越好    """    ai = from_genome_to_ai(genome)    return decide_best_ai(ai,random_ai,accuracy)

• 你的变异是如何工作的？

儿子继承父亲80%的基因和母亲20%的基因。除了这一点之外，没有其他形式的随机变异。

那么reduce_by_all_functions()是如何使用的？我看到它接受一个棋盘和一个染色体并返回一个数字。这个数字是如何使用的，它代表什么，以及…为什么要返回模9？

reduce_by_all_functions()用于实际应用之前由染色体获得的函数。这个数字是AI想要走的方块。它是模9因为它必须在0到8之间，因为棋盘有9个格子。

我到目前为止的代码：

...

回答：

首先，我有义务说，井字游戏实在是太简单了，不适合用遗传程序来解决。你根本不需要GP的强大功能来赢得井字游戏；你可以用暴力查找表或简单的游戏树来解决它。

话虽如此，如果我理解正确的话，你的基本概念是这样的：

1) 创建长度为8的染色体，每个基因是一个算术运算，8基因染色体作为每个棋盘的评估函数。也就是说，一个染色体接受一个棋盘表示，并吐出一个代表该棋盘好坏的数字。

这不是完全清楚你正在做什么，因为你的棋盘表示是9个整数（仅1、2、3），但你的例子是根据“赢得三连”给出的，这些是2个整数（0到8）。

2) 启动AI，在AI的回合，它应该获取所有合法移动的列表，根据其染色体评估每个合法移动的棋盘，然后…取那个数字，模9，并用它作为下一步移动？当然，里面应该有一些代码来处理移动非法的情况….

3) 让这些染色体表示物与标准实现对战，或者相互对战，并根据赢的次数来确定适应度。

4) 一旦一整代的染色体被评估，创建新一代。我不清楚你是如何从池中选择父母的，但是一旦选择了父母，孩子是通过80-20规则从父母那里获取单个基因来产生的。

你的整体高层次策略是合理的，但在执行中存在很多概念和实施上的缺陷。首先，让我们谈谈完全可观察游戏和为它们制作AI的简单方法。如果游戏非常简单（如井字游戏），你可以简单地制作一个暴力极小极大游戏树，如这个。TTT足够简单，即使是你的手机也能很快到达树的底部。你甚至可以通过暴力查找表来解决它：只需列出所有棋盘位置和对每个位置的响应即可。

当游戏变得更大时——想想跳棋、国际象棋、围棋——这不再是真的，解决这个问题的方法之一是开发所谓的棋盘评估函数。这是一个接受棋盘位置并返回一个数字的函数，通常对于一个玩家来说，数值越高越好，对于另一个玩家来说，数值越低越好。然后执行搜索到某个可接受的深度，并瞄准最高的（比如说）棋盘评估函数。

这就引出了一个问题：我们如何得出棋盘评估函数？最初，人们会请游戏专家为你开发这些函数。有一个很好的论文，作者是Chellapilla和Fogel，与你想要为跳棋做的类似——他们使用神经网络来确定棋盘评估函数，并且，这些神经网络被编码为基因组并进行演化。然后它们在搜索深度为4的树中使用。最终结果在与人类玩家对战中非常有竞争力。

你应该阅读那篇论文。

我认为你试图做的非常相似，只是你不是将神经网络编码为染色体，而是试图编码一个非常受限的代数表达式，总是这样的形式：

((((((((arg1 op1 arg2) op2 arg3) op3 arg4) op4 arg5) op5 arg6) op6 arg7) op7 arg8) op8 arg)

…然后你用它模9来选择一个移动。

现在让我们谈谈遗传算法、遗传程序以及创建新孩子的过程。进化技术的整个想法是结合两个希望好的解决方案的最佳属性，希望它们会更好，而不会陷入局部最大值。

通常，这是通过锦标赛选择、交叉和变异来完成的。锦标赛选择意味着根据适应度按比例选择父母。交叉意味着将染色体分为两个通常是连续的区域，从一个父母中取一个区域，从另一个父母中取另一个区域。（为什么是连续的？因为Holland的模式定理）变异意味着偶尔改变一个基因，作为保持种群多样性的手段。

现在让我们看看你在做什么：

1) 你的棋盘评估函数——你的染色体转变成的函数，作用于棋盘位置——是高度受限和非常任意的。将1、2和3指定为这些数字没有多少理由，但这可能还可以。更大的缺陷是你的函数是整体函数空间中非常受限的一部分。它们总是相同的长度，解析树总是看起来相同。

没有理由期望在这个限制性空间中找到任何有用的东西。需要的是提出一个允许更一般解析树集合的方案，包括交叉和变异方案。你应该查找一些由John Koza写的论文或书籍，了解这个话题的想法。

请注意，Chellapilla和Fogel也有固定形式的函数，但他们的染色体比他们的棋盘表示要大得多。一个跳棋棋盘有32个可玩空间，每个空间可以有5种状态。但他们的神经网络有大约85个节点，染色体包括这些节点的连接权重——数百个，如果不是数千个值的话。

2) 然后是这个整个模9的事情。我不明白你为什么要这样做。不要这样做。你只是在扰乱你的染色体中可能存在的任何信息。

3) 你生成新孩子的函数不好。即使作为遗传算法，你也应该将染色体分为两部分（在随机点上），并从一侧取一个父母的一部分，从另一侧取另一个父母的另一部分。对于你正在做的遗传编程，有类似的策略来对解析树进行交叉。参见Koza。

你必须包括变异，否则你几乎肯定会得到次优结果。

4a) 如果你通过与一个能力强的AI对战来评估适应度，那么要意识到你的染色体永远不会赢。它们会输，或者会平局。一个能力强的AI永远不会输。而且，很可能你的AIs会一直输，初期几代都可能表现出同样（灾难性）的差劲表现。摆脱这个困境并非不可能，但会很困难。

4b) 另一方面，如果像Chellapilla和Fogel一样，你让AIs相互对战，那么你最好确保AIs能玩X或O。否则你永远不会取得任何进展。

5) 最后，即使解决了所有这些问题，我也不确定这会取得很好的结果。请注意，跳棋的例子搜索到深度4，这在可能持续20或30步的跳棋游戏中不是一个大的视野。

TTT最多只能持续9步。

如果你不进行搜索树而只是追求最高的棋盘评估函数，你可能会得到一些有效的东西。你也可能不会。我不确定。如果你搜索到深度4，你还不如直接搜索到第9级，按传统方法进行。