どうぶつしょうぎを解く
要点
- 3×4の子ども向け将棋であるどうぶつしょうぎは強解決済みで、後手が78手で勝つ。田中哲朗が2009年に解いた。
- 私はRustでゼロから再現した。到達可能な246,803,167局面すべてを求め、Robert Clauseckerの独立した解と50,000サンプルで照合して不一致はゼロだった。
- 深さを生むのは駒を打つルールだ。取った駒が戻ってくるルールを外すと、局面数は962,894まで落ち、最も深い勝ちは173手から37手になり、序盤は引き分けになる。
- 局面ブラウザは、すべての合法手を最善手のもとでの結果によって色分けする。
どうぶつしょうぎは、3×4の盤と8枚の駒で遊ぶ子ども向けの将棋だ。すでに完全に解かれており、最善手を続けると先手が負ける。
プロ棋士の北尾まどかが、子どもに将棋を教えるため2008年に考案した。2009年、田中哲朗が到達可能なすべての局面の正確な値を計算した。後手が78手で勝つ。
この記事では、解の中から見えてきたことと、なぜこれほど小さな盤が深いゲームになるのかを扱う。深さの原因は、小さな抽象ゲームの多くが省いている将棋由来の一つのルール、取った駒が盤に戻ることにある。
出典: 田中哲朗「『どうぶつしょうぎ』の完全解析」（情報処理学会研究報告, Vol. 2009-GI-22, 2009）。NII 恒久リンク
下で解の全体を探索できる。到達できるどの局面からでも、すべての合法手が最善手のもとでの結果によって色分けされている。
緑は勝ち、灰色は引き分け、赤は負け。バッジは詰みまでの手数。駒をドラッグするか手をクリックすると変化を追える。
ゲームについて
各プレイヤーは4枚の駒を持つ。ライオン、きりん、ぞう、ひよこで、互いに鏡像の配置で並べる。各駒に描かれた点は、その駒が進めるマスを示している。
駒の動き
どの駒も1手に1マスだけ動く。
- ライオン: 8方向のいずれか（チェスのキングと同じ）。
- きりん: 縦横に1マス。
- ぞう: 斜めに1マス。
- ひよこ: 前方に真っすぐ1マス。最奥の段へ進むとにわとりに成る（後ろ斜めの2方向を除く全方向に1マス）。最奥の段に打ったひよこは成らないので、そこで動けなくなる。
駒を打つ
1手ごとに、駒を動かすか打つかを選ぶ。駒を取るとそれは持ち駒になり、後の手で空いているどのマスにでも自分の駒として打つことができる。取られた駒は盤から消えるのではなく、所有者が入れ替わる。これが将棋を象徴するルールで、チェスにはないものだ。
勝ち方
勝ち方は2つ。相手のライオンを取るか（キャッチ）、自分のライオンを相手の最奥の段の、相手がすぐには取れないマスへ進める（トライ）。
結果
どうぶつしょうぎは強解決済みだ。参照表（テーブルベース）が到達可能なすべての局面の正確な値を保持しているので、それを備えたプログラムは序盤だけでなくどの局面からでも最善手を指せる。田中は終了局面から逆向きにたどって表を構築し、ゲームが到達しうるすべての局面を網羅した。
初期局面は後手が78手で勝つ（1手は片方のプレイヤーの一指しなので、78手は双方39手ずつにあたる）。先手はツークツワンクで負ける。どの手を指しても局面が悪くなり、パスは許されないので、先に指すこと自体が不利になる。
その78手の対局を1手ずつ再生して、最善手が続いた末のライオンの捕獲まで見ることができる。
私はこれをRustでゼロから再現し、ルールエンジンと後退解析ソルバーを書いた。初期局面から列挙すると、田中の到達可能局面数246,803,167（うち非終端は99,485,568）を正確に再現できた。ただし彼の局面カウントの流儀（トライは1手あとで決着する）に合わせたうえでの話だ。局面の値は、独立した完全解であるRobert Clauseckerのオープンソース dobutsuと照合し、サンプリングした50,000局面で不一致はゼロだった。初期局面の評価値は #-78（手番側が78手で負け）で、4つの合法な初手はいずれも負けになる。
Gc4-c3 : #-78
Lb4-c3 : #-78
Lb4-a3 : #-78
Cb3xb2 : #-76
解の全体を数値で示す（田中の数値。局面数は私の列挙で正確に再現できたが、値の内訳は彼のもの）。
| 項目 | 値 |
|---|---|
| 到達可能な局面 | 246,803,167 |
| 非終端の局面 | 99,485,568 |
| 勝ち / 引き分け / 負け（手番側） | 56,474,473 / 2,682,700 / 40,328,395 |
| 1局面あたりの平均合法手数 | 9.4 |
計算量は1台のマシンで再実行できる程度だ。田中の2009年の計算は2.6 GHzのOpteron機（メモリ16 GB）で、局面の列挙に約19分、後退解析に5.5時間かかった。私のRustでの再実行はApple Silicon上で約75分、メモリ約7 GBを使い、2.14 GBのソート済みレコード形式のテーブルベースを書き出し、その後333 MBのコンパクト表に詰め込んだ。公開中の局面ブラウザは、常駐メモリ約400 MBのプローブプロセスを通してそのコンパクトファイルを提供している。
最初の実装は8 GBにまたがるハッシュマップに頼っていて、それがClauseckerの参照実装の計算（約1分、167 MB）よりはるかに遅かった理由だ。彼の版は、各局面の内容、つまりどの駒が盤上にあるか、2頭のライオンがどこにいるか、残りがどう並んでいるかから計算されたアドレスを割り当てる。ハッシュを使わないので、表全体が連続した1本のバイト配列になる。このインデックスを移植したところ、私の計算は243 MB、3.5分になり、速くなると同時に小さくもなった。8 GBにわたるランダムアクセスはキャッシュを乱すが、詰め込んだ配列はそうならないからだ。値はまったく同一で、Clauseckerのプローブと手数まで一致した。彼の167 MBちょうどに到達するには、彼が畳み込んでいて私がまだ扱っていない対称性がもう一つ必要だが、これは洞察というより帳簿仕事だ。
注目すべき発見
目を引く結果以外にも、いくつか際立った点がある。
勝ちは早く決まるが、長い裾がある。 勝ちの局面の大半は15手以内で終わる。最も深い必勝は173手で、序盤の78手をはるかに超え、そこに該当するのは14局面だけだ。次のグラフは勝ちの局面を勝ちまでの距離ごとに対数目盛で数えたもので、数手のあと急に落ち、その後173まで細い裾が伸びている。
その最も深い勝ちは次の局面から始まる。手番側は駒損しているのに、173手後に勝つ。
68局面では、唯一の勝ち手が動けないマスにひよこを打つことだ。 相手の最奥の段にあるひよこは前方にマスがないので、打っても局面はほとんど変わらず、パスに近い。それでも他のすべての手は負けで、そのパス同然の手だけが勝つ。次の局面では、唯一の救いとなる打ちを丸で囲んである。
図なしで、さらにいくつかの発見を挙げる。
- 勝ち手が1つだけのことが多い。 勝ちの局面の約3分の1では、勝ちを保つ手は1つだけで、他のすべての手は勝ちを失う。
- ツークツワンクは珍しくない。 序盤は特別な例ではない。少なくとも21,839局面が、指すと負けるがパスが許されるなら保てる、という罠になっている。
- 勝ちの局面の約30%には必至の詰みが含まれ、その詰みは短いままだ。最長は23手。
打つルールを外すと
深さの容疑者は1つ、駒を打つルールだ。取った駒が戻ってくるので盤から駒が消えず、局面は薄くなって終盤へ向かうのではなく組み替わり続ける。打つことが本当に原因かを確かめるため、チェスのように取った駒が盤から消える形でルールを外して解き直した。結果は崩壊する。到達可能な局面は246,803,167から962,894に落ち、最も深い必勝は173手から37手になる。序盤も反転する。実際のゲームでは78手で負けだった先手が、今度は引き分けになる。同じ盤、同じ8枚の駒で、ルールを1つ抜いただけだ。（この変種を扱う外部ソルバーはないので、標準のゲームで検証した仕組みに依拠している。）
| 打ちあり | 打ちなし | |
|---|---|---|
| 到達可能な局面 | 246,803,167 | 962,894 |
| 最も深い必勝 | 173手 | 37手 |
| 序盤の値 | 後手が78手で勝ち | 引き分け |
まとめ
12マスと8枚の駒が、78手の必勝として解かれ、その裾は173手まで伸びる。駒が循環するとき、小さなゲームは深くなる。
参考資料:
- 田中「『どうぶつしょうぎ』の完全解析」: 最初の解（日本語）。
- brianhliou/dobutsu-shogi: 私がゼロから書いたRustのソルバーと局面ブラウザ。
- clausecker/dobutsu: Robert Clauseckerによる独立したオープンソースの解。私のソルバーの照合先となる完全なテーブルベース。
- 駒と盤のイラスト © 藤田麻衣子、どうぶつしょうぎ（「Let’s Catch the Lion!」）より。考案は北尾まどか、ねこまど。許諾を得て使用。