microRTS 是一个精简版的 Real-Time Strategy 游戏,我这学期的算法课程的大作业就是完成一个 AI。我会把期间遇到的所有问题、想法与进展记录下来。

开发环境 🏠

Mac 10.15.1

Ubuntu 18.04 LTS

Intellij IDEA

openjdk 13

项目简介 🌟

microRTS 是如星际、魔兽这样大型 RTS 游戏的一个精简版,所以很多操作都有所省略。环境也由很多复杂的地形精简到了现在的状态,游戏中的单位有:base、barracks、resources、worker、light、heavy 和 ranged。最终游戏的胜利是消灭一方玩家所有的单位。许多像维修建筑、出售建筑等操作都被省略了。

单位介绍

resouces

这是玩家所要进行采集的资源,worker 通过向 resources 采集资源后向 base 运回使得玩家的资源数量增加。

base

玩家生产 worker 的地方,采集到的资源也需要运回这里才算真正地采集结束。血量为 10,建造代价为 10 。在游戏中的图形化界面中可以显示当前玩家的资源数量,但是摧毁 base,资源仍旧存在。

barracks

这里是生产更为高级的兵种的单位,在较大的地图中要尽快建造出兵营来增加自己的攻击力。血量为 4,建造代价为 5 。

worker

这是游戏中最为基础的单位,其可以采集资源,建造 base 和 barracks,也可以进攻敌人。血量为 1, 建造代价为 1,攻击范围为 1,生产时间为 50,攻击力为 1,移动时间为 10,攻击时间为 5,采集时间为 20,运回资源时间为 10 。

light

较高级的兵种。血量为 4,建造代价为 2,攻击范围为 1,生产时间为 80,移动时间为 8,攻击时间为 5,攻击力为 2 。

heavy

最重型的高级兵种。血量为 4,建造代价为 2,攻击范围为 1,生产时间为 120,移动时间为 12,攻击时间为 5,攻击力为 4 。

ranged

远程攻击的高级兵种。血量为 1,生产代价为 2,攻击范围为 3,生产时间为 100,移动时间为 10,攻击时间为 5,攻击力为 1 。

战略 📖

硬编码算法

自动采矿算法

硬编码,在自己基地附近的区域内进行采矿,合适的采矿的 worker 暂定为$ n(resources)+1 $,附近的矿定义为距离 base 不超过 5 个单位距离。采矿的 worker 为当前无任务的 worker 和已在采矿队列中的 worker 中选取,如果该 worker 在采矿中会自动

编写固定脚本

较为简单但是较为死板,需要为每种情况都编写对应的脚本,同时需要较高的 domain knowledge。

有限状态机

对于简单的 AI 来说足够好了,但是无法处理复杂的任务,很难保证一直处于理想的状态中。

混合其他的有限状态机,可以一定成都上地扩展可用性。

决策树

相比于有限状态机,它提供了一个更加简单的决策判断,但是考虑情况过多就会变得代码特别臃肿,条件也会越来越复杂。

有限状态机与决策树相结合

决策论算法

有更加高级的蒙特卡洛搜索树算法等,没有过多了解,略。

战术 🏹

寻路算法

AI 需要提供给主程序的,是当前时间应该行动的一系列 actions,但是我们在程序中需要设计的是一系列更为抽象的行为,例如 attckharvestbuildtrain 等。对于这些更为抽象的行为,我们需要提供一个寻路算法,供其计算出当前应该采取的行为。目前游戏中内置的寻路算法有 BFS、FloodFill、Greedy 寻路算法。

损失函数

如何决定一个有效的损失函数能够更好更正确地决定下一步的动作。这里损失函数的具体定义由主观的游戏经验所决定,所以存在不合理性,一开始我希望通过随机梯度下降等算法对于该函数进行调整,但是 合适的训练样本极难获取,因为我们无法判断在对局的过程之中哪方处于优势,如果由人工标定仍旧引入了主观因素,那么意义不大。

初版决策函数(2019.11.14)

我决定使用别人已有的 AI 进行 action 的提供,同时根据下面的决策函数决定出下一步应该执行的最佳操作。目前仍旧存在的问题是仍旧无法在小地图中打败 workRush,根据多次观察,是由于兵营位置选择不恰当,这样的话,本来快要建造好的兵营就被赶来的 worker 打掉了,所以说要有 defense 机制来对于进攻的兵力有所防备。

$$ Action(gs) = \argmax(\sum_{i=1}^n dis(myActiveUnit_i, enemyBaseBarrack) - \sum_{j=1}^m dis(enemyActiveUnit_j, myBaseBarrack) + \sum_{k=1}^n hitNum(myUnit_k), -\sum_{l=1}^m hitNum(enemyUnit_l)) $$