「どうぶつしょうぎ」の完全解析

田中哲朗

女流棋士の北尾まどか初段によって考案されたボードゲー ム どうぶつしょうぎ(Wikipedia: どうぶつしょうぎ) の初期局面 から(相手のライオンを取れる時は必ず取るという条件で)到達可能な局面すべ てを求め，後退解析(retrograde analysis)により，すべての局面の「勝ち」/ 「引き分け」/「負け」と双方最善を尽くした時の手数を求めるプログラムを作成 しました．

ゲーム情報学研究会での発表について

2009年6月26日に開催された第22回ゲーム情報学研究会で発表した際の資料と，プレゼンテーション資料を置きます． なお，資料の図5に誤りがあります．正しい図は，

となります． また，参考文献として2009年6月時点で「どうぶつしょうぎ」のオフィシャルサイト を記載しましたが，現在は有効ではないようです．

プログラム

dobutsu-src-20150109.tar.gzを展開すると，dobutsuというディレクトリができます．その下のMakefileを適当に修正してmakeするといくつかの実行ファイルができます．以下に簡単な説明を書きます
makeAllState
初期配置から到達可能な局面(64bit)のソート済みの配列を作成し，allstates.dat というファイルに出力します．実行には，14GB程度のメモリが必要なので，普通の人はこのプログラムは実行せずに，データファイルをダウンロードして使うのが良いでしょう
makeWinLose
後退解析により，各局面の勝敗を記録する配列，勝敗に要する手数を記録 する配列を作成し，winLoss.dat, winLossCount.dat というファイルに出力し ます．メモリは3GB程度で動きますが，実行は数時間(Opteron 2.6GHzのマシン で5.5時間)かかります．普通の人は，このプログラムは実行せずに，データファ イルだけをダウンロードして使うのが良いでしょう．
checkState
csa棋譜形式風に書かれた局面ファイルを読み込んで，引き分け以外の局面の時は勝つ側は最短の，負ける側は最長の手を選んだ場合の終局までの手順を出力します．

たとえば，初期局面ファイルinit.txtの内容は以下のようなものですが， 

-KI-LI-ZO
 . -HI . 
 . +HI . 
+ZO+LI+KI
000000
+
意味は，以下のようになります． また，出力中に「+B4C3LI」のような7文字での手の表現が現れますが，これは，最初の1文字が手番，次の2文字が移動元のマス(00の時は持駒から)，次の2文字が移動先のマス，最後の2文字が駒の種類(ただし，ひよこからにわとりに成る手の時はNIとする)となります．実行例を示します．
checkcsa
1行に1手ずつ並んだ棋譜ファイルを読み込んで，どこで勝敗が入れ替わった かを表示するプログラムです．詳細は省略します．
findDropBaby
発表資料中で説明した「敵陣へのひよこ打ちが有効な局面」を捜すプログラムです．詳細は省略します．
findZugZwang
発表資料で説明した「ZugZwang局面」を捜すプログラムです．詳細は省略します．
longestWin
最長手数での勝ち局面を捜すプログラムです．
maxbf
分岐数を数え，最大値を更新するたびに局面を表示するプログラムです．
makeCheckmate
後退解析により，各局面に詰みがによる勝ち負けがあるかを記録する配列，詰みによる勝ち負けに要する手数を記録する配列を作成し，winLossCheck.dat, winLossCheckCount.dat というファイルに出力します．
checkCheckState
局面ファイルを読み込んで，詰みのある局面では詰み上がりまでの手順を出力します．
testAll
UnitTest用プログラム

データ

上記のプログラムを動かすのに必要なデータファイルです．　 dobutsu-dat.tar.gz(圧縮しているが約560MB)を展開すると以下のファイルができます．プログラムと同じディレクトリに置く必要があります．　 
dobutsu/allstates.dat
dobutsu/winLoss.dat
dobutsu/winLossCount.dat
dobutsu/winLossCheck.dat
dobutsu/winLossCheckCount.dat

ライセンス(2015年1月9日追加　)

ライセンス表示がないという指摘があったので，二条項BSDライセンスのライセンスファイルを配付プログラムに含めるように変更しました．データに関しても同じライセンスが適用されます．