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步内是否有解，如果没解，那这步就别走了。