“进化”一条贪吃蛇

尼克徐 发布于 2016年05月03日 | 更新于 2016年05月03日
无人欣赏。

“进化一条贪吃蛇”是我多年前写的程序,差点就要遗失掉了。这两天整理了一下,重新放在网上。

网址:Evolve a Greedy Snake

我是根据这篇论文 Application of Genetic Programming to the Snake Game 来写这个程序的,主要是参考它的思路。

由于是多年前写的程序,有些地方已经不符合现在的Java规范了,暂时没有做太多改动。

它是根据“遗传程序设计”的算法,在很基础的“语法模块”的基础上,从随机生成的“语法树”开始,通过杂交交叉变异进化若干代后,会自动生成贪吃蛇行动的“程序”,使得贪吃蛇越来越“聪明”,能够自动躲避障碍物,自动寻找食物。

当时研究“遗传程序设计”的动机,是希望能够找到办法,不写程序,而让程序按照需求自动产生。

这个目标虽难以实现,但至今给我很多启发。

以下是进化贪吃蛇时,采用的基础语法模块:

叶子节点集合:

Forward:贪吃蛇向前走一步 
Left:贪吃蛇向左走一步 
Right:贪吃蛇向右走一步 

函数节点集合:

ifDangerAhead:如果前方再走一步就会遇到危险,就执行第一个分支,否则执行第二个
ifDangerTwoAhead:如果前方再走两步就会遇到危险,就执行第一个分支,否则执行第二个 
ifDangerLeft:如果向右再走一步就会遇到危险,就执行第一个分支,否则执行第二个 
ifDangerRight:如果向右再走一步就会遇到危险,就执行第一个分支,否则执行第二个 
ifFoodAhead:如果前方有食物,就执行第一个分支,否则执行第二个 
ifFoodRight:如果右边有食物,就执行第一个分支,否则执行第二个 
ifFoodUp:如果上边有食物,就执行第一个分支,否则执行第二个 
ifMovingDown:如果贪吃蛇正在向下走,就执行第一个分支,否则执行第二个
ifMovingLeft:如果贪吃蛇正在向左走,就执行第一个分支,否则执行第二个 
ifMovingRight:如果贪吃蛇正在向右走,就执行第一个分支,否则执行第二个 
ifMovingUp:如果贪吃蛇正在向上走,就执行第一个分支,否则执行第二个 
progn2:先执行第一个分支,再执行第二个分支 

以下是用该算法“进化”出的一个程序(采用这个程序,贪吃蛇可以平均吃25个食物才死掉):

ifFoodRight
|-ifDangerRight
| |-ifDangerAhead
| | |-Left
| | |_ifDangerRight
| |   |-ifDangerRight
| |   | |-Forward
| |   | |_Left
| |   |_ifDangerRight
| |     |-ifMovingRight
| |     | |-ifFoodRight
| |     | | |-ifDangerRight
| |     | | | |-ifFoodRight
| |     | | | | |-Forward
| |     | | | | |_Right
| |     | | | |_ifDangerAhead
| |     | | |   |-ifFoodUp
| |     | | |   | |-Right
| |     | | |   | |_Right
| |     | | |   |_ifDangerAhead
| |     | | |     |-Forward
| |     | | |     |_Forward
| |     | | |_ifDangerRight
| |     | |   |-ifDangerLeft
| |     | |   | |-Left
| |     | |   | |_Left
| |     | |   |_ifMovingDown
| |     | |     |-Forward
| |     | |     |_Forward
| |     | |_ifDangerAhead
| |     |   |-ifFoodAhead
| |     |   | |-Left
| |     |   | |_Right
| |     |   |_ifDangerAhead
| |     |     |-Forward
| |     |     |_Forward
| |     |_progn2
| |       |-ifDangerTwoAhead
| |       | |-ifFoodAhead
| |       | | |-Left
| |       | | |_Forward
| |       | |_ifFoodUp
| |       |   |-Forward
| |       |   |_Forward
| |       |_progn2
| |         |-Right
| |         |_Forward
| |_ifMovingRight
|   |-ifMovingLeft
|   | |-Forward
|   | |_ifFoodUp
|   |   |-Left
|   |   |_Forward
|   |_Right
|_ifDangerRight
  |-ifMovingRight
  | |-Left
  | |_Forward
  |_ifDangerAhead
    |-Right
    |_Forward

alt text

暂无回复
登录 或者 注册
相关帖子