1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@sen-ltd

ドット・アンド・ボックス — David Wilson の解析ページの 2,129 個のスコアを、印刷された盤面をそのまま読み込んで全部再計算する（3×5 Icelandic の 2^30 局面は 150 秒）

1
Posted at

ドット・アンド・ボックス（Dots and Boxes）をブラウザに実装した。相手のコンピュータは盤面を全部解いてある。3×3 の盤なら、線の引き方 16,777,216 通りすべてについて最善の結果を知っている。まだ引かれていない線の上には、その線を今引いて、以降お互いが最善を尽くしたときの最終スコア（A の箱数 − B の箱数）が出る。David Wilson（ウィスコンシン大学）の解析ページと同じ表示形式にした。そのうえで、Wilson のページ 8 枚（2017 年のアーカイブ）に載っている盤面の図を1 文字も変えずにファイルに保存し、パーサで読み戻して、図の上の数字をソルバーで全部計算し直した。89 面・2,129 個のスコアがすべて一致した。中には 2^30 = 1,073,741,824 局面ある 3×5 Icelandic の初手 30 通りも入っている。Wilson は 2002 年の PC で「約 30 分」かけた。ここでは 1 GB の Int8Array 1 本を使い、Node で 150.3 秒。3×3 は「どの初手でも後手が 3 箱差で勝つ」。これは Berlekamp の本の 9 ページにある「後手は 1 箱差の勝ちを強制できる」より強い結論で、Wilson のページの注記どおりになった。Wilson の「初手は中央が良い。後手が間違える余地が一番大きい」という助言も数えられる。中央の箱に接する 4 本のどれかを引くと、後手が最善を保てる応手は 23 手中 5 手しかない。それ以外の初手では 19〜21 手ある。テスト 12 件。ソルバー内蔵パズル第 77 弾。

デモ: https://sen.ltd/portfolio/dots-and-boxes/
リポジトリ: https://github.com/sen-ltd/dots-and-boxes

盤面

ルール

点が格子状に並んでいる。2 人が交互に、隣り合う 2 点を結ぶ線を 1 本ずつ引く。箱（1×1 のマス）の 4 辺目を引いた人がその箱をもらい、もう 1 本続けて引く。全部の線が引かれたら、箱を多く取った方の勝ち。

盤の大きさの呼び方には注意が要る。Wilson のページの「3x3」は箱が 3×3（点は 4×4）の盤のことで、本人が表記の説明ページに書いている。

Some people call this a 3x4 game because it's 3 dots by 4 dots. Others call it a 2x3 game because it's 2 boxes by 3 boxes. At this web site, I use the latter convention.

英語版 Wikipedia が入門用に「2×2 の盤（3×3 の点）」を勧めているように、点の数で呼ぶ資料も多い。「3×3 の結果」を読むときは、まずどちらの数え方かを確かめる必要がある。この記事とアプリでは Wilson に合わせて箱の数で呼ぶ。

Wilson は、外周の線をあらかじめ引いておく変種も解析している。

名前 最初から引いてある線
American なし（普通のルール）
Swedish 外周すべて
Icelandic 左辺と下辺

ページでは 2×2、2×3、3×3、3×4 Icelandic、3×5 Swedish の 5 つの盤で遊べる。コンピュータに A・B どちらを持たせるか、どちらも持たせないかを選べる。Hint を押すと最善手の 1 本が光る。

数字の意味

盤の空いている線の上に出る数字は、その線を今引いたときの最終スコア（最後に A が持っている箱の数 − B の数）で、以降は両者とも最善を尽くすものとする。A は大きい数字、B は小さい数字の線を選びたい。手番の人にとっての最善が緑、それより悪い線が赤で表示される。

Wilson のページの図も同じ意味で数字を書いている。

 + -3  + -3  + -3  +        3x3 game.  Page 9 of The Dots-and-Boxes Game describes how player B
                            can force a win by 1.  However, player B really should win by 3.  This
-3    -3    -3    -3        game is more interesting if a loss by 1 is considered a win for player A.

（results.shtml の冒頭。+ が点で、数字は線の位置に置かれている。）

3×3 の空の盤では 24 本すべてが −3 になっている。先手が何を引いても、後手は 6 対 3 で勝てるということだ。

局面は「引かれた線の集合」だけ

このゲームの解析で一番大事なのは次の事実だ。

それまでのスコアは、この先の最善手に影響しない。

すでに取られた箱は、この先どう打っても動かない。残りの箱をどれだけ差をつけて取れるかだけが問題になる。そして「どの線が引かれているか」がわかれば、どの箱が閉じているかも、どの線がまだ引けるかもわかる。そこで局面は線の集合だけで表せる。1 本の線を 1 ビットにすると、3×3 の 24 本は 24 ビットの整数 1 つになる。

table[s] には、局面 s で手番の人がこれから取れる箱 − 相手がこれから取る箱の最大値を入れる。線を 1 本引いた結果は：

  • 箱が閉じなければ、手番が相手に移る。値は -table[子]
  • 箱が g 個閉じれば、g 個もらって手番が続く。値は g + table[子]

線を足すとビットが増えるので、整数としては必ず大きくなる。だから全部引いた盤から空の盤に向かって、整数を大きい順に 1 回なめるだけで、どの局面を計算するときも子はすべて計算済みになっている。再帰も、置換表も、手番のフラグも要らない。

export function solve(sv: Solver, onProgress?: (done: number) => void): Solver {
  const { n, maskA, maskB } = sv;
  const size = 2 ** n;
  const full = size - 1;
  const T = new Int8Array(size);
  for (let s = full - 1; s >= 0; s--) {
    let best = -128;
    let m = ~s & full;
    while (m !== 0) {
      const b = m & -m;
      const i = 31 - Math.clz32(b);
      const c = s | b;
      const a = maskA[i], z = maskB[i];
      const gain = ((c & a) === a ? 1 : 0) + ((c & z) === z ? 1 : 0);
      const v = gain !== 0 ? gain + T[c] : -T[c];
      if (v > best) best = v;
      m ^= b;
    }
    T[s] = best;
    if (onProgress && (s & 0xfffff) === 0) onProgress(1 - s / size);
  }
  sv.table = T;
  return sv;
}

m & -m で「まだ引かれていない線」の最下位ビットを 1 つずつ取り出し、Math.clz32 でその番号を得る。箱が閉じたかどうかは、線 i に接する箱（最大 2 つ）のまだ引かれていない線のマスク maskA[i] / maskB[i] を前計算しておき、(c & mask) === mask で判定する。線が盤の端にあって片側に箱がないときは、どの局面にも立たないビット 2^n をマスクにしておけば、判定は常に偽になる。値は最大でも箱の数なので Int8Array で足りる。

Wilson の解析プログラムも、解説ページ（Dots-and-Boxes Analysis Methodology）によれば同じ考え方で作られている。

For each position the program stores the best score for the player on the move for future boxes. Boxes already surrounded are ignored. Thus, each position is uniquely identified by the lines present. No data about scoring up to that move is kept.

違いはメモリの事情にある。Wilson は 2002 年当時 256 MB の RAM で 3×5（38 本、2^38 バイト = 256 GB）を解くため、線をグループに分けてディスクと行き来させ、対称性で容量を削っている。ここでは 30 本以下の盤しか扱わないので、表は配列 1 本にそのまま入る。30 本で打ち切るのは、ビット演算を 32 ビット整数のまま使うためでもある。

盤ごとの所要時間（Node v26、1 プロセス）:

盤 空いている線 局面数 最善の結果 ここでの時間 Wilson（2002）
2×3 17 131,072 −2 0 秒 –
3×3 24 16,777,216 −3 2 秒 1 分未満
3×5 Swedish 22 4,194,304 +5 0.6 秒 1 分未満
3×4 Icelandic 24 16,777,216 +4 2.4 秒 –
3×5 Icelandic 30 1,073,741,824 −1 150.3 秒 約 30 分

Wilson の時間は Analysis Programs のページの記述（"swed.txt and 3x3.txt were analyzed in less than a minute. iceland.txt took half an hour."）から取った。

ブラウザ版は Web Worker の中で表を作り、postMessage の transfer で ArrayBuffer をコピーせずにメインスレッドへ渡す。3×3 は Playwright の Chromium で 2.1 秒だった。

Wilson の図をそのまま読み込む

照合で一番手間がかかるのは、数字を拾うところだ。Wilson のページの図は <pre> で組まれた ASCII で、手で写すと必ず写し間違える。そこで tools/wilson/*.txt にはアーカイブから取った <pre> の中身をタグだけ外して 1 文字も変えずに保存し、パーサで読み戻すことにした。

図の文法は次のとおり。

  • 点は +。直前に引いた線の両端だけ # になる
  • 点と点の間は 5 文字。----- なら引かれた横線、そうでなければ数字（その線を引いたときのスコア）
  • 縦線は点の真下の列に | を 3 行続けて書く。スコアは真ん中の行に、点の列で右揃えで書かれる
  • 取られた箱は中央に A か B
  • loony 解析つきの盤では、スコアの後ろに ^ か v が付く

これで文法としては十分だが、実際のページを読むと落とし穴がいくつかあった。

  1. タブが混ざっている。完全対局のページ（3x3perfect.html）は、空白とタブが混在している。8 桁ごとのタブストップで展開してから読む
  2. 盤が横に 2 枚並ぶ。完全対局のページは「A の手番」と「B の手番」を左右に並べている。行頭から 1 枚と決め打ちせず、どの列から始まる点列でも盤の候補として扱う
  3. 盤の右に地の文が続く。results.shtml では盤の右に説明文が同じ行で続く。点が 6 列おきに続き、しかも間の 5 文字が線か数字である限りを 1 行の点列とする
  4. 縦に並んだ盤がつながってしまう。次の盤が空行 3 行を挟んで置かれていると、点の行がちょうど 4 行周期で続くので、2 枚が縦長の 1 枚に見える。行と行の間の「縦線の行」が読めることを条件に加えた
const DOT = /[+#]/;
const H_FIELD = /^(?:-----|\s*-?\d+[\^v]?\s*)$/;

/** Number of boxes in a row of dots starting at column c, 0 if there is none. */
function dotRow(line: string | undefined, c: number): number {
  if (line === undefined || !DOT.test(line[c] ?? '')) return 0;
  let k = 0;
  while (DOT.test(line[c + 6 * (k + 1)] ?? '') && H_FIELD.test(line.slice(c + 6 * k + 1, c + 6 * k + 6))) k++;
  return k;
}

      // Boards stacked three blank lines apart line up too; a row of boxes
      // needs a readable line of verticals in its middle.
      const verticals = (s: string | undefined) =>
        s !== undefined && Array.from({ length: cols + 1 }, (_, x) => vField(s, c + 6 * x)).every(Boolean);
      while (dotRow(lines[L + 4 * (rows + 1)], c) === cols && verticals(lines[L + 4 * rows + 2])) rows++;

4 番目は、最初のバージョンで 3x3.html（初手のあとの 4 局面）から盤が 1 枚も読めなかったことで気づいた。4 枚が縦につながった 3×12 の盤として読まれ、空行のところで縦線の読み取りに失敗して、全体が捨てられていた。

手番はどちらか

スコアを計算し直すには、それぞれの図でどちらの手番かを知る必要がある。図には手番が書かれていない。

  • 箱がまだ 1 つも取られていなければ、手番は引かれた線の本数（変種で最初から引いてある線を除く）の偶奇で決まる
  • 箱が取られた後は、箱を取った人が続けて打つので、偶奇では決まらない。そういう図は完全対局のページにしか出てこない。このページは見出しに「Player A to move」「Player B to move」と書かれ、左右の列で手番が分かれているので、列で決める

箱が取られていれば、図の A と B を数えて現在の差 D を出す。手番が A なら符号 σ = +1、B なら σ = −1 として、空いている線 e ごとに次の値を計算し、図の数字と比べる。

D + σ × (e を引いたときの、手番側から見た差)

結果

ページ 盤 スコア 一致
Analysis Results 4 100 100
3×3: 初手のあと 4 92 92
3×3: 完全対局 13 226 226
3×5 Swedish: 初手のあと 7 147 147
3×5 Icelandic: 初手のあと 30 870 870
3×4 Icelandic: 初手のあと 24 552 552
Analysis Programs（実行例） 4 93 93
Board Notation Explanation 3 49 49
計 89 2,129 2,129

1 つも食い違わなかった。完全対局は、取られた箱が入った局面も手番の決め方も含めて全部合い、最後の盤の説明 "Player A gets one more corner for a total of 3; player B gets the rest for a total of 6." もそのとおりになる。

照合しなかったものも書いておく。

  • 空いている線が 33〜60 本の盤 8 面（3×5 American、4×4、4×6 Swedish、5×5 の局面、表記説明ページの 4×4）。1 本の表には入らない
  • loony の印（^ / v）。表記説明ページで照合した 49 個のうち 17 個に付いている。数字は照合したが、印そのもの（次に loony な手を強いられるのはどちらか）は計算していない

表記も一緒に確かめる

Wilson の手は、図の文字グリッドの行と列を a から始まる英字で書く（例: be）。点は偶数行・偶数列にあるので、偶数行なら横線、奇数行なら縦線になる。

export function wilsonName(g: Geometry, e: number): string {
  const l = lineInfo(g, e);
  const L = (i: number) => String.fromCharCode(97 + i);
  return l.kind === 'h' ? L(2 * l.y) + L(2 * l.x + 1) : L(2 * l.y + 1) + L(2 * l.x);
}

Analysis Programs のページの実行例は、3×5 Swedish で A が be、B が fg と打ち、そのたびに盤を出している。テストでは、図 2 枚目の線の集合が「1 枚目 + be」、3 枚目が「1 枚目 + be + fg」とちょうど一致することを確かめている。表記説明ページの 2×3 の例（B の手番）は、Wilson が挙げた良い手 [af] [bg] [cb] [cf] [da] [dc] [eb] [ed] [ef] の 9 本と、ソルバーが最善とする線の集合が一致する。

「1 箱差」と「3 箱差」

results.shtml の 3×3 の注記：

Page 9 of The Dots-and-Boxes Game describes how player B can force a win by 1. However, player B really should win by 3.

Wilson によれば、Berlekamp の The Dots-and-Boxes Game（2000）の 9 ページは、後手が 1 箱差の勝ちを強制する方法を説明している。これは後手が少なくとも 1 箱差で勝てるという主張で、最善の差を述べたものではない。表でも空の盤の値は −3（24 本すべて）なので、後手の最善は 3 箱差で、1 箱差の勝ちを強制できるという主張とも矛盾しない。「3×3 は後手必勝」という点ではどちらも同じだが、差まで言うなら 3 になる。

「中央の手が良い」を数える

Wilson は 3×3 の初手について「どれも 3 箱差の負けだが、後手が間違える余地が一番大きいので中央の手が良い」と書いている。

Although all moves result in the second player winning by 3 with best play, a center move is best since that gives the second player the greatest opportunity to make a mistake.

表があれば、この「余地」を数えられる。初手 24 本それぞれについて、後手の応手 23 本のうち最善（−3 を保つ手）が何本あるかを数えた。

初手 本数 後手の最善の応手
中央の箱に接する線（h(1,1) h(2,1) v(1,1) v(1,2)） 4 5 / 23
外周の辺の中央の線 4 20 / 23
外周の角に接する線 8 19 / 23
その他の内側の線 8 21 / 23

中央の 4 本だけが極端に少なく、ほかの初手では後手の応手の 8 割以上が最善になる。Wilson のページ 3x3.html の 4 枚目の図（中央の横線を引いた局面）で −3 が少なく −1 が並んでいるのは、このためだ。

ページのコンピュータも、最善手が複数あるときはこの基準で選ぶ。相手の最善の応手が最も少ない手を選び、同数なら乱数で決める。箱を取れる最善手があれば先に取る。完全対局のページの説明 "each player has chosen a best move--giving the opponent as few good choices as possible" に合わせたものだ。

Wilson が載せていない盤

30 本以下の盤は全部 1 本の表に入るので、ついでにまとめて解いた。正の数は先手の勝ち（箱の差）。

盤 空いている線 最善の結果 最善を保つ初手 時間
1×1, 1×3, 1×5, 1×7 4〜22 −1 全部 0.4 秒以下
1×2, 1×4, 1×6, 1×8 7〜25 0 1 本 3.3 秒以下
2×2 12 +2 8 / 12 0 秒
2×3 17 −2 17 / 17 0 秒
2×4 22 +2 18 / 22 0.5 秒
2×5 27 −2 27 / 27 15.9 秒
3×3 Icelandic 18 −1 2 / 18 0 秒
3×3 Swedish 12 +7 4 / 12 0 秒
4×4 Swedish 24 0 8 / 24 2.3 秒
3×6 Swedish 27 +4 2 / 27 20.3 秒

1×n の盤は、奇数なら後手がどう打っても 1 箱差で勝ち、偶数なら引き分けになる。偶数の盤で引き分けを保てる初手は 1 本だけだ。2×n も n = 2〜5 では、偶数で先手 +2、奇数で後手 +2 と交互になる。Winning Ways が「4 箱のゲーム」として紹介する 2×2 は先手が 3 対 1 で勝つが、12 本の初手のうち 4 本では引き分けまでしか取れない。

テスト

12 件。

  • 線の数（3×3 で 24、3×5 で 38、Icelandic 3×5 で 30、Swedish 3×5 で 22）と、Wilson 式の手の名前の往復
  • 表を使わない素朴なゲーム木探索（スコアを持ち回る、履歴つきの実装）と、ランダムな局面で表の値が一致する（1×1、1×2、1×3、2×2）
  • 各局面の値が、子の評価の最大値になっている
  • 3×3 で、左右反転した局面の値が等しい
  • 31 本以上の盤は表を作らずに例外を投げる
  • Wilson の図: 3×3 の初期値、表記説明ページの例と良い手 9 本、実行例の be → fg、完全対局 13 面、3×4 Icelandic の初手 24 面、3×3 と 3×5 Swedish の応手

3×5 Icelandic（1 GB・150 秒）はテストに入れず、npm run stats で照合している。

まとめ

  1. スコアは局面の外に出す。 それまでの得点が今後の最善手に影響しないゲームでは、局面は盤の状態だけでよい。ドット・アンド・ボックスなら「引かれた線の集合」で、1 本の整数になる
  2. 線を足すと整数が増えるなら、大きい方から 1 回なめるだけ。 探索の順序を考える必要がない
  3. 公表値は写さずに読む。 ASCII 図をそのまま保存してパーサで読むと、2,129 個の数字を 1 つも写し間違えずに照合できる。ただし実際のページには、タブ、横並び、地の文、縦につながって見える盤、という罠がある
  4. 「3×3」はまず単位を確かめる。 点の数か箱の数かで盤が違う
  5. 「必勝」と「差」は別の主張。 1 箱差の勝ちを強制できることと、最善の差が 3 であることは両立する

数値はすべて npm run stats が出力する src/stats.json から、ページのノートとこの記事に写している。照合したスコア 2,129 個とチェック 8 件は、すべて一致した。テスト 12 件。ソルバー内蔵パズル第 77 弾。

参考文献:

  • D. Wilson, "Dots-and-Boxes Analysis Results" / "Analysis Methodology" / "Analysis Programs" / "Board Notation Explanation", University of Wisconsin, http://wilson.engr.wisc.edu/boxes/ （web.archive.org の 2017 年のスナップショットを 2026年9月28日参照）
  • E. Berlekamp, The Dots-and-Boxes Game: Sophisticated Child's Play, A K Peters (2000)
  • E. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays, Vol. 2, Chapter 16 (1982)
  • Wikipedia, "Dots and boxes"（2026年9月28日参照）

デモ: https://sen.ltd/portfolio/dots-and-boxes/
リポジトリ: https://github.com/sen-ltd/dots-and-boxes

1
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?