幅優先探索:BreadthFirstAIPlayer

BreadthFirstAIPlayer は、幅優先探索により最善手を探すプレーヤーです。
深さ優先探索がとにかく次へ次へと何手も先の手を読んでいくのに対して、幅優先探索は一手先のすべての手を読んでからさらに次の手を読むように、探索範囲を横に横にと広げていきます。

BreadthFirstAIPlayer01b

思考アルゴリズム

深さ優先探索を採用する DepthFirstAIPlayer は、ゲームの終盤にならないと手を読み切ることができず、結局、次にどの手を選択すればよいのか判断できないというのが最大の弱点でした。

幅優先探索を採用する BreadthFirstAIPlayer は、この弱点の克服を狙ったものです。具体的には、次のようなアルゴリズムで手を選択します。

  1. 数手先の手を網羅的に予測する。
  2. 予測した数手先の手それぞれに対して、どの程度自分に有利かを示すスコアを算出する。
  3. より高いスコアが得られる手を選択する。

それぞれのステップについて、より詳しく見てみましょう。

ステップ1) 数手先の手を網羅的に予測する

今、●(黒) の番だとします。

ここから、次の手、次の次の手、そのまた次の手・・・ を機械的・網羅的に洗い出します。

BreadthFirstAIPlayer02
BreadthFirstAIPlayer05
BreadthFirstAIPlayer03
BreadthFirstAIPlayer05
BreadthFirstAIPlayer04

ふぅ…
たったの2手先で、これだけのパターン数になりました。

実際には、これを数手~十数手先まで機械的・網羅的に読んでいきます。人間にとってはツラい作業ですが、コンピュータにとってはどうということのない作業です。

ステップ2) 予測した数手先の手それぞれに対して、どの程度自分に有利かを示すスコアを算出する。

さて次に、ステップ1で洗い出した手それぞれについて、自分にとってどの程度有利な状態なのかを見極めなければなりません。それが分からなければ、結局どの手を目指せばよいのか判断できないからです。

リバーシ盤の状態が自分にとってどの程度有利なのかを、スコア、つまりひとつの数字で表すことにしましょう。スコアを算出するロジックを評価関数と呼ぶことにします。

この評価関数をどのように設計するかでAIプレーヤーの強さが決まると言っても過言ではありません。

ここでは試しに、リバーシ盤のマス目ごとに点数を付け、自分の石が置かれている場合は加算し相手の石が置かれている場合は減算することでスコアを算出する評価関数を採用してみましょう。

BreadthFirstAIPlayer06a

角を取ると有利なことが経験的に分かっているため、20点という大きな数字を付けてみました。角の隣は相手に角を与えることに繋がりやすいため、0点としています。その他のマス目にも適当に点数を付けました。
※ ご存知の通りリバーシ盤は8×8ですが、ここでは簡略化して6×6としています。

この評価関数によってそれぞれの状態のスコアを算出すると、次のようになります。

BreadthFirstAIPlayer07

プラスの数字は ●(黒) が優勢であることを、マイナスの数字は ○(白) が優勢であることを表します。

ステップ3) より高いスコアが得られる手を選択する。

ステップ2で得られたスコアに基づき、DepthFirstAIPlayer の解説でも触れた「ミニマックス法」を用いて手を選択します。

n+1手目は ○(白) の番ですので、自分にとって有利な手、つまりスコアの小さな状態に繋がる手を選ぶはずです。そう仮定することにより、n+1手目のスコアが決まります。

BreadthFirstAIPlayer08a

n手目は ●(黒) の番ですので、スコアの高い状態に繋がる手を選ぶべきです。

BreadthFirstAIPlayer09a

以上により、今 ●(黒) が打つべき手が決まりました。●(黒) は左上の角に打つべきです。
結果として現時点(n手目)のスコアが 0 となりましたので、黒白拮抗しているということになります。

評価関数について

ここまで見てきたように、幅優先探索を採用する BreadFirstAIPlayer はゲーム中盤までしか読みを進めません。そのため、ゲーム中盤のリバーシ盤の状態を評価する必要があり、この評価関数の精度(妥当性)が極めて重要になります。

上の説明では「リバーシ盤のマス目に付けた点数によりスコアを算出する」という単純な評価関数を採用し、マス目の点数も適当に付けたものでした。恐らく、非常に弱いAIプレーヤーが出来上がるでしょう。マス目ごとの点数を最適化することで少しは改善されるでしょうが、たかが知れています。強いAIプレーヤーを作成するためには、この評価関数を改善する必要があります。

BreadthFirstAIPlayer では、次の2つの評価関数のハイブリッドでリバーシ盤の状態を評価しています。

  1. 自分の石を打てる場所の数によってリバーシ盤を評価する評価関数
  2. 既に置かれている石の数によってリバーシ盤を評価する評価関数

ゲーム序盤はA、ゲーム終盤はBにウェイトを置いて評価を行います。
しかしこれも改善余地が大きいでしょう。

実は、この評価関数の精度を各段に向上させる簡単な方法があります。
これについては次の MonteCarloAIPlayer で紹介します。

実装について

BreadthFirstAIPlayer は幅優先探索アルゴリズムを実装したものですが、次の工夫を加えています。

・残り時間に応じた先読み

何手先まで先読みするのかを予め決めておくのではなく、残り時間に応じて先読みする手数を調整します。

・前回の先読み結果の再利用

n手目の自分の番で先読みした結果を、次の自分の番であるn+2手目でも再利用します。これにより、毎回毎回ゼロから思考することを回避し、より先の手まで読めるようにしています。

・評価関数の指定が可能

評価関数部分にストラテジーパターンを採用し、評価関数を実行時に指定できるようにしています。
具体的には、BreadthFirstAIPlayer クラスのオブジェクトをインスタンス化する際に、評価関数を実装したクラスのクラス名をオプションパラメータとして渡すことができます。

BreadthFirstAIPlayer の解説は以上となります。
いかがでしたか? これまでの単純なAIプレーヤーよりもぐっと “AIらしさ” が増したのではないでしょうか。

幅優先探索の考え方は、リバーシに限らずチェスや将棋や囲碁においても、より強いAIプレーヤーを作成する際の基礎となるものです。ぜひ考え方をマスターし、ご自身で応用を考えてみてください。

もしこのページの解説で分かりにくい部分がありましたら、こちらまでご質問いただければと思います。

スポンサーリンク
reversi_main 336*280
reversi_main 336*280

フォローする