オセロの合法手はどう探すのか：8方向を一歩ずつ歩く

合法手の条件を「歩き方」に言い換える

黒番で空きマスに置けるのは、8方向のうち少なくとも1方向で次の形ができるときです。

1. 隣のマスから、白が1個以上続く。
2. その白の列の直後に、黒がある。

この形を歩き方にすると、次のようになります。

1. 空きマスを出発点にして、1方向へ1歩進みます。
2. 白なら記録して、さらに進みます。
3. 白でないマスに着いたら止まります。
4. 止まったマスが黒で、記録した白が1個以上あれば成功です。記録した白がその方向で返る石です。
5. 空きマス、盤の外、または白を1個も踏まずに黒に着いた場合は失敗です。

8方向すべてを歩き、成功した方向の白を全部集めます。集めた石が、そのマスに置いたときに返る石の一覧です。一覧が空なら、そのマスは置けません。

盤面の図で8方向を歩く

練習用に5×5の小さな盤を使います。実際の対局の局面ではなく、8方向の結果がすべて違うように作った配置です。黒番で、列は a〜e、行は上から1〜5とし、B が黒、W が白、. が空き、* が調べるマスの c3 です。

   a b c d e
1  . . B . B
2  . . W W .
3  . B * W W
4  . W W . .
5  B . . . .

c3 から8方向を歩いた結果は、次のとおりです。

• 上、歩いた先：c2 が白、c1 が黒、結果：成功：c2 が返る
• 右上、歩いた先：d2 が白、e1 が黒、結果：成功：d2 が返る
• 右、歩いた先：d3 が白、e3 が白、その先は盤の外、結果：失敗：黒に届かない
• 右下、歩いた先：d4 が空き、結果：失敗：白が1個もない
• 下、歩いた先：c4 が白、c5 が空き、結果：失敗：白の列が空きで終わる
• 左下、歩いた先：b4 が白、a5 が黒、結果：成功：b4 が返る
• 左、歩いた先：b3 が黒、結果：失敗：隣が自分の石
• 左上、歩いた先：b2 が空き、結果：失敗：白が1個もない

3方向が成功したので、c3 は合法手です。返る石は c2、d2、b4 の3つです。右の方向は白が2個続いていても盤の端で終わるので、1つも返りません。「白が続いていること」ではなく「白の列の先に黒があること」が条件だと、この図から読み取れます。

同じ手順をコードにする

図の手順を、そのままコードにします。盤は2次元配列で、'B' が黒、'W' が白、null が空きです。8方向は「行の増分、列の増分」の組で表します。

const DIRS = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

function flipsInDirection(board, r, c, dr, dc, me) {
  const n = board.length;
  const opp = me === 'B' ? 'W' : 'B';
  const line = [];
  let y = r + dr, x = c + dc;
  const inside = () => y >= 0 && y < n && x >= 0 && x < n;
  while (inside() && board[y][x] === opp) {
    line.push([y, x]);
    y += dr; x += dc;
  }
  return line.length > 0 && inside() && board[y][x] === me ? line : [];
}

function flipsAt(board, r, c, me) {
  if (board[r][c] !== null) return [];
  return DIRS.flatMap(([dr, dc]) => flipsInDirection(board, r, c, dr, dc, me));
}

function legalMoves(board, me) {
  const moves = [];
  board.forEach((row, r) => row.forEach((_, c) => {
    const flips = flipsAt(board, r, c, me);
    if (flips.length > 0) moves.push({ r, c, flips });
  }));
  return moves;
}

// 図の5×5盤で c3（行2・列2、0始まり）を調べる
const rows = ['..B.B', '..WW.', '.B.WW', '.WW..', 'B....'];
const board = rows.map(s => [...s].map(ch => ch === '.' ? null : ch));
console.log(flipsAt(board, 2, 2, 'B'));

実行すると [[1,2],[1,3],[3,1]] が出るはずです。行と列は0始まりなので、c2、d2、b4 に当たります。DIRS の並び順に結果が並ぶため、順序は図の表と少し違って見えます。

図の表とコードの対応は次のとおりです。

• 表の1行が flipsInDirection の1回の呼び出しです。
• 「白が続く間は進む」が while です。
• 「黒に届いたか」が最後の return の条件です。
• 8行の結果を結合する処理が flatMap です。
• 空きマスの全探索が legalMoves です。

起こりやすい間違い

この手順は短いぶん、間違いの入り込む場所も決まっています。

• 範囲の確認より先に盤を読むと、盤の端で未定義の値を読んでしまいます。while の条件で、範囲の確認を先に書きます。
• 白を1個も踏まずに黒へ着いた場合を成功にしてしまうと、隣が自分の石のマスまで置けることになります。上のコードの line.length > 0 がその防止です。
• 方向ごとに「成功か失敗か」を決めずに、白を全体の一覧へ直接足してしまうと、失敗した方向の白まで返ってしまいます。図の「右」の方向が、この間違いの確認に使えます。
• 空きでないマスを調べてしまうと、すでに石のあるマスが合法手になります。flipsAt の先頭で弾きます。
• 探索中に盤を書き換えると、次の方向の判定が狂います。探索は読むだけにして、石を返す処理は置く手を決めたあとで行います。

自分で確かめる確認問題

開始局面の黒番の合法手は、d3、c4、f5、e6 の4つです。開始局面は d4 と e5 が白、d5 と e4 が黒です。この4手を、図と同じ表の形で手計算してから、コードの結果と照らし合わせてみてください。どれも返る石は1つです。

もう一問あります。黒が d3 に置くと、d3、d4、d5、e4 が黒、e5 だけが白になります。この局面で白の合法手を、白の e5 から8方向のうち黒が続く方向を歩いて探してみてください。答えは c3、e3、c5 の3つです。コードで legalMoves を白番で呼んで一致するか、自分の手計算と見比べます。

候補を数える手順は、そのまま「置ける手がない手番のパス」にもつながります。legalMoves の結果が空なら、その手番は置けません。

「潮目のオセロ」から読み取れること

「潮目のオセロ」には、返る石のプレビュー、理由付きヒント、友達との招待リンクのオンライン対局があり、置けない手番は自動でパスになります。ここから、設計について次のことが読み取れます。

• 返る石のプレビューは、flipsAt が返す一覧と同じ種類の情報を画面に出したものと考えられます。合法判定とプレビューは、一つの探索から両方作れるからです。
• 理由付きヒントも、成功した方向と挟まれた石が分かれば文章にしやすくなります。実際の文面の作り方は、作品を開いて確かめる部分です。
• 自動パスは「合法手が一つもない」状態を検出する仕組みを前提にしています。
• オンライン対局では、手番・合法手・勝敗の確認をサーバーが行います。画面の表示とサーバーの判定が同じルールで一致している必要があります。

作品の内部のコードは確認済み事項にないので、実装の細部は断定できません。代わりに、作品の中で自分の手計算と見比べる方法があります。ひとり対局で、置く前にマスへ合わせたプレビューが、自分で歩いた結果と一致するか確かめます。自動パスは、置けるマスがない局面に出会うまで遊ぶか、実際の対局で確かめます。

次の行動

まず上のコードを単独のHTMLに貼り、図の5×5盤で [[1,2],[1,3],[3,1]] が出ることを確認してください。次に8×8の開始局面で黒の4手を出し、確認問題の白の3手と照らし合わせます。最後に「潮目のオセロ」を開き、プレビューの石が自分の手計算と一致するか、局面をいくつか見比べてみてください。