囲碁の整地最適化

思ったよりも X 上で反応をもらえたので内部でどのような処理をしているのか書こうと思います。

囲碁の整地

囲碁は対局が終わった後にお互いの確保した陣地を数える整地という工程があります。
目視で数が確認しやすいよう基本的には10の倍数になるように陣地を整えます。

整地は一般には速いほうが好まれ、棋力が高い人のほうが速い傾向があります。
速いということは動かす石の数や距離が小さいということだよなということで、最適化問題に落ちそうだなと思ったのが着想でした。

1. 盤面生成

まずは囲碁の対局が終わった状態を用意する必要があります。
終局後に石の生死判定をすることなどは避けたかったので、実際の棋譜を収集したり、対局をシミュレートする方針は捨てました。

囲碁の終局盤面には「黒地」 「黒石」 「白地」 「白石」の4つがあり、（死に石や例外は無視します）、「黒地」は「黒地」または「黒石」に、「白地」は「白地」または「白石」に囲まれている必要があります。
4つも状態があると大変なので、まずは盤面を黒石と白石で埋めてから、その中をくり抜こうというアイディアを採用しました。

盤面を黒石と白石で埋める際に、後で中をくり抜けるぐらいのサイズは確保したうえである程度塊を盤面全体に散布したくなります。
この生成にパーリンノイズを用い、適当な閾値より上を黒地、下を白地とすることで盤面を埋めました。
雰囲気としては凸凹した地形を作るのによく採用されるアルゴリズムを持ってきて、標高の高さで黒白に分けた感じです。
気に入った雰囲気の生成が繰り返されるようにパラメータの調整は行いました。

その後、適当な確率で黒石や白石の中をくり抜いて地を生成しました。
ただ、場合によっては十分な数くり抜けず、死に石となってしまうものも存在したので、簡単な死活判定を行って死に石を除去するなどの後処理を入れました。

2. 移動する石の最小化

黒地と白地は同様に扱えるので、黒地についてのみ考えます。

なるべく少ない数の黒石を動かすことで黒地の形を整形することが目標になります。
整地において採用される地の形にはいくつかパターンがあり、例えば、「2x5」型、「3x4-2」型、「3x7-1」型などがあります。
実は10の倍数のパターンは少なく、形も長方形なので扱いやすいのですが、端数は数として9個あり、かつ奇数の場合は回転で4パターンあったりするのでこちらのほうが厄介です。

地の全パターンの全置き場所を01変数として、整数計画問題を解きました。
制約としては、内部が黒地または黒石であることや、パターンの領域が重複しないこと、地の数が一致することなどをおきました。
評価としては、勿論動かす石の個数が小さいほうが良いのですが、境界に相手の石があることに対してもペナルティを設定しました。実際の整地においても境界が相手の石になるということが避けられないケースはあるのですが、可能なら避けて欲しいという気持ちを反映したものになります。

ソルバとしてはgood_lpにてサポートされていたhighsを用いました。
実はアルゴリズム部分はWASMとして実装していたのですが、このソルバを使うためにAPI形式にした背景があります。

3. 移動する距離の最小化

2. 移動する石の最小化によって、初期盤面と整地後盤面がわかったとき、石が動くアニメーションを作りたいなと思って解いた問題になります。
黒石と白石と同様に扱えるので、黒石についてのみ考えます。

初期の黒石の配置と整地後の黒石の配置が与えられたとき、各黒石がどこに移動すれば移動距離が最小になるかという問題になります。
これはアルゴリズムに慣れているとフローを使えば解けることがわかるのですが、調べてみるとハンガリアン法というもう少し狭いアルゴリズムが存在したのでそちらを適用しました。

あとがき

実は自分は一行もコードを書いておらず、生成AIに指示して着想から半日ほどで作りました。
生成AIがなかったら1週間で作れたかも怪しいので、便利だけど怖い時代になったなと思いました。

成果物はGitHubに置きましたが、実装細部の保証はないです。