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（様々なバージョンのダウンロードやヒントなど）

2011-06-25

ICFP Programming Contest 2011

http://www.icfpcontest.org/

今年は会社の同僚と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 初参加のメンバーが何人かいたんですが、その人達が面白さを感じられるようもっと配慮してあげられたら良かったなと。

ともあれ、今回の問題は最高に良く出来てて楽しかったです。ジャッジの皆さん、参加者の皆さんお疲れさまでした。また来年お会いしましょう！

2011-06-16

そんなことより

明日からICFPCですよ。今年はチームで参加しまーす。

2011-06-16

Marathon Match 70

TopCoder

２年ぶりのマラソン。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&compid=16072&rd=14525 (要ログイン)

一本のDNA（A,T,G,C からなる文字列）と酵素の集合が与えられる。
酵素は固有のパターンを持っていて、そのパターンが現れた位置でDNAをカットする。
カット後のDNA片が与えられた条件を満たすような酵素の部分集合を求めよ。

条件は8種類。

DNA片の数の最小値。
DNA片の数の最大値。
DNA片の長さの最小値。
DNA片の長さの最大値。
DNA片の長さの比の最小値。長さが近すぎる２つのDNA片があったらダメ。
酵素のパターン長の最小値。
酵素の数の最大値。
DNA位置の範囲（0〜3つ）。指定された範囲内に少なくとも1つのカットが必要。

あとはDNAは環状になってるかもしれないとか、酵素は順方向と逆方向でマッチが可能とか細かいルールが色々。

得点

返した酵素の部分集合の数（最大１００個）が得点となる。ただし、実行時間が0.3秒を超えると得点が減っていく。

解き方

前処理部分と探索部分に分けて考える。

前処理

条件6を満たすそれぞれの酵素に対して、DNAをカットする位置を求める。
パターンマッチは酵素ごとにDFAを作った。いくつかの酵素はワイルドカードが多くてDFAの状態数が膨大になるので、それらについてはナイーブな strstr的方法で。改善の余地はだいぶあるけど、どうせ前処理部全体で0.1秒以内で終わるのであまりここは凝らなかった。

また探索を高速化するために、いろいろ計算しておく。