オセロAIの教科書 10 【探索】 枝刈り
こんにちは、にゃにゃんです。
この記事集「オセロAIの教科書」は私の世界1位AIの技術を中心に、オセロAI(オセロの相手をしてくれるプログラム)を初歩から段階を踏んで作っていく記事集です。全編無料でこちらから読めます。
この記事について、わかりにくい点や疑問点、おかしな点がありましたら気楽にコメントとかTwitterとかで教えて下さい。みなさんの力で記事を洗練したいです。
この記事を読むのに必要な知識
この記事を読むのに必要な(ある程度前提とする)知識を列挙します。これらの知識がない状態で読んでもある程度理解できるとは思いますが、途中でわからなくなったらキーワードとして使ってください。
オセロのルール
基礎的なプログラミングの知識・経験
C++
基礎的な統計の知識(標準偏差)
最適化アルゴリズム(焼きなまし)(知らなくても読めます)
これまでの枝刈り
これまではalphabeta法の解説で枝刈りという言葉が出てきました。alphabeta法での枝刈りは、もう少し詳しく言うと後ろ向きの枝刈りと言って、minimax値が正しく求まる保証のある枝刈りです。つまり、純粋に無駄な探索をカットしています。
人間の枝刈り
人間は計算性能がとても悪いですが、時にはかなりの手数を先読みして着手すると思います。これは後ろ向きの枝刈りだけでは実現できません。
人間が何をしてそんなに深くまで読むことを実現しているのかを考えると、あまりにも良い/悪い手は読むのをやめて、接戦の手を読むことをしていると思います。
コンピュータでもこれを実装してしまいましょう。
multi prob cut
以上を実現する方法の一つに、multi prob cut (MPCと略されます)があります。MPCでは、探索の最中に訪れたノードXに対して深さDの探索をするとき、Dよりも浅い深さdの探索を予めやってしまいます。そして、深さdの探索から深さDの探索結果を推測します。その値がノードXの探索窓から著しく外れていた場合はその時点でそれ以上の探索をやめます。この浅い探索にはNWS(null window search)を使います。
この方法は一定の確率でminimax値が正確には求まらないことがあります。このような枝刈りを前向きな枝刈りと言います。
深さの対応
深い探索の深さDと浅い探索の深さdは必ず一対一対応していて、この例はMPCが発表された論文に記載されています。世界1位AIのこの対応は論文の数値を参考にしました。
論文:
私が使っている深さの対応:
探索結果の推測
MPCでは深さDの深い探索と深さdの浅い探索の結果がある程度似ているという前提で話が進みます。つまり、評価関数の精度が悪いと役に立ちません。
さて、深さDの探索結果を深さdの探索から予測して、その予測結果と探索窓を比べるのですが、この予測はどうすれば良いでしょうか。
上の論文で提案されている手法は、深さDの探索結果をV、深さdの探索結果をvとして、定数aとbを使って
Vの推測値 = av + b
という式で近似してしまう手法です。
実際にこのaとbを求めるのには、私はデータを集めて焼きなまし法で調整してみましたが、ほとんどa=1、b=0でした。
そのため、私はそのまま
Vの推測値=v
という推測を使いました。この記事でもこの単純な近似を使います。性能が上がらない場合は焼きなまし法などで調整してみてください。
標準偏差の利用
実際にMPCを実行することを考えましょう。たとえば探索窓が[-1,10]の場合にminimax値が10を超えそうかを判定したいとします。このとき、評価値が10より少し大きいところでNWSを打ってしまって本当に良いでしょうか？深さdの探索では評価値が例えば11であっても、深さDの深い探索では9になるかもしれません。これは危険そうです。
そこで登場するのが標準偏差です。
前もって適当なデータセットで深さDとdの探索を行っておいて、その誤差を標準偏差として調べます。そして、正の定数tを使って、以下の式で表されるboundの周りでNWSを実行します。
上限を超えそうかの判定:
bound=(探索窓の上限) + t * (標準偏差)
下限を割りそうかの判定:
bound=(探索窓の下限) - t * (標準偏差)
こうすると、上限より少し上、または下限より少し下でNWSを実行することになります。それでも深さdの浅い探索でその値よりも大きい/小さい値が出てきたら、ついにこれは読む必要がありません。枝刈りを実行してしまいましょう。
V=av+bで近似した場合には上の式が変わります。
定数tの意味について少し解説すると、細かいことは(私がそんなに理解していないので)置いておいて、標準正規分布の-∞からtまでで積分した値を全体の面積で割った値を確証(確率)として前向きな枝刈りを実行できるという意味らしいです。世界1位AIはt=1.5付近(確証は93%程度)を使いました。
実装
申し訳ありませんが、さすがにサンプルコードとして実装するのはだるくなってきました。私の世界1位AIの改良版AIの該当部分のコードを貼るので(読みにくいと思いますが)気になる方はご覧ください。
↑中盤探索部分です。mpc_higher関数とmpc_lower関数がMPC実行部分です
↑MPCの標準偏差計算に使ったスクリプトで、標準偏差を今何手目かという情報やDの値によって細かく分けて計算しました。なお、コメントアウトしてある部分でV=av+bに近似しようとしてaとbを焼きなました痕跡があります。
なお、終盤探索でMPCをする場合は私の経験上別途計算した方が良いです。具体的には終盤の最善進行の棋譜を数千局用意して、その結果(最終石差)と浅い探索の結果とで標準偏差を計算すると良いと思います。しかし、終盤探索は一般的に高速にできるかつミスが許されないので、私が現在制作中のAIでは導入するか迷っています。
まとめ
MPCは実はオセロにおいてかなり強力で、私の場合、同じ時間なら正確性を損なわずにMPCなしと比べて3手くらい深くまで読むことが可能でした。
次回予告
次回は探索の定数倍高速化を紹介します。
たかが定数倍と侮ってはいけません。特に葉に近いノードの高速化は全体としてとても強力になります。
スキと投げ銭で喜びます
noteではログインなしでスキできます！役に立ったぞ、面白かったぞ、という方はぜひハートマークをポチッと押してください！
この記事は全編無料ですが、投げ銭してくれたら私が喜びます。喜ぶだけです。何も見返りはありません。「役に立ったし投げ銭してやっても良いぞ」という方はポチっとしてくださると嬉しいです。
ここから先は
¥ 100
この記事が気に入ったらサポートをしてみませんか？