ダッジェム（Dodgem）をブラウザに実装した。n×n の盤で、青は左端から右へ、赤は下端から上へ車を走らせ、自分の車を全部盤の外へ出した方が勝ち。ただし相手が 1 手も指せなくなる手を指したら負け。3×3 は先手必勝で、4×4 と 5×5 は 1996 年に David desJardins がニュースグループで「引き分け（車が永遠に横へ逃げ続ける）」と報告している。コンピュータは 3×3 と 4×4 の全局面をその場で解き、ヒントを付けると全部の手に「勝ち・引き分け・負け」と残り手数が付く。裏側では 5×5 の 2 億 4,006 万局面（手番込み）を Node で 323 秒で解き、1996 年の rec.games.abstract のスレッドと GamesCrafters の数字を全部確かめ直した。3×3 の到達可能局面 1,963（勝ち 1,123・負け 840）、Fleury の 666、4×4 と 5×5 の引き分け、「1. b1-a1 は 4×4 では負けで 5×5 では引き分け」はすべて一致した。ずれたのは 3 か所で、Erickson が描いた「後手勝ちの 3 局面」の 3 つ目は実は先手勝ち、Erickson の局面数は 2×2 以外が合わない、そして desJardins の引き分けの棋譜では O の 1 手目 a4-b4 が 38 手で負けだった。テスト 16 件。ソルバー内蔵パズル第 87 弾。
デモ: https://sen.ltd/portfolio/dodgem/
リポジトリ: https://github.com/sen-ltd/dodgem
ルール
Colin Vout が 1972 年に考案し、『Winning Ways』で紹介されたゲーム。
- n×n の盤。各自 n−1 台の車を持つ。
- 青は左端の列（左下の角を除く）に並び、右・上・下のどれかへ 1 マス動く。
- 赤は下端の行（左下の角を除く）に並び、上・左・右のどれかへ 1 マス動く。
- 他の車がいるマスには入れない。取ることはない。
- 盤の外へ出られるのは前進方向の端だけ（青は右端から、赤は上端から）。出た車はゲームから消える。
- 自分の車を全部外へ出した方の勝ち。
- 相手に合法手を 1 つも残さない手を指したら、その人の負け。言い換えると、手番が来たのに動けない人は勝ち。
- 青が先手。
最後の規則が効いている。相手を閉じ込めて勝つのではなく、閉じ込めたら負けになる。だから「相手の通り道をふさぐ」は、やりすぎると自分の首を絞める。
3×3 は先手必勝、4×4 以上は引き分け
3×3 は先手必勝で、『Winning Ways』には全局面の勝敗表が載っている。ここまでは古くから知られている。
それより大きい盤については、1996 年 3 月にニュースグループ rec.games.abstract で「"Dodgem" . . . any info?」というスレッドが立った（David Eppstein が自分のサイトに保存している）。Jeff Erickson が局面数を数え、David desJardins が 4×4 と 5×5 を全部解いて「どちらも引き分け」と報告し、ほかにもいくつか具体的な数字や局面が書き込まれた。
今回の作業は 2 つ。
- 完全プレイヤーと対戦できるページを作る。
- このスレッドに書かれた数字と局面を、一つ残らず計算し直す。
ソルバー: 車の台数で層に分けて、後ろ向きに解く
局面の数え方
局面は「青の車の位置」「赤の車の位置」「手番」の 3 つで決まる。盤は 5×5 でも 25 マスなので、車の位置はそれぞれ 32 ビット整数のビットマスク 1 個で持てる。
車は一度出たら戻ってこない。したがって、盤上の台数 (青 a 台, 赤 b 台) は減る一方で、どの手も
- 同じ層 (a, b) に留まる
- 青が 1 台出て (a−1, b) に落ちる
- 赤が 1 台出て (a, b−1) に落ちる
のどれかになる。そこで台数の少ない層から順に解けば、層の外へ出る手の行き先はいつも解き終わっている。
層 (a, b) の中では、青の a 台は 25 マスから a 個を選ぶ組合せ、赤の b 台は残りの 25−a マスから b 個を選ぶ組合せになる。どちらも組合せ数系（colex 順）で 0 から隙間なく番号が付くので、層全体を
index = (rank(青) × C(25−a, b) + rank(赤)) × 2 + 手番
という 1 本の配列に詰められる。ハッシュ表は使わない。5×5 の最大の層（4 台対 4 台）は 2 × C(25,4) × C(21,4) = 151,420,500 局面になる。
ループがあるので、前からは解けない
Chomp やハノイの塔と違い、Dodgem の車は横に動ける。同じ層の中で局面が循環するので、「行き先を全部解いてから自分を解く」という順番が存在しない。引き分けがあるのもこのせいだ。
そこで後退解析（retrograde analysis）を使う。
- 種まき: 層の全局面について合法手を生成する。動けない局面は手番側の勝ち（深さ 0）。層の外へ出る手は、下の層の値を引く。行き先に「相手の負け」があれば勝ち候補、全部が「相手の勝ち」なら負け候補にする。層の中へ行く手の数を数えておく。
-
深さ順に広げる: 深さ d の局面を確定したら、その局面へ 1 手で来られる局面（前の局面）を全部作る。
- 確定したのが負けなら、前の局面は深さ d+1 の勝ち。
- 確定したのが勝ちなら、前の局面のカウンタを 1 減らす。0 になったら、全部の手が相手の勝ちに行くので負け。深さは一番長く粘れる手に合わせる。
- 最後まで値が付かなかった局面は引き分け。どちらも勝ちを強制できず、車が永遠にうろうろする。
前の局面は、車を 1 台「逆向きに動かす」と作れる。青なら左・下・上へ、赤なら下・右・左へ戻す。逆向きの手で層の外から車が入ってくることはないので、前の局面は必ず同じ層に収まる。
深さは「最善を尽くしたときに終局まで何手かかるか」（勝つ側は最短、負ける側は最長）で、コンピュータはこれを見て指す。勝ちの局面で勝ちの手を適当に選ぶと、深さが減らない手を選び続けてぐるぐる回ることがあるので、最短の勝ちを選ぶ必要がある。
計測
Node 26、12 コアの Mac mini、1 スレッド。
| 盤 | 局面数（手番込み） | 解く時間 |
|---|---|---|
| 3×3 | 2,846 | 13 ms |
| 4×4 | 555,986 | 0.86 秒 |
| 5×5 | 240,060,402 | 323 秒 |
5×5 の時間の大半は最後の層で、(3,4) と (4,3) が各 46 秒、(4,4) が 204 秒だった。到達可能局面の集計まで含めると 629 秒、最大メモリは 928 MB。値 1 バイトと深さ 2 バイトを全層ぶん、カウンタ 1 バイトを解いている層のぶんだけ持っている。
ページでは 3×3 と 4×4 をその場で解く。4×4 でも 1 秒かからないので、局面表を配る必要がない。
公表されている数字と突き合わせる
| 主張 | 出典 | 結果 |
|---|---|---|
| 3×3 は先手必勝 | 『Winning Ways』 | 一致。19 手で勝つ。勝てる初手は角から一番遠い車を進める 1 手だけ |
| 3×3 の到達可能局面は 1,963、手番側の勝ち 1,123・負け 840、引き分けなし | GamesCrafters（Wikipedia 経由） | 完全一致 |
| 対称性で半分にすると、3×3 の合法局面は 666 | Marc Fleury（1996-03-04） | 一致。両者とも 1 台以上盤上にある局面 1,332 の半分 |
| 3×3 で後手が勝つ局面は 3 つ（鏡映を含めて 6 つ） | Jeff Erickson（1996-03-04） | 6 つは一致。ただし図の 3 つ目が違う（後述） |
| 2×2〜5×5 の合法局面は 21 / 1,495 / 303,433 / 197,841,801 | Jeff Erickson（1996-03-11） | 2×2 しか合わない（後述） |
| 4×4 の開始局面と「一番簡単な引き分け局面」は引き分け | David desJardins（1996-03-18, 19） | 一致 |
| 1. b1-a1 は 4×4 では負け、5×5 では引き分け | desJardins（1996-03-20） | 一致。4×4 では 38 手で負け |
| 5×5 は引き分け | desJardins（1996-03-20） | 一致 |
| 5×5 の局面の約 40% は引き分け | desJardins（1996-03-20） | 両者が盤上にいる局面の 35.7%、開始局面から到達できる局面の 32.1% |
| 4×4 の引き分けの棋譜。「!」は唯一の引き分け手 | desJardins（1996-03-19） | 「!」の 3 手はすべて正しい。ただし O の 1 手目が負け（後述） |
GamesCrafters の 1,963 / 1,123 / 840 が手番込みで 1 局面もずれずに出たので、規則の解釈（特に「相手を動けなくしたら負け」と「全部出したら勝ち」の優先順位）は合っていると判断した。
desJardins の記法は盤の向きが逆で、X が下端から上へ進む先手、O が左端から右へ進む後手になっている。盤を反対角線で折り返すと青と赤がそのまま入れ替わるので、変換関数を 1 つ書いて棋譜を再生している。
ずれ 1: Erickson の 3 つ目の図
Erickson は 3×3 の後手勝ち局面（どちらが先に指しても、指した方が負ける局面）を次のように描いた。> が青、^ が赤。
. > > > . . > > .
. . ^ ^ . . . . ^
. . . . . . . . ^
数は合う。全局面を分類すると、どちらが先手でも後手が勝つ局面はちょうど 6 つで、3 組の鏡映ペアになっている。1 つ目と 2 つ目の図もその中にある。
ところが 3 つ目の図は、印刷されたとおりに読むとどちらが先に指しても先手が勝つ（13 手）。本当の 3 組目は
> > . . . .
^ ^ . . > ^
. . . . > ^
の 2 つで、印刷された図は左の局面から青を、右の局面から赤を取った形になっている。元の投稿は等幅の ASCII 図で、行ごとに字下げがずれているので、どこかで写し間違えたのかもしれない。
ずれ 2: Erickson の局面数
Erickson は「n×n 盤の合法局面」を数えて、次の値を出している。
| n | Erickson | 各色 n−1 台以下を別々のマスに置く数 |
|---|---|---|
| 2 | 21 | 21 |
| 3 | 1,495 | 1,423 |
| 4 | 303,433 | 277,993 |
| 5 | 197,841,801 | 120,030,201 |
右の列は、0 ≤ a, b ≤ n−1 について C(n², a)·C(n²−a, b) を足したもの。「片方か両方の車が全部出た局面も含め、対称性は考えない」という彼の説明どおりに数えるとこうなる。Erickson の値はこれより大きい。車をマスに置く方法の総数より多いので、何か別のものを数えている。手番を含めると 2,846 / 555,986 / 240,060,402 になり、これも違う。投稿には式が書かれていないので、ここで止めた。合うのは 2×2 の 21 だけ。
ずれ 3: desJardins の棋譜の 1 手目
desJardins は 4×4 の開始局面が引き分けだと分かった後、「両者が最善を尽くした例」として 12 手の棋譜を載せている。「!」は唯一の引き分け手。
1. d1-d2 a4-b4 2. d2-d3 b4-c4 3. d3-d4 a3-b3
4. c1-c2 c4-c3! 5. b1-b2 a2-a3! 6. c2-d2 c3-c2
7. d2-d3 a3-a2 8. d3-c3 a2-a3! 9. b2-a2 b3-b2
10. c3-c4 c2-c1 11. d4-off c1-c2 12. d3-off b2-b3
これを 1 手ずつ再生し、各局面の値と「引き分けになる手が何個あるか」を数えた。
- 「!」の 3 手（4… c4-c3、5… a2-a3、8… a2-a3）は、どれもその局面で引き分けになる唯一の手だった。
- 12 手目の「d3-off」は、その時点で d3 に車がいないので指せない。直後に載っている図と合うのは c4-off で、書き間違いだろう。
- 問題は 1 手目。1. d1-d2 の後、O には 4 つの手がある。
| O の手 | 結果（O から見て） |
|---|---|
| a2-b2 | 引き分け |
| a3-b3 | 引き分け |
| a2-a1 | 32 手で負け |
| a4-b4（棋譜の手） | 38 手で負け |
a4-b4 の後は X の 2. c1-c2 で勝ちが決まる。棋譜の 2. d2-d3 はこれを逃して引き分けに戻している。つまりこの棋譜は「両者最善」ではなく、O の悪手と X の見落としがちょうど打ち消し合った棋譜だった。3 手目以降の局面はすべて引き分けで、「!」の判定も全部合っているので、desJardins の表そのものは正しく、例を手で書くときに 1 手目を選び間違えたのだと思う。
38 手は長い。手で読み切れる長さではなく、表を引かないと気づけない。
ほかに分かったこと
- 3×3 の初手は 3 通りあり、勝てるのは角から一番遠い車を前に出す手だけ。残りの 2 手は 18 手と 16 手で負ける。スレッドで David Boll が「外側の端の車から動かして、それを常に外側に保てば先手が有利」と書いているのと合う。
- 最善を尽くしても終わるまでに一番長くかかる勝ち局面は、3×3 で 21 手、4×4 で 42 手、5×5 で 81 手。
- 5×5 では、開始局面からの 5 通りの初手が全部引き分けになる。desJardins が「ひどい手」と呼んだ角への 1. b1-a1 も含めて。
- 開始局面から到達できる局面は、4×4 で 393,900 のうち 35,281（9.0%）、5×5 で 164,308,067 のうち 52,703,322（32.1%）が引き分け。盤が大きいほど引き分けが増える、という desJardins の見立てどおり。
- どちらが先に指しても後手が勝つ局面は、3×3 で 6、4×4 で 14、5×5 で 36 しかない。
対戦画面
- 盤の大きさ（3×3 / 4×4）と自分の色を選ぶ。青が先手。
- 自分の車をクリックすると行き先に印が出る。ヒントを付けていると、印に「W12」（12 手で勝ち）、「L30」（30 手で負け）、「=」（引き分け）が付く。車を選んでいないときは、全部の手が小さな色付きの点で表示される。
- 盤の外へ出る手は、盤の上（赤）と右（青）の点線の枠に印が出る。
- コンピュータは勝てるなら最短で勝ち、負けるなら最長で粘り、引き分けなら引き分けの手の中から無作為に選ぶ。
- 4×4 で同じ局面が 3 回現れたら、ステータスにそう表示する。終局は強制しない。
テスト
16 件。主なもの:
-
独立なソルバーとの全局面照合。層分けも組合せ数系も逆向きの手も使わず、
Mapに全局面を入れて「勝ちの行き先があれば勝ち、全部が勝ちなら負け」を収束まで繰り返すだけのソルバーを別に書いた。同時更新で反復すると、t 回目に決まった局面の深さはちょうど t になる。3×3 の 2,846 局面と 4×4 の 555,986 局面すべてで、値と深さが一致する。 - 反対角線で折り返して色と手番を入れ替えると、値と深さが変わらない。
- 勝ちの局面には深さ −1 の負けへ行く手があり、負けの局面の手は全部相手の勝ちへ行く。
- GamesCrafters の 1,963 / 1,123 / 840、Fleury の 666、Erickson の 6 局面と 3 つ目の図のずれ、desJardins の主張と棋譜（「!」、d3-off、1 手目）。
- 3×3 でコンピュータが先手を持つと、赤のどんな応手に対しても勝つ（全分岐を試す）。
まとめ
- Dodgem は車が一度出たら戻らないので、台数で層に分けて少ない方から解ける。層の中はループがあるので、深さ順の後退解析で勝ち・負け・引き分けと手数を出した。
- 5×5 の 2 億 4,006 万局面は Node 1 スレッドで 323 秒、928 MB。
- 1996 年のスレッドの主張は大部分が再現した。4×4 と 5×5 は引き分け、1. b1-a1 は 4×4 で負け 5×5 で引き分け、GamesCrafters の 1,963 / 1,123 / 840 と Fleury の 666 は完全一致。
- ずれは 3 か所。Erickson の後手勝ち 3 局面の図の 3 つ目は先手勝ち。Erickson の局面数は 2×2 以外合わない。desJardins の引き分けの棋譜では、O の 1 手目 a4-b4 が 38 手で負けで、X の 2 手目がそれを見逃している。
参考文献:
- "'Dodgem' . . . any info?"、rec.games.abstract、1996 年 3 月（David Eppstein によるアーカイブ）、https://www.ics.uci.edu/~eppstein/cgt/dodgem.html（2026 年 10 月 17 日参照）
- E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays, 2nd ed., Vol. 3, A K Peters, 2003
- M. Gardner, "Mathematical Games", Scientific American, 1975 年 6 月
- Wikipedia "Dodgem"（GamesCrafters の数字の引用元）、https://en.wikipedia.org/wiki/Dodgem（2026 年 10 月 17 日参照）
デモ: https://sen.ltd/portfolio/dodgem/
リポジトリ: https://github.com/sen-ltd/dodgem