Home > 程序/算法 > AI game player

AI game player

November 21st, 2009 Leave a comment Go to comments

刚刚从水木上得知一个星际争霸AI挑战赛的消息,久违的竞争欲望又开始弥漫……实际上我早就觉得应该有人举办这样的比赛了。想起两年前在老blog上发过的一篇文章,现在转过来:

本文说的不是“游戏里的AI”,而是“用AI来玩游戏”

曾经有一段时间对人工智能,尤其是博弈类的人工智能非常痴迷,大概是“深蓝II”打败卡斯帕罗夫的时候吧,写了一个五子棋程序,棋力很差,因为当时思路有问题,只用了一层搜索,大部分的时间都耗费在局面估价函数上了。结果是唬一唬五子棋初学者还行,下过我自己基本没戏,更不用说打败全人类了J。其实五子棋是状态空间很小的一个博弈游戏,很容易搜索到相当的深度,甚至某些开局已经被证明是必胜或必败而在正式比赛中被禁用,这也是阻碍它成为一个大的竞技项目的原因吧,相信现在最好的五子棋程序应该能轻松击败人类了。

扯远了,有了这个爱好以后养成一个习惯,玩很多游戏的时候总会不禁想能不能写一个外挂来自动玩。在01年联众还比较流行的时候写了一个俄罗斯方块外挂,昵称叫“我是机器人”,练到了22级。而不作弊的人类高手基本上不会超过21级(我本人的水平只有15级左右),这个程序能到这个级别很重要的原因是它摆的比人要快,实际上速度是可调的,我做过一些试验,如果保持和对手基本相同的摆放速度,只能达到17级左右,对于更厉害的高手就只能以速度取胜了。因为俄罗斯方块游戏允许看到下一个将要出现的方块,所以基本上可以(也只可能)实现两层的状态搜索,于是经常会看见一些人类很难想出的匪夷所思的摆放方式,另外它还不会失误(除非网络出问题),我想这就是它比我高两级的原因吧,呵呵。当时还有不少高手听说我用外挂还不惜等级分的损失主动向我约战,对AI提出了一些修改意见,回想起来还挺感激的,可惜都不记得他们的id了。后来联众冒出了很多直接导致对方堆满而死的没技术含量的外挂,俺就再也不去了……

03年初的时候参加过一个贪吃蛇AI比赛,无疑是我的AI历程里最激动人心的一幕。规则是同时两个AI(蛇)参加比赛,抢果子吃,第一个果子1分,第二个果子2分……撞死扣50分(如果两蛇相撞就各扣50),死后随机在几个出生点之一重生,蛇的初始长度是2,吃了果子以后蛇的身体会长出果子分数相当的长度,达到预定的回合数时得分高的一方获胜。接口是游戏平台每回合(每帧)调用双方AI提供的特定函数,带有一个描述当前局面状态的参数,基本上是完全信息的:当前自己的位置数组(每个位置代表身体的一段),对方的位置数组,果子位置,当然还有关卡地图。AI的输出(函数返回值)只是三个方向之一:左转,直行或右转。函数执行时间有一个限制,超时就自动直行一步。显然,AI的目的有两个,一个是尽量多吃果子自己得分,另一个是尽量压缩对方的生存空间,把对方“憋死”而使对方扣分。这其中有一些有趣的辩证关系:吃果子越多身体越长,就越容易死;但是身体越短又越不可能把对方憋死。还有一些细节:自己身体长度是偶数时相对安全,因为只要能看见自己的尾巴,即使空间很小也可以循环追自己的尾巴来苟且偷生;另外根据地图的奇偶性(我们把双方蛇头永远不可能位于相邻格子的地图叫“奇性”地图),会有不同的策略;另外有一次在内部交流中发现一名选手开发出了“囚禁”AI,就是说在本来可以憋死对方的时候故意留出一条生路,让对方在自己指定的路线上前进(当然,只在特定的地图上有效),这样在比分领先的情况下可以一直拖到比赛结束!从那以后,大家都加入了自杀AI……后来又发现,其实有很多情况下都应该自杀:比如对方要吃超过50分的果子时应该毫不犹豫一头撞死;在对方吃到现有果子后可预见的回合之内自己必死,自杀(除非对方先死)。还有很多策略就不一一说了,实际上比赛之后我们都觉得这个项目还有很多潜力可挖,如果能办成周期性的比赛就好了。这一次我吸取了教训,在代码优化上下了不少功夫,搜索深度一般能达到7层以上(赛扬2的机器),在空间狭小短兵相接的时候甚至能达到接近20层。但是大的搜索深度带来了很多调试上的困难,估价函数的bug很容易被掩盖而难以察觉。值得一提的是由于比赛用机器比我的电脑快很多,导致比赛中的AI表现比练习时强了不少。

quake3源码公开的时候也曾经研究过bot接口,但想到实际上这种游戏类型的AI和人类比赛是不公平的,因为存在瞄准和射击命中率问题,如果AI愿意可以每枪都命中(仅限railgun这样忽略子弹飞行时间的枪),后来也没有深究。

博弈类游戏的AI可以认为是纯技术层面的,也就是说只要我的搜索深度足够就会更强,除非是象围棋这样状态空间极其变态的。另外还有一类游戏,有足够的对抗性,而且又能做到对AI和人类基本公平,比如即时战略。当然,还是有操作频率和准确度的差别,可以考虑采用一些技术手段削弱二者APM的差距。如果将来有条件来写这类游戏的AI的话,估计要花很多精力在“揣摩”人类心理上,应该比“纯技术”的AI更有挑战吧(想象一下,如果AI能战胜人类的星际冠军……)

Categories: 程序/算法 Tags:
  1. 小喵
    November 21st, 2009 at 18:17 | #1

    写得不错,保持下去啊,能更新的快点吗?

  2. CainYang
    November 28th, 2009 at 01:49 | #2

    头,来顶你一下
    呵呵

 

Spam Protection by WP-SpamFree