どうぶつしょうぎを解く
どうぶつしょうぎは、3×4の盤と8枚の駒で遊ぶ子ども向けの将棋ゲームである。すでに完全に解かれており、最善手を尽くすと先に指す側が負ける。
プロ棋士の北尾まどかが、子どもに将棋を教えるために2008年に考案した。2009年、田中哲朗が到達可能なすべての局面の正確な値を計算した。後手が78手で勝つ。
この記事では、解いた結果から何が分かったのか、そしてこれほど小さな盤がなぜ深いゲームを生むのかを扱う。その深さは、小さな抽象ゲームの多くが省いている将棋のひとつのルール、すなわち取った駒が盤に戻ってくることに由来する。
出典: 田中哲朗「『どうぶつしょうぎ』の完全解析」（情報処理学会研究報告, Vol. 2009-GI-22, 2009）。NII 永続リンク
以下で完全解を探索できる。到達できるあらゆる局面から、すべての合法手が最善手のもとでの結果によって色分けされている。
緑は勝ち、灰色は引き分け、赤は負け。バッジは詰みまでの手数。駒をドラッグするか手をクリックすると手順を追える。
ゲームの内容
各プレイヤーはライオン、きりん、ぞう、ひよこの4枚を持ち、互いに鏡像となる配置で並べる。駒に描かれた点が、その駒が進めるマスを示している。
駒の動き
どの駒も1手に1マスだけ動く。
- ライオン: 8方向のいずれへも（チェスのキング）。
- きりん: 縦横に1マス。
- ぞう: 斜めに1マス。
- ひよこ: 真っすぐ前に1マス。最奥の段へ進むとにわとりに成る（後ろ斜め2方向を除く全方向へ1マス）。最奥の段に打ったひよこは成らないので、そこで動けなくなる。
駒を打つ
各手番では、駒を動かすか、持ち駒を打つかのどちらかを行う。駒を取るとそれは持ち駒になり、後の手番で空いているマスへ自分の駒として打つことができる。取られた駒は盤から消えず、所有者が入れ替わる。これはチェスにはない、将棋を象徴するルールである。
勝利条件
勝ち方は2つ。相手のライオンを取るか（キャッチ）、自分のライオンを相手陣の最奥の段、しかも相手にすぐには取られないマスへ進めるか（トライ）である。
結果
どうぶつしょうぎは完全に解かれている。参照表（テーブルベース）が到達可能なすべての局面の正確な値を保持しているので、それを備えたプログラムは序盤だけでなく任意の局面から最善手を指せる。田中哲朗は終了局面から逆向きにたどってこの表を構築し、ゲームが到達しうるすべての局面を網羅した。
初期局面は後手が78手で勝つ（1手は片方のプレイヤーの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枚のライオンがどこにいるか、残りがどう並んでいるかである。ハッシュを取らないので、表全体がひと続きのバイト配列になる。この索引方式を移植したところ、私の解析は243 MB・3.5分になり、速さと小ささが同時に得られた。8 GBにまたがるランダムアクセスはキャッシュを壊すが、詰めた配列はそうならないからだ。値は完全に一致し、Clauseckerのプローブと手数単位まで照合済みである。彼の167 MBぴったりに届くには、彼が畳み込んでいて私がまだ扱っていない対称性がもう1つ必要だが、これは洞察というより事務作業だ。
注目すべき発見
目立つ結果のほかにも、いくつか際立つ点がある。
勝ちは速く決まるが、長い裾がある。 勝ちの局面の大半は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!」）、ねこまどより、許諾を得て使用。