最強の立体四目並べAIを作る part1 | 概観

今回作ったのがどんな特徴をもつAIなのか、まずは概観から見ていこうと思います。
コードはこちらで公開しています↓↓↓。
https://github.com/mikanakim/score4_AI/tree/main/score4 

目次

ボードゲームが強いAIの特徴

今回作成したAIは木探索アルゴリズム(alpha beta法)とヒューリスティックな評価関数を用いた実装となっています。
そもそもボードゲームAIには強化学習と木探索の大きく2つの種類があります。強化学習とは、自己対戦によって強くなっていくAIのことで、囲碁でイ・セドルを破ったAlpha GoやAlpha Zeroで注目を浴びました。木探索は多くのAIで使用されている盤面の先読みをするためのアルゴリズムです。今回は後者を選択しました。
では、木探索を用いた強いボードゲームAIはどういう特徴を持っているのでしょうか？大まかに言うと次の2つが特に重要だと考えます。

1. 読みの深さ

盤面の枝分かれが木のように見えるので、木探索という

自分がこう打ったら相手はここに打ってくるはずで、、、など人間がゲームをするときも少なからず先の展開を予想して進めていると思います。当然先の展開まで幅広くかつ正確に読めれば強いはずです。
とはいうものの、実は深い読みを実装するのは案外難しいことなのです。例えば立体四目並べでは1手選ぶのに選択肢が16通りあるので、単純計算で2手の先読みでは256通り、3手だと4,096通り、4手だと65,536通りと指数関数的に状態数が増えていくからです。すると、1回1msで行えるような一見速い処理でも4手読みで65,000回繰り返すと65秒かかってしまう計算になります。
実際は更に多くの回数処理をする必要があるため、先読みは実装上、高速化が鍵となります。そもそもPythonではなくC++で実装したのも処理速度が速いのが主因です。このAIでは以下のような高速化を施しました。

• bit board

• alpha beta法

• iterative deepening(反復深化)

• move ordering

• zobrist hash

• その他、C++の実装上の高速化

その結果、このAIでは最大で序盤は9手、中盤は15手、終盤は29手程度の先読みが可能になりました。ちなみに以前高速化手法を何も知らなかった時にPythonでAIを作ったら、実用的な時間でできる先読みは4手が最大でした。大きな進歩です。

2. 評価関数の正確性

不適切な評価関数を使うとむしろ不利な状態になってしまう

次に重要なのは評価関数の正確性です。
ただ単に機械的に先読みができるだけではどの展開が最適なのかはわからないので、先読みした盤面を評価する必要があります。そこで、盤面に点数をつけることを考えます。
例えば、オセロは角を取ると良い、将棋は飛車と角が強いというように、ゲームには盤面の良し悪しを規定する要素がいくつかあります。これらをうまく数値化して評価値として扱います。そして盤面情報から評価値を計算する関数を評価関数といいます。
自分の評価値を最大化し、相手の評価値を最小限に抑えることが最善手の選択、さらには勝利へとつながるわけです。しかし、評価関数が間違っていると、有望な手を逃してしまうことになります。そのためできる限り正確な評価関数の設計が求められます。
本AIではretu27.comさんのAI¹⁾の評価関数を改良したものと、私自身で作成した独自の評価関数を組み合わせたものを使用しています。具体的には以下の項目を評価しています。

1. 座標ごとの将来的にできうる連の数

2. lineに含まれる球の種類・数・パターン

3. 三段決勝点の数

4. 立体四目並べの勝利条件に基づいた評価(ゲームロジックベース)

序盤は1, 2、中盤は2, 3, 4、終盤は4が主に活躍します。終局まで完全読みをする
段階になると評価関数は必要なくなります。

※余談ですが、二人零和有限確定完全情報ゲームという言葉があります。
二人対戦で、一方が得をするともう一方は同じだけ損をし、終局があり、偶然性に左右されず、互いの情報がすべて公開されているゲームということです。理論上完全な先読みが可能ですが、状態数が多いので多くのゲームで現実的には不可能です。そこで我々は評価関数を使って擬似的に損得を表現し、最善手を探しているのです。

コードの構成

alpha_beta.cpp

探索アルゴリズム(alpha beta法)と反復深化、move orderingなど。

evaluation.cpp

評価関数を定義してある。
potential_4_line(): 将来的にできうる連の数を計算する関数。
line_evaluation(): retu27.comさんの評価関数の改良版
game_logic_evaluation(): 今回新規で作成した独自の評価関数。

game.cpp

bit boardを使った盤面管理やロジックが書いてある。
リーチの検出や棋譜の作成、出力のための関数など。

global.cpp

global変数。
終盤の完全読みの手数などをここで指定できる。

hash.cpp

zobrist hashで探索を高速化するための関数。
手番が変わるたびにhashを計算したり、盤面をhash化して保存したり。

main.cpp

実際のゲーム進行部。

player.cpp

人間がプレイする時ための関数とAIがプレイするための関数。

time.cpp

対局時に探索が制限時間内に終わらなければ打ち切る処理を設けている。
その時間管理をするための関数。

次回のテーマ

立体四目並べのbit boardによる実装について解説します。

参考文献

1) retu27.com
　 https://retu27.com/scorefour_cpu_nosupport.html