どうぶつしょうぎ

https://www.joshi-shogi.com/ec/bankoma/animal.html

ほうほう、これは面白そう。どうぶつしょうぎ・ルール概要 (1DAYトーナメント｜日本女子プロ将棋協会)



とりあえず作った。ふむ、これは駒の少なさの割には意外と考えられているなぁ。

後退解析をやるとする。とりあえず「敵が入玉したがそれを取ることができない」と「自分が取られた」が負け局面なんだな。

ああ、だめだ。後退解析は単調減少な特徴量がないと使えないらしい。CiNii - Retrograde Analysis of Dodgem Game

いや、まてよ。CiNii - Complete Analysis of a Board Game "SIMPEI"(Analysis, Game Programming)には単調減少な特徴量はないよな。そっか、単調減少な特徴量があれば、その特徴量を使ってゲームの局面を「一方通行な」いくつかのグループに分割することができるというのが前者の話で、「シンペイは状態空間が小さいから全体を一つのグループとして後退解析できてしまう」というのが後者の話か。

きちんとどうぶつしょうぎの状態数を計算してみよう。まず、ライオンが先手が12ヶ所のうちのどこか、後手が残り11ヶ所のうちのどこか、で132通り。ゾウとキリンが「先手で空きマスにいる」「後手で空きマスにいる」「先手の持ち駒」「後手の持ち駒」なので(10 + 10 + 1 + 1) * (9 + 9 + 1 + 1) * ... = 12672022 ** 4 =234256あれば十分。「十分」と言ったのは、両方先手や両方後手だったりすると交換したものも同一局面なので1/4くらいは頑張れば節約できるから。(追記: 持ち駒のときは置ける場所が減らないので22 ** 4に変更)

最後にヒヨコが厄介だ。成るから。

ここで対人戦を2回ほど。Google Spredsheetはチャットもついていて同時編集もできてとても便利だということを知った。

キリンとゾウと、どちらも4地点に動くけどどう考えてもゾウの方が弱いよね、という話。端の影響で動けなくなるのがゾウの方が多いから。各12マスで何地点に動けるかを合計したもの: ヒヨコ9, ゾウ24, キリン34, ニワトリ46, ライオン58。単純にこの数字だけだと、ゾウ+ヒヨコをキリンと交換しても得ということになるが実際はどうだろうか。

さてヒヨコの続き。ヒヨコは「ヒヨコであるとき9通り」「ニワトリであるとき12通り」「持ち駒」だから先手後手あわせて44通り。置ける場所が減る効果を無視すると1936通りあれば十分。ニワトリであるときの置ける場所は10個以下。よって1600通りで十分。

さて、全部の合計で59864589312。600億。60G。んー、これはちょっと多いなぁ。

まだきっちり理解していないんだけども退行解析って一状態当たりに持つべき情報は「勝ち、負け、千日手」の2ビットなのかな。だとすると15GB。対称性を使って3.75GB。あ、ニワトリであるときの置ける場所も10通り以下なので元の値が50Gに減る。だからここまでで3.15GBだな。上の「頑張れば3/4くらいに減る」をまじめに実行すれば半分以下になって2GBの僕のMacBookでもオンメモリで持てるレベルになるなぁ。


先手ライオンL0 0-11
後手ライオンL1 0-10 (if L1 > L0: L1--)
キリン、まず「先手先手」「先手後手」「後手後手」の3つにわけられる「後手先手」は正規化。先手先手と後手後手に関しては「小さい方が先」ルールでさらに半分になる。
先先は「2枚とも持ち駒」「1枚持ち駒、残りが0-9」「0-9と0-8、ただし小さい順で1/2」で1 + 10 + 45、後後も同じなので合計112、先後は「2枚とも持ち駒」「1枚持ち駒、残りが0-9、持ち駒なのが先手か後手かで2倍」「0-9と0-8」の合計で1 + 20 + 90 = 111。全体の合計で223通り。最初の22 ** 2 = 484という概算から半分に減ったな。「後手先手」が消えて1/4減と、先手先手と後手後手がそれぞれ半分になったことで1/4減だね。ゾウとヒヨコに関しても同じように半減するなら全体で3GBの1/8になって750MBくらいで動くようになるな。

ゾウとヒヨコについて「キリンがすでにいるせいで置けないマス」による削減を入れると小さくなるけど複雑になりすぎる気がする。ライオンだけ飛ばして計算する程度で十分かもしれない。そうするともれなく0-9 * 0-9で、キリンが121 * 122 = 243。これでも半分。ゾウも複雑に考える必要がなくなって、キリンと全く同じで243。

ヒヨコも(ヒヨコ領域にライオンがいるかどうかの条件分岐は面倒だから省いたとして) 0-8(ヒヨコ) + 0-9(ニワトリ)の19ヶ所に置く場所が増えただけなので、先先が1 + 19 + 19 * 18 / 2 = 191、先後が1 + 19 * 2 + 19 * 19 = 400、全体で782通り。

さて、12 * 11 * 243 * 243 * 782 = 6095273976。うーん、1状態2bitでpackして1.5GBか。あ、で、ここから左右の対称性で半分に減らして、「先手の勝ち局面は後手の負け局面」の対称性でまた半分に減らすけども、局面に「いまどちらの手番か」をつけないと行けないのと相殺して、最終的に0.75GBか。んー、左右の対称性での削減は面倒だなぁ。1.5GBだったら一応MacBookで動くはずだからいいか。

めんどくさそうだしバグが入りそうだからってスキップしたけど0.9 * 0.8 * 0.7 * 0.6 * 0.5 = 0.1512から考えるとキリンの駒でゾウの駒が置ける場所が減る効果を実装すると4 ~ 5倍小さくなってもおかしくないなぁ。桁が固定じゃないエンコーディングはややこしいが、キリンの桁数が223なのはわかっているので x mod 223の値をキリンの位置の特定に使って、それによって決まる値Nで (x / 223) mod Nしてゾウの位置を決めて...と階層的にやっていけばいいだけか。落ち着いてやればできる気がする。それにここまで小さくなると局面がuint32tに収まるようになるんだよな。ちょっと惹かれる。


via id:TOKOROTEN
http://sig-gi.tanaka.ecc.u-tokyo.ac.jp/cfp/20091-program.html

3.「どうぶつしょうぎ」の完全解析
○田中哲朗(東京大学)

後退解析を用いて「どうぶつしょうぎ」というボードゲームの完全解析をおこなった．その手法と，解析の結果分かったゲームの性質を説明する．


orz...

しかも
http://toybox.tea-nifty.com/memo/2009/04/post-3f5f.html

探索局面数が約2億局面あったそうで、意外に難解なゲームのようです。

概算で600億あるのを頑張って60億まで減らして、もうちょっと頑張れば6億になりそう(持ち駒でない駒が盤面をしめる効果＋左右の対称性)ってところまでやっとのことでたどり着いたのに、まださらに3倍も削るところがあるとは…。