問題は Boulder Dash 風のゲームを解く AI を作れというもの。TopCoder のマラソン(Marathon Match)にありそうな問題だなーという印象でした。マラソンと違うのは、コンテストの途中でルールの追加が予告されていることと、スコアボードがないので終了まで他のチームの状況がわからないこと。

え、じゃあ適当なマラソンに参加したほうが楽しいんじゃ…などということは考えないようにして、金曜の夜はシミュレータを実装して終わり。

土曜は朝起きたら最初の仕様追加（マップが水没していく）がアナウンスされていたのでシミュレータに実装して、後は lightning division 用に適当な局面評価で探索するソルバーをでっちあげました。

日曜起きると、新たにルールが２つ追加されていました。トランポリンとヒゲ。何だヒゲって。とりあえず追加仕様は置いておいて、寝ている間に思いついた(?)詰み検知ルーチンを実装。やっとまともに問題が解けるようになってきました。

引き続きトランポリンとヒゲの対応をシミュレータと AI に組み込んで、再度全マップを試してみたら contest*.map が解けなくなってる…。初めて git bisect のお世話になりました。これはいかんと思いテストスクリプトを整備。

そうこうしているうちに、次の追加ルールが発表されました。高階岩。これを実装して日曜は終了。

最終日はちょっとモチベーションの維持に失敗した感じでした。だらだらと AI のパラメータをチューニングして、大きいマップで壊れないようにして、駆け込みで幾つかのハックを追加して提出。

提出したソースコード。

配布されたマップでの成績はこんな感じでした。得点/ハイスコアの平均は86%。

マップ	得点	ハイスコア
contest1.map	212	212
contest2.map	281	281
contest3.map	275	275
contest4.map	575	575
contest5.map	1297	1303
contest6.map	1177	1177
contest7.map	869	869
contest8.map	1915	1973
contest9.map	3083	3095
contest10.map	3588	3634
flood1.map	945	945
flood2.map	281	281
flood3.map	846	1303
flood4.map	653	1594
flood5.map	575	575
trampoline1.map	426	426
trampoline2.map	1742	1742
trampoline3.map	554	5477
beard1.map	860	860
beard2.map	4461	4522
beard3.map	628	1789
beard4.map	1830	3103
beard5.map	655	946
horock1.map	745	762
horock2.map	747	747
horock3.map	1582	2406

感想

なんだか不完全燃焼な感じで終わってしまいました。ネタに走るという方向も一瞬考えたのですが、今回の問題で Unlambda とかで何かするのはちょっと難しそうなので諦めました。Befunge 力を上げておけばよかったのか…！
仕様変更に関しては、ゆるい作りにしていたお陰でそれほど困りませんでした。最適化が終わってからひっくり返されてたら発狂してたかもしれませんが。
次回はあまりマラソンっぽくない問題がいいなー。

2011-12-26

Adventure in Unlambda 解説その2

Unlambda

前回の続きです。今回は Adventure のゲーム部分の実装について解説します。

2011-12-18

Adventure in Unlambda 解説その1

Unlambda

Adventure in Unlambda のコード解説です。（ゲームのネタバレはありません。）

2011-12-10

Adventure in Unlambda

Unlambda

世界最初のアドベンチャーゲームであり、「アドベンチャー」ゲームというジャンルの語源ともなった Colossal Cave Adventure を Unlambda に移植しました。

advent-unlambda.tar.gz (github)
（2011/12/15 ソースコードが一部抜けていたのを修正しました）

コードサイズは約 600KB で、自分の知る限り最も大規模な Unlambda プログラムです。

Colossal Cave Adventure

Colossal Cave Adventure（Adventure, ADVENT とも言われる）は 1976-77 年に William Crowther と Don Woods によって書かれました。画像はなく文字のみで、表示されるメッセージをたよりに 1-2 語の簡単な英語でコマンドを打ち込んでゲームを進めていきます。
以下は Adventure 序盤のスクリーンショット(?)です。

Welcome to Adventure!!  Would you like instructions?
** no

You are standing at the end of a road before a small brick building.
Around you is a forest.  A small stream flows out of the building and
down a gully.
* east

You are inside a building, a well house for a large spring.
There are some keys on the ground here.
There is a shiny brass lamp nearby.
There is food here.
There is a bottle of water here.
* take keys
OK.
* eat food
Thank you, it was delicious!

現在ではこのようなスタイルのゲームはテキストアドベンチャー、あるいは海外ではインタラクティブ・フィクションと呼ばれています。

Unlambda 版

Adventure にはいくつもの派生版、移植版がありますが、この Unlambda 版は 350 point version と呼ばれるオリジナルを Donald Knuth 教授が文芸的プログラミングで書きなおした CWEB版を元にしています。

Unlambdaインタプリタは Emil Jerabek 氏のものが速くておすすめです。Unlambda 2.0.0 付属の c-refcnt インタプリタでも十分動作します。

ゲームについて

なにぶん昔のゲームなので難易度は高めです。といっても警告なしに理不尽に死んだりはしないので、いろいろ試してみるといいでしょう。google:Colossal Cave Adventure でググるとマップやヒントが見つかります。詰まったらネタバレを見てしまうのもいいでしょう。

ゲームの基本的な目的は洞窟から宝物を持ち帰ることです。宝物はスタート地点から見える建物の中に置くと得点になります。満点の 350 点を目指しましょう。

以下はコマンドの一部です。コマンドを探すのもゲームの楽しみなので、基本的なもののみ紹介します。

NORTH (N), SOUTH (S), WEST (W), EAST (E), UP (U), DOWN (D), NW, NE, SW, SE: 指定した方向に進む。コマンドは最初の5文字しか認識しないため、NORTHEAST と打つと NORTH の意味になってしまうので注意。
BACK: 前にいた場所に戻る。（戻れない場合もある）
LOOK (L): あたりの様子を表示する。
TAKE (GET): 指定したものを取る。
DROP: 指定したものを置く。
INVENTORY (I): 持っているものの一覧を見る。
LAMP ON: ランプを点ける。
LAMP OFF: ランプを消す。
SCORE: 現在の得点を見る。
QUIT: ゲームを終了する。

look と inventory のショートカット L と I は本家 Adventure では使えませんが、以降のテキストアドベンチャーでは標準的なコマンドであり便利なので追加しました。

コードについて

実装に使ったテクニックなどは、こちらの記事で紹介しています。
Adventure in Unlambda 解説その1
Adventure in Unlambda 解説その2

参考リンク

wikipedia:アドベンチャーゲーム
 wikipedia:en:Colossal Cave Adventure
The Colossal Cave Adventure Page（様々なバージョンのダウンロードやヒントなど）