Jidi Snakes 3V3

发表于 2021-08-21 更新于 2022-06-18 阅读次数：

及第平台贪吃蛇3V3环境启发式算法, 可以迁移至1V1, 2P, 5P等多个环境

贪吃蛇(Snake)起源于1976年的街机游戏Blockade. 在此游戏中, 玩家控制一条蛇, 一边吃豆子, 一边避免碰撞自身和障碍物. 1996年, Next Generation将贪食蛇类游戏列入"史上100款最佳游戏".

随着多智能体强化学习的发展, 国内外涌现了众多多智能体游戏环境, 多人贪吃蛇游戏便是其一. 此类游戏虽然规则简单, 但涉及到多条蛇之间的合作或竞争, 使得策略复杂.

本文介绍了一种适用于及第平台贪吃蛇1V1, 3V3, 2P, 5P四个环境的启发式算法.

环境介绍

这里仅介绍及第贪吃蛇3V3的环境.

本游戏共有两方，每个玩家分别在n*m的网格中操纵三条蛇。n为垂直高度，m为水平宽度。

蛇是一系列坐标构成的有限不重复有顺序的序列，序列中相邻坐标均相邻，即两坐标的x轴坐标或y轴坐标相同，序列中第一个坐标代表蛇头。玩家只能通过控制蛇头的朝向(上、下、左和右)来控制蛇。

蛇以恒定的速度前进(前进即为序列头插入蛇头指向方向下一格坐标，并删除序列末尾坐标)。蛇的初始位置为网格中的随机位置，初始长度为3格。每吃掉一个豆子长度加1。在游戏中豆子数量维持一个常数（5）不变，即被吃掉则重新随机生成等数量的豆子。

蛇头在自己蛇的身体(即序列重复)、其他蛇的身体(即与其他序列有相同坐标)均判定为死亡。当输入了非法方向时(如正在向左前进，无法选择向右)，随机选择一个合法方向。与传统贪吃蛇不同的是，蛇头超过边界时可以穿越到对称位置，不算做死亡。蛇死亡时可以按照初始化的设置重生。

到达指定步数时游戏结束。游戏结束后，蛇身长度总和大的一方获胜。

观测为一个字典，字典的键为1至7的正整数和"board_width"、"board_height"、"last_direction"、"controlled_snake_index"。其中1表示豆子，2至7表示蛇；字典的中的值为一个以[h,w]坐标为元素的列表，表示豆子的位置或蛇身的位置，其中h表示距左上角原点的垂直距离，w表示距原点的水平宽度；在2至7对应的值当中，列表元素从左至右表示对应蛇的蛇头至蛇尾的位置；"board_width"的值为地图的宽，"board_height" 的值为地图的高，"last_direction"的值为上一步各个蛇的方向，"controlled_snake_index"的值为控制蛇的序号。

动作空间为长度为n_action_dim的列表，其中n_action_dim=1，每个元素为Gym当中的Discrete类（ Discrete Link），如[Discrete(4)]。

算法强度

在及第平台贪吃蛇1V1, 3V3, 2P, 5P四个环境中取得前两名 (截至2021年8月21日).

RLChina2021智能体竞赛四强 (八强中唯一的启发式算法)

RLChina智能体挑战赛 - 辛丑年秋赛季第二名

算法概览

本算法会依次判断给定条件是否满足, 从而做出下列五个动作之一:

defensive move: 衔尾
claim move: 以最短路径吃豆子
safe move: 最大化生存空间
attack move: 侵略性的动作
random move: 没有操作空间, 随机动作

本文主要介绍claim move和safe move是如何确定的.

领土矩阵 (Territory Matrix)

领土矩阵反映了每条蛇能先于其他任意一条蛇到达的区域. 本节首先描述该矩阵的计算方式, 然后给出一种编码方式.

注意在贪吃蛇3V3环境中, 一方控制深绿, 浅绿, 青, 一方控制红, 粉, 褐.

计算方式

计算领土矩阵的一个例子如下图所示. 简单说明如下:

领土的申明由两个循环构成:
1. 外循环
  - 对每条蛇, 维护一个待探列表, 外循环直至该列表为空才结束, 比如在循环开始时, 该列表即为六条蛇的蛇头.
  - 每次循环开始首先去掉蛇尾 (若蛇尾存在的话), 这样做的目的是为了使得领土的计算更加精确, 否则将有很多蛇身未被申明.
2. 内循环
  - 即每条蛇按顺序申明领土, 比如下面的例子的顺序为:深绿→浅绿→青→红→粉→褐.
同一层外循环中, 短的蛇覆盖长的蛇的领土, 这可以保证短的蛇做更多攻击性的动作, 而长的蛇趋向防守.
同一层外循环中, 若蛇长度相同, 则将领土视为有争议的区域, 均放入待探列表, 并存储信息放入争议列表.
同一层外循环中, 若短的蛇可以申明一块争议区域, 且产生争议的两条蛇的长度都比其大, 则短的蛇直接申明该点, 并将该点移出争议列表.

下面做更加细节的逐图分析, 首先给出该例子的原图如下:

Step 1

首先去除尾部.

然后遍历每条蛇的待探列表, 将已探测点移出待探列表, 将即将探测的点 (下图共\(3\times5+2=17\)个) 加入待探列表.

Step 2

探索完深绿和浅绿后, 青与深绿在两个点产生了争议.

接着探索完红和粉后, 褐由于长度比深绿和青都短, 直接覆盖了青所占的两块领土, 以及深绿和青的一块争议领土.

Step 4

探索完深绿和浅绿后, 青由于长度比浅绿长, 且无处申明领地, 故在此步后待探列表变为空集, 从此再也不能进行领土申明.

Step 5

这一步深绿左下部分没有在待探列表中的点 (可以观察到这一步待探列表中的点回溯至其对应蛇的蛇头的距离 (若不做特殊说明, 下文简记为距离) 均为\(4\), 后文会将其定义为该点的state), 因此不能沿着左下进行探索. 之后会发现深绿进入了褐的包围圈.

最终结果

下图呈现了领土矩阵的最终计算结果, 做几点说明:

每个方格中的数字表示自该点回溯至其对应蛇的蛇头所需要的步数, 定义为该蛇的state.
非黑色的网格线代表蛇的初始蛇身, 按颜色一一对应 (共用边框使用了混合色).
每条蛇的蛇头所处位置均被申明, 按照深绿→浅绿→青→红→粉→褐的被衔尾顺序依次为:
1. 褐色→深绿: 褐衔深绿尾
2. 浅绿→浅绿: 浅绿自衔尾
3. 浅绿→青: 浅绿衔青尾
4. 浅绿→红: 浅绿衔红尾
5. 粉→粉: 粉自衔尾
6. 浅绿→褐色: 浅绿衔褐尾
每条蛇的所申明的领土数统计如下表: (共用领土按比例均分)

深绿 浅绿 青 红 粉 褐

申明领土数 12.5 69 7.5 14 59 38
每条蛇所申明领土上的豆子数统计如下表: (共用领土按比例均分)

深绿 浅绿 青 红 粉 褐

申明豆子数 1 0 0 0 1 3

	`深绿`	`浅绿`	`青`	`红`	`粉`	`褐`
申明领土数	12.5	69	7.5	14	59	38

	`深绿`	`浅绿`	`青`	`红`	`粉`	`褐`
申明豆子数	1	0	0	0	1	3

编码方式

编码方式如下, 做几点说明:

上图的矩阵只有state信息, 但不能表达其属于哪条蛇
下表中数值为正的编码很好理解, 其商代表该点与蛇头的距离, 余数代表该点所属蛇的编号
下表中数值为负的编码, \(-6\)表示空白格, 其余被\(6\)整除的数都留空未用; 剩余的数, 其商代表该点与蛇头的距离的相反数, 余数代表争议蛇的数量\(-1\), 该点产生争议的蛇的具体信息另计入一个字典中, 待需要时, 通过领土矩阵的编码进行索引.
该编码方式可以扩展至有限多条蛇的对抗, 这也是该算法能直接应用于多个环境的原因.

	余0	余1	余2	余3	余4	余5
商-2	-12: 未用	-11: 两条蛇争议 (state=2)	-10: 三条蛇争议 (state=2)	-9: 四条蛇争议 (state=2)	-8: 五条蛇争议 (state=2)	-7: 六条蛇争议 (state=2)
商-1	-6: 空白格	-5: 两条蛇争议 (state=1)	-4: 三条蛇争议 (state=1)	-3: 四条蛇争议 (state=1)	-2: 五条蛇争议 (state=1)	-1: 六条蛇争议 (state=1)
商0	0: `深绿`蛇身	1: `浅绿`蛇身	2: `青`蛇身	3: `红`蛇身	4: `粉`蛇身	5: `褐`蛇身
商1	6: `深绿`领土 (state=1)	7: `浅绿`领土 (state=1)	8: `青`领土 (state=1)	9: `红`领土 (state=1)	10: `粉`领土 (state=1)	11: `褐`领土 (state=1)
商2	12: `深绿`领土 (state=2)	13: `浅绿`领土 (state=2)	14: `青`领土 (state=2)	15: `红`领土 (state=2)	16: `粉`领土 (state=2)	17: `褐`领土 (state=2)

指派表 (Assignment Table)

指派表用于确定可能存在的claim move.

按从上到下, 从右到左的顺序依次给五颗豆标号.以豆子编号为行, 蛇编号为列, 创建一个\(5\times6\)的表格, 记录下蛇与其申明豆子的距离并填写, 得到如下表格.

接下来对这五个元素使用双索引排序法, 递归地给出一种指派: 即每次按此排序选取一个元素后划去该元素所在行和列, 形成一个子矩阵, 然后对子矩阵重复上述操作.

这两种索引方式具体为:

数值大小 (即state大小), 按递增顺序, 上表中最优先的数值为\(2\).
所在行列值为空的个数和, 按递减顺序, (注意一旦选择了一种指派, 则矩阵会删去所选元素所在行列, 因此该指标是动态变化的), 此时最优先的元素是\(3,4\), 因为其所在行列上的值除自身外均为空, 故个数和为\(9\).

这两种索引的优先级可以调整, 即产生了两种排序方式, 依次具体说明如下: (若优先级相同则随机选择一个)