公告

计蒜之道2016程序设计大赛 决赛题目

角色介绍

  1. 游戏只有 种角色:蒜头和破坏者。
  2. 每局比赛初始均有 只蒜头,你需要写出 AI 控制其中一只蒜头在地图上进行各种操作,而另一只蒜头将由其他同学写出的 AI 进行控制。
  3. 每局比赛初始均有 个破坏者。
  4. 保证任意两个角色不会在地图的同一位置中出现。
  5. 保证两个破坏者的角色对两位蒜头是绝对公平的。

地图介绍

  1. 地图为 列由格子组成的矩阵。每个格子为以下几种类型中的一种:
    • 墙:任何角色都无法移动到这种格子。
    • 地面:角色可以移动到这种格子上。地面上可能有 普通星 和 超级星。每个格子上至多会有一个星星(普通星或超级星)。
  2. 各种角色的初始位置都一定是地图中的地面而非墙。
  3. 保证地图对两只蒜头是绝对公平的。
  4. 我们用坐标 表示地图中第 列的格子,即下标从 开始。

移动规则

  1. 每个角色当前回合可以移动至上下左右四个相邻 地面格子 中的一个,或选择 不移动
  2. 蒜头和蒜头之间、破坏者和破坏者之间不会发生碰撞。
  3. 每个破坏者的移动具有一定的随机性,且会考虑破坏者到两只蒜头的 最短距离(从格子 移动到格子 的最少次数,被称为 的最短距离,注意这并不是曼哈顿距离,因为有障碍物)。若某个破坏者到蒜头 的最短距离为 ,到蒜头 的最短距离为 ,则该破坏者朝蒜头 的方向移动的概率为 ,朝蒜头 的方向移动的概率为 。注意,若有两个方向均为最短路方向,则等概率随机选择两个方向中的一个。若有不少于一只蒜头处于 强化状态 或已经从地图上消失,则破坏者将会等概率随机游走。
  4. 若你的 AI 没有移动到合法的下一步位置上,则会被系统认定为 自杀

回合介绍

  1. 每个回合分为两部分:蒜头移动和破坏者移动。首先进行蒜头移动阶段,之后进行破坏者移动阶段。
  2. 蒜头移动阶段,每只蒜头给出自己下一步移动的坐标,同时进行移动。
  3. 破坏者移动阶段,每个破坏者根据确定的移动策略,同时进行移动。

抢分规则

  1. 蒜头和星星重合时,星星会从地图上消失,同时蒜头增加该星星对应的分数。若同时有多只蒜头与同一星星重合,和单独相遇时增加的分数相同。
  2. 蒜头和超级星重合时,蒜头会变为 强化状态,并获得分数。若两只蒜头同时与超级星重合,则均变为 强化状态。且获得的分数与单独相遇时增加的分数相同,具体分数会在 积分规则 部分介绍。
    破坏者和处于普通状态的蒜头重合时,蒜头会从地图上消失,并且不会再进行任何操作,称为破坏者对蒜头的 抢分
  3. 破坏者和处于强化状态的蒜头重合时,破坏者会回到比赛初始时的位置。若多个强化状态的蒜头和同一破坏者重合,则和单独相遇时增加的分数相同,具体分数会在 积分规则 部分介绍。
  4. 处于普通状态的蒜头和处于强化状态的蒜头重合时,处于普通状态的蒜头将会从地图上消失,并且不再进行任何操作,称为蒜头对蒜头的 抢分
  5. 两个处于强化状态的蒜头重合时,不会发生任何事情。

优先级

以下行为按优先级从高到低排列,若两个行为同时发生,则先进行优先级更高的行为,再进行优先级更低的行为。

  • 强化状态的蒜头对普通状态的蒜头抢分
  • 强化状态的蒜头对破坏者抢分
  • 破坏者对普通状态的蒜头抢分
  • 蒜头收集星星

状态转换

  1. 处于普通状态的蒜头与超级星重合后,该蒜头会变为强化状态,持续 回合(从当前回合为第一个回合开始,到第 个回合结束时状态消失),即为该蒜头的 强化周期
  2. 处于强化状态的蒜头与超级星重合后,则将强化状态的剩余持续回合数刷新至
  3. 破坏者被蒜头吃掉后回到初始位置时,有持续至接下来蒜头或破坏者的一次移动完成的 强化期,即在强化期内,破坏者不会被处于强化状态的蒜头抢分。
  4. 回合数从当前回合开始计算,即当前回合为强化周期的倒数第 回合。

计分规则

  1. 每个回合结束时,所有未从地图上消失的蒜头同时扣 分。
  2. 蒜头与一个普通星重合,增加 分。
  3. 蒜头与一个超级星重合,增加 分。
  4. 蒜头被破坏者抢分,扣掉 分。
  5. 强化状态的蒜头与破坏者重合,增加 分。
  6. 蒜头 被蒜头 抢分,则蒜头 将自己分数 的一半下取整(即 )转移至蒜头
  7. 蒜头自杀,扣 分。

结束条件

满足以下条件之一时,游戏结束:

  • 两只蒜头均已从地图上消失;
  • 游戏已进行了 回合,其中 分别为地图的行数和列数;
  • 地图上的星星全部消失。

赛制介绍

比赛分为小组赛和淘汰赛两个阶段。其中小组赛分为 组,每组 人(有 人),采用单循环积分制,分组情况见下表。每组前两名晋级淘汰赛阶段。

组别 编号列表 第一名 第二名
A 1,16,17,32,33,48,49 A1 A2
B 2,15,18,31,34,47 B1 B2
C 3,14,19,30,35,46 C1 C2
D 4,13,20,29,36,45 D1 D2
E 5,12,21,28,37,44 E1 E2
F 6,11,22,27,38,43 F1 F2
G 7,10,23,26,39,42 G1 G2
H 8,9,24,25,40,41 H1 H2

小组赛阶段

  1. 小组赛阶段,两位选手将会在一张 的地图上进行游戏。
  2. 每场比赛中两只蒜头在游戏结束时分数不同,则分数高者积 分,分数低者积 分;若分数相同则均积 分。
  3. 组内排名按积分从高到低排序,若积分相同则比较参与的每场比赛的分数总和,总和越高排名越靠前。若仍并列,则按复赛排名取靠前者。

淘汰赛阶段

在淘汰赛阶段,两两选手之间对战将会使用 张地图,尺寸分别为 。仍旧采用积分制,每张地图胜者积 分,负者积 分,平则二人各积 分。积分高者进入下一轮;若两人积分相同,则比较每场比赛的分数总和,总和高者进入下一轮;若分数总和仍然相同,则按复赛排名取靠前者。

个小组的前两名捉对厮杀,对阵如下表:

选手 1 选手 2 胜者 败者
A1 H2 AH1W AH1L
A2 H1 AH2W AH2L
B1 G2 BG1W BG1L
B2 G1 BG2W BG2L
C1 F2 CF1W CF1L
C2 F1 CF2W CF2L
D1 E2 DE1W DE1L
D2 E1 DE2W DE2L

个胜者为胜者组,将继续选出其中的一等奖和二等奖。首先是胜者组四分之一决赛:

选手 1 选手 2 胜者
AH1W DE2W ADEH1W
AH2W DE1W ADEH2W
BG1W CF2W BGCF1W
BG2W CF1W BGCF2W

未晋级胜者组半决赛的四位选手均为三等奖。之后是胜者组半决赛(进入半决赛的均为一等奖或二等奖):

选手 1 选手 2 胜者
ADEH1W BGCF2W W1
ADEH2W BGCF1W W2

之后通过 W1 和 W2 的决赛选出一等奖。

然后将会从败者组的 位选手中选出一位胜者,作为这次比赛的三等奖最后一名。

败者组四分之一决赛:

选手 1 选手 2 胜者
AH1L DE2L R2W1
AH2L DE1L R2W2
BG1L CF2L R2W3
BG2L CF1L R2W4

败者组半决赛:

选手 1 选手 2 胜者
R2W1 R2W4 R3W1
R2W2 R2W3 R3W2

败者组决赛,R3W1 和 R3W2 的胜者为全场第九名,获得三等奖。

开发引导

在每位选手机器的 ~ 目录中有一个 game_xx 文件夹(若选手编号为 ,则目录名为 game_05),你接下来的开发都将在这个文件夹中进行。请注意,不要将该目录删除或更名,否则会造成不可预知的问题。

如果你误删了这个目录,请联系工作人员恢复到初始状态。但你已经编辑的代码将无法恢复。

目录概览

.
|— bin
| |— check_computer
| |— check_player
| |— computer
| |— judge
| `— player
|— code
| |— computer.hpp
| `— player.hpp
|— data
| `— map.txt
|— include
| `— playerbase.h
|— lib
| `— libplayer.a
|— log
|— Makefile
|— run.sh
`— src
|— check_computer.cpp
|— check_player.cpp
|— main_computer.cpp
`— main_player.cpp

你需要在 `code/player.hpp` 文件中实现你的 AI 算法。不要随意修改 `Makefile` 文件、其他的脚本和头文件,这些文件都将会在评测时被原始版本覆盖。

请将所有代码逻辑都实现在该文件内,我们评测时 只保留 `Player.hpp` 代码,其余代码将会被评测系统的代码替换。

对战时将会把双方的代码分别命名为 `computer.hpp` 和 `player.hpp`,先后顺序见 赛事介绍 部分。我们会确保先后手不会对对战结果产生影响。

地图格式

`data/map.txt` 为一个供你测试的 的地图。第一行为两个整数 ,分别表示矩阵的行数和列数。接下来一共 行,每行 个字符,表示地图每个格子的类型信息。每个格子的类型和对应的符号如下表:

类型 符号
#
带有普通星的地面 o(小写字母 o)
带有超级星的地面 O(大写字母 O)
地面 .

接下来四行,每行两个整数,分别表示第一个破坏者、第二个破坏者、你的对手控制的选手、你控制的选手的初始坐标 ,其中第一个整数为初始行数,第二个整数为初始列数,均从 开始编号。

PlayerBase 类

class PlayerBase { // 要实现的 Player 类的基类
public:
virtual void _recv(const int &read_fd) final;
virtual void _send(const int &write_fd, const char *sendbuf) final;
virtual void _work(const int &read_fd, const int &write_fd, int playid) final;
static void* _init_thread(void *arg);
static void* _walk_thread(void *arg);
virtual void _syscall_check(const string &data_path);

vector mat; // 地图数据
int row_cnt; // 地图行数
int col_cnt; // 地图列数
int ghost_posx[2]; // 两个破坏者的横坐标(行数)
int ghost_posy[2]; // 两个破坏者的纵坐标(列数)
int your_posx; // 你控制的蒜头的横坐标(行数)
int your_posy; // 你控制的蒜头的纵坐标(列数)
int opponent_posx; // 你对手控制的蒜头的横坐标(行数)
int opponent_posy; // 你对手控制的蒜头的纵坐标(列数)
int your_status; // 你控制的蒜头的状态,
// -1 代表蒜头已经从地图上消失,
// x(x>0) 代表蒜头处于强化状态,且将持续 x 回合,
// 0 代表蒜头处于普通状态。
int opponent_status; // 对手控制的蒜头状态,意义同上。
int your_score; // 你控制的蒜头分数。
int opponent_score; // 对手控制的蒜头分数。

virtual void init() = 0; // 游戏的初始化阶段,你可以根据地图信息进行一些预处理计算。你需要在 Player 类中实现这个方法。
virtual pair<int, int> walk() = 0; // 计算并返回每个回合你控制的蒜头移动到的新坐标。你需要在 Player 类中实现这个方法。
};

测试运行

执行 ./run.sh 脚本即可测试。可以在 logs 目录内查看游戏过程和最终分数。

可以执行 ./run.sh —visible 进行可视化测试。

时间限制

  1. 初始化的时间限制为 1s。
  2. 每回合移动的计算时间限制为 100ms。
  3. 若回合移动的计算超时,则系统会认为此次不移动。
  4. 我们会确保在最终评测时,如果选手的程序在机器上可以在时间限制内跑完结果,那么一定能在评测机上获得符合预期的结果。

空间限制

空间限制为 1G,于最终评测时进行限制。

函数调用限制

以下系统调用及函数禁止使用

  • 新建进程(调用 fork)
  • 禁止读写文件
  • 禁止调用 PlayerBase 类的 _recv、_send、_work、_init_thread、_walk_thread、_syscall_check 方法。

程序异常处理

若 AI 进程在某次 walk 计算时异常退出,则系统会认为此次不移动。

程序异常退出或程序超时会导致数据被恢复为上回合时的状态。

评论

你的邮箱地址并不会被公开显示 Required fields are marked *

你可以使用 HTML 标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>