0927
2012-09-27
*1348675384*SamurAI Codingのゲームルールを勝手に解説
SamurAI Codingは情報処理学会主催で行われる国際プログラミングコンテスト。9月28日にシンガポール予選、10月11日にシリコンバレー予選、24日に日本予選が行われる。 公式サイト: https://samuraicoding.org/
f:id:nishiohirokazu:20120927021251p:image
ゲームは簡潔に言えば「サムライと犬を動かして陣取りをするゲーム」で、その動かすアルゴリズムをGunbai Scriptっていうこのゲーム専用の言語で実装して提出する。だから「慣れた言語やライブラリが使えるかどうか」っていう点での有利不利はなく、同じスタートラインから「理解し、よいプログラムを作る」という力を競い合うことができる。
ちなみに10月22日がソースコードの提出期限。24日は対戦が行われる日なので勘違いしないように。
** ゲームルール
ここではざっくりとルールの概要を解説する。ざっくりとしか書かないので細かいことはオフィシャルのPDFを参考にすること。
これはサムライと犬を操って、マップを歩きまわって陣取りをするゲームだ。サムライが通ったマスは自分の色の足跡がつき、自分の陣地になる。この足あとで囲みを作るとその囲みの中も自分の陣地になる。基本的には一定ラウンド経過後にこの陣地が一番広かった人が勝ちになる。
ただし、それだけじゃ考える面白みがないので、細かいルールが付け加えられている。
- 陣地がマップの端から端までつながったら、即座に勝利
- サムライは犬が怖くて、犬に隣接するマスに入れない
- マップの端にある鳥居に入るとワープする
- 4体のキャラクターが一直線に並んだら、場所が交換される(syzygy)
- 自分の陣地の周りを他人の陣地が取り囲んだら、「囲みの中も陣地になる」効果で陣地を取られてしまう(siege)
オフィシャルのPDFにはスクリーンショットや図を使ってしっかり解説してある。ここには詳細な発動条件とかは書かないのでオフィシャルを参照。
** 試してみる
ログインして「Trial Games」から試すことができる。予想をいい方向に裏切って、なんとブラウザ上で JavaScript + Canvas で動く！てっきり何かJavaとかで書かれたプログラムをインストールさせられるのかと思っていた。GREEの中の人がだいぶ技術協力しているのかな？
f:id:nishiohirokazu:20120927010215p:image
処理系がオープンなのは素晴らしい。勝手に社内プログラミングコンテストとかを開催できる。
ざっとコードを眺めてみたけども、random命令が普通にMath.random()を叩いているところがちょっと気になった。これだと「プログラムを書いて走らせたら予期しない挙動をした→バグを直した→もう一回実行したら乱数列が違うから同じ局面が再現せずバグがとれたのかどうかわからない！」が起きそうだ。あとUIの更新をスキップして高速に実行したりとか、特定の条件を満たしたらブレークしてそこからステップ実行するとか、局面の情報を流しこんでそこから実行再開とかしたいね。効率の良い開発のためには若干手を入れる必要がありそうだ。
** Gunbai Script
Gunbai Scriptは、キャラクタを動かすmove命令や、いろいろな情報を取得するための関数が用意されている、動的型付けのスクリプト言語だ。
ここの下の方にサンプルコードがいくつも載っているので、ざっと眺めるとつかみやすいかも。 https://samuraicoding.org/rules/
ifとかwhileとかbreakとかは普通にサポートされてるし、関数も作れるし、加減乗除やその優先順位も普通な感じ、特に習得に苦労する所は無さそう。
組み込みのデータ型としては「Array」があって、これは数値からArrayを含む任意の型へのマッピングを表現する。逆に言えばこれしかないので、これを使ってどう工夫するかが問われるかも。
興味深い点は、命令ごとに「コスト」が決まっていること。最近のCPUは高速化のために分岐予測だのキャッシュだの色々積んでいるので、同じ命令でも状況によって実行にかかる時間が変わるようになってしまった。そのせいで「このプログラムは2000msec以内に終わるはずだ」なんて判断ができなくなってしまった。「時間をぎりぎりまで使い切って最良の判断を目指すプログラム」なんてのが書きづらい。Gunbaiスクリプトは命令ごとに掛かるコストが決まっていて、リミットは2000に設定されている。この2000のタイムリミットが来た時点でプログラムの実行は終了され、最後に行ったmove命令が採用される。だから時間ギリギリまで使い切るカリカリチューニングができるわけだ、じゅるり(よだれ)
とはいえ「命令ごとにコストが決まっているとか、考えることが多くて大変そう」と思う人もいるかもしれない。心配しなくても、命令の種類がそもそもPDF半ページに収まるくらい少ないし、コストのつき方の種類はもっと少ない。
ざっくり説明するとこんな感じ：
- 0ステップ: alert(デバッグ出力)、return、ローカル変数の宣言、大部分の情報取得系API
- 1ステップ: 数値リテラル、Arrayの生成、大部分の文、演算
- 2ステップ: 乱数
- 関数呼び出しは、引数の個数×2
- 4ステップ: get_hexel_owner, get_agent_status
数値リテラルや加減乗除に1ステップ掛かるのを基準にすると、Arrayが1ステップなのはものすごく安いな。乱数も安い。一方でget_hexel_ownerが4ステップ掛かるから「まず全部の情報を収集して～」的なアプローチは辛いね。マップが20x30だとするとマップの状態を確認するだけで2400ステップ掛かってしまうのでアウト。どこの情報をチェックするべきか、に知恵を絞る必要がありそうだ。
2009-09-27
*1254024228*ダイコン
f:id:nishiohirokazu:20090927130214j:image
ワタシ
ダイコン
みたいな
カレ？
チキン
まじ軟弱
*1254041931*インクレディブルマシーン
img src=http://gyazo.com/4af2b4241e3faabf7de08955160da9b2.png
…なんだと？！