Lazy K Playground
Lazy K もブラウザ上で実行できるようにしたいなぁ、でも JavaScript でインタプリタ実装するの面倒だなぁ、と思っているうちに世の中が進歩して簡単になったので作ってみました。
いくつか例を。
http://lazy-k.appspot.com/p/kyYMG82oRh
http://lazy-k.appspot.com/p/2koJ2YQ9fD
App Engine はコードの保存のために使っているだけで、実行はブラウザ上で行われます。バックグラウンドでインタプリタを動かすのに Web Workers を使っている関係で IE9 以前では動きません。ごめんなさい。
適当なベンチマークもしてみました。ベンチマークといえば円周率、ということで円周率を100桁計算するプログラムです。
http://lazy-k.appspot.com/p/jMQX90iL_S
手元のマシンでは以下のような結果になりました。
| Firefox 22 | 80.1 sec. |
| Chrome 27 | 97.4 sec. |
| IE 10 | 314 sec. |
| ネイティブ (lazyk.c) | 39.0 sec. |
よく言われている通り asm.js に最適化された Firefox 22 ではネイティブの倍程度の実行時間になりました。Chrome も健闘してますね。
JavaScript Unlambda interpreter
http://inazz.jp/unlambda/
inazz さんがブラウザ上で動く Unlambda インタプリタを作っておられます。
実行中の式を表示しながらステップ実行できます。しかも速いです。 Adventure がサクサク動いてびっくりしました。
ICFP Programming Contest 2012
http://icfpcontest2012.wordpress.com/
今年は一人で参加してました。
問題は 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 力を上げておけばよかったのか…！
仕様変更に関しては、ゆるい作りにしていたお陰でそれほど困りませんでした。最適化が終わってからひっくり返されてたら発狂してたかもしれませんが。
次回はあまりマラソンっぽくない問題がいいなー。
Adventure in Unlambda 解説 その1
Adventure in Unlambda のコード解説です。（ゲームのネタバレはありません。）
続きを読むAdventure in 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（様々なバージョンのダウンロードやヒントなど）
ICFP Programming Contest 2011
今年は会社の同僚と6人で、チーム名 widecat で参加しました。
成績は…よくわかりません。けっこう相性で勝敗が決まるので。とりあえず上位30チームの決勝には残れてるんじゃないかと思います。
AIの戦略
開始直後はまず、復活用の魔法を準備します。
- 1 ターンで発動し、スロット 0〜82 を revive、さらに inc する
- 1 ターンで発動し、スロット 192〜255 を revive、さらに inc する
この2種類を用意し、さらにそれぞれのコピーを作っておきます。使うときはコピーの方を使い、オリジナルから複製し直すことで作り直しの手間を少なくしています。
inc で体力を 2 まで回復させているのは、生き返らせたあとに dec ですぐまた殺されるのを防ぐためです。まあ 2 回 dec されるとアウトなんですが。
これを作り終わるまで 75 ターン。その頃には 255 が殺されていることも多いですが、敵のゾンビの初撃には十分間に合います。
次に attack 0 0 8192, attack 1 0 8192 で相手の 255 を殺します。もちろんゾンビを送り込むためです。
その後ゾンビを作ります。こんなコード。
f = '(\i. help i i 8192)' # f i = help i i 8192 g = '(S %s succ)' % f # g n = f n; return n+1 twice = '(S (S (K S) K) I)' # twice f x = f (f x) x256 = '(S (S I I) (S I I) %s)' % twice # x256 f x = f^256 x gx256 = '(%s %s)' % (x256, g) # gx256 x = g^256 x make_zombie = "\start. zombie 0 (S (K %s) (K start))" % gx256
これで make_zombie に数値を適用すると、その番号のスロットから順番に help で殺していく (1 回に 82 体ほど殺せる) ゾンビを敵の 255 番スロットに送り込みます。
このゾンビコードの構築には 110 ターンほどかかります。ちょっと遅いですね。
ゾンビの挙動は自分のスロットに入れておいて、copy で持ってくるというのが定石だったみたいですが、うちのチームは最後まで気づきませんでした。
何もしない敵を倒すには結局 292 ターンほどかかっていました。
やったこと
主に式からコマンド列へのコンパイラを書いてました。
あとチーム内で SKI 経験者（って何だ）は自分だけだったので、S (K f) (K x) で遅延できるよーとかイディオム的なのを紹介したり。
他には AI の回復系の処理を作ったり、他のメンバーが書いた式を軽くゴルフして縮めたりしてました。
感想
チーム参加ってどんな感じだろうと思って初チーム参加だったわけですが、良い点も悪い点も色々見えて興味深かったです。
まず戦略考えるのは複数人のほうが絶対いいですね。自分じゃ思いつかないようなアイデアもいくつかありました。
それと、下回りを作ってくれる人がいると楽だなーと思いました。今回はシミュレーターとか各種ツールをかなりしっかりと作ってくれていて、快適に作業できました。
逆に個人参加のほうが良かった点は、当たり前ですが一人当たりのパフォーマンスは個人参加のときのほうが高かったなあと。昼も夜もなく、コーディングしては寝て、目が覚めたらまたコーディング…という濃密な 72 時間が ICFPC の醍醐味だと思うのですが、今回は昼間はチームで集まって作業、夜は自宅で寝るというスタイルだったのでそんな感じではなかったです。合宿形式だったらまた違ったかもしれませんが。
あとチームで分業するにはあらかじめタスクを分割しておかないといけないので「作りながら考える」方式が使いにくいなあと思いました。一人のほうが早く作り始められるので、実は lightning division は一人でも勝ち目があるのかも。
あとこれは今回の反省点ですが、ICFPC 初参加のメンバーが何人かいたんですが、その人達が面白さを感じられるようもっと配慮してあげられたら良かったなと。
ともあれ、今回の問題は最高に良く出来てて楽しかったです。ジャッジの皆さん、参加者の皆さんお疲れさまでした。また来年お会いしましょう！
