代码之家 › 专栏 › 技术社区 › codymanix

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

turing-complete genetic-programming evolutionary-algorithm abstract-syntax-tree artificial-intelligence

1

codymanix · 技术社区 · 7 年前

我想开发一个基因程序,可以解决一般问题,比如在电脑游戏中生存。因为这是为了娱乐/教育,我不想使用现有的图书馆。

遗传程序由多达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常见的一些问题?

2 回复 | 直到 7 年前

1

3

Michal Bida 7 年前

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

话虽如此,我还是有理由尝试在基因组中编码一种形式的决策树,并对其进行进化。然而,根据我的经验,AI游戏中的遗传算法在用于“计算”某些特定行为的某些参数的最优值,然后“进化”行为本身时效果最好。

2

1

Manuel Rodriguez 7 年前

抽象语法树(AST)相当于用领域特定语言表示的程序流。如果语言由可能的命令组成:up、left、down、right,那么可能的AST是:up、up、up、left。遗传编程试图做的是进化AST,这意味着找出解决游戏的许多不同程序流。更好的方法不是只进化AST,而是进化语法。这意味着,要修改用于制定AST的领域特定语言。例如,通过添加一个附加命令,如gocenter。新语言现在包含5种可能的行为:gocenter、up、left、down、right,并且有可能测试出新的人群。为了系统地发展语法,需要通过互动学习语法。这意味着,我们从一个空语法开始,小心地添加新的可能的动作命令。在文献中,这被描述为语法归纳法,是指从人类互动中获取输入流并从头生成新语言。有了这种语法,就有可能发展出可能的AST。

语法进化(GE)是一种基于语法的遗传进化形式通过上下文无关语法来源:Perez,Diego等,“进化行为” 使用语法进化的马里奥ai竞赛树。” 斯普林格,柏林,海德堡,2011年。