オセロAIの教科書 6 【探索】 negascout法
こんにちは、にゃにゃんです。
この記事集「オセロAIの教科書」は私の世界1位AIの技術を中心に、オセロAI(オセロの相手をしてくれるプログラム)を初歩から段階を踏んで作っていく記事集です。全編無料でこちらから読めます。
この記事について、わかりにくい点や疑問点、おかしな点がありましたら気楽にコメントとかTwitterとかで教えて下さい。みなさんの力で記事を洗練したいです。
今回で3回続いた探索編も最終回です。
この記事を読むのに必要な知識
この記事を読むのに必要な(ある程度前提とする)知識を列挙します。これらの知識がない状態で読んでもある程度理解できるとは思いますが、途中でわからなくなったらキーワードとして使ってください。
オセロのルール
基礎的なプログラミングの知識・経験
C++
データ構造(ハッシュテーブル)
alphabeta法を改善するアイデア
今回はalphabeta法をさらに改善します。
alphabeta法は良さそうな手の順に探索することで効率的に枝刈りが起きていました。
これを、以下のようには考えられないでしょうか。良さそうな手の順に並べ替えるのであれば、最初の手だけ普通に探索して、2番手以降の手は最初の手より悪いことだけ確認して探索終了とできないだろうか、と。
実は、minimax値がある値よりも大きいか小さいかだけを知りたいのであれば、高速な処理が可能です。これについて詳しく書きましょう。
null window search
null window search(NWSという省略をします)を使うと、所望が達成できます。
NWSでは、alphabeta法におけるalphaとbetaの幅(これを探索窓と言います)を極限まで小さく(*1)した探索を行います。
探索窓が極限まで小さいので、探索をするとすぐに探索窓を外れた値が評価値として出てきます。minimax値が探索窓の上限よりも大きいことをfail high、下限よりも小さいことをfail lowと言います。
私が個人的に持っているイメージですが、敵がどこにいるかわからない状態で自分が敵にビームを当てて倒さなくてはいけないゲームに例えるとわかりやすいと思います。
適当にビームを打ってみて、外れたら敵がそれより右にいるか左にいるのかだけわかるとします。敵が右にいるのであればもう左にビームを打つ(探索する)必要はありません。ちょっと厳密には探索と違いますね…
(*1)実装上の都合で探索窓を1にします。実装可能な最小の値という意味です。ちなみに第3回目の記事で、評価値は整数にしましょうと書いた理由の一つがこれで、実数だとこの探索窓を何に設定すれば良いのかよくわからなくなってしまいます。
negascout法
実際に最初に出したアイデアを実現可能なアルゴリズムに落とし込みましょう。
まずは一番良さそうな手を探索し終えて子ノードから伝播してきた評価値Vを得たとします。そうしたら、残りの子ノードの探索を探索窓をVの周りの微小範囲に限定してNWSを行います。子ノードの評価値はV未満=良くない手だった場合はそのままその手をこれ以上探索する必要はありません。子ノードの評価値がV以上だった=良い手だった(*2)場合には、通常の探索窓で再度その手を探索し、厳密な評価値を得ます。
こうすることで、move orderingがある程度妥当であればminimax値を高速に得ることができます。逆に、move orderingがあまりにも狂っていると、NWSをしてから通常探索を行うという二重の探索が大量に起きるので効率は落ちます。
置換表
negascout法ではNWSと通常探索の2種類の探索を行いますが、NWSをした際に置換表にヒントとなる値を格納しておくことで、通常探索が少し高速になります。
前回、alphabeta法ではminimax値が求まったときだけ置換表に値を格納していましたが、NWSでは厳密なminimax値が求まることはまずないので、もう少し工夫します。
置換表を上限値の置換表と下限値の置換表の2種類用意します。上限値の置換表にはそのノードのminimax値が存在する上限値を、下限値の置換表には下限値を格納します。
NWSの途中で枝刈りが起きた際にも上限と下限の片方がわかるので、それぞれわかった方の置換表に値を格納しておきます。こうすることで、次に通常窓で探索するときに予め置換表を使って探索窓を狭めることができるので若干高速になります。
(*2) 直感的にはV「より大きい」場合に再探索するようだと思いますが、実装上の都合で、V「以上」の場合に再探索します。
実装
サンプルコードを見てみましょう。
記事に貼るにはコードが長くなってきたので記事に貼るのは割愛します。
実行してみる
実行は以下のコマンドで行います
$ g++ -O3 ai5_negascout.cpp -o ai.out
$ python3 main.pyコンソール表示は高速化したnegaalpha法と同じです。
試しに同じ盤面で訪問ノード数を比べてみましょう。
高速化したnegaalpha法
searched depth 5 policy 3 visited nodes 4585
searched depth 6 policy 24 visited nodes 12395
searched depth 7 policy 24 visited nodes 53397
searched depth 8 policy 24 visited nodes 145014negascout法
searched depth 5 policy 3 visited nodes 4542
searched depth 6 policy 24 visited nodes 11477
searched depth 7 policy 24 visited nodes 55861
searched depth 8 policy 24 visited nodes 139887若干ノード数が減っていますかね…？
実は現在使っているマスの重みによる評価はそんなに性能が良くないので、move orderingの性能もそんなに良くないことが予想されます。
次回、評価関数を大幅にアップデートしますが、試しにアップデートした評価関数を使って実験してみました。
高速化したnegaalpha法
searched depth 5 policy 24 visited nodes 4998
searched depth 6 policy 24 visited nodes 15170
searched depth 7 policy 24 visited nodes 74337
searched depth 8 policy 24 visited nodes 212772negascout法
searched depth 5 policy 24 visited nodes 4010
searched depth 6 policy 24 visited nodes 12266
searched depth 7 policy 24 visited nodes 64369
searched depth 8 policy 24 visited nodes 169517今度はそこそこの差でnegascout法の訪問ノード数が少なくなりました。
本当はこれだけの実験で結論してはいけませんが、一般的にnegascout法はmove ordering性能によってスピードが大きく変動します。
まとめ
今回は基本的な探索アルゴリズムの最終回として、negascout法を紹介しました。
一応negascout法よりも性能が良いとされるMTD法などの方法もありますが、私の経験上そんなに変わりませんでした。とは言え、世界1位のオセロAIではMTD法を独自に改善して調整した手法で若干高速化しています。MTD法は第12回で解説します。
さて、ここまで探索ノード数を減らすことによる高速化を行っていましたが、高速化手法はこれだけではありません。多少訪問ノード数が増えたところで1ノードあたりにかける時間を減らせれば高速化ができます。
さらなる高速化は記事集の後半で発展的な内容として扱いますが、ぜひ読む前に一度考えてみてください。
また、サンプルコードはわかりやすさ重視でチマチマした高速化をある程度怠っています。このあたりも記事集の後半で書きます。
次回予告
ここまでしばらく探索アルゴリズムを学びましたが、次は評価関数を工夫します。
現在のマスの評価を行う評価関数でも結構強いものが作れますが、それよりも強い、世界1位AIでも使っている発展的な評価関数をご紹介します。
評価関数に話が移り変わるので、探索アルゴリズムがよくわからなかった方も新たな気持ちでお読みください。
スキと投げ銭で喜びます
noteではログインなしでスキできます！役に立ったぞ、面白かったぞ、という方はぜひハートマークをポチッと押してください！
この記事は全編無料ですが、投げ銭してくれたら私が喜びます。喜ぶだけです。何も見返りはありません。「役に立ったし投げ銭してやっても良いぞ」という方はポチっとしてくださると嬉しいです。
ここから先は
¥ 100
この記事が気に入ったらサポートをしてみませんか？