ColorShapeLinks AI competition 2021 参加記

CoG

参加者10人中、BaseTrackで同率1位、UnknownTrackで2位でした。

ゲームルール

f:id:assy0000:20210821143447p:plain 重力付き4目並べ(https://en.wikipedia.org/wiki/Connect_Four)。ただし、通常と異なるのは、コマには色(color)と形(shape)の2要素があり、どちらかの要素で4目連続で並べたら勝ち。

  • ボードサイズは6 x 7
  • 先手は白い丸いコマを10個と白い四角いコマを11個持っている
  • 後手は赤い丸いコマを10個と赤い四角いコマを11個持っている
  • 先手は白のコマを4目並べる or 丸いコマを4目並べれば勝ち
  • 後手は赤のコマを4目並べる or 四角いコマを4目並べれば勝ち

1盤面で同時に2つの4目並べを行うイメージ。通常のConnect4では自分の手番で相手が勝つことはないが、このルールだと、相手の形を自分が並べてしまうことがある。

(上記パラメータはBaseTrackのものでUnknownTrackではもっと大きいサイズとなる)

戦略

基本的にはMCTS。木の展開はWikipediaそのまま(https://ja.wikipedia.org/wiki/モンテカルロ木探索#UCT_(Upper_Confidence_Tree))。cは0.8に設定。

高速化

盤面をビット表現して高速化した。ビット表現は通常のConnect4を完全解析するコードの解説記事を参考にした(http://blog.gamesolver.org/)。64bit整数5つ*1で盤面表現でき、手番を進める操作・4目並んでいるかの判定がビット演算で高速に行える。すごく賢い。他の落ち物ゲーでも使えそう。

ランダムプレイアウトの改良

プレイアウトは以下のようにした 。

  • 勝ち確定の手があればそれを指す(一手読み)
  • 次の相手の手番で置かれたら負ける列があるなら、その列に置く(二手読み?)
  • 次の相手の番に同じ列に置かれたら負けるなら、その列には置かない(二手読み。相手の形を置く場合は、次の相手の手番で別の列に置かれて負けることもあり得るが、そこまで計算していると遅くなり弱くなったので、同じ列のみ考慮した。)
  • 序盤(先手・後手5手ずつ)は自分の形しか使わない
  • 上記以外はランダムに選択

序盤定石

序盤(先手・後手5手ずつ)は定石を作成した。自分のAIのリプレイを見ていると、序盤は自分の形しか使わないし、直感的にも序盤に相手の形使ったら弱そうなので、そのように限定する。自分の形しか使わないと通常のConnect4と同じになるので、通常のConnect4の最善手を使えば良いのではと思い、使ってみると後手はめっちゃ強くなった。しかし、面白いことに先手は全く強くならなかった。なので、先手の定石は一手30秒かけてMCTSで作成した。 提出コードサイズの制限は1MBなので、定石は序盤のみしか使用できなかった。

終盤読み切り

終盤(先手12手目以降・後手11手目以降)はαβ法で最後まで読み切って最善手を指すようにした。ただ、終盤までくるとMCTSでも勝ち負けが逆転するような手は指されないっぽいので、あまり意味がなかったかもしれない。

Unknown Track

今までの話は全てBase Trackの戦略。Unknown Trackでは盤面が64bitに収まらないのでBigIntegerを使ったが、使い物にならないくらい遅くなったので、何の工夫もせず完全にランダムプレイアウトでMCTSをした。

その他

  • 言語はC#のみだったが、余裕を持って打ち切ったつもりでも、GCのせいでTimeoutするということが頻発した。プレイアウトの回数に上限を設けるのと、制限時間の50ms前に打ち切るようにした。GCの起動が相手のプログラムにも依存しているっぽいのがやばかった。時間ギリギリまで使う相手だったらGCを押し付ける闇のゲームが可能かもしれない。
  • Unknown Trackでは複数コア使えるので、来年も参加するなら並列化を試してみたい。
  • 頑張れば完全解析できそうな気がする。完全解析されても提出1MB制限があればコンペは成立するか(?)

*1:頑張れば64bit整数3つでいけそうだったけど、プログラムが複雑になる&速くはならなそうなので5つにした