オセロAIの教科書 12 【探索】 使わなかった方法

こんにちは、にゃにゃんです。

この記事集「オセロAIの教科書」は私の世界1位AIの技術を中心に、オセロAI(オセロの相手をしてくれるプログラム)を初歩から段階を踏んで作っていく記事集です。全編無料でこちらから読めます。

オセロAIの教科書｜にゃにゃん(山名琢翔)｜note

この記事について、わかりにくい点や疑問点、おかしな点がありましたら気楽にコメントとかTwitterとかで教えて下さい。みなさんの力で記事を洗練したいです。

今回は最終回として、私がボツにしたアイデアをご紹介します。ボツにしたものの、使えるアイデアがあるかもしれないと思います。

この記事を読むのに必要な知識

この記事を読むのに必要な(ある程度前提とする)知識を列挙します。これらの知識がない状態で読んでもある程度理解できるとは思いますが、途中でわからなくなったらキーワードとして使ってください。

• オセロのルール

• 基礎的なプログラミングの知識・経験

ビットボード

第2回のボードの実装解説でビットボードを軽く扱いましたが、この記事ではインデックス化を使うと言ってボツにしました。

ビットボードはとても良い手法です。SIMDとの相性も良く、手動でかなり高速化できます。実際、初期に私も使っていました。しかし、個人的にインデックス化の方が良いと思ったことがあります。

インデックス化の方が様々なパラメータの計算がしやすいのです。この記事では、マスの重さや着手可能数、さらには囲み具合まで全てインデックスに紐付けた前計算を行いました。インデックス化をすれば、適当な前計算によって、様々な盤面に関連するパラメータを高速に計算できます。これがとても魅力的でした。

MTD法

MTD法は、この記事で紹介した探索アルゴリズムの系統に含まれるアルゴリズムです。

入力された局面から1手進めた局面を生成して、その局面についてNWSを繰り返し使ってminimax値を求める手法です。NWSを打ってみるとminimax値がその上にあるのか下にあるのかがわかるので、繰り返せばminimax値を求められます。考え方としては二分探索に若干似ています。NWSにきちんと置換表を組み込めば高速です。

MTD法にも様々な種類があり、一番有名なのはminimax値の推定値を何らかの方法で計算して、その値から計算を開始するMTD-fです。他にもMTD-biやMTD-stepなどがあります。

一般的に、MTD-fはnegascoutよりも高速なアルゴリズムと言われています。

しかし、私がMTD法を色々実装してみたところ、正直negascout法と比べてどれも性能は上がりませんでした。

最終的に、MTD-fとMTD-biを融合したアルゴリズムにnegascout法を組み合わせる手法で少しだけ性能が上がることを確認しました。

実現確率探索

これは将棋AIについて調べていて知った手法です。

本記事で紹介した探索は、必ず予め読む手数を決めてから探索していました。しかし、実現確率探索では、読む手の深さを予め決めることをしません。代わりに、「この手筋が選ばれる確率が一定値を切ったら探索を打ち切る」という探索の終わらせ方をします。

具体的には、まずある局面Xが確立pで実際に現れるという情報(実現確率)を再帰関数の引数で受け取ります。そして局面Xから分岐する子の局面全てについて、それぞれの局面が選ばれる確率q(全部足すと1.0になる)を何らかの方法で計算します。そして、再帰関数で子の局面の探索をするときに、確率pと確率qをかけ合わせたものを引数に取らせます。

そして、再帰でどんどん深くまで探索していって、実現確率が一定値を下回ったら探索を打ち切り、そのノードでの評価値を伝播していきます。

なお、確率の値はものすごく小さくなるので、実装上は確率の対数を取ったものを使います。つまり、p * qをどんどん計算していくのではなくて、log(p) + log(q)を使います。

この問題の弱点の1つは、子の局面が選ばれる確率を計算することにあります。私はとりあえずその局面を評価関数にかけて良し悪しを考えましたが、あまりうまくいきませんでした。評価値と局面が選択される確率は別物のようです。

さらに、オセロ特有の問題として、オセロがダイナミックなゲームであることが挙げられます。オセロの評価関数は、私の経験上、黒が打った直後の評価値は実際のものより黒有利に、白が打った直後は白有利に出やすい傾向があると思います。手数を予め決めて探索すると、パスがない限りは葉ノードの手番は同じになるので無視できる問題なのですが、実現確率探索ではこれが問題になります。もちろん、これくらいであれば小手先の調整で評価関数を呼ぶ手番を揃えれば済みますが…

将棋AIでは、(私が持っている知識は情報源の問題で2012年頃の古いものですが)この探索が使われることがあるそうです。

move ordering最上位探索伸長

こちらも将棋AIについて調べていて知ったことです。

negascout法では、move orderingで最上位になった手を通常探索しましたが、最上位の手は探索深さも増やしてしまおうという手法です。

意図としては、単純に「良さそうな手は深く読もう」というだけです。move orderingが妥当であれば強くなることが予想されます。

この手法は上の実現確率探索と同様に評価関数を呼ぶ際の手番を統一すればある程度使えるかもしれませんが、私は採用しませんでした。不採用理由は面倒だったからです(実際、採用しなくても世界1位になれてしまったのでそこまで重要性を感じませんでした)。

実装する際には、move orderingで最上位の手を探索するときに、再帰で深さを減らさなければ良いだけです。

ただ、深さを減らさないと無限に探索が続いてしまう(正確には終局まで続いてしまう)気がするので、深さを整数値ではなくて実数値で持つようにして、通常探索では深さを1減らして、move ordering最上位は深さを0.5減らす、などとして、深さが0以下になったら探索終了、とするのが良さそうです。

モンテカルロ木探索

第4回の記事で名前だけ紹介しましたが、この記事で紹介したminimax法を起点とする探索アルゴリズムの系統の他に、原始モンテカルロ法というアルゴリズムを起点とするアルゴリズムの系統があります。

原始モンテカルロ法は弱いので、通常はそれを改善したモンテカルロ木探索(MCTS: Monte Carlo Tree Search)が使われるのですが、これをオセロAIに使ってみたことがあります。結論から言えばイマイチでした。一応頑張って世界17位までは行きましたが、それより上は無理でした。

原始モンテカルロ法やMCTSの最大の特徴は評価関数がいらないことです。これらのアルゴリズムでは、ランダムに手を打っていって、平均的に良さそうな手を見つけてそれを選びます(*1)。だから第4回のminimax法の説明で平均を使う手法として紹介したのです。平均的に見てしまっているので、「1手だけが良手で他は全て悪手」といった場合に弱いです。

評価関数が作りにくいゲームとして有名なのが囲碁です。ですので、囲碁においてMCTSはとても強いです。と言うか、そもそも原始モンテカルロ法系統のアルゴリズムは囲碁のために開発されたらしいです。

私が採用したのは、PV-MCTSという種類のMCTSです。囲碁で初めて人間の世界チャンピオンを倒したAlphaGoの発展的アルゴリズム、AlphaZeroに使われているアルゴリズムです。

AlphaZeroでは、機械学習したモデルをMCTSと組み合わせることで、MCTSをさらに改善しました。しかし、やはりオセロにおいては評価関数を作って探索するのが一番強いようです。

(*1)正確には平均ではなかったりするのですが、ここで話すとややこしいので気になる方は調べてみてください。

まとめ

今回は私がボツにしたアイデアを紹介しました。ボツとは言っても、オセロAIには適さなかったり、単にだるかったりという理由ですので、一般的にゲームAIを作る上でとても価値のあるアイデアだと思います。頭の片隅にでも留めておいてください。

次回予告

ありません！今回が最終回です！長々とありがとうございました！！！

良いオセロAIライフを！

スキと投げ銭で喜びます

noteではログインなしでスキできます！役に立ったぞ、面白かったぞ、という方はぜひハートマークをポチッと押してください！

この記事は全編無料ですが、投げ銭してくれたら私が喜びます。喜ぶだけです。何も見返りはありません。「役に立ったし投げ銭してやっても良いぞ」という方はポチっとしてくださると嬉しいです。