forked from takashi-chikayama/SamurAI-Dig-Here-2020-21
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrules-jp.html
More file actions
492 lines (478 loc) · 20.4 KB
/
Copy pathrules-jp.html
File metadata and controls
492 lines (478 loc) · 20.4 KB
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
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
<!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 2020 ゲームルール</title>
</head>
<body>
<span style="float:left">
<a href="rules.html" target="_blank">English</a>
</span>
<h1>SamurAI Dig Here 2020 ゲームルール</h1>
<center>
<p>
情報処理学会プログラミングコンテスト委員会<br>
2020/12/07
</p>
</center>
<div style="margin: 0% 15% 0% 15%">
<p>
この文書は情報処理学会主催の <em>SamurAI Coding 2020-21</em>
コンテストの対象である <em>SamurAI Dig Here 2020</em>
ゲームのルールを述べるものである.
</p>
</div>
<h2>ゲームの概要</h2>
<p>
ゲームは 2 チーム間で競う零和不完全情報ゲーム,
競技参加者によるプログラムで制御する各 2 エージェントが競い合うものである.
ゲームの目的は競技の場に隠されている埋蔵金をより多く掘り出すことである.
</p>
<img src="screenShots/small-field.png" width="50%" class="figure">
<h3>競技場</h3>
<p>
競技場は正方形で,
正方格子状に並ぶ小正方形 (<em>セル</em>) に分かれている.
競技場のサイズ, すなわち競技場の一辺に並ぶセルの数はゲームごとに異なる.
サイズは最小 6 最大 20 である.
</p>
<p>
右図は正方形の競技場を斜め方向から俯瞰したものである.
</p>
<h3>ゲームエージェント</h3>
<p>
両チームにはそれぞれ 2 体のゲームエージェント,
<em>侍</em>と<em>犬</em>がある.
</p>
<p>
ゲームエージェントは競技者が提供するプログラムで制御する.
同じチームの犬と侍は同じプログラムが動くふたつのプロセスで制御し,
両プロセス間の通信はゲーム管理システムを介したものだけで,
他の通信手段はない.
</p>
<p>
ゲーム開始時にはエージェントは競技場内の別々のセル上にある.
ゲームを通して複数のエージェントが同時に同じセル上に来ることはない.
</p>
<p>
ゲームの 1 ステップごとに, 犬エージェントはその 8 近傍セル,
すなわち現在のセルと 4 隅のひとつかふたつを共有するセルに動くことができる.
侍エージェントはゲーム開始直後のステップと休憩した直後のステップでは 8
近傍セルのどれにでも動けるが,
それ以外のステップでは現在のセルと 4 辺のいずれかを共有する 4
近傍セルにしか動けず, 斜め方向の 4 セルには動けない.
現在のセルから動かないこともできる.
</p>
<p>
ふたつ以上のエージェントが同じセルに動くよう指示された場合など,
指示が無効となる場合はどちらも動くことはできず, 元の位置に留められる.
詳細は<a href="#viability">プレイプランの有効性判定</a>の節に記す.
</p>
<h3>穴</h3>
<p>
競技場内のセルには<em>穴</em>があることもあり,
そこにはエージェントは動けない.
侍エージェントは動く代わりに, 近傍セルのひとつにある穴を埋めたり,
近傍セルのひとつに新たな穴を掘ることができる.
ゲーム開始直後と休憩した直後のステップでは 8
近傍セルのどれでもひとつの穴を埋めたり新たな穴を掘ったりできるが,
そうでないステップでは 4 近傍セルだけを対象とできる
また, ステップ開始時に既に他のエージェントがいたり,
掘ろうとする同じステップで他のエージェントが動いてきたセルには穴を掘れない.
</p>
<p>
エージェントの初期位置に穴はない.
</p>
<h3>埋蔵金</h3>
<p>
競技場内のセルには<em>埋蔵金</em>が埋められていることがある.
埋蔵金のあるセルに穴を掘ると, 埋蔵金を掘り出すことができる.
両チームの侍が同時に同じセルに穴を掘った場合は,
埋蔵金は両チームが半分ずつ獲得することになる.
なお, 埋蔵金の量は常に偶数で, その総量が 10<sup>9</sup> を超えることはない.
</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>
競技場の状態だけから実行できないとわかるプレイプランは<em>不正</em>であるという.
競技場の状態だけからは実行できるかもしれなかったが,
他のエージェントの動きとの干渉のために実行できないプレイプランは<em>無効</em>であるという.
たとえば, 穴のあるセルに移動しようとするプランは<em>不正</em>であり,
ふたつのエージェントが同じセルに移動しようとするプランは<em>無効</em>である.
</p>
<p>
不正なプレイプランも無効なプレイプランも実際には行われない.
両者の違いは不正なプレイプランは休憩とまったく同様に扱われる点にある.
無効なプレイプランはそのままゲーム状態情報のゲームプランの項目に反映されるが,
不正なプレイプランは<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>
犬は穴掘り, 穴埋めができない. 犬のプレイプランが −1 以上 7
以下の整数でなければ<em>不正</em>である.
</p>
<p>
競技場外の方向への移動, 穴掘り, 穴埋め,
穴があるセルの穴掘り, 穴のないセルの穴埋め,
ステップ開始時に他のエージェントがいるセルへの移動や穴掘り・穴埋めは,
いずれも<em>不正</em>である.
</p>
<p>
不正ではないプレイプランであっても,
他のエージェントのプレイプランとの干渉により<em>無効</em>となる場合がある.
詳細は次節に記す.
</p>
<h3 id="viability">プレイプランの有効性判定</h3>
<p>
プレイプランが有効性の判定は, 以下の手順に従う.
<dl>
<dt>不正プレイの除外</dt>
<dd>
不正なプレイプランを休憩と同一視する.
</dd>
<dt>斜め方向動作の交差判定</dt>
<dd>
斜め方向の移動, 穴掘り, 穴埋めのすべてのプレイプランについて,
その動線が交差する場合,
侍同士あるいは犬同士の場合は両者のプラン共に無効に,
一方が侍で他方が犬の場合は犬のプランを無効とする.
</dd>
<dt>移動先の衝突判定</dt>
<dd>
複数のエージェントが同一セルに移動するプレイプランを無効とする.
</dd>
<dt>移動先の穴掘り</dt>
<dd>
他エージェントが移動する先のセルの穴掘りを無効とする.
</dd>
</dl>
各項目により不正あるいは無効とされたプランは,
以降の有効性判定においては無視される．
したがって以下のようになる.
<ul>
<li>
移動のプランが他のエージェントのプランとの動線の交差により無効になれば,
第 3 のエージェントは無効になった移動の行先に動ける.
</li>
<li>
複数のエージェントが同一セルに移動するプランが無効になれば,
他のエージェントの移動先だったセルへの穴掘りは無効にならない.
</li>
</ul>
</p>
<div class="figure" style="width:30%; margin:1%">
<img src="viability.png" width="100%">
<center>
<caption>有効性判定例</caption>
</center>
</div>
<p>
右図に示す配置のときに以下のプレイプランを指定したとする.
<ul>
<li>赤の侍: 南東方向への移動 (7)</li>
<li>赤の犬: 北西方向への移動 (5)</li>
<li>青の侍: 西方向への穴掘り (10)</li>
<li>青の犬: 北東方向への移動 (3)</li>
</ul>
上述の手順に従って, 以下の有効性判定がなされる.
<ul>
<li>どのプレイプランも不正ではない.</li>
<li>
赤の侍と青の犬の動線が交差する.
侍が優先なので, 青の犬の移動は無効である.
</li>
<li>
青の犬の移動が無効になったので,
同じセルに移動する赤の犬の移動は無効にならない.
</li>
<li>
赤の犬の移動先に穴掘りをする青の侍のプレイプランは無効になる.
</li>
</ul>
結局, 赤のエージェントのプランはいずれも有効,
青のエージェントのプランはいずれも無効となる.
</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 だった.
侍エージェントのプレイプランはどちらも −1 ではないので,
両者ともこのステップでの斜め方向への移動や穴掘り穴埋めは不正になる.
</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>
</body>
</html>