-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrule-jp.html
More file actions
530 lines (503 loc) · 21.7 KB
/
Copy pathrule-jp.html
File metadata and controls
530 lines (503 loc) · 21.7 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
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<link rel="stylesheet" type="text/css" href="samurai-docs.css">
</head>
<body>
<a href="rule-en.html">English Version</a>
<h1>SamurAI Jockey 2018 ゲームルール</h1>
<div class='centered'>
2019年1月8日<br>
情報処理学会プログラミングコンテスト委員会
</div>
<div class="abstract">
SamurAI Coding 2018-19 に用いるゲームのルールを述べる.
</div>
<h2>ゲームの概要</h2>
<p>
1回の<b>レース</b>は,
ふたりのプレイヤがスタート位置から開始し,
障害物や水溜りがあるレースコース上で<b>ステップ</b>ごとに加速・減速しながら,
ゴールに到達する速さを競うゲームである.
プレイヤの動きはステップごとにAIプログラム (以下単に<b>AI</b>と呼ぶ) が制御する.
</p>
<p>
ひとつの<b>ゲーム</b>は,
同じ<b>レースコース</b>で両プレイヤのスタート位置を交換した2回のレースからなる.
両レースのゴールタイムの合計が短い方がゲームの勝者である.
合計タイムが同一である場合は, そのゲームは引き分けである.
</p>
<figure style="float:right; width: 50%;">
<img src="../screenshots/sample-course.png"
style="width: 100%; object-fit: scale-down">
<figcaption>レースコースの例</figcaption>
<p style="margin: 10px">
このコースは幅16, 長さ20で, 両プレイヤは (3, 0) および (7, 0) に位置している.
</p>
</figure>
<h2>レースコース</h2>
<p>
レースコースは2次元の枡目からなり, ゲーム毎に幅・長さや障害物・水溜りの数や位置が異なる.
以下では<b>コース幅</b>を <var>w,</var> <b>コース長</b>を <var>l</var> とし,
各枡目の座標を (<var>x, y</var>) とする.
</p>
<p>
各ステップの開始時, 終了時においてプレイヤはいずれかの枡目にある.
プレイヤはコース幅の外に出ることはできない.
すなわちプレイヤのいる枡目の <var>x</var> 座標について
0 ≤ <var>x</var> < <var>w</var>
が成り立つ.
プレイヤが <var>y</var> ≥ <var>l</var> の枡目に到達した際には,
そのプレイヤはゴールしたことになる.
スタート位置より後ろの <var>y</var> < 0 の枡目にも到達できる.
</p>
<p>
レース開始時には, 両プレイヤは <var>y</var> 座標が 0 で,
<var>x</var> 座標が相異なる枡目に位置する.
</p>
<p>
コース上の枡目の一部は<b>障害</b>あるいは<b>水溜り</b>である.
障害や水溜りの枡目は固定されており, レース中に変化することはない.
障害や水溜りの座標は
0 ≤ <var>x</var>< <var>w,</var>
0 ≤ <var>y</var>< <var>l</var>
の範囲に限られる.
つまり, コース幅の外, スタート位置より前, ゴールより後には存在しない.
障害や水溜りでない枡目は<b>平坦</b>である.
</p>
<p>
右図にレースコースの例を示す.
枡目のアイコンの意味は以下のとおりである.
<table style="border-spacing: 20px">
<tr>
<td><img src="../icons/lawn.png" width="36px"></td>
<td><img src="../icons/obstacle.png" width="36px"></td>
<td><img src="../icons/jump.png" width="36px"></td>
<td><img src="../icons/withPlayer0.png" width="36px"></td>
<td><img src="../icons/withPlayer1.png" width="36px"></td>
</tr>
<tr>
<td>平坦</td>
<td>障害</td>
<td>水溜り</td>
<td colspan="2">プレイヤの位置</td>
</tr>
<tr>
</tr>
</table>
</p>
<p>
コースは大きな後戻りが必要ないように設定される.
レース開始時の両プレイヤの位置から到達可能なコース内のどの枡目からも,
十分小さい速度で移動すれば,
<var>y</var> 座標を一度もコースごとに定める<b>視界距離</b>以上減らすことなく,
障害やコース端にぶつからずに
<var>y</var>座標がより大きい点に移動できる.
</p>
<h2>視界の制約</h2>
<p>
AI にはコースの各枡目が平坦, 障害, 水溜りのいずれであるかを通知されるが,
各ステップにおいてこの情報が与えられる枡目は,
その <var>y</var> 座標が<b>視界限界</b>未満のもののみである.
視界限界は, 当該ステップまでにいずれかのプレイヤが達した <var>y</var> 座標の最大値に,
コースごとに定める<b>視界距離</b>を加えたものである.
</p>
<p>
視界限界はいずれかが到達した <var>y</var> 座標の最大値によって決まるので,
いずれかのプレイヤがより大きい <var>y</var> 座標まで進めば,
それにしたがって視界も広がる.
プレイヤが <var>y</var> 座標が小さい方向に逆行しても,
視界限界が小さくなることはない.
</p>
<p>
両プレイヤの視界限界は同一であり,
したがって両プレイヤが得られるコースの情報も同一である.
</p>
<p>
上掲のレースコース例の図中で,
コース画面の上半分程度の白く紗がかかっている枡目は,
初期状態での視界の外にあることを表している.
この例では視界距離は10である.
</p>
<h2>レースの進行</h2>
<p>
各レースでは, ステップごとに AI にレースの状況についての情報を与え,
それに対して AI は加減速の指示を応答する.
その指示によってプレイヤは加減速され,
レースの状況は更新される.
このステップを両プレイヤが共にゴールまたは失格するまで繰り返す.
ただし,
レースコースごとに定める制限ステップ数に達してもゴールしないプレイヤがある場合,
その時点でレースは終了し, ゴールに達していないプレイヤは失格となる.
</p>
<h3>考慮時間</h3>
<p>
AI が1レースで使える<b>考慮時間</b>の合計には, 制限を設ける.
考慮時間はゲーム管理プログラムがプレイヤに情報を送信し終わってから,
プレイヤからの応答を受信し終わるまでの実時間である.
考慮時間の合計が制限値を超えたプレイヤは失格となる.
</p>
<h3>プレイヤの状態</h3>
<p>
プレイヤは各ステップ開始時の状態として位置する枡目の座標と速度を持つ.
位置と速度はいずれも2次元のベクトルで, 両要素は整数値である.
以下, ステップ開始時のプレイヤの位置を (<var>x, y</var>),
<b>速度</b>を (<var>v<sub>x</sub>, v<sub>y</sub></var>) とする.
</p>
<p>
各ステップ開始時の状態は, 前ステップ終了時の状態と同じである.
ただし, レース開始時の最初のステップでは,
位置がコースに指定された初期位置,
速度は (0, 0) である.
</p>
<h3>加減速と予定位置</h3>
<p>
AI はステップごとに速度を変更する<b>加速度</b>
(<var>a<sub>x</sub>, a<sub>y</sub></var>)を指示する.
<var>a<sub>x</sub>, a<sub>y</sub></var> は各々
−1, 0, 1 のいずれかである.
座標 (<var>x+v<sub>x</sub>+a<sub>x</sub>, y+v<sub>y</sub>+a<sub>y</sub></var>) の枡目をこのプレイヤのこのステップにおける<b>予定位置</b>と呼ぶ.
当該ステップでプレイヤが後述のコースアウトや衝突により停止するのでなければ,
ステップ終了時のプレイヤの位置は予定位置になる.
ステップ終了時のプレイヤの速度は, 予定位置が水溜りならば (0, 0), さもなくば
(<var>v<sub>x</sub>+a<sub>x</sub>, v<sub>y</sub>+a<sub>y</sub></var>)
となる.
</p>
<figure style="float:right; width: 20%">
<img src="../screenshots/off-the-track.png"
style="margin: auto; width: 100%; height: 100%;
object-fit: scale-down">
<figcaption>コースアウト</figcaption>
</figure>
<h3>動線とコースアウト</h3>
<p>
ステップ開始時にプレイヤが位置する枡目の中心と,
終了時の予定位置の枡目の中心を両端とする線分を,
このプレイヤの当該ステップでの<b>動線</b>と呼ぶ.
</p>
<p>
以下の場合, 当該プレイヤは<b>コースアウト</b>を生じているという.
<ul>
<li>
予定位置がコース幅の外である,
すなわち予定位置の <var>x</var> 座標が
0 ≤ <var>x</var> < <var>w</var>
を満たさない.
</li>
<li>
動線が障害の枡と交差あるいは接する.
</li>
</ul>
右図中の赤い動線 a, b, c, d はコースアウトであり,
青の動線 e, f はコースアウトではない.
動線 a, b は障害の枡目と交差しており,
動線 c は障害の枡目の角と接している.
動線 d は予定位置がコース幅の外である。
</p>
<p>
コースアウトしたプレイヤのステップ終了時の位置は開始時と変化しない.
また, 速度は (0, 0) すなわち停止状態となる.
</p>
<h3>衝突と優先権</h3>
<p>
コースアウトがなく, 両プレイヤの動線が交差あるいは接触する場合,
<b>衝突</b>が生じたという.
</p>
<p>
衝突が生じた場合,
<b>優先権</b>を持つプレイヤはステップ終了時に予定位置に動くが,
優先権のないプレイヤの位置は元のままで,
速度は (0, 0) すなわち停止状態になる.
</p>
<figure style="float:right; width: 45%; margin: 0px 0px 10px 10px;">
<table style="padding: 10px; spacing: 0px;">
<tr>
<td>
<img src="../screenshots/collision-1.png"
style="width: 100%; object-fit: scale-down">
</td>
<td>
<img src="../screenshots/collision-2.png"
style="width: 100%; object-fit: scale-down">
</td>
</tr>
<tr>
<td>Case 1</td>
<td>Case 2</td>
</tr>
<tr>
<td>
<img src="../screenshots/collision-3.png"
style="width: 100%; object-fit: scale-down">
</td>
<td>
<img src="../screenshots/collision-4.png"
style="width: 100%; object-fit: scale-down">
</td>
</tr>
<tr>
<td>Case 3</td>
<td>Case 4</td>
</tr>
</table>
<figcaption>衝突と優先権</figcaption>
</figure>
<p>
優先権を持つのは,
ステップ開始時の位置の <var>y</var> 座標がより小さいプレイヤである.
<var>y</var> 座標が同じ場合, <var>x</var>座標がより小さいプレイヤが優先権を持つ.
ただし, 動線が相手プレイヤのステップ開始時の位置の枡目と交差あるいは接する場合は,
優先権は相手プレイヤに移る.
</p>
<p>
衝突した両方の動線が相手のステップ開始時の位置の枡目と交差あるいは接する場合,
両者とも優先権を失い, ステップ終了時の位置は元のまま,
速度は (0, 0) となる.
</p>
<p>
右図に掲げる具体例について説明する.
<ul>
<li>
Case 1 では,
青い動線のプレイヤのステップ開始時の <var>y</var> 座標の方が小さいので,
このプレイヤが優先権を得た.
</li>
<li>
Case 2 では,
赤い動線のプレイヤの動線は相手プレイヤのステップ開始時の位置の枡目と接しているので,
青い動線のプレイヤが優先権を得た.
</li>
<li>
Case 3 では,
<var>y</var> 座標の小さいプレイヤの動線は相手プレイヤのステップ開始時の位置の枡目を通るが,
互いの動線は交差も接触もしていないので, そもそも衝突ではない.
</li>
<li>
Case 4 では衝突が生じており,
両者の動線は共に相手のステップ開始時の位置の枡目と交差あるいは接しているので,
ステップ終了時のの位置は両者ともにステップ開始時のまま,
速度は (0, 0) となる.
</li>
</ul>
</p>
<h3>水溜り</h3>
<p>
ステップ終了時の位置の枡目が水溜りならば, そのプレイヤの速度は (0, 0) になる.
したがって,
水溜りの枡目 (<var>x</var>, <var>y</var>) から出発するステップでは
(<var>x</var>±1, <var>y</var>±1)
の範囲にしか動けないことになる.
</p>
<h3>ゴールとゴールタイム</h3>
<p>
プレイヤがステップ <var>s</var> の開始時に座標
(<var>x</var>, <var>y</var>) の枡目にあり,
ステップ終了時に位置 (<var>x'</var>, <var>y'</var>) に達し,
<var>y'</var> ≥ <var>l</var> であるとき,
そのプレイヤはゴールしたものとされる.
このとき<b>ゴールタイム</b>は
<var>s</var> + (<var>l</var> − <var>y</var>) / (<var>y'</var> − <var>y</var>)
となる.
</p>
<p>
ゴール時, 相手プレイヤがまだゴールも失格もしていなければ,
ゴールしたプレイヤをコースから取り除いた状態でレースを継続する.
</p>
<h3>失格</h3>
<p>
プレイヤは以下のいずれかの場合, 当該プレイヤはそのレースについて<b>失格</b>となる.
</p>
<ul>
<li> 制限ステップ数に達してもゴールできなかった.</li>
<li> 考慮時間の合計が制限値を超えた</li>
<li> 後述の規定に反する出力を行った</li>
</ul>
<p>
失格したステップまでに相手プレイヤがゴールも失格もしていなければ,
失格したプレイヤをコースから取り除いた状態でレースを継続する.
失格したプレイヤのゴールタイムは制限ステップ数の2倍とする.
</p>
<p>
なお, 失格は当該レースのみであり,
次以降のレースには通常通り参加できる.
</p>
<h2>AIの入出力</h2>
<p>
AI は初期化時にレース全体に関する情報を入力し,
初期化終了を示す応答を出力する.
ステップごとにはレース状況の情報を入力し,
応答として加速度指示を出力する.
ただし, ゴールあるいは失格したプレイヤのAIには,
その後のステップではこのやりとりは行われない.
</p>
<p>
入力はただひとつの空白あるいは改行で区切った10進整数の並びである.
負の数にはマイナス符号を前置する.
初期化時の入力およびステップごとの入力の最後は必ず改行を置く.
</p>
<p>
AI の応答出力も空白あるいは改行で区切った10進整数の並びで,
負の数にはマイナス符号を前置する.
<b>出力の最後には必ず改行を置く. </b>
</p>
<figure style="float:right; margin: 0px 0px 10px 10px;">
<p class="input-example">
<code>
120000<br>
100<br>
16 20<br>
10
</code>
</p>
<figcaption>初期化時の入力</figcaption>
</figure>
<h3>初期化時の入力</h3>
<p>
初期化時の AI の入力は下記の項目がこの順に並ぶものである.
<ul>
<li>
考慮時間: このレースで使える合計考慮時間をミリ秒単位の整数値として.
</li>
<li>
制限ステップ数: ゴールまでのステップ数の上限を整数値として.
</li>
<li>
コースサイズ: コースの幅 <var>w</var> および長さ
<var>l</var> をふたつの整数値として.
</li>
<li>
視界距離: 視界を決める距離を整数値として.
</li>
</ul>
各項目の直後には改行が置かれ,
ひとつの項目 (1行) に含まれる複数の整数はひとつの空白で区切られる.
</p>
<p>
右図に初期化時の入力の例を示す。
</p>
<figure style="float:right; margin: 0px 0px 10px 10px;">
<p class="output-example">
<code>
0
</code>
</p>
<figcaption>初期化時の出力</figcaption>
</figure>
<h3>初期化時の出力</h3>
<p>
AIは初期化が終了したら、そのことを整数 0 ひとつ及び改行で伝える.
</p>
<figure style="float:right; margin: 0px 0px 10px 10px;">
<p class="input-example">
<code>
3<br>
118628<br>
5 1 0 0<br>
4 6 -1 3<br>
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br>
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br>
0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1<br>
2 2 2 2 2 0 2 2 2 0 0 0 0 0 0 0<br>
2 2 2 2 2 2 2 1 1 1 1 0 0 0 0 0<br>
2 2 2 2 0 0 2 2 0 0 0 0 0 0 0 0<br>
2 2 2 2 0 0 0 2 0 0 0 0 0 0 0 0<br>
2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0<br>
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br>
0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0<br>
0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0<br>
0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0<br>
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0<br>
0 2 2 2 0 0 0 0 0 0 0 1 1 1 0 0<br>
0 2 2 2 0 0 0 1 1 1 1 1 1 1 0 0<br>
0 0 0 0 0 0 2 2 2 1 1 1 0 0 0 0<br>
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1<br>
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1<br>
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1<br>
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1<br>
</code>
</p>
<figcaption>ステップごとの入力</figcaption>
</figure>
<h3>ステップごとの入力</h3>
<p>
ステップごとのAIの入力は下記の項目の整数がこの順に並ぶものである.
<ul>
<li>
ステップ: 当該のステップの番号を整数値として.
ステップ番号は 0 から始まる.
</li>
<li>
残り考慮時間: このレースで使える考慮時間の残りをミリ秒単位の整数値として.
</li>
<li>
自プレイヤの状態: 当該のAIが制御するプレイヤの位置のステップ開始時の位置の座標
(<var>x</var>, <var>y</var>) と速度
(<var>v<sub>x</sub></var>, <var>v<sub>y</sub></var>) を,
この順に 4 整数値として.
</li>
<li>
相手プレイヤの状態: 相手プレイヤの位置のステップ開始時の位置の座標
(<var>x</var>, <var>y</var>) と速度
(<var>v<sub>x</sub></var>, <var>v<sub>y</sub></var>) を,
この順に 4 整数値として.
ただし, 相手プレイヤが既にゴールしたか失格した場合は,
0, <var>l</var>, 0, 0 の 4 整数になる.
</li>
<li>
コースの枡目の情報:
各枡目がどのような枡目であるかの情報で,
<var>w</var> 個の整数値からなる行を <var>l</var> 行,
計 <var>w</var> × <var>l</var> 個の整数値として与えられる.
各行内の複数の整数値はひとつの空白で区切られる.
情報の順序は枡目の<var>y</var> 座標の昇順,
同じ <var>y</var> 座標の枡目の中では <var>x</var> 座標の昇順である.
<br>
情報の意味は以下の通りである.
<ul>
<li> 0: 当該の枡目は障害でも水溜りでもない. </li>
<li> 1: 当該の枡目は障害である. </li>
<li> 2: 当該の枡目は水溜りである. </li>
<li> −1: 当該の枡目は視界の外であるため不明. </li>
</ul>
</li>
</ul>
コースの枡目の情報以外については, 項目の間と最後に改行が置かれ,
ひとつの項目に複数の整数が含まれる場合, それらはひとつの空白で区切られる.
</p>
<figure style="float:right; margin: 0px 0px 10px 10px;">
<p class="output-example">
<code>
-1 1
</code>
</p>
<figcaption>ステップごとの出力</figcaption>
</figure>
<h3>ステップごとの出力</h3>
<p>
AI は当該ステップの加速度 (<var>a<sub>x</sub>, a<sub>y</sub></var>)
を空白ひとつで区切ったふたつの整数
<var>a<sub>x</sub></var> および <var>a<sub>y</sub></var>
で指定する. 両者は −1, 0, 1 のいずれかでなければならない.
これらの後に改行を出力する.
</p>
<h3>情報の記憶</h3>
<p>
ゲーム管理システムは,
各ステップについて出力を得た AI の動作を一時停止し,
次ステップの情報を与える際に動作を再開させる.
このため, ステップとステップの間に計算を進めることはできないが,
変数値などの実行コンテキストは 1 レースの間保持し続けることができる.
</p>
<p>
AIはファイル出力やネットワークアクセスができない環境で動作し,
ゲーム管理システムはレース毎にAIを初期状態から立ち上げ直す.
このため, AIは複数のレースの間で情報を受け渡すことはできない.
</p>
<div>
<p class="flushright">
以上
</p>
</div>
</body>
</html>