競プロでも探索を行う問題が出題されることがあります。BFS(幅優先探索)とかDFS(深さ優先探索)とかで簡単に解けちゃう問題から、評価関数をうまく定義して、chokudaiサーチ(Beam Searchの亜種)みたいなので解決しないといけない問題まであります。

いまから書くのは将棋AI限定の話ではなく、似たゲーム性のゲームなら大抵通用する考え方です。たぶんコードを書いてゲームAIを作る系のコンペでも通用するんじゃないかな。

その秘伝(←チェスプログラミングのWikiに載ってますが)について20分ぐらいでざっと書いていきます。

私の作った将棋ソフトはたぶん10000NPSくらいしか出ないんだけど、まぁそれはいいとして、
短時間で結果返せるのαβで探索して3手先、4手先までくらいなんだよね。
やねうら王さんとか探索局面10000くらいで8手先くらいまで読んでるみたいなのでどうなっているのか

— 凪なぎさ (@nagi_nagisachan) November 10, 2020

なぎなぎが言う通り、評価関数の質を上げるとαβ探索でもそれなりに深く読めるだろうし、評価関数の質が高ければ枝刈りをきつくしても、間違った枝刈りになる確率は低くて、大丈夫というのはその通りなのだけど、まあ、そのへんは理解しているとして、いまから一つだけとても大切なテクニックを伝授します。

それは、move ordering(指し手オーダリング)です。その局面の指し手をすべて生成したあと、それの指し手を良い順に並び替えるってことです。

評価関数の精度をいくら上げても、愚直に生成された順で指し手を調べていくとしたら、なかなか当たり(枝刈りができるような良い指し手)を引いてきません。神様の評価関数があったとしても1手は局面を進めないといけないわけですよね？ましてもっと精度の悪い評価関数だとしたら、1手どころか5手とか10手ぐらい進めても優劣が正確に判定できないかもしれません。なので、どの指し手から試すかという部分で、我々はランダムガチャをやるわけにはいかないのです。

そこで、当たりそうな指し手から順番に調べていきたいわけです。αβ探索は早めに当たりの指し手を引ければ、探索効率は全く違ってきますからね！

これは1手も局面を進めずに指し手にスコアをつけるわけで、すなわち、評価関数を呼び出さずに、“当たり”の指し手を引き当てたい、引き当てられるようなスコアリングをしたいということです。

さて、どういう指し手が当たりなのでしょうか？

激指は、統計情報を事前に調べてあって、例えば79の升に銀を打つ手の実現確率はいくらいくらのように、各升に駒を移動させる指し手の実現確率を持っていました。(詳しくは知らないので間違っていたらゴメン)

こう考えると実現確率の高そうな(＝当たりの指し手)を探す問題とは、機械学習でよくある多クラス分類だとみなせます。

「ほな、教科書見てなー。ばははーい！」で記事を終わっても良いのですが、やねうら王を始めとする現代の探索部では、そのような事前に調べた統計情報を持っていません。探索時にそういった統計をとって、それに基づき、move orderingするわけです。

どんな統計を取れば良いでしょうか？

その指し手が良い指し手であったときに、その指し手に似た指し手が次に出てきたときに加点されてほしいです。

ここには、２つの問題が潜んでいます。

まず、「良い指し手であったとき」の「良い指し手」とは誰がどうやって判断するのかということです。

しかし、これは、実は簡単な問題でαβ探索でその局面の最善手を発見した(βを上回る指し手が見つかった)時に、それを良い指し手であったとみなすのです。また、αβ探索は、depth(残り探索深さ)の回数だけ再帰的にsearch関数を呼び出すのが普通ですが、このdepthが大きいときに見つけた最善手ほど、それを価値の高い指し手とみなすわけです。

やねうら王でも、この時に統計情報を更新しています。

さて、２つ目の問題として、どんな統計情報を保存しておき、何と何を似た指し手(同一のカテゴリーに属する指し手)とみなせば良いかということです。

これは、上の激指の例で書いたように、例えば「移動先の升(to)」と「そこへ移動させた駒(Piece)」のペアが考えられます。

「79に銀を移動させる手は(それがどの升からであろうとも)よさげ！」ということはわりとありえそうですね。これをPieceとToの履歴情報なので、PieceToHistoryと呼ばれます。(やねうら王のソースコードのMovePicker.hにあります。)

他には、移動元の升(from)と移動先の升(to)と先後(Color)を組にした、ButterflyHistoryだとか、1手前の相手の指し手と今回のbestの指し手とを組にしたCounterMoveHistory(応手履歴？)なんてのも、やねうら王では使っています。

これらをもとに指し手に点数をつけて、その点数順に並び替えて、よさげな指し手から試していくというわけですね。

また、統計情報の更新は、やねうら王のソースコードのmovepick.hにありますが、以下の更新式を用いています。

うまくできてますね。

将棋って、例えば、探索中に3手先の局面で79銀が良い指し手だとわかったとして、でもその1手前で相手はそれをさせまいと他の指し手をやるわけです。それによって3手先の79銀はよくない指し手になるかも知れないですけど、1手先とか5手先とかではやはり79銀が有効かも知れないじゃないですか？

そのように、ある局面で良さげだとわかった指し手はそのほかの局面(兄弟局面)でも有効であることが多いという、そういうゲームの性質を生かしているのが上のPieceToHistoryだとか、ButterflyHistory、CounterMoveHistoryなわけです。

つまり、この性質があるような似たゲームにおいて、このテクニックは非常に有用で、プログラムを書いて戦うゲーム系のコンペでも、わりと使えるはずです。

move orderingに興味を持ったら、是非、やねうら王のmovepick.hを読んでください。
きっと得るものがあるはずです。

資料

やねうら王V5.31の movepick.h

Move Ordering(Chess Programming Wiki)
https://www.chessprogramming.org/Move_Ordering