ヒキガエルとカエル（Toads and Frogs）をブラウザに実装した。1 列のマスに ヒキガエル（T, Left） と カエル（F, Right） が並び、ヒキガエルは右へ 1 マス進むか、カエル 1 匹を跳び越えて空きマスに着地する。カエルは同じことを左向きにする。取られる駒はなく、動けなくなった方の負け。Winning Ways の最初のほうに出てくる組合せゲーム理論の定番で、局面ごとに ±1/8 のような「熱い」値、{13/2 | 1} のような切り替え、95/16 のような数、何十文字にもなる無限小が出てくる。前回のハッケンブッシュで作った標準形エンジンを流用し、局面の値・サーモグラフ（平均と温度）・全部の手の勝ち負け（✓ / ✗）を出すようにした。検算として 12 マス以下の全 797,160 盤面で「簡約ルールあり」「ルールなし」「値を使わない勝敗探索」の 3 つを突き合わせ（不一致 0）、さらに Erickson（1996）と Thanatipanonda（2008）の 2 本の論文の表・定理・予想 1,733 項目を再計算した。合わなかったのは 1 項目だけで、それは2 本の論文どうしが食い違っているマスだった。値を使わない探索で、Erickson の値が正しく Thanatipanonda の表の T5□4F3 が誤りだと確かめた。テスト 16 件。ソルバー内蔵パズル第 93 弾。
デモ: https://sen.ltd/portfolio/toads-and-frogs/
リポジトリ: https://github.com/sen-ltd/toads-and-frogs
ルール
- 盤は 1×n のマス。各マスは空き（□）、ヒキガエル（T）、カエル（F）のどれか。
- ヒキガエル（Left）: 右隣が空きならそこへ 1 マス進む。右隣がカエルで、その先が空きなら跳び越えてそこへ着地する（跳ばれたカエルはそのまま）。
- カエル（Right）: 同じことを左向きに。
- 2 匹以上は跳べない。自分の駒も跳べない。手番で動ける駒がない方の負け。
記法は論文に合わせて、T が a 匹・空きが b マス・F が c 匹並んだ「初期配置」を Ta□bFc と書く（デモの入力欄では T3□2F3）。
値と温度
組合せゲーム理論では局面を {Left が行ける局面 | Right が行ける局面} というゲームとみなし、各局面に「値」を付ける。勝敗は値と 0 の大小で決まる。
| 値 G | 意味 |
|---|---|
| G > 0 | ヒキガエルの勝ち（どちらが先手でも） |
| G < 0 | カエルの勝ち |
| G = 0 | 後手の勝ち |
| G ‖ 0（比べられない） | 先手の勝ち |
Toads and Frogs が面白いのは、値が数でないことが普通な点。たとえば TTT□□FFF の値は ±1/8 = {1/8 | −1/8} で、先に動いた方が 1/8 手ぶん得をする。こういう「動くと得をする」局面を熱いという。どれくらい熱いかを表すのがサーモグラフで、「1 手ごとに t の税を払う」としたときに先手のヒキガエルが行ける値（左の壁）と先手のカエルが行ける値（右の壁）を t の関数として描く。2 本の壁が合流する t が温度、合流したあとの垂直な線（マスト）の位置が平均。
デモの初期局面 T□TF□F□6 は {13/2 | 1}: ヒキガエルが先に動けば 13/2、カエルが先に動けば 1。平均 15/4、温度 11/4 で、スクリーンショット右下の山形がそのサーモグラフ。
エンジン
標準形（前回のハッケンブッシュから流用）
src/cgt.ts はゲームを**標準形（canonical form）**に簡約して整数 id で持つ。支配される選択肢を消し、相手にすぐ取り返される（可逆な）選択肢を迂回する、を不動点まで繰り返すと形が一意になるので、値が等しいこと = id が等しいことになる。比較 le は Conway の再帰定義そのままで、id の組でメモ化する。詳しくは前回の記事に書いた。
Erickson の簡約ルール
src/toads.ts は盤を 'T', 'F', '.' の文字列で持つ。手を全部生成して再帰で値を出すだけでも正しいが、盤が長くなると局面数が爆発する。そこで、値を出す前に Erickson（1996）の簡約ルールで盤を小さく切る。
// X T .^n = X .^n + n（右にカエルのいないヒキガエルは、前の空きマスの数だけの「タダの手」）
const j = Math.max(s.lastIndexOf('T'), s.lastIndexOf('F'));
if (j >= 0 && s[j] === 'T') {
int += s.length - 1 - j;
s = s.slice(0, j) + s.slice(j + 1);
}
- 死んだ駒: TT（または左端）から FF（または右端）までの駒の並びは二度と動かず、その左右は干渉しない。盤をそこで 2 つの独立なゲームに分けて、値を足す。
- ゴールしたヒキガエル（terminal toad）: 右にカエルが 1 匹もいないヒキガエルは、前にある空きマスの数だけの整数になる。X T □n = X □n + n。カエル側も同じ（finished frog）。
-
Death Leap Principle:
TF□□・□□TF・T□・□Fのどれも含まない局面（できるのは孤立した空きへの跳躍だけ）は 0。
これで盤は「整数 + 独立な部分の和」になり、部分は文字列をキーにメモ化する。Erickson の論文にある例 TFTFF□FT□□TTFF□TFF□□TT は、探索を 1 手もせずに 1 になる。
サーモグラフ
src/thermo.ts は壁を t ≥ 0 の区分線形関数（折れ点の配列 + 最後の傾き）で持つ。
- 数 x の壁は定数 x。
- 数でない G の左の足場は「Left の各選択肢の右の壁 − t」の最大、右の足場は「Right の各選択肢の左の壁 + t」の最小。
- 左の足場は単調減少、右の足場は単調増加なので、初めて左 ≤ 右になる t が温度、そこでの値が平均。それより上は両方の壁がマスト（定数）になる。
折れ点は全部 2 進分数なので、double のままで誤差なく計算できる。max / min は 2 つの関数の折れ点を合わせ、区間ごとに交点を足すだけ。
最初に書いたテストで {1 | {1/2 | 0}} の平均を 3/4・温度を 1/4 と期待したら、エンジンは 5/8 と 3/8 を返して落ちた。手で計算し直すと、右の選択肢 {1/2 | 0} の壁は t = 1/4 でもうマストになっていて、左の足場 1 − t と右の足場 1/4 + t は t = 3/8 で交わる。間違っていたのはエンジンではなく、テストに書いた期待値のほうだった。
検算 1: 12 マス以下の全盤面 797,160 個
長さ 1〜12 のすべての盤（3n 通り）について、
- 簡約ルールを使った値と、ルールを一切使わずに定義どおり再帰した値が同じ id
- 鏡像（左右反転して T と F を入れ替え）の値が符号反転
- 値から読んだ勝敗（G > 0 / < 0 / = 0 / ‖ 0）が、値を使わない勝敗探索（両方の先手で）と一致
を確かめた。29 秒、不一致 0。
| マス | 盤 | 異なる値 | 数 | 無限小 | 熱い（温度 > 0） | いちばん熱い盤 | その値 | 温度 |
|---|---|---|---|---|---|---|---|---|
| 4 | 81 | 14 | 77 | 2 | 2 | T2□F | {1/2 | 0} | 1/4 |
| 6 | 729 | 54 | 633 | 36 | 34 | T4□F | {{2 | 1} | 0} | 3/4 |
| 8 | 6,561 | 280 | 5,224 | 335 | 532 | T5□TF | {4 | 1} | 3/2 |
| 10 | 59,049 | 1,613 | 42,770 | 2,829 | 6,894 | T4□T□TF2 | {8 | {3* | 1*}} | 3 |
| 11 | 177,147 | 4,272 | 122,781 | 7,813 | 24,395 | T4□2T□TF2 | {12 | {{6* | 9/2} | 4}} | 15/4 |
| 12 | 531,441 | 11,107 | 352,717 | 21,560 | 84,662 | T5□2T□TF2 | {15 | {{8* | 11/2} | 5}} | 19/4 |
12 マスでは 66% が数、16% が熱い。いちばん熱い盤は 9 マスから先は Tk□…T□TF2 の形で、温度は 1 マス増えるごとに 3/4〜1 ずつ上がっていく。
サーモグラフも別に検算した。12 マス以下のランダムな盤の組 20,000 組（半分は熱い盤どうし）で、平均の加法性 mean(G + H) = mean(G) + mean(H) と、温度(G + H) ≤ 2 つの温度の大きい方が全部成り立ち、2 つの盤を死んだ壁 TTFF でつないだ 1 本の盤の値も G + H と同じ id になった。
検算 2: 2 本の論文を再計算する — 1,733 項目中 1,732 項目が一致
一次資料は 2 本。
- J. Erickson, New Toads and Frogs Results（Games of No Chance, 1996）: 簡約ルール、知られていた初期配置の値の表、5 つの予想
- T. Thanatipanonda, Further Hopping with Toads and Frogs（arXiv:0804.0640, 2008）: 表の拡張、Erickson の予想の証明と反例、新しい予想
表は PDF の画像から、arXiv 版は LaTeX ソースから値を拾い、src/notation.ts で {{3*|5/2}|2} や ±({1|*}, {{3/2|{1|{0|0,v*}}}|0}) のような論文の記法を標準形に変換して、文字列ではなく id で比べた。
| 出典 | 項目 | 一致 |
|---|---|---|
| Erickson の Ta□bFa 表 | 26 | 26 |
| Erickson の Ta□bFc 表（c ≤ 4） | 86 | 86 |
| Thanatipanonda の Ta□bFa 表（14 マス以内） | 42 | 42 |
| Thanatipanonda の Ta+1□bFa 表 | 30 | 30 |
| Thanatipanonda の Ta+2□bFa 表 | 25 | 24 |
| Thanatipanonda の Ta+3□bFa 表 | 17 | 17 |
| Erickson の補題 4.1〜4.4（駒が 1 か所に固まった「結び目」は整数） | 567 | 567 |
| Erickson の定理 3.1, 3.3, 3.5, 5.2, 7.7、系 3.2、補題 6.3 | 173 | 173 |
| Erickson の予想 7.1〜7.5、Thanatipanonda の定理と予想 1, 3, 4 | 765 | 765 |
| 食い違ったマスの値を使わない判定 | 2 | 2 |
Erickson が「全部書くと長い」として本文に載せている T4□□F4 の標準形
±({1 | *}, {{3/2 | {1 | {0 | 0, ↓*}}} | 0})
もそのまま一致した。T7□4F3 は論文に「(7*|9/2‖4)-ish」としか書かれていないので、{{7* | 9/2} | 4} と平均・温度が同じかどうかで確かめた（一致）。
1 マスだけ合わない: T5□4F3
合わなかったのは Thanatipanonda の Ta+2□bFa 表の a = 3, b = 4、つまり T5□4F3 だけ。
| 出典 | T5□4F3 |
|---|---|
| Erickson（1996）, p. 309 の表 | {{3* | 5/2} | 2} |
| Thanatipanonda（2008）, Ta+2□bFa の表 | {{5/2 | 2} | 2} |
| このエンジン | {{3* | 5/2} | 2} |
エンジンは Erickson と一致する。ただしエンジン同士で比べても「エンジンが正しい」根拠にはならないので、値の比較を一切使わない判定を足した。盤 T5□4F3 と候補の値 X の差 T5□4F3 − X を 1 つのゲームとして、
- Left は盤のヒキガエルを動かすか、−X の中で動く（X の Right の選択肢の符号反転へ行く）
- Right も同様
として素朴な勝敗探索をする。X は選択肢のリストとしてしか使わないので le は通らない。差が 0 なら、どちらが先手でも後手が勝つ。
const wins = (b: string, x: GameId, left: boolean): boolean => {
for (const m of moves(b, left)) if (!wins(m.after, x, !left)) return true;
// −x で Left が動く = x の Right の選択肢の符号反転へ
for (const o of left ? rightOptions(x) : leftOptions(x)) if (!wins(b, o, !left)) return true;
return false;
};
const isZero = !wins(board, X, true) && !wins(board, X, false);
結果は、T5□4F3 − {{3* | 5/2} | 2} は後手必勝（= 0）、T5□4F3 − {{5/2 | 2} | 2} はそうではない。Erickson の値が正しく、Thanatipanonda の表のこのマスは写し間違いか計算違いだと言える。同じ表の T5□3F3 = 3/2 と T5□5F3 = 4 は両論文とエンジンで一致しているので、この 1 マスだけの誤り。
定義されていない a: Erickson の定理 3.5
Erickson の定理 3.5 は「任意の n ≥ 6 で T□TF□F□n = {a + ½ | 1}」と印刷されているが、a はどこにも定義されていない。計算すると n = 6〜16 の全部で {n + ½ | 1}、温度は (2n − 1)/4 だった。
| n | 4 | 5 | 6 | 7 | 8 | … | 16 |
|---|---|---|---|---|---|---|---|
| 値 | {3 | 1} | {5 | 1} | {13/2 | 1} | {15/2 | 1} | {17/2 | 1} | … | {33/2 | 1} |
| 温度 | 1 | 2 | 11/4 | 13/4 | 15/4 | … | 31/4 |
論文の「温度がいくらでも大きい 1/4 の倍数になる局面がある」という主張どおりで、a は n の誤植と読める。デモの初期局面はこの n = 6。
予想たち
- Erickson の予想 7.4（Ta□aFa−1 = 1 または 1*）は a ≤ 6 で 1, 1, 1*, 1*, 1, 1。Thanatipanonda は a = 7 で T7□7F6 > 2 という反例を報告しているが、20 マスの盤はこの実装では届かない。
- Thanatipanonda の予想 2（a ≥ 7 で TT□aFF は a = 7 + 6n のとき *、それ以外 0）と、論文の注「21 ≤ b ≤ 103 で T2□bF2 は b = 25, 31, …, 103 以外 0」は、ここでは b = 70 まで確かめた。0 でないのは b = 1, 2, 3, 4, 7, 13, 19, 25, 31, …, 67 で、7 から先はきっちり 6 おき（値は全部 *）。
- T3□bF3 は b = 29 まで計算し、0 でないのは b = 1, 2, 4, 6, 14, 29 だけだった。b = 15〜28 はすべて 0 で、b = 29 でだけ * になる。論文の注「21 ≤ b ≤ 53 では b = 29 以外は 0」にある唯一の例外が、そのまま再現した。
不等式でしか載っていなかったマス
Thanatipanonda の表には「< 11/2」「5/2 < V < 3」のように不等式だけのマスがある。18 マス以内のものは厳密な値が出た。
| 盤 | 論文 | 厳密な値 |
|---|---|---|
| T4□9F3 | < 11/2 | 43/8 |
| T4□10F3 | < 6 | 23/4 |
| T5□7F4 | 5/2 < V < 3 | 43/16 |
| T5□8F4 | < 4 | 29/8 |
| T6□5F5 | 5/4 < V < 2 | 2 + 4·↓ |
| T6□6F3 | ‖ 8 | {8, 8↓* | {15/2 | 7}} |
| T7□6F4 | ‖ 5 | 62 文字の形、平均 23/4・温度 3/4 |
T6□5F5 は最初「24↓」と表示されていた。数 2 と ↓ の 4 倍をつなげて書いたせいで、24 + ↓ にも読めてしまう。名前を付ける関数（前回のハッケンブッシュから流用したもの）を「2 + 4·↓」と書くように直し、記法のパーサにも 4·↓ と + を足して、表示した名前を読み戻すと同じ id になることをテストに入れた。
計算量の目安
Ta□bFa は簡約ルールがあってもマスの数に対して急に重くなる。1 マスぶんを新しい表で計算し直したとき、T2□bF2 は b = 70 で約 243 万の部分局面・63 秒、T3□bF3 は b = 29 で約 1,153 万・285 秒、T4□bF4 は b = 13 で 566 万・172 秒（数本を同時に走らせたので時間は目安）。部分局面は盤の文字列をキーにした Map なので、メモリは文字列の長さにも比例する。論文の注にある b = 103 まで行くには、盤を駒の位置だけの整数に詰めるなどの工夫が要る。
デモ
- 局面は選択式（{13/2 | 1}、±1/8、TT□FF = *、T4□□F4 の長い無限小、{6 | 11/2}、95/16、Erickson が「厄介」と書いた T7□4F3、定理 7.7 の {{2 | −1} | −2}、簡約の例 = 1、1 匹カエル）か、編集モードで 24 マスまで自由に作れる。
T3□2F3のように打ち込んでもよい。 - ヒントを付けると、動かせる駒の上に ✓（勝ちを保つ）/ ✗（勝ちを渡す）が出て、下の表に各手のあとの値が並ぶ。
- 右のパネルには値、勝敗、平均と温度、簡約後の「整数 + 部分」、サーモグラフ。コンピュータは勝てる手のうち平均がいちばん良くなる手を選ぶ。
- 計算は Web Worker で、ページを開いている間は部分局面の表を使い回す。
まとめ
- 前回の標準形エンジンに Erickson の簡約ルールとサーモグラフを載せ、Toads and Frogs の任意の盤の値・平均・温度を出した。
- 12 マス以下の全 797,160 盤で「ルールあり = ルールなし = 値を使わない勝敗探索」、鏡像 = 符号反転が成り立ち、熱い盤どうしの和 10,000 組で平均の加法性も成り立った。
- 2 本の論文の 1,733 項目を再計算して、合わないのは 1 項目だけだった。それは T5□4F3 の値が 2 本の論文で違っているマスで、値を使わない探索で Erickson の {{3* | 5/2} | 2} が正しいと確かめた。Erickson の定理 3.5 の a は n の誤植だった。
参考文献:
- J. Erickson, New Toads and Frogs Results, in R. J. Nowakowski (ed.), Games of No Chance, MSRI Publications 29, Cambridge University Press, 1996, pp. 299–310
- T. Thanatipanonda, Further Hopping with Toads and Frogs, arXiv:0804.0640, 2008
- E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays, 2nd ed., vol. 1, A K Peters, 2001
- A. N. Siegel, Combinatorial Game Theory, Graduate Studies in Mathematics 146, AMS, 2013（標準形、サーモグラフ）
デモ: https://sen.ltd/portfolio/toads-and-frogs/
リポジトリ: https://github.com/sen-ltd/toads-and-frogs