forked from takashi-chikayama/Software-for-IPSJ-International-AI-Programming-Contest-SamurAI-Coding-2019-2020
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathrules-jp.html
429 lines (416 loc) · 17.4 KB
/
rules-jp.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link rel="stylesheet" href="samuraidocs.css" >
<title>SamurAI Dig Here ゲームルール</title>
</head>
<body>
<span style="float:left">
<a href="rules.html" target="_blank">English</a>
</span>
<h1>SamurAI Dig Here ゲームルール</h1>
<center>
<p>
情報処理学会プログラミングコンテスト委員会<br>
2019/08/31 暫定版
</p>
<p>
この文書は情報処理学会主催の <em>SamurAI Coding 2019-20</em>
コンテストの対象である <em>SamurAI Dig Here</em>
ゲームのルールを述べるものである.
</p>
<p>
ここに記述するルールは暫定版であり, 今後改定される可能性がある.
</p>
</center>
<h2>ゲームの概要</h2>
<p>
ゲームは 2 チーム間で競う零和不完全情報ゲーム,
競技参加者によるプログラムで制御する各 2 エージェントが競い合うものである.
ゲームの目的は競技の場に隠されている埋蔵金をより多く掘り出すことである.
</p>
<img src="screenShots/small-field.png" width="50%" class="figure">
<h3>競技場</h3>
<p>
競技場は正方形で,
正方格子状に並ぶ小正方形 (<em>セル</em>) に分かれている.
競技場のサイズ, すなわち競技場の一辺に並ぶセルの数はゲームごとに異なる.
最小サイズは 6 である.
</p>
<p>
右図は正方形の競技場を斜め方向から俯瞰したものである.
</p>
<h3>ゲームエージェント</h3>
<p>
両チームにはそれぞれ 2 体のゲームエージェント,
<em>侍</em>と<em>犬</em>がある.
</p>
<p>
ゲームエージェントは競技者が提供するプログラムで制御する.
同じチームの犬と侍は同じプログラムが動くふたつのプロセスで制御し,
両プロセス間の通信はゲーム管理システムを介したものだけで,
他の通信手段はない.
</p>
<p>
ゲーム開始時にはエージェントは競技場内の別々のセル上にある.
ゲームを通して複数のエージェントが同時に同じセル上に来ることはない.
</p>
<p>
ゲームの 1 ステップごとに, 侍エージェントはその 4 近傍セル,
すなわち現在のセルと 4 辺のいずれかを共有するセルに動くことができる.
犬エージェントは 8 近傍セル,
すなわち現在のセルと 4 隅のひとつかふたつを共有するセルに動くことができる.
現在のセルから動かないこともできる.
</p>
<p>
ふたつ以上のエージェントが同じセルに動くよう指示された場合,
いずれも動くことはできず, 元の位置に留められる.
</p>
<h3>穴</h3>
<p>
競技場内のセルには<em>穴</em>があることもあり,
そこにはエージェントは動けない.
侍エージェントは動く代わりに, 4 近傍セルのひとつにある穴を埋めることができる.
また, 侍は 4 近傍セルのひとつに新たな穴を掘ることもできる.
ただし,
ステップ開始時に既に他のエージェントがいたり,
掘ろうとする同じステップで他のエージェントが動いてきたセルには穴を掘れない.
</p>
<p>
エージェントの初期位置に穴はない.
</p>
<h3>埋蔵金</h3>
<p>
競技場内のセルには<em>埋蔵金</em>が埋められていることがある.
埋蔵金のあるセルに穴を掘ると, 埋蔵金を掘り出すことができる.
両チームの侍が同時に同じセルに穴を掘った場合は,
埋蔵金は両チームが半分ずつ獲得することになる.
なお, 埋蔵金の量は常に偶数である.
</p>
<p>
犬は埋蔵金のあるセルの 8 近傍セルに来ると,
埋蔵金の位置と量を感知することができる.
その情報は他のエージェントには伝えられない.
犬が埋蔵金のあるセルそのものに来ると, 犬は吠え,
埋蔵金の位置と量とは全エージェントの知るところとなる.
同じチームの侍だけでなく, 相手チームの侍や犬にも吠え声は聞こえてしまう.
</p>
<p>
エージェントの初期位置や穴のあるセルには埋蔵金がない.
</p>
<h3>ゲームのステップ</h3>
<p>
ゲームはステップ単位で進行する.
ステップ開始にあたって,
全エージェントは同時にそのステップの<em>プレイプラン</em>を立てる.
全エージェントのプランの有効性や衝突をチェックして,
各エージェントの<em>行動</em>を決定する.
決定した行動にしたがって競技の状態を更新する.
</p>
<p>
ステップ数があらかじめ決めた最大値に達するか,
すべての埋蔵金が掘り尽くされるまで,
このゲームステップを繰り返す.
</p>
<h2>プレイヤプログラム</h2>
<h3>プレイヤプロセス</h3>
<p>
競技参加者は自チームのふたつのエージェント,
侍と犬を制御する<em>プレイヤプログラム</em>を用意する.
</p>
<p>
ゲームの開始に当たってゲーム管理システムは,
両チームについてふたつの<em>プレイヤプロセス</em>を起動する.
各チームふたつのプレイヤプロセスは同じプログラムを実行するが,
ひとつは侍を, ひとつは犬を制御する.
制御するエージェントは起動後にゲーム管理システムから通知される.
</p>
<p>
プレイヤプロセス同士の通信はゲーム管理システムを介したものだけで,
直接通信することはできない.
</p>
<h3>入出力</h3>
<p>
ステップの開始時にゲーム管理システムはゲーム状態情報を各プレイヤプロセスに送る.
プレイヤプロセスはこれを受け取って,
担当するエージェントのプレイプランを返答しなければならない.
</p>
<p>
プレイヤプロセスはゲーム管理システムからのゲーム状態情報は標準入力から読み込む.
これに対する返答のプレイプランは標準出力に書き出す.
</p>
<h3>プレイプランと行動</h3>
<p>
<em>プレイプラン</em>は各プレイヤプログラムが送ったエージェントの動作案で,
<em>行動</em>はゲーム管理システムがそれらを照合して調整した結果,
実際に各エージェントがとる動作である.
</p>
<p>
プレイプランや行動は以下の意味を持つ整数値 <var>m</var> (-1
≤ <var>m</var> ≤ 23) で表す.
<div class="figure">
<table class="bordered">
<tr>
<th></th>
<th><var>x</var>−1</th>
<th><var>x</var></th>
<th><var>x</var>+1</th>
</tr>
<tr>
<th><var>y</var>−1</th>
<td>3</td><td>4</td><td>5</td>
</tr>
<tr>
<th><var>y</var></th>
<td>2</td><td></td><td>6</td>
</tr>
<tr>
<th><var>y</var>+1</th>
<td>1</td><td>0</td><td>7</td>
</tr>
</table>
<center>
<caption>対象セル</caption>
</center>
</div>
<dl>
<dt>−1</dt>
<dd>現在位置に留まり, 何もしない.</dd>
<dt>0, …, 7</dt>
<dd>近傍セルのいずれかに動く.</dd>
<dt>8, …, 15</dt>
<dd>近傍セルのいずれかに穴を掘る.</dd>
<dt>16, …, 23</dt>
<dd>近傍セルのいずれかの穴を埋める.</dd>
</dl>
動いたり穴掘りや穴埋めをする対象セルの座標は
<var>d</var> = <var>m</var> modulo 8
によって決まる.
その意味は右図に示すとおりである.
</p>
<p>
侍の移動や穴掘り穴埋めの対象は 4 近傍セルのいずれかでなくてはならなず,
上述の <var>d</var> は偶数でなければならない.
侍のプレイプランが 22 以下の非負の偶数でも −1
でもなければ, それは<em>不正</em>である.
</p>
<p>
犬は穴掘りや穴埋めができない.
犬のプレイプランが −1 以上 7 以下の整数でなければ<em>不正</em>である.
</p>
<p>
不正なプレイプランは −1 と同様に扱う.
当該エージェントの行動が −1 になるだけでなく,
後述するゲーム状態情報にもプレイプラン
−1 を指定したものとして扱う <a href="#invalid plan">[1]</a>.
</p>
<p>
一方, セルの状態やエージェントの位置や動きのために,
プレイプランが通りの動きができない場合,
そのプレイプランは<em>無効</em>であるという.
</p>
<p>
競技場外の方向へ移動, 穴掘り, 穴埋めは無効である.
穴があるセルの穴掘り, 穴のないセルの穴埋めも無効である.
ステップ開始時に他のエージェントがいるセルへの移動や穴掘り・穴埋めも無効である.
</p>
<p>
同一ステップでの同一セルへの複数のエージェントの移動は,
すべてが無効になる.
同一ステップで他のエージェントが移動してくるセルの穴掘りも無効である.
しかし, 複数のエージェントが同一セルに移動しようとして移動が無効になれば,
別のエージェントによるそのセルへの穴掘りは有効になる.
</p>
<p>
無効なプレイプランに対する行動も −1 になるが,
不正なプレイプランとは異なり,
プレイプラン自体は後述するゲーム状態情報に反映される.
</p>
<h3>ゲーム状態情報</h3>
<p>
各ステップの開始時に,
ゲーム管理システムからプレイヤプロセスに<em>ゲーム状態情報</em>を送る.
ゲーム状態情報は以下の各項目がこの順に並ぶものである.
<ul>
<li>
この情報を受け取るプレイヤプロセスが制御するエージェント番号.
一方の侍が 0, 他方の侍が 1, 0 番の侍と同じチームの犬が 2,
他方の 犬が 3 である.
</li>
<li>
競技場のサイズ, すなわち競技場の一辺のセル数 (整数値).
</li>
<li>
現在のステップ番号 (整数値). ステップ番号は 0 から始める.
<li>
最大ステップ番号 (整数値).
</li>
<li>
穴のあるセルの位置のリスト.
</li>
<li>
全エージェントに知られている (公知の) 埋蔵金のリスト.
既に掘り出された埋蔵金は含まない.
</li>
<li>
制御するエージェントが犬である場合,
その位置の 8 近傍セルにある公知になっていない埋蔵金のリスト.
エージェントが侍ならば空リスト.
</li>
<li>
各エージェントの位置 (エージェント番号順).
</li>
<li>
直前ステップでの各エージェントのプレイプラン
(エージェント番号順).
上述の通り不正なプレイプランについては −1 になる.
ゲーム開始時のステップではすべて −1 になる.
</li>
<li>
直前のステップで各エージェントが実際にとった行動 (エージェント番号順).
ゲーム開始時のステップではすべて −1 になる.
</li>
<li>
スコア, すなわち,
両軍それぞれが直前ステップにまでに掘り出した埋蔵金の総量
(整数値ふたつ).
エージェント 0, 2 のチームのスコアが先, 1, 3 のスコアが後に来る.
</li>
<li>
まだ掘り出されていない埋蔵金の総量 (整数値).
</li>
<li>
残る<a href="#timeLimit">考慮時間</a>
(ミリ秒単位の整数値).
</li>
</ul>
</p>
<p>
ゲーム状態情報の要素はすべて整数である.
前述の箇条書の各項目の間は改行で区切り,
項目内の整数の間は空白で区切る.
最後の要素の後には改行が置かれる.
</p>
<p>
上述の項目で<em>リスト</em>と記したものは,
先頭にリスト要素の個数 (整数値) が来る.
リストが空なら 0 である.
その後にリストの各要素の記述が続く.
各要素はひとつ以上の整数値である.
</p>
<p>
位置はセルのx-座標とy-座標のふたつ組で表す.
座標値は非負整数で, 競技場のサイズより小さい.
埋蔵金は整数値みっつで表す.
最初のふたつは埋蔵金のあるセルの座標で, みっつ目は埋蔵金の量である.
埋蔵金の量は必ず非負の偶数である.
</p>
<div class="exampleText">
<table class="shrunk">
<tr><td><tt>3</tt></td><td>// エージェントの番号</td></tr>
<tr><td><tt>10</tt></td><td>// 競技場のサイズ</td></tr>
<tr><td><tt>1</tt></td><td>// ステップ番号</td></tr>
<tr><td><tt>100</tt></td><td>// 最大ステップ番号</td></tr>
<tr><td><tt>6 5 1 7 3 7 0 8 1 6 0 5 2</tt></td>
<td>// 穴のあるセルの位置のリスト</td></tr>
<tr><td><tt>1 6 6 6</tt></td><td>// 公知の埋蔵金</td></tr>
<tr><td><tt>1 2 7 8</tt></td><td>// 感知した埋蔵金</td></tr>
<tr><td><tt>9 6 2 4 5 3 1 6</tt></td><td>// エージェントの位置</td></tr>
<tr><td><tt>0 0 7 7</tt></td><td>// 直前ステップでのプレイプラン</td></tr>
<tr><td><tt>0 0 7 7</tt></td><td>// 直前ステップでの行動</td></tr>
<tr><td><tt>0 0</tt></td><td>// スコア</td></tr>
<tr><td><tt>50</tt></td><td>// 残る埋蔵金</td></tr>
<tr><td><tt>299941</tt></td><td>// 残る考慮時間</td></tr>
</table>
</div>
<p>
ゲーム状態情報の例を右図に示す.
"//" から以降はここでの説明のためのもので,
実際にプレイヤプロセスには送られない.
<ul>
<li>
この情報の送り先のプレイヤ番号は 3, つまり片方のチームの犬である.
</li>
<li>
競技場は 10×10 のセルからなる.
</li>
<li>
ステップ番号は 1.
</li>
<li>
最大ステップ番号は 100.
</li>
<li>
穴のあるセルは 6 箇所で, その座標は (5, 1), (7, 3), (7, 0),
(8, 1), (6, 0), (5, 2) である.
</li>
<li>
公知の埋蔵金が (6, 6) にあり, その量は 6 である.
</li>
<li>
この情報を受ける犬は (2, 7) にある埋蔵量 8 の埋蔵金を感知した.
</li>
<li>
4 エージェントの位置は (9, 6), (2, 4), (5, 3), (1, 6) である.
</li>
<li>
直前ステップでの各エージェントのプレイプランは 0, 0, 7, 7 だった.
</li>
<li>
直前ステップで各エージェントが実際にとった行動も 0, 0, 7, 7,
つまりすべてプレイプランどおりだった.
</li>
<li>
掘り出した埋蔵金はまだない.
</li>
<li>
残る埋蔵金の総量は 50 である.
</li>
<li>
このエージェントの残り考慮時間は 299941 ミリ秒である.
</li>
</ul>
</p>
<h3>プレイプラン</h3>
<p>
プレイヤプログラムはゲーム状態情報を読んだら,
それに応じて対応するエージェントのプレイプランを出力する.
プレイプランは整数値ひとつで, その意味は上述のとおりである.
プレイプランの後には改行がなくてはならない.
</p>
<h3 id="timeLimit">考慮時間制限</h3>
<p>
プレイヤプロセスの考慮時間には制限が設けられる.
考慮時間とはゲーム管理システムがプレイヤプロセスにゲーム状態情報を送ってから,
その返答であるプレイプランを受け取るまでの時間のことである.
これは実際の経過時間であって CPU 時間ではないことに注意.
各ステップの考慮時間は累積され, その総計に対して制限が課せられる.
</p>
<p>
考慮時間制限はプレイヤプロセスごとに設ける.
同じチームの侍と犬の考慮時間は別々に累積される.
</p>
<p>
考慮時間制限を越えたプレイヤプロセスは,
その後の全ステップにおいて −1 (その場に留まること)
をプレイプランとして選択したものとみなされる.
</p>
<p>
考慮時間制限の値はゲームごとに定める.
</p>
<h2>試合</h2>
<p>
2 チームの間の試合は,
同じ初期状態でエージェントの配置だけを交換した 2 ゲームで競う.
試合の勝敗は 2 ゲームを通じて掘り出した埋蔵金の総量で判定する.
</p>
<hr>
<ul class="footnotes">
<li id="invalid plan">
不正なプレイプランをそのままゲーム状態情報に反映すると,
エージェント同士の自由な通信ができてしまうため.
</li>
</ul>
</body>
</html>