読者です 読者をやめる 読者になる 読者になる

ブロックスデュオ プログラム対戦 結果

Blokus

http://hp.vector.co.jp/authors/VA003988/gpcc/07g1b.htm

なんと一位をとってしまったらしい。
とりあえずソース置いときます。応募した版から微妙に修正してます。

hmmm 同士の対戦では勝率 7:3 くらいで先攻が有利だったので、2位との対戦で先攻だったのがラッキーだったかも。*1

以下、アルゴリズムの解説とか。

局面評価

hmmm の評価関数は非常にシンプルです。先手後手それぞれの

  • 置かれたピースの数と種類
  • 勢力範囲

からスコアを計算し、局面を評価しています。

置かれたピースによる評価

盤面に置かれている自分のピースの大きさと数で評価します。

  • 大きさ 5 のピースが 1 個置かれているごとに +16 点
  • 大きさ 4 のピースは +10 点
  • それ以外は ピースの大きさ × +2 点

大きいピースを優先的に置くような重み付けです。最初に実装したとき適当に決めた値そのままですが、それなりにうまく動いてるようです。

勢力範囲

これがミソ。それほど重くない計算で、かなり正確に形勢を評価できます。

こいつに辿り着くまでは、いくつかの尺度を組み合わせて重み付けを調整して…とかやってたんですが、こいつが効果的すぎて全部吹っ飛んでしまいました。

自分のピースと角を共有して辺を共有しない空きマス(下図☆)と、☆のマスから距離 3 までの空きマスで

  • ピースが置かれているマス
  • 自分のピースと辺を共有した空きマス

を通らずに行けるマス(下図・)を勢力範囲とします。スコアは勢力範囲 1 マスにつき +1 点とします。

下図の例だと、左側で☆か・がついているマスが先手側の勢力範囲、右側で☆か・がついているマスが後手側の勢力範囲になります。先手側の勢力範囲は 69 マス、後手側は 55 マスで先手優勢です。

1 2 3 4 5 6 7 8 9 A B C D E 1 2 3 4 5 6 7 8 9 A B C D E ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━┓ 1┃・・ ■ □・・・・ ┃ □☆ ■ ☆・・・・ ┃ 2┃・・ ■ □□□☆・・・ ┃ □ ■■■ ☆・・・┃ 3┃・☆ ■ ・□■□□・ ┃ □☆ ■□■■ ☆・・┃ 4┃・ ■■ ☆ ■■□□ ┃ □□・☆ □□■■ ・・┃ 5┃・☆ ■ ■■ ☆□ ┃ □・□□☆ ■ ・・┃ 6┃・・ ■■■ ☆□ ┃ □□□・☆ ■ ☆・・┃ 7┃・・☆ ■ ■■□□□・ ┃ □ □□■■■ ・・┃ 8┃・・・☆ ■ ■■■□・・ ┃ □ □□□■ ・・┃ 9┃ ・・・ ■□ □□☆・・・┃ □■ ■■ ☆・・┃ A┃・・・・ ■□ □□・・・ ┃ □■ ■■ ・・・┃ B┃・・☆ ■□ □・・・ ┃ □■ ■ ☆・・・┃ C┃・・ ■ ■□□・ ・ ┃ □ □■■ ☆・・・ ┃ D┃・・ ■■ ☆・・・ ┃ □□☆ ☆・・・ ┃ E┃・・☆ ■■ ・・ ┃ □□・・・・・ ┃ ┗━━━━━━━━━━━━━━┻━━━━━━━━━━━━━━┛

☆から距離 2、距離 4 までの場合も試しましたが距離 3 までの場合がやや強いようです。
意味づけをするなら、勢力範囲は「次の一手でピースを置けるマスの数の近似」という感じでしょうか。陣地の広さと着手の自由度を表していると考えられます。

シンプルな評価方法ですが、数手先まで読むと

  • 相手がすり抜けられないように囲む
  • 広い陣地を確保しようとする
  • 自陣内ではできるだけピースの間を詰めて置く

など、賢い置き方をするようになります。

あと人間が盤面の形勢を見るときの感じに近いんじゃないかという気がします。自分は弱いので強い人がどう見てるかは分かりませんが…

探索アルゴリズム

評価関数が決まったらあとは探索を効率化して、より先の手まで読めるようにしていきます。

素人なのでオセロの解説サイトで勉強しつつ。詳しく知りたい人は各自検索してください。

  • NegaScout 法
  • 置換表
  • 反復深化
  • ProbCut (2,4)

ProbCut は大会前日の差し替えで入れたんですが、かなり効果があって 4 倍くらい速くなりました。

序盤(〜12手目)は 4〜5 手、中盤(13手目〜20手目)は 6〜10 手くらいまで先読みしています。20手目〜25手目から必勝読み、27手目からは完全読みです。
序盤は定石ベースにしたかったんですが、そんなものを作る時間があるはずもなく。先手の1手目だけ、あらかじめ持ってる 10 パターンからランダムに選んでいます。

感想とか

単純な盤面評価でここまで強くなるのが面白いですね。hmmm の方法は評価関数をシンプルにして深くまで読むというある種力技なんですが、他のプログラムがどうやってたのか知りたいところです。

あと、hmmm の思考の弱点ってあるのかなと。今回はお互い手の内が見えない状態での対戦だったわけですが、アルゴリズムを公開したことで、hmmm の裏をかくような思考をするプログラムが作れるのかどうか。

大会後の懇親会では人間の勝ちだったそうです。私は思考時間 5 秒の hmmm にすら勝てないのに…

*1:この週末に 2位の "BlocksDuo" との再戦(BlocksDuo が先手)があるとのこと。楽しみ。