オセロAIの教科書 9 【探索】 完全読み、必勝読み
こんにちは、にゃにゃんです。
この記事集「オセロAIの教科書」は私の世界1位AIの技術を中心に、オセロAI(オセロの相手をしてくれるプログラム)を初歩から段階を踏んで作っていく記事集です。全編無料でこちらから読めます。
この記事について、わかりにくい点や疑問点、おかしな点がありましたら気楽にコメントとかTwitterとかで教えて下さい。みなさんの力で記事を洗練したいです。
この記事を読むのに必要な知識
この記事を読むのに必要な(ある程度前提とする)知識を列挙します。これらの知識がない状態で読んでもある程度理解できるとは思いますが、途中でわからなくなったらキーワードとして使ってください。
オセロのルール
基礎的なプログラミングの知識・経験
C++
終盤の探索
終盤も現在は評価関数を使って探索していますが、探索中に終局した時には終局結果を使ったほうが良さそうですよね。ということで、オセロAIでは終盤N手(Nマス空き)は終局するまで探索する、といったことをします。
終盤の探索には2通りあります。必勝読みと完全読みです。
必勝読み
必勝読みでは、最終石差は関係なく、両者最善手を打ち続けた場合に勝てるか引き分けるのか負けるのかを探索します。
この探索をすることで、勝てる手筋が見つかれば必ず勝てるという状態になります。
完全読み
完全読みでは、勝ち負けだけではなく、最終石差も読み切ります。完全読みをすれば、勝てるなら最大石差で勝てますし、負ける場合でも石差を最小限にできます。
必勝読みより探索に時間がかかります。
アルゴリズム
基本的には中盤の探索と同じです。しかし、必勝読みの場合は終局状態が勝ち負け引き分けの3パターンしかないので、negascout法を使う意味はなく、negaalphaで良いと思います。
終盤の探索で重要なのが、move orderingです。
一般的に、終盤は特に速さ優先探索という手法を使います。これはなにも新たなアルゴリズムではなくて、move orderingの一種です。これは、相手の打てる場所が少ない順に並べ替えて探索することを言います。一般的に、終盤は相手の打てるマスの多さと探索ノード数はある程度正の相関があると言われているためです。
速さ優先探索で使う着手可能数は高速に計算できる近似ではパフォーマンスが上がりません。多少遅くても厳密な着手可能数を計算した方が結局速いです。
枝刈り
終盤は確定石(今後絶対に返されない石)が増えていきます。これを使って枝刈りができる場合があります。
自分の確定石がN個、相手の確定石がM個だった場合、自分目線の最終石差は2N-64石以上64-2M石以下になります。探索窓がこの範囲を逸脱していれば即座に枝刈りができてしまいます。
とは言え確定石の計算は簡単ではありません。とりあえず辺のパターンについて確定石の個数を前計算しておいてインデックスと関連付ける手法が簡単です。
さらに、各空きマスから8方向に伸びるラインにある石は返される可能性があると判断して、すべての空きマスについてこのラインを引いて、ラインが一度も当たらなかったマスを確定石とする手法も併せて使えます。
この手法では、計算した確定石の個数が真の確定石の個数以下であれば探索結果が不正確にならない枝刈りとなります。
なお、以下のサンプルコードでは確定石による枝刈りは実装していません。私が2021/12/10現在開発中のオセロAIには搭載しているのでリンクを貼ります。
この中のstability_cut関数が確定石による枝刈りを行う関数です。
実装
繰り返しますが、基本的には中盤の探索と同じです。
私の実装は以下です(完全読みのみの実装です)。
終盤の評価関数(終局したときに石を数える部分):
探索を含めたAI本体:
実行
以下のコマンドで実行してください。
$ g++ -O3 ai8_endgame_search.cpp -o ai.out
$ python3 main.pyデフォルトだと終盤16マス空きから完全読みをするようになっています。
終盤はミスをしなくなったと思います。
まとめ
完全読みをすれば終盤、AIがミスすることはなくなります。
今回は実装しませんでしたが、余力があれば必勝読みもぜひ実装してみてください。基本的には完全読みをする直前のAIの手番で必勝読みを行います。
次回予告
次回は人間が先読みをするときに考えることを模倣して、同じ時間で3手くらさらに深く読めるようにもできる最強の枝刈りを解説します。
スキと投げ銭で喜びます
noteではログインなしでスキできます！役に立ったぞ、面白かったぞ、という方はぜひハートマークをポチッと押してください！
この記事は全編無料ですが、投げ銭してくれたら私が喜びます。喜ぶだけです。何も見返りはありません。「役に立ったし投げ銭してやっても良いぞ」という方はポチっとしてくださると嬉しいです。
ここから先は
¥ 100
この記事が気に入ったらサポートをしてみませんか？