English

SamurAI Dig Here ゲームルール

情報処理学会プログラミングコンテスト委員会
2019/08/31 暫定版

この文書は情報処理学会主催の SamurAI Coding 2019-20 コンテストの対象である SamurAI Dig Here ゲームのルールを述べるものである.

ここに記述するルールは暫定版であり, 今後改定される可能性がある.

ゲームの概要

ゲームは 2 チーム間で競う零和不完全情報ゲーム, 競技参加者によるプログラムで制御する各 2 エージェントが競い合うものである. ゲームの目的は競技の場に隠されている埋蔵金をより多く掘り出すことである.

競技場

競技場は正方形で, 正方格子状に並ぶ小正方形 (セル) に分かれている. 競技場のサイズ, すなわち競技場の一辺に並ぶセルの数はゲームごとに異なる. 最小サイズは 6 である.

右図は正方形の競技場を斜め方向から俯瞰したものである.

ゲームエージェント

両チームにはそれぞれ 2 体のゲームエージェント, がある.

ゲームエージェントは競技者が提供するプログラムで制御する. 同じチームの犬と侍は同じプログラムが動くふたつのプロセスで制御し, 両プロセス間の通信はゲーム管理システムを介したものだけで, 他の通信手段はない.

ゲーム開始時にはエージェントは競技場内の別々のセル上にある. ゲームを通して複数のエージェントが同時に同じセル上に来ることはない.

ゲームの 1 ステップごとに, 侍エージェントはその 4 近傍セル, すなわち現在のセルと 4 辺のいずれかを共有するセルに動くことができる. 犬エージェントは 8 近傍セル, すなわち現在のセルと 4 隅のひとつかふたつを共有するセルに動くことができる. 現在のセルから動かないこともできる.

ふたつ以上のエージェントが同じセルに動くよう指示された場合, いずれも動くことはできず, 元の位置に留められる.

競技場内のセルにはがあることもあり, そこにはエージェントは動けない. 侍エージェントは動く代わりに, 4 近傍セルのひとつにある穴を埋めることができる. また, 侍は 4 近傍セルのひとつに新たな穴を掘ることもできる. ただし, ステップ開始時に既に他のエージェントがいたり, 掘ろうとする同じステップで他のエージェントが動いてきたセルには穴を掘れない.

エージェントの初期位置に穴はない.

埋蔵金

競技場内のセルには埋蔵金が埋められていることがある. 埋蔵金のあるセルに穴を掘ると, 埋蔵金を掘り出すことができる. 両チームの侍が同時に同じセルに穴を掘った場合は, 埋蔵金は両チームが半分ずつ獲得することになる. なお, 埋蔵金の量は常に偶数である.

犬は埋蔵金のあるセルの 8 近傍セルに来ると, 埋蔵金の位置と量を感知することができる. その情報は他のエージェントには伝えられない. 犬が埋蔵金のあるセルそのものに来ると, 犬は吠え, 埋蔵金の位置と量とは全エージェントの知るところとなる. 同じチームの侍だけでなく, 相手チームの侍や犬にも吠え声は聞こえてしまう.

エージェントの初期位置や穴のあるセルには埋蔵金がない.

ゲームのステップ

ゲームはステップ単位で進行する. ステップ開始にあたって, 全エージェントは同時にそのステップのプレイプランを立てる. 全エージェントのプランの有効性や衝突をチェックして, 各エージェントの行動を決定する. 決定した行動にしたがって競技の状態を更新する.

ステップ数があらかじめ決めた最大値に達するか, すべての埋蔵金が掘り尽くされるまで, このゲームステップを繰り返す.

プレイヤプログラム

プレイヤプロセス

競技参加者は自チームのふたつのエージェント, 侍と犬を制御するプレイヤプログラムを用意する.

ゲームの開始に当たってゲーム管理システムは, 両チームについてふたつのプレイヤプロセスを起動する. 各チームふたつのプレイヤプロセスは同じプログラムを実行するが, ひとつは侍を, ひとつは犬を制御する. 制御するエージェントは起動後にゲーム管理システムから通知される.

プレイヤプロセス同士の通信はゲーム管理システムを介したものだけで, 直接通信することはできない.

入出力

ステップの開始時にゲーム管理システムはゲーム状態情報を各プレイヤプロセスに送る. プレイヤプロセスはこれを受け取って, 担当するエージェントのプレイプランを返答しなければならない.

プレイヤプロセスはゲーム管理システムからのゲーム状態情報は標準入力から読み込む. これに対する返答のプレイプランは標準出力に書き出す.

プレイプランと行動

プレイプランは各プレイヤプログラムが送ったエージェントの動作案で, 行動はゲーム管理システムがそれらを照合して調整した結果, 実際に各エージェントがとる動作である.

プレイプランや行動は以下の意味を持つ整数値 m (-1 ≤ m ≤ 23) で表す.

x−1 x x+1
y−1 345
y 26
y+1 107
対象セル
−1
現在位置に留まり, 何もしない.
0, …, 7
近傍セルのいずれかに動く.
8, …, 15
近傍セルのいずれかに穴を掘る.
16, …, 23
近傍セルのいずれかの穴を埋める.
動いたり穴掘りや穴埋めをする対象セルの座標は d = m modulo 8 によって決まる. その意味は右図に示すとおりである.

侍の移動や穴掘り穴埋めの対象は 4 近傍セルのいずれかでなくてはならなず, 上述の d は偶数でなければならない. 侍のプレイプランが 22 以下の非負の偶数でも −1 でもなければ, それは不正である.

犬は穴掘りや穴埋めができない. 犬のプレイプランが −1 以上 7 以下の整数でなければ不正である.

不正なプレイプランは −1 と同様に扱う. 当該エージェントの行動が −1 になるだけでなく, 後述するゲーム状態情報にもプレイプラン −1 を指定したものとして扱う [1].

一方, セルの状態やエージェントの位置や動きのために, プレイプランが通りの動きができない場合, そのプレイプランは無効であるという.

競技場外の方向へ移動, 穴掘り, 穴埋めは無効である. 穴があるセルの穴掘り, 穴のないセルの穴埋めも無効である. ステップ開始時に他のエージェントがいるセルへの移動や穴掘り・穴埋めも無効である.

同一ステップでの同一セルへの複数のエージェントの移動は, すべてが無効になる. 同一ステップで他のエージェントが移動してくるセルの穴掘りも無効である. しかし, 複数のエージェントが同一セルに移動しようとして移動が無効になれば, 別のエージェントによるそのセルへの穴掘りは有効になる.

無効なプレイプランに対する行動も −1 になるが, 不正なプレイプランとは異なり, プレイプラン自体は後述するゲーム状態情報に反映される.

ゲーム状態情報

各ステップの開始時に, ゲーム管理システムからプレイヤプロセスにゲーム状態情報を送る. ゲーム状態情報は以下の各項目がこの順に並ぶものである.

ゲーム状態情報の要素はすべて整数である. 前述の箇条書の各項目の間は改行で区切り, 項目内の整数の間は空白で区切る. 最後の要素の後には改行が置かれる.

上述の項目でリストと記したものは, 先頭にリスト要素の個数 (整数値) が来る. リストが空なら 0 である. その後にリストの各要素の記述が続く. 各要素はひとつ以上の整数値である.

位置はセルのx-座標とy-座標のふたつ組で表す. 座標値は非負整数で, 競技場のサイズより小さい. 埋蔵金は整数値みっつで表す. 最初のふたつは埋蔵金のあるセルの座標で, みっつ目は埋蔵金の量である. 埋蔵金の量は必ず非負の偶数である.

3// エージェントの番号
10// 競技場のサイズ
1// ステップ番号
100// 最大ステップ番号
6 5 1 7 3 7 0 8 1 6 0 5 2 // 穴のあるセルの位置のリスト
1 6 6 6// 公知の埋蔵金
1 2 7 8// 感知した埋蔵金
9 6 2 4 5 3 1 6// エージェントの位置
0 0 7 7// 直前ステップでのプレイプラン
0 0 7 7// 直前ステップでの行動
0 0// スコア
50// 残る埋蔵金
299941// 残る考慮時間

ゲーム状態情報の例を右図に示す. "//" から以降はここでの説明のためのもので, 実際にプレイヤプロセスには送られない.

プレイプラン

プレイヤプログラムはゲーム状態情報を読んだら, それに応じて対応するエージェントのプレイプランを出力する. プレイプランは整数値ひとつで, その意味は上述のとおりである. プレイプランの後には改行がなくてはならない.

考慮時間制限

プレイヤプロセスの考慮時間には制限が設けられる. 考慮時間とはゲーム管理システムがプレイヤプロセスにゲーム状態情報を送ってから, その返答であるプレイプランを受け取るまでの時間のことである. これは実際の経過時間であって CPU 時間ではないことに注意. 各ステップの考慮時間は累積され, その総計に対して制限が課せられる.

考慮時間制限はプレイヤプロセスごとに設ける. 同じチームの侍と犬の考慮時間は別々に累積される.

考慮時間制限を越えたプレイヤプロセスは, その後の全ステップにおいて −1 (その場に留まること) をプレイプランとして選択したものとみなされる.

考慮時間制限の値はゲームごとに定める.

試合

2 チームの間の試合は, 同じ初期状態でエージェントの配置だけを交換した 2 ゲームで競う. 試合の勝敗は 2 ゲームを通じて掘り出した埋蔵金の総量で判定する.