読者です 読者をやめる 読者になる 読者になる

8cc.unl

Unlambda

Unlambdaで動くCコンパイラができました。

https://github.com/irori/8cc.unl

id:shinichiro_hさんのbflispで使われている改造版8ccアセンブリ出力からUnlambdaへのトランスレータです。

これで同一のCプログラムをBrainfuckとUnlambdaの両方で動かせます。便利!

ただBrainfuckと比べてもかなり重くて、8ccのセルフコンパイルをすると10GB以上のメモリを消費して37時間かかりました。整数の表現が真偽値24個のリスト(もちろん真偽値もリストも関数で表現される)で結構でかいので、メモリを大量に使うプログラムだと厳しいようです。別の整数表現も試してみたんですが遅かったので断念しました…。

Lazy K でも同じようにやればできると思います。気が向いたらそのうち。

BfLazyK

Lazy-K

Lazy K のオリジナルの配布物には bf2lazy.c というファイルが含まれていて Brainfuck プログラムを Lazy K にコンパイルできるのですが、逆に Brainfuck で Lazy K のプログラムを動かす方法はこれまで存在しませんでした。Lazy K で Brainfuck の配列のようなものは比較的簡単に実現できるのに対し、Lazy K の実行はポインタを含む小さなオブジェクトを作っては捨て、作っては捨て…という感じになるので Brainfuck で実現するのは明らかに大変そうです。現実的な速度で動かすのは無理かもしれません。

ところが id:shinichiro_h さんがなんと Lazy K どころか Lisp が動くインタプリタBrainfuck で作ってしまいました。16bit の仮想マシンを定義してそのアセンブリから Brainfuck に変換するというもので、便利なことに仮想マシンアセンブラコードを生成するCコンパイラまで使えます。

Lisp が動くなら Lazy K も動くだろ、ということで以前作った Lazy K インタプリタを仮想 16bit マシン環境で動くようにして Brainfuckコンパイルしてみました。

https://github.com/irori/bflazyk

手を入れたのは主にメモリ管理の部分で、ヒープ領域を固定にしたのと、値の表現でポインタか即値データかを下位ビットで判断していたのを数値比較にした(ビット演算が重いので)のが大きな変更です。 ヒープ領域は 48k ワードありますが、Copying GC のために2分割して片方しか使わないのでメモリ制限は厳しめです。どのくらい厳しいかというと剰余を使うアルゴリズムFizzBuzz を動かしたら 50 あたりでメモリ不足になってしまいました。

実行速度ですが、生成された .bf を bflisp 付属の bfopt.cc で C に変換して gcc で -O なしでコンパイルしたところ Hello, world が48秒、FizzBuzz が22分でした。

lazy2c スクリプトは Lazy K プログラムを埋め込んだインタプリタの .c ファイルを生成します。これを C → Brainfuckコンパイラと組み合わせることで、Lazy K から Brainfuckコンパイラとして使えます。さらに hs2lazy と組み合わせると Haskell から Brainfuck への(超非効率な)コンパイラになりますね。*1

*1:ちなみに Haskell から Brainfuck へ直接変換するコンパイラがあるようです http://www.xanxys.net/hs2bf/

BlokusFS

Blokus

ブロックスデュオのゲーム木をマウントできる FUSE ファイルシステムを作りました。

https://github.com/irori/BlokusFS

使い方

チェックアウトして src ディレクトリ内のソースをコンパイルします。 FUSE の開発用ライブラリが必要です。

$ sudo apt-get install libfuse-dev   # Ubuntuの場合
$ git clone https://github.com/irori/BlokusFS.git
$ cd BlokusFS
$ make -C src

src/blokusfs にマウントポイントを与えて実行します。

$ mkdir mnt
$ src/blokusfs mnt

これでマウントできました。忘れないうちに書いておくと、使い終わったら fusermount コマンドでアンマウントします。

$ fusermount -u mnt

マウントした状態では mnt の中に大量のディレクトリといくつかのファイルが見えます。

$ src/blokusfs mnt  # もう一度マウント
$ ls -px mnt
35j2/  35k2/  35k7/  35l2/  35l7/  35o3/  35o6/  35q0/  35q2/
44k1/  44k6/  44l1/  44l6/  44m1/  44m6/  44n1/  44n6/  44p0/
...
75j2/  75k3/  75k6/  75l3/  75l6/  75o2/  75o7/  75q1/  75q3/
board  piece  score  value

このファイルシステムでは各ディレクトリがゲームの状態を表していて、ルートディレクトリは初期状態(ピースがまったく置かれていない状態)に対応します。 子ディレクトリは初期状態から先手が打てる手の 4文字コードです。

例えば mnt/66t0 は先手が 66t0 を打った状態になり、その子は後手が選択できる手になります。

$ ls -px mnt/66t0
8Aj2/  8Ak2/  8Ak7/  8Al2/  8Al7/  8Ao3/  8Ao6/  8Aq0/  8Aq2/
99k1/  99k6/  99l1/  99l6/  99m1/  99m6/  99n1/  99n6/  99p0/
...
CAj2/  CAk3/  CAk6/  CAl3/  CAl6/  CAo2/  CAo7/  CAq1/  CAq3/
board  piece  score  value

各ディレクトリにあるファイル board は盤面の状態、piece は各プレイヤーの手持ちピース、score は現在のスコア(置いたマスの数)です。value は盤面の評価値(後述)です。

$ cat mnt/66t0/board
..............
..............
..............
..............
....1.........
....111.......
.....1........
..............
..............
..............
..............
..............
..............
..............
$ cat mnt/66t0/piece
a b c d e f g h i j k l m n o p q r s u
a b c d e f g h i j k l m n o p q r s t u
$ cat mnt/66t0/score
5
0
$ cat mnt/66t0/value
-56

piece と score は1行目が先手、2行目が後手です。

子ディレクトリを辿っていくことでゲームが進んでいきます。子がないディレクトリに到達したところでゲーム終了です。

ブロックスデュオのゲーム木の大きさは 1070 〜 1080 と推定されていますが、これで歩きまわり放題ですね!

評価値

各ディレクトリの value ファイルには、盤面の評価値を hmmm の評価関数で計算した値が入っています。 ただし、後手番のディレクトリでは値の符号を反転しています。つまり先手番では評価値が大きいほうが先手有利、後手番では評価値が大きいほうが後手有利です。これによって探索のコードが簡単になります。

評価値は board ファイルと piece ファイルから計算できるのでファイルシステムに含めなくても良かったんですが、あると便利なので…。

AIを作る

ゲームのルールと評価関数はファイルシステムに組み込まれているので、探索ルーチンを書くだけで AI が作れます。 ファイルシステムにする一番のメリットは言語に依存しなくなることで、ファイルの読み込みとディレクトリの一覧取得ができる言語ならなんでも使えます。 とりあえずシェルスクリプトで書いてみました。

上がネガマックス法、下がネガアルファ法を実装したものです。探索したい局面のディレクトリと探索深さを引数にして実行すると、探索の結果最善と思われる手を出力します。

$ time ai/negaalpha.sh mnt/66t0 2
8Aj2 71
8Ak2 62
8Ak7 51
8Al7 48
9Bk3 47
9Bl3 46
9Bl3
ai/negaalpha.sh mnt/66t0 2  0.97s user 0.98s system 44% cpu 4.362 total

最後の 9Bl3 以外は stderr に出力される途中経過です。

さてシェルスクリプト版は案外簡単に書けてしまったので、別の言語も試してみることにしました。 Makefile です。(GNU make 専用)

$ time make -f ai/negaalpha.mk DIR=mnt/66t0 DEPTH=2
-46 -46 99999 9Bl3  # stderr出力
9Bl3
make -f ai/negaalpha.mk DIR=mnt/66t0 DEPTH=2  0.46s user 0.94s system 15% cpu 9.251 total

ネガマックス版の negamax.mk を解説してみます。コーナーケースの処理等を省くとこんな感じになっています。

depth-1 := $(word $(DEPTH), 0 1 2 3 4 5 6 7 8 9)

ifeq ($(MAKELEVEL), $(depth-1))

negamax: $(DIR)
  sort -n $(DIR)/*/value |head -n1

else

subdirs := $(wildcard $(DIR)/????)
.PHONY: negamax $(subdirs)
tempfile := $(shell mktemp)

negamax: $(subdirs)
  sort -r -n $(tempfile) |head -n1 |sed -e 's/^/-/' -e 's/^--//'
  rm $(tempfile)

$(subdirs):
  $(MAKE) DIR=$@ -f ai/negamax.mk >>$(tempfile)

endif

どうでもいいけどシンタックスハイライト激しすぎですね…。

変数 DIR と DEPTH は外から与えられます。1行目では「depth-1」という名前の変数を定義しています。 DEPTH から 1 を引いた値にしたいのですが、組み込みの算術演算がないので word 関数を使っています。 特殊変数 MAKELEVEL には make の再帰呼び出しの深さが入っているので、例えば DEPTH が 3 なら 2 回目の再帰 (sub-sub-make) で 5 行目の negamax ルールが実行されます。 この場合、DIR のサブディレクトリすべての value ファイルの中で一番小さい値が出力されます。 MAKELEVEL が DEPTH に等しい時に value ファイルを cat したほうが単純ですが、高速化のために一段浅いところで処理しています。

MAKELEVEL が depth-1 より小さい場合は、各サブディレクトリに対して再帰します。$(MAKE) で始まる行がそれで、結果はテンポラリファイルに追記されていきます。 すべての再帰呼び出しの結果が集まったら、negamax ルール(else の中のほう)が実行されて評価値が最大のものが選ばれ、符号反転して出力します。 実際は MAKELEVEL が 0 のときは最大の評価値のディレクトリ名をかわりに出力するなどの処理が入っています。

ちなみに negamax.mk は再帰を並列実行可能なので、マルチコア環境では make に -j オプションをつけると探索が速くなります。

一方ネガアルファ版の negaalpha.mk はループの各実行で α, β の値を受け渡していく必要があるため -j は使えません。 make の変数もループ中に変化させることはできないので、テンポラリファイルに(今までの最良の評価値、α、β、最良の手の4文字コード)の組を入れて awk で頑張るという遅そうな実装になっています。βカットが起こると make の実行が中断されるため何やらエラーっぽいのが出力されますが気にしないでください。

遊ぶ

interface/play ファイルはゲームのフロントエンドです。100行足らずのシェルスクリプトですが、いっちょまえに盤面を色付きで表示したりします。 オプションで AI のプログラムを指定して対戦できます(自分の手は4文字コードを入れないといけないので大変ですが…)。

$ interface/play -v ai/negaalpha.sh -o "make -f ai/negaalpha.mk" mnt

などとすると、シェル対 make の対戦が見られます。

感想

さすがに遅いので本格的な AI には使えないですが、ファイルシステムとして扱えると既存のツールで色々出来て楽しいです。

あと使い終わったらアンマウントしておきましょう。忘れていたらバックアップスクリプトが走ってえらいことになりました。

ICFP Programming Contest 2014

http://icfpcontest.org/

うーん今年はあまりうまくいきませんでした。

今年の題材はパックマンで、プレイヤー側の AI を SECD マシン風のコードで、敵側を普通の 8 ビット CPU 風のコードで書けというもの。

金曜の夜は問題文(やたら長い)を読んでコードは書かず就寝。いつものパターンなら朝になると仕様のバグが取れてやりやすくなっているはず。

土曜はとりあえず順当に Lisp 風言語から AI CPU へのコンパイラを書く。SICP を引っ張り出してきて末尾再帰のやりかたを復習したり。それなりに動くコンパイラができたのが午後 3 時くらいで、そこから 6 時間で lightning division 用の AI を書く。方針としては、

  • マップの各マスを通った回数を覚えておいて、一番少ない方向に進む
  • 自分から直線上に敵がいたらそちらへは進まない

という感じ。Lightning division が終わって追加のタスク(敵側の AI を書く)が発表されたので、方針を考えつつ寝る。

日曜は敵側 CPU 用のアセンブラと AI を書く。適当にプレイヤーを追いかけるようにしたら前日に書いた AI が思ったより弱いことがわかってしょんぼり。プレイヤー側の AI にちびちび修正を入れるがあまりうまくいかない。AI の作り方とかよくわからんのよね……。このあたりから集中力が切れてきて、だらだらし始める。

月曜起きるとスコアボードができていた。自分の AI を送ってみるも全然ダメでしょんぼり。外はいい天気だなあ、有給だし遊びに行こうかなあ。

そんな感じでしょんぼりなまま終了。提出物はこちらになります。

今回は手も足も出なかった(というほどでもないけど)ので、上位チームはどんな AI を書いてたのか気になります。やっぱり真面目にゲーム状態を計算してたりするんでしょうか。自分は tick の計算とか面倒で逃げちゃったんですが。

Lazy K で Lisp インタプリタ

Lazy-K

https://github.com/irori/lazyk-lisp
http://lazy-k.appspot.com/p/ptHm_GwfAY

Lazy K でも Lisp インタプリタを作ってみました。

機能は Unlambda 版とだいたい同じですが call/cc が無くなり、代わりに set でグローバル変数に代入できるようになりました。局所変数の書き換えは大変すぎるので断念しました…。

今回はジェネレータとして、以前作った Haskell → Lazy K トランスレータを使いました。200 行ほどの Haskell コードを変換して 300kb の Lazy K プログラムになりました。ジェネレータの抽象度が高い分、Unlambda 版よりかなり大きくなってしまいました。一方インタプリタのコーディングは単なる Haskell なのでこっちの方が楽でした。(モナドが使えないとか let でパターンが使えないとか、エラーメッセージが殆どノーヒントとか色々制限はありますが。)

ちなみに lisp.hs は正しい Haskell プログラムなので、GHC でもコンパイルできます。当たり前ですがコンパイルしたものはずっと速いです。

遅い理由のひとつはシンボルを文字列のまま扱ってるからで、Unlambda 版と同様にシンボルテーブルを作って整数比較で済むようにすればもう少し速くなると思います。

Unlambda で Lisp インタプリタ

Unlambda

https://github.com/irori/unlambda-lisp

3 連休だったので Unlambda で Lisp インタプリタを作ってみました。

Adventure を作ったときのコードジェネレータを流用して、今回新たに書いたコードは 400 行ちょっとでした。生成された Unlambda プログラムは 35kb ほど。

構文は quote, if, lambda, defun が、組み込み関数は基本的なリスト用関数 (cons, car, cdr) と四則演算が使えます。代入はありませんが、代わりに call/cc を使えるようにしてみました。数値は非負整数のみ使えます。内部表現はチャーチ数なので大きい数を作ると大変なことになります。全体的にエラー処理が甘いので壊れた式を入れるとおかしくなりがちです。

次回は Lazy K で Lisp インタプリタを作る予定です。