BlokusFS

ブロックスデュオのゲーム木をマウントできる 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 には使えないですが、ファイルシステムとして扱えると既存のツールで色々出来て楽しいです。

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