Snake Challenge算法思路

Snake Challenge是GuruDigger推出的一个活动。游戏脱胎于经典的贪吃蛇,双方用程序控制snake,在规定步数内吃到最长的为获胜方。该平台的SDK以及范例放在BitBucket上,部署好的比赛平台在 http://pythonvsruby.org 。比赛平台上4四个房间,可以任意选择一个房间开始比赛(访问速度好像很悲催,我的snake一直掉线)。

我的AI程序在:https://bitbucket.org/vicalloy/snake-challenge 对应的目录为:snake-challenge/examples/vicalloy

下面简单的介绍一下主要的算法思路:

地图的表示

简单的说就是将地图上的障碍物实物等标记出来,这是整个程序中最简单的一部分。地图可以简单的用二维数组(python中实际为list)表示,数组中的值代表地图上的物品,如 0:BLANK 10:EGG 20:WALL。

查找目标食物

选择哪个食物

服务端会返回所有的egg和gem信息,要找到食物是很容易的,真正的问题是具体要选那个。

我们当然希望去吃最近的食物,或扎堆的食物(虽然远点,不过食物多),只是在真实环境下问题会非常多。如何才是最近,有些食物虽然看起来近,但算上绕过障碍物的距离就不近了。扎堆的食物看起来不错,问题是你没等你到那里,食物已经被别人给吃光了。如果想做到最优,那绝对不是一件容易的事。

既然不管怎么做都很难做到最优,倒不如简单些,直接选择忽略障碍物后距离最近的食物。

面对顺道的食物该怎么办

snake challenge中食物是会慢慢增加的,可能走到一半,你发现身边有个食物离得更近。这时候是否应优先去吃更近的?首先,我们说的更近都是忽略障碍物的情况下,虽然看上去近,但不一定真的近。其次原先的食物,虽然看上去更远,但不少路程已经探索过了,绕过新食物的路径是完全没有探索过的,更换目标也并不见得更好。路边的野花还是等下来采吧。

绝对不能吃的食物

有些食物刚好放在了陷阱里,吃完后无论如何都逃不出去。根据上面一条不吃野食的规定,你会绕着食物团团转,死不了也活不了。

我们加个步数的限制,如果食物距离5步以内,但你已经走了15步都没能将食物吃到,这时候还是换个目标吧。

寻路算法

寻路,就是如何才能最快的到达目的地。寻路算法中听的最多的就是A*算法。A*算法的核心思想是:

  1. 查看下一步能去的位置(去除障碍物等)
  2. 从下一位置中剔除已经走过的位置
  3. 算出所有:下一位置到起始位置的距离+下一位置到起始位置到目的地位置的具体
  4. 选择总距离最短的位置
  5. 将当前位置加入已经走过的位置列表
  6. 没看明白的自行google

对我们的贪吃蛇来说,可以将A*算法做到非常的简化。首先snake无法走斜线,无法后退,snake能去的位置只有三个,而且离当前位置的距离都为1。因此,我们只需要计算3个位置中那个位置离食物最近即可。在计算到食物的距离时,延续查找最近食物的方法,忽略障碍物。

除障碍物外,地图上还会有些危险物品,敌方的食物或是已经走路。

地方的食物,吃过后会变短,但还不至于挂掉。已经走过的路,虽然尽量不要走,但无路可走的时候,反倒也是个选择。

我们根据地图属性,给位置打分,然后选择得分最高的位置。

空(远离目标): -9

空(靠近目标):9

空(不变):0

敌方食物:-20

已经走过的路: -40

墙:-999

蛇:-888

陷阱

地图上总会有些小陷阱,进去后发现是个死胡同,怎么都出不来。

做个递归,查看N步内是否有解,如果没解,那这步就别走了。