分享一个AI编程游戏HaliteIII

朋友介绍给我一个很有兴趣的编程游戏，空余时间玩了一下，挺有意思。

这类编程游戏我想大家以前也有接触过，例如坦克大战，机器人大战，解谜闯关等。游戏的玩法大致是通过编程控制游戏中的人物或道具，以达到某个目的。

游戏的目标通常有：

Halite III机器人，它是Two Sigma举办的AI编程游戏竞赛，至今已经是第三届了，很多算法大佬都参与其中。它是一个资源管理游戏，支持多种编程语言编写算法，打排位赛。

广义上讲，HaliteIII是个游戏，在连续的二维地图上，有限的回合内，控制船队，寻路，并在船与船之间对战，抢夺资源等等。

Halite还支持直接在网站上编写算法（仅支持部分语言，Python, Java 和 C++），或者下载相应编程语言的脚手架编写，再上传（可以将本地生成的回放上传到网站上播放）。

基本游戏玩法

简单介绍一下基本玩法。玩家一开始只有一个船厂和一艘小船，你需要在二维地图上搜索并搜集更多的石盐（halite），每个回合每个小船可选择移动或者停留，回合结束后收集石盐最多的玩家胜出。

你需要在代码中编写好船队调度算法，控制船队，寻路，对战，抢夺资源。然后将代码上传到官网，系统会按一定的匹配规则安排排位赛，根据胜率和表现，统计出你机器人的排名和分数。

官方提供的API已经涵盖所有基本的内容（提供的多种编程语言的脚手架API保持一致）：

GAME。整个游戏的上下文，支撑整个游戏的架构，处理游戏初始化，生成地图、注册玩家。
PLAYER。玩家，一般一个地图只有2个或4个玩家。
SHIP。船，每艘船能携带1000的石盐，每个回合小船可移动或者停留，移动则消耗当前位置10%的石盐，停留将收集当前位置25%的石盐。消耗3000石盐从船厂生成一个新的船。所有石盐都需要输送到船厂或者仓库才会计入总收集石盐数量。船与船之间相撞会导致两船沉没，船上的所有石盐会掉落到当前位置。
SHIPYARD。船厂，每个玩家从这里开局，生产一艘全新的船需要消耗3000的石盐。
DROPOFF。姑且翻译为仓库吧，可由船转换而成，也是存放石盐的地方。
MAP。整个地图，大小分为32x32、40x40、48x48、56x56、64x64几种，地图上的资源也是按随机生成的。
MAP CELL。点个坐标位置上的详细信息，具体包括位置、石盐数量、这个位置上的船。
POSITION。当前位置x和y，采用的是屏幕坐标系，左上角为原点。
DIRECTION。方向：东南西北。

我并没有用到很高深的算法，基本上都是一些常规算法和细节的处理：

有限状态机是一种有用的模型，它可以进行对象行为建模，其作用主要是描述对象在它的生命周期内所经历的状态序列，以响应外部的各种事件。

其实也就是我们常用的状态控制。通过状态来控制船的行为，这样能让代码表达清晰，有利于封装逻辑，避免了代码结构混乱，难以测试和除错等问题。

我把状态划分为了“探索”，“返回”和“强制返回”，探索和返回就如字面意思，探索就是向外寻找资源，返回则将资源运回船厂或者仓库，强制返回在后面战术有详细说明。如果有时间的话，后续考虑会添加攻击，抢夺等状态。

在每个回合，船可选择移动或者停留，如果这一回合这艘船选择了停留，完全不影响下一回合的操作，因为它们是独立的。

每一步操作有(停留,向上,向下,向左,向右)五种选择，一步接着下一步，这其实就是一个树状结构的延伸，每个节点延伸出五个子节点，每一步意味着深度+1，于是我使用了深度搜索+评估函数，来猜测一条最佳的移动路线。

但目前仍然存在很多问题，例如搜索深度受限、障碍物该如何判断、该怎么剪枝和评估方式局限于一艘船内，无法考虑到全局。

虽然每个回合玩家们是保持一致的，就是说就是你的运算速度非常快，也得按照回合进行操作，但如果一个回合的运算时间超过2000毫米，即为超时，这时你就输掉了比赛。得益于Rust的高性能，暂时没出现超时的情况，但是还是不能设置太高的搜索深度。

当船运满后打算返回船厂的时候，要考虑移动最少步数和消耗最少的石盐，这其实就是一个单源单目的求最优解的问题。A*搜索算法就是一个很不错的选择，它结合了广度搜索和Djikstra搜索的特性，在进行启发式搜索提高效率的同时，可以保证找到一条最优路径。

A*的估算函数是： $f(n)=g(n)+h(n)$ 。

g(n)表示起点到任意顶点n的实际距离。

f(n)表示顶点n到目标顶点的估算距离。

其中两个比较重要的变量就是步数和资源数。正确调解两者的权重是决定最优解的关键。

最后几个回合的收场。当比赛临近结束的时候，只剩下几个回合的时间，船队再去收集资源已经来不及了，这时候可以把所有小船剩余的石盐强制运回船厂或者仓库，把剩余的价值压榨干净。这时候就会出现这样的现象，大家的船纷纷往船厂冲去，哪怕会在船厂被撞沉没。这种方法能在最后一刻多收集一些石盐，小小的差距可能会影响你的胜率。

堵门大法。这是一种狡猾的方式，大多数的人的策略是尽量减少碰撞的损失，于是有人利用这一点直接把敌方船厂堵住，使敌方无法返回，无法收集资源，查看回放。以一举三，有一艘船的堵门，就有四艘船的堵门，要应对这种战术，在路径搜索的判断要多多考虑。

关注官方twitter可获得更多信息和战术。

其实，这种游戏没有最优的玩法，就是一道开放题，只要不偏离题意，你可以自由地回答。