[どうぶつしょうぎ] 完全解析ツールの checkState で最善手順を求める

田中先生による完全解析結果のページには、 先手の４つの初手からの最善手順しか掲載されていないので、 それ以外の手順は自分で解析ツールを実行する必要がある。

• 「どうぶつしょうぎ」の完全解析
  東京大学情報基盤センター 田中先生

解析ツールは 田中先生の完全解析結果のページからダウンロードできる。

Unix 系なので 久しぶりに Amazon EC2 の Amazon Linux を使ってみた。
マイクロインスタンスなので CPU パワーはないが、 局面解析をするわけではなく、解析結果を使って最善手を探すだけなのでこれで十分。

---

ソースとデータファイルを入手する。

ソースコードとデータファイルをダウンロードする。

wget http://media.itc.u-tokyo.ac.jp/ktanaka/dobutsushogi/dobutsu-src.tar.gz
wget http://media.itc.u-tokyo.ac.jp/ktanaka/dobutsushogi/dobutsu-dat.tar.gz

ソースファイルのアーカイブは139KB 程度だが、データファイルの方はアーカイブしてあっても537MBある。

ソースを展開するとこんな感じ。

[dobutu-shogi]$ tar xzvf dobutsu-src.tar.gz
dobutsu/
dobutsu/testAll.cc
dobutsu/maxbf.cc
dobutsu/winLoseTable.cc
dobutsu/makeAllState.cc
dobutsu/longestWin.cc
dobutsu/makeCheckmate.cc
dobutsu/allStateTable.h
dobutsu/allStateTable.cc
dobutsu/checkcsa.cc
dobutsu/findDropBaby.cc
dobutsu/Makefile
dobutsu/checkState.cc
dobutsu/move.cc
dobutsu/dobutsu.h
dobutsu/checkCheckState.cc
dobutsu/dobutsu.cc
dobutsu/countReachable
dobutsu/makeWinLose.cc
dobutsu/stateTable.cc
dobutsu/winLoseTable.h
dobutsu/move.h
dobutsu/findZugZwang.cc

---

Make する

展開したソースファイルを make する。

[dobutsu]$ make
-bash: make: command not found

やられた。make も入っていないとは。

[dobutsu]$ sudo yum install make
...
[dobutsu]$ make
g++-4.3 -Wall -Wno-deprecated -DNDEBUG -O3 -c -o makeAllState.o makeAllState.cc
make: g++-4.3: Command not found
make: *** [makeAllState.o] Error 127

gcc と g++ をインストールする。

[dobutsu]$ sudo yum install gcc
[dobutsu]$ sudo yum install gcc-c++

gcc は4.6.2 がインストールされたみたい。
Makefile ではコンパイラに g++-4.3 が指定されているので、g++ に変更

#CXX = g++-4.3
CXX = g++

再度 make する。
警告がいっぱいでたがビルドはできたようだ。

---

データファイル展開

ダウンロードしたデータファイルを展開する。

[dobutu-shogi]$ tar xzvf dobutsu-dat.tar.gz
dobutsu/allstates.dat
dobutsu/winLoss.dat
dobutsu/winLossCheck.dat
dobutsu/winLossCheckCount.dat
dobutsu/winLossCount.dat

[dobutsu]$ ls -l --block-size=1M *.dat
-rw-r--r-- 1 ec2-user ec2-user 1883 Jun 29  2009 allstates.dat
-rw-r--r-- 1 ec2-user ec2-user  236 Jun 29  2009 winLossCheckCount.dat
-rw-r--r-- 1 ec2-user ec2-user  236 Jun 29  2009 winLossCheck.dat
-rw-r--r-- 1 ec2-user ec2-user  236 Jun 29  2009 winLossCount.dat
-rw-r--r-- 1 ec2-user ec2-user  236 Jun 29  2009 winLoss.dat

３GB近いとは。
ディスク８Ｇなのに。

[dobutsu]$ df
Filesystem   1K-blocks      Used　 Available  Use%   Mounted on
/dev/xvda1     8361916   4672124     3605928   57%   /
tmpfs           304796         0      304796    0%   /dev/shm

よかった。まだ半分近く余ってた。

データファイルの展開が終わった段階で以下のファイルができている。

この中で主に使うのはcheckStateコマンド。
checkState コマンドで、解析結果データファイルをもとに指定した局面からの 最善手順を求めることができる。

---

checkState コマンドで指定局面からの最善手順を求める。

指定した局面からの最善手順を求めるには checkState コマンドを使用する。
先ほど展開したデータファイルに全局面の解析結果がおさめられていて、 そこから最善手を求めるだけなので時間はかからず瞬時に答えが返ってくる。

まず、最善手順を求める局面ファイルを作成する。
初期局面は以下のようになる。

-KI-LI-ZO
 . -HI . 
 . +HI . 
+ZO+LI+KI
000000
+

フォーマットは 田中先生のページ にも記載されているが以下の型式。

• 1-4行目が盤面。１マスは３文字で表す。
  「+」(先手)または「-」(後手)一文字と駒の種類を表す2文字。
  空マスは「 . 」(スペース, ピリオド, スペース)
  
• 5行目の6つの数字は持ち駒の数。左から「先手のひよこ，ぞう，きりん」、
  「後手のひよこ，ぞう，きりん」
• 6行目は手番を表す。「+」：先手，「-」：後手

盤面行は必ず９文字。余計な空白があったり、空きマスのスペースが足りなかったりするとエラーになる。
フォーマットのチェックはかなり厳しい。

先手一手損ぴよ替わり（▲Ｂ２ひよこ、△同ぞう、▲Ｂ３ぞう）から互いにキリンが上がった局面は 以下のようになる。

 . -LI .
-KI-ZO .
 . +ZO+KI
 . +LI .
100100
-

実行してみよう。
checkState 実行時には引数に先ほど作成した局面ファイルを指定する。

[dobutsu]$ ./checkState data/B3B2HI-C4C3KI.txt
------------------
 . -LI .
-KI-ZO .
 . +ZO+KI
 . +LI .
100100
-

-1(44)
0 : -00A4HI 1(22)
1 : -00A3HI 1(30)
2 : -A2A3KI 0(0)
3 : -B2A3ZO 0(0)
4 : -00A1HI 1(34)
5 : -B1A1LI 1(44)
6 : -A2A1KI 1(66)
7 : -B2A1ZO 1(70)
8 : -00C4HI 1(22)
9 : -B2C3ZO -1(43)
10 : -00C2HI 1(20)
11 : -B1C2LI 1(0)
12 : -00C1HI 1(32)
13 : -B1C1LI 1(18)
14 : -B2C1ZO 1(58)
Move : -B2C3ZO -1(43)
------------------
 . -LI .
-KI .  .
 . +ZO-ZO
 . +LI .
100101
+

-1(43)
0 : +00C1HI 1(0)
1 : +00C2HI 1(0)
....
....

こんな感じでコンソールに結果が出力される。
標準出力ではなく標準エラー出力に出力されているので、
出力結果をファイルに落とす場合には、

[dobutsu]$ ./checkState data/B3B2HI-C4C3KI.txt 2> result.txt

とする必要がある。

次回、これを使っていくつか代表的な手順を見てみる。