Archive

Posts Tagged ‘AI’

AI game player

November 21st, 2009 2 comments

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

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

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

Read more…

Categories: 程序/算法 Tags:

推箱子游戏的AI求解算法(二)

February 25th, 2008 2 comments

上篇。前面有4个小问题没有解决。具体的问题可以在上篇搜“子问题n”

  • 问题1

这实际上是一个寻路问题,最简单的用一个广度优先搜索就可以找到最短路径。从角色当前位置开始,每次向所有可能方向展开一层,如下图直到扩展到目标位置。根据节点的父子关系能反推出移动步骤。如下图

25_000807_pusher Read more…

Categories: 程序/算法 Tags: ,

推箱子游戏的AI求解算法(一)

February 24th, 2008 1 comment

只有算法,没有代码,希望不会编程的也能看懂(俺每次都这么说,但结果每次都很受伤……)

推箱子游戏大家都玩过吧,在封闭的关卡里分布着若干箱子,玩家控制主角把所有箱子推到指定位置即可过关。

以下是关于游戏规则的一些表述:

  • 关卡中的每一格要么是墙,要么是空地
  • 主角和箱子只能呆在空地上,不能穿墙
  • 主角不能穿过箱子
  • 箱子的目标位置在空地上
  • 箱子数量和目标位置数量相等(但每个箱子并不和唯一的目标位置一一对应)
  • 主角只能往前推动箱子,不能向后或向侧面拉箱子

这是个典型的递归/回溯(好像是这个字吧)搜索问题,栈数据结构的典型应用。和算法课上常常举的老鼠走迷宫的例子差不多,只是一些细节上稍稍复杂一点。

Read more…

Categories: 程序/算法 Tags: ,