福野泰介の一日一創

Code for KOSENで開催中、第三回、囲みますプロコン（プログラミングコンテスト競技部門）の盛り上がりました。 それぞれ個性的なAIを持ち寄り、リーグ戦、優勝したのはjigインターン2020参加OB、ぷれーん！

その中の一戦をご紹介！点数のグラフ表示が交錯する熱い展開、ゲーム実況強い人、観戦するだけの方もウェルカムです。

実際対戦してみて次の戦略を練る人、よりわかりやすくフロントエンドをいじる人、よりAIが作りやすくなるバックエンドをいじる人、私はバックエンドの一部、コアを中心にあれこれサポート。 いろんなプログラミング言語でぜひ参戦ください！（コメント・要望大歓迎、プルリクはmasterをロックし1人レビューでマージ可能としています）

福井高専の学生から指摘あって、今回修正した「囲みます」の一番のウリ、JavaScriptで実装している囲むアルゴリズムを解説。

囲むアルゴリズム
1. 全プレイヤー分、囲まれたフィールドをフラグ設定する
  1.1 外側1マス残した内側を全点をチェック (chk関数)
    1.1.1 自分の色の壁、チェック済みなら、チェック継続
    1.1.2 外周に出たら囲まれていないことが確定するので、チェック中断し、次の点へ
    1.1.3 8方向(上下左右斜め)を再帰的にチェック
2. プレイヤー同士、かぶったところは小さい方を優先する
  2.1 領域の大きさをカウントする再起関数 countArea を用意
  2.2 かぶっている他プレイヤーの領域を削除する再起関数 removeAreaExcept を用意
  2.3 領域のかぶっているところは、一番小さな領域のプレイヤー分だけを残す
3. 最終的に残った分の領域で、フィールドの部分をそのプレイヤーIDで塗る

以下、その実装です。（src on GitHub）

fillBase() { const w = this.board.w; const h = this.board.h; const field = this.field; // 1. 全プレイヤー分、囲まれたフィールドをフラグ設定する const areas = []; for (let pid = 0; pid < this.board.nplayer; pid++) { const flg = new Array(w * h); const area = new Array(w * h); areas.push(area); for (let i = 1; i < w - 1; i++) { for (let j = 1; j < h - 1; j++) { if ( flg[i + j * w] || this.field[i + j * w][0] === Field.WALL ) { continue; } const fill = new Array(w * h); const chk = function (x, y) { if (x < 0 || x >= w || y < 0 || y >= h) return false; const n = x + y * w; if (fill[n]) return true; fill[n] = true; const f = field[n]; if (f[0] === Field.WALL) { if (f[1] === pid) { return true; } } else { fill[n] = true; } if (!chk(x - 1, y)) return false; if (!chk(x + 1, y)) return false; if (!chk(x - 1, y - 1)) return false; if (!chk(x, y - 1)) return false; if (!chk(x + 1, y - 1)) return false; if (!chk(x - 1, y + 1)) return false; if (!chk(x, y + 1)) return false; if (!chk(x + 1, y + 1)) return false; return true; }; if (chk(i, j)) { fill.forEach((f, idx) => { area[idx] = true; }); } } } } // 2. プレイヤー同士、かぶったところは小さい方を優先する const countArea = (area, x, y) => { const flg = new Array(w * h); const countA = (x, y) => { const idx = x + y * w; if (!area[idx] || flg[idx]) return 0; flg[idx] = true; let cnt = 1; cnt += countA(x - 1, y); cnt += countA(x + 1, y); cnt += countA(x, y - 1); cnt += countA(x, y + 1); return cnt; }; return countA(x, y); }; const removeAreaExcept = (x, y, expid) => { const flg = new Array(w * h); const area = areas[expid]; const removeAE = (x, y) => { const idx = x + y * w; if (!area[idx] || flg[idx]) return 0; flg[idx] = true; for (let pid = 0; pid < this.board.nplayer; pid++) { if (pid === expid) { continue; } areas[pid][idx] = false; } removeAE(x - 1, y); removeAE(x + 1, y); removeAE(x, y - 1); removeAE(x, y + 1); }; removeAE(x, y); }; for (let i = 0; i < w; i++) { for (let j = 0; j < h; j++) { const idx = i + j * w; let min = w * h; let pmin = -1; let nfill = 0; // 競合数 for (let pid = 0; pid < this.board.nplayer; pid++) { const area = areas[pid]; if (area[idx]) { const cnt = countArea(area, i, j, 0); if (cnt > 0) { nfill++; if (cnt < min) { min = cnt; pmin = pid; } } } } if (nfill > 1) { removeAreaExcept(i, j, pmin); } } } // 3. 最終的に残った分の領域で、フィールドの部分をそのプレイヤーIDで塗る for (let pid = 0; pid < this.board.nplayer; pid++) { const area = areas[pid]; for (let i = 0; i < w; i++) { for (let j = 0; j < h; j++) { const idx = i + j * w; if (area[idx]) { if (this.field[idx][0] === Field.BASE) { this.field[idx][1] = pid; } } } } } }

他のプログラミングでコアを作る人の参考になれば幸いです。
もっと効率良いアルゴリズムあるぞって方、ぜひプロジェクトご参加ください！
（ヒミツにして強いAIに活かして参戦もありです！）

links
- Code for KOSEN - About