这种语言是否足够通用/强大到可以用于通用游戏AI？

Question

我想开发一个遗传程序，可以解决像在电脑游戏中生存这样的一般性问题。由于这是为了娱乐/教育，所以我不想使用现有的库。

我想出了以下想法：

输入是由N个整数组成的数组。遗传程序由最多N个AST组成，每个AST从一些数组元素获取输入，并将其输出写入单个特定的数组元素。

AST可以是任意复杂的，并且只由四个算术运算符(+，-，*，/)组成，并且可以对给定数组的常量和固定元素进行操作(无随机访问)。

因此，对于N=3，我们有3个AST，例如：

a[0] = {a[0] + 1}
a[1] = {a[0] + a[1]}
a[2] = {a[0] * 123 + a[1]}

N个AST一个接一个地执行，并且无限地重复执行。

现在我的问题是，这个系统是否足够“强大”(图灵完备性？)或者它会不会解决游戏AI中常见的一些问题？

Answer 1

在我看来，系统的图灵完整性不是这里的主要问题。当使用遗传算法来进化某种应用于游戏环境的策略时，该算法的一个特性--这将是有用的--我相信--解决方案的“基因组”中的微小变化会导致行为上的合理微小变化。如果这不是真的，那么每个变异或交叉都会产生一个表现完全不同的实体，在这种情况下，遗传算法可能会出现问题，因为适应度函数的情况不够连续。

话虽如此，但对我来说，尝试以某种方式在基因组中编码一种决策树并进行进化是有意义的。然而，从我的经验来看，用于游戏的人工智能中的遗传算法在用于“计算”某些特定行为的某些参数的最佳值，然后“进化”行为本身时效果最好。

Answer 2

抽象语法树(AST)等同于以领域特定语言表示的程序流。如果语言由可能的命令组成: up，left，down，right，则可能的AST是: up，left。遗传编程试图做的是进化AST，这意味着要找出许多不同的程序流来解决一个游戏。与其仅仅进化AST，更好的想法是进化语法。这意味着，要修改制定AST的领域特定语言。例如，通过添加额外的命令，如“gocenter”。新语言现在包含5种可能的动作: gocenter，up，left，down，right，并且可以测试出新的群体。为了系统地发展一种语法，需要通过交互来学习语法。这意味着，我们从一个空的语法开始，并仔细添加新的可能的操作命令。在文献中，这被描述为“语法归纳”和从人类交互中获取输入流并从头开始生成新语言的手段。有了这个语法，就有可能进化出可能的AST。

引用：“语法进化(GE)是一种基于语法的遗传编程形式，它通过上下文无关的语法指定可能的解决方案的语法”来源:佩雷斯，迭戈等人。“使用语法进化为mario ai竞赛进化行为树。”欧洲进化计算应用会议。施普林格，柏林，海德堡，2011。