SamurAI Jockey 2018 ゲームルール

2019年1月8日
情報処理学会プログラミングコンテスト委員会

SamurAI Coding 2018-19 に用いるゲームのルールを述べる.

ゲームの概要

1回のレースは, ふたりのプレイヤがスタート位置から開始し, 障害物や水溜りがあるレースコース上でステップごとに加速・減速しながら, ゴールに到達する速さを競うゲームである. プレイヤの動きはステップごとにAIプログラム (以下単にAIと呼ぶ) が制御する.

ひとつのゲームは, 同じレースコースで両プレイヤのスタート位置を交換した2回のレースからなる. 両レースのゴールタイムの合計が短い方がゲームの勝者である. 合計タイムが同一である場合は, そのゲームは引き分けである.

レースコース

レースコースは2次元の枡目からなり, ゲーム毎に幅・長さや障害物・水溜りの数や位置が異なる. 以下ではコース幅を w, コース長を l とし, 各枡目の座標を (x, y) とする.

各ステップの開始時, 終了時においてプレイヤはいずれかの枡目にある. プレイヤはコース幅の外に出ることはできない. すなわちプレイヤのいる枡目の x 座標について 0 ≤ x < w が成り立つ. プレイヤが y ≥ l の枡目に到達した際には, そのプレイヤはゴールしたことになる. スタート位置より後ろの y < 0 の枡目にも到達できる.

レース開始時には, 両プレイヤは y 座標が 0　で, x 座標が相異なる枡目に位置する.

コース上の枡目の一部は障害あるいは水溜りである. 障害や水溜りの枡目は固定されており, レース中に変化することはない. 障害や水溜りの座標は 0 ≤ x< w, 0 ≤ y< l の範囲に限られる. つまり, コース幅の外, スタート位置より前, ゴールより後には存在しない. 障害や水溜りでない枡目は平坦である.

右図にレースコースの例を示す. 枡目のアイコンの意味は以下のとおりである.


平坦	障害	水溜り	プレイヤの位置

コースは大きな後戻りが必要ないように設定される. レース開始時の両プレイヤの位置から到達可能なコース内のどの枡目からも, 十分小さい速度で移動すれば, y 座標を一度もコースごとに定める視界距離以上減らすことなく, 障害やコース端にぶつからずに y座標がより大きい点に移動できる.

視界の制約

AI にはコースの各枡目が平坦, 障害, 水溜りのいずれであるかを通知されるが, 各ステップにおいてこの情報が与えられる枡目は, その y 座標が視界限界未満のもののみである. 視界限界は, 当該ステップまでにいずれかのプレイヤが達した y 座標の最大値に, コースごとに定める視界距離を加えたものである.

視界限界はいずれかが到達した y 座標の最大値によって決まるので, いずれかのプレイヤがより大きい y 座標まで進めば, それにしたがって視界も広がる. プレイヤが y 座標が小さい方向に逆行しても, 視界限界が小さくなることはない.

両プレイヤの視界限界は同一であり, したがって両プレイヤが得られるコースの情報も同一である.

上掲のレースコース例の図中で, コース画面の上半分程度の白く紗がかかっている枡目は, 初期状態での視界の外にあることを表している. この例では視界距離は10である.

レースの進行

各レースでは, ステップごとに AI にレースの状況についての情報を与え, それに対して AI は加減速の指示を応答する. その指示によってプレイヤは加減速され, レースの状況は更新される. このステップを両プレイヤが共にゴールまたは失格するまで繰り返す. ただし, レースコースごとに定める制限ステップ数に達してもゴールしないプレイヤがある場合, その時点でレースは終了し, ゴールに達していないプレイヤは失格となる.

考慮時間

AI が1レースで使える考慮時間の合計には, 制限を設ける. 考慮時間はゲーム管理プログラムがプレイヤに情報を送信し終わってから, プレイヤからの応答を受信し終わるまでの実時間である. 考慮時間の合計が制限値を超えたプレイヤは失格となる.

プレイヤの状態

プレイヤは各ステップ開始時の状態として位置する枡目の座標と速度を持つ. 位置と速度はいずれも2次元のベクトルで, 両要素は整数値である. 以下, ステップ開始時のプレイヤの位置を (x, y), 速度を (v_x, v_y) とする.

各ステップ開始時の状態は, 前ステップ終了時の状態と同じである. ただし, レース開始時の最初のステップでは, 位置がコースに指定された初期位置, 速度は (0, 0) である.

加減速と予定位置

AI はステップごとに速度を変更する加速度 (a_x, a_y)を指示する. a_x, a_y は各々 −1, 0, 1 のいずれかである. 座標 (x+v_x+a_x, y+v_y+a_y) の枡目をこのプレイヤのこのステップにおける予定位置と呼ぶ. 当該ステップでプレイヤが後述のコースアウトや衝突により停止するのでなければ, ステップ終了時のプレイヤの位置は予定位置になる. ステップ終了時のプレイヤの速度は, 予定位置が水溜りならば (0, 0), さもなくば (v_x+a_x, v_y+a_y) となる.

動線とコースアウト

ステップ開始時にプレイヤが位置する枡目の中心と, 終了時の予定位置の枡目の中心を両端とする線分を, このプレイヤの当該ステップでの動線と呼ぶ.

以下の場合, 当該プレイヤはコースアウトを生じているという.

予定位置がコース幅の外である, すなわち予定位置の x 座標が 0 ≤ x < w を満たさない.
動線が障害の枡と交差あるいは接する.

右図中の赤い動線 a, b, c, d はコースアウトであり, 青の動線 e, f はコースアウトではない. 動線 a, b は障害の枡目と交差しており, 動線 c は障害の枡目の角と接している. 動線 d は予定位置がコース幅の外である。

コースアウトしたプレイヤのステップ終了時の位置は開始時と変化しない. また, 速度は (0, 0) すなわち停止状態となる.

衝突と優先権

コースアウトがなく, 両プレイヤの動線が交差あるいは接触する場合, 衝突が生じたという.

衝突が生じた場合, 優先権を持つプレイヤはステップ終了時に予定位置に動くが, 優先権のないプレイヤの位置は元のままで, 速度は (0, 0) すなわち停止状態になる.

優先権を持つのは, ステップ開始時の位置の y 座標がより小さいプレイヤである. y 座標が同じ場合, x座標がより小さいプレイヤが優先権を持つ. ただし, 動線が相手プレイヤのステップ開始時の位置の枡目と交差あるいは接する場合は, 優先権は相手プレイヤに移る.

衝突した両方の動線が相手のステップ開始時の位置の枡目と交差あるいは接する場合, 両者とも優先権を失い, ステップ終了時の位置は元のまま, 速度は (0, 0) となる.

右図に掲げる具体例について説明する.

Case 1 では, 青い動線のプレイヤのステップ開始時の y 座標の方が小さいので, このプレイヤが優先権を得た.
Case 2 では, 赤い動線のプレイヤの動線は相手プレイヤのステップ開始時の位置の枡目と接しているので, 青い動線のプレイヤが優先権を得た.
Case 3 では, y 座標の小さいプレイヤの動線は相手プレイヤのステップ開始時の位置の枡目を通るが, 互いの動線は交差も接触もしていないので, そもそも衝突ではない.
Case 4 では衝突が生じており, 両者の動線は共に相手のステップ開始時の位置の枡目と交差あるいは接しているので, ステップ終了時のの位置は両者ともにステップ開始時のまま, 速度は (0, 0) となる.

水溜り

ステップ終了時の位置の枡目が水溜りならば, そのプレイヤの速度は (0, 0) になる. したがって, 水溜りの枡目 (x, y) から出発するステップでは (x±1, y±1) の範囲にしか動けないことになる.

ゴールとゴールタイム

プレイヤがステップ s の開始時に座標 (x, y) の枡目にあり, ステップ終了時に位置 (x', y') に達し, y' ≥ l であるとき, そのプレイヤはゴールしたものとされる. このときゴールタイムは s + (l − y) / (y' − y) となる.

ゴール時, 相手プレイヤがまだゴールも失格もしていなければ, ゴールしたプレイヤをコースから取り除いた状態でレースを継続する.

失格

プレイヤは以下のいずれかの場合, 当該プレイヤはそのレースについて失格となる.

制限ステップ数に達してもゴールできなかった.
考慮時間の合計が制限値を超えた
後述の規定に反する出力を行った

失格したステップまでに相手プレイヤがゴールも失格もしていなければ, 失格したプレイヤをコースから取り除いた状態でレースを継続する. 失格したプレイヤのゴールタイムは制限ステップ数の2倍とする.

なお, 失格は当該レースのみであり, 次以降のレースには通常通り参加できる.

AIの入出力

AI は初期化時にレース全体に関する情報を入力し, 初期化終了を示す応答を出力する. ステップごとにはレース状況の情報を入力し, 応答として加速度指示を出力する. ただし, ゴールあるいは失格したプレイヤのAIには, その後のステップではこのやりとりは行われない.

入力はただひとつの空白あるいは改行で区切った10進整数の並びである. 負の数にはマイナス符号を前置する. 初期化時の入力およびステップごとの入力の最後は必ず改行を置く.

AI の応答出力も空白あるいは改行で区切った10進整数の並びで, 負の数にはマイナス符号を前置する. 出力の最後には必ず改行を置く.

120000 100 16 20 10

初期化時の入力

初期化時の AI の入力は下記の項目がこの順に並ぶものである.

考慮時間: このレースで使える合計考慮時間をミリ秒単位の整数値として.
制限ステップ数: ゴールまでのステップ数の上限を整数値として.
コースサイズ: コースの幅 w および長さ l をふたつの整数値として.
視界距離: 視界を決める距離を整数値として.

各項目の直後には改行が置かれ, ひとつの項目 (1行) に含まれる複数の整数はひとつの空白で区切られる.

右図に初期化時の入力の例を示す。

0

初期化時の出力

AIは初期化が終了したら、そのことを整数 0 ひとつ及び改行で伝える.

3 118628 5 1 0 0 4 6 -1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 2 2 2 2 2 0 2 2 2 0 0 0 0 0 0 0 2 2 2 2 2 2 2 1 1 1 1 0 0 0 0 0 2 2 2 2 0 0 2 2 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 2 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 1 1 1 0 0 0 2 2 2 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 1 1 1 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

ステップごとの入力

ステップごとのAIの入力は下記の項目の整数がこの順に並ぶものである.

ステップ: 当該のステップの番号を整数値として. ステップ番号は 0 から始まる.
残り考慮時間: このレースで使える考慮時間の残りをミリ秒単位の整数値として.
自プレイヤの状態: 当該のAIが制御するプレイヤの位置のステップ開始時の位置の座標 (x, y) と速度 (v_x, v_y) を, この順に 4 整数値として.
相手プレイヤの状態: 相手プレイヤの位置のステップ開始時の位置の座標 (x, y) と速度 (v_x, v_y) を, この順に 4 整数値として. ただし, 相手プレイヤが既にゴールしたか失格した場合は, 0, l, 0, 0 の 4 整数になる.
コースの枡目の情報: 各枡目がどのような枡目であるかの情報で, w 個の整数値からなる行を l 行, 計 w × l 個の整数値として与えられる. 各行内の複数の整数値はひとつの空白で区切られる. 情報の順序は枡目のy 座標の昇順, 同じ y 座標の枡目の中では x 座標の昇順である.
情報の意味は以下の通りである.
- 0: 当該の枡目は障害でも水溜りでもない.
- 1: 当該の枡目は障害である.
- 2: 当該の枡目は水溜りである.
- −1: 当該の枡目は視界の外であるため不明.

コースの枡目の情報以外については, 項目の間と最後に改行が置かれ, ひとつの項目に複数の整数が含まれる場合, それらはひとつの空白で区切られる.

-1 1

ステップごとの出力

AI は当該ステップの加速度 (a_x, a_y) を空白ひとつで区切ったふたつの整数 a_x および a_y で指定する. 両者は −1, 0, 1 のいずれかでなければならない. これらの後に改行を出力する.

情報の記憶

ゲーム管理システムは, 各ステップについて出力を得た AI の動作を一時停止し, 次ステップの情報を与える際に動作を再開させる. このため, ステップとステップの間に計算を進めることはできないが, 変数値などの実行コンテキストは 1 レースの間保持し続けることができる.

AIはファイル出力やネットワークアクセスができない環境で動作し, ゲーム管理システムはレース毎にAIを初期状態から立ち上げ直す. このため, AIは複数のレースの間で情報を受け渡すことはできない.

以上


Case 1	Case 2

Case 3	Case 4