将棋におけるMCTS（モンテカルロ木探索）の強さ

今回は技術寄りの話。

注：この記事はコンピュータ将棋非開発者によって書かれたものであり、技術的な情報に関して誤りが含まれている可能性があります。指摘等、コメントでお待ちしております。

芝浦工業大学の学生、教員らによって開発されている「芝浦将棋」というソフトがある。普通、（ディープラーニングを使わない将棋ソフトでは、）min-max探索というゲーム木探索を行う。将棋の盤面を何手分か先まで全ての組み合わせを調べ*1、最も評価値の高い局面へ至る手を最善手とする探索である。

ところが、芝浦将棋はモンテカルロ木探索という、確率情報に基づくゲーム木の探索を行う*2、世界コンピュータ将棋選手権出場プログラムとしては極めてユニーク*3なソフトである*4。

コンピュータ将棋のmin-max探索と囲碁のモンテカルロ木探索（読み飛ばしてもよい）

モンテカルロ木探索は囲碁ソフトでポピュラーな（というか唯一の）ゲーム木探索手法であり、囲碁ソフトはモンテカルロ木探索を行うことによりアマ有段の強さに、そして更にディープラーニングによる局面および手の評価を組み合わせることで、人類を遥かに凌駕する強さに至った。

囲碁は局面の分岐が膨大であり、min-max探索で深く探索することが不可能であるという問題、地という概念に対してまともな評価関数を設計することが極めて難しい*5という問題、そして正解となる着手が沢山あり、更にデタラメに石を置いても終局に至るというゲームの性質から、勝率の高そうな手からゲームの分岐を限定して読み、末端でランダムに石を置いて勝率を測定して*6手の情報を更新することを繰り返すというモンテカルロ木探索の相性が良かった。

逆に、将棋ではモンテカルロ木探索はあまり有効な手法であるとは思われてこなかった*7。

これは、将棋というゲームは局面の有力な分岐が少なく、全ての手を調べることが容易であること、また、そこそこの精度を持つ高速な評価関数が簡単に設計できる*8ことから、将棋とmin-max探索の相性が余りにも抜群であったことによる。

線形評価関数モンテカルロ木探索将棋ソフト

残念ながら、芝浦将棋、毎年一次予選敗退でめちゃくちゃ弱いのである……（ごめんなさい）

と言ってもアマチュアの有段クラスではあるのだが、おそらく大昔のBonanza6に勝ちこせるかも怪しい。

そんなわけで、MCTSは将棋ではかなり弱いものだと思い込んでいたのだが、「PAL」の開発者の山口祐氏がモンテカルロ木探索を「やねうら王」上に学習部から実装し、強さを測定するという実験をされた。（第29回世界コンピュータ将棋選手権決勝進出者の詳細アピール文書を参照。）

なんと、三駒関係による方策関数を評価関数と別に導入すると、前年度のPALに対してレートたったのマイナス250で済むというのである。

これは私にとって驚愕の実験結果だった。まず、やねうら王の探索部はStockfish*9を元に様々な枝刈り手法が導入され、それらのパラメータも限界近くまでチューニングされていて、どのパラメータをどういじってもレートが下がるような状態である。

そんな探索部に対して、線形関係という荒い方策関数を導入して、細かいチューニングはまだ施していない段階のモンテカルロ木探索が、たったのマイナス250である。

これまでディープラーニングの将棋ソフトがモンテカルロ木探索で従来のmin-max探索の将棋プログラムに勝利していたことを、私はディープラーニングの評価関数のパワーによるゴリ押しだと思っていた。

だが、正しく実装されたモンテカルロ木探索は恐ろしく有望だったのだ。

min-max探索は並列化が大変難しく*10、min-max探索よりはスケールのしやすいMCTSなら、ひょっとするとパラメータや学習のチューニングがもっと進めば、ディープラーニングを使わずともmin-max探索を凌駕するポテンシャルすらあった*11ということになる。

来年以降の世界コンピュータ将棋選手権

dlshogiのソースコード、およびネットワークが公開され、更にレートが300ほど上がる改良の余地が発見されたとのことなので、おそらく決勝に勝ち進むためには全チームがディープラーニングを取り入れるのが必須であるような、ディープラーニング全盛の時代が到来すると思われる*12。

Bonanzaによる機械学習がコンピュータ将棋界を席巻したとき、YSSの山下氏は手打ちした評価を機械学習のそれに置き換えるときに、YSSが自分のプログラムではなくなるような寂しさを覚えたという。

そのような大きな時代の転換が、ディープラーニング、そしてMCTSの盛隆により再び到来しつつあるのかもしれない。

*1:実際にはmin-max探索に等価になる枝刈りをしたαβ探索に、更に各種の枝刈り技法を組み合わせるため、実際に調べる局面はいくぶん少ない。

*2:正確には芝浦将棋の手法はMC Softmaxという、プレイアウト自体にランダム性を持たせるという独自のモンテカルロ木探索の亜種である。

*3:ディープラーニング勢を除く。ディープラーニングは評価関数が低速すぎるという都合上、min-max探索で性能を出すことが不可能で、MCTSが必須である。

*4:floodgateにはかつてやねうらお氏により開発されたひよこカルロというソフトがいた。おそらくMCTSをやっていた？

*5:というか誰にも不可能だった。

*6:MCTSとディープラーニングと組み合わせて用いる囲碁ソフトであるAlphaGoの、中期バージョン以降では、この部分でランダムロールアウトをせずに、ニューラルネットで勝率を予測する。

*7:AlphaZeroが将棋で当時最強格ソフトであったelmoをボコボコにしたため、現在ではディープラーニングと組み合わせれば強い、そうでなければゴミ、という認識になっていると思われる。

*8:Bonanzaの三駒関係という手法が長らくスタンダードだった。

*9:オープンソースの超強豪チェスソフト。現在の最強格将棋ソフトはほぼStockfish由来の探索部を持つか、AlphaZeroのディープラーニング方式のどちらかである。

*10:主要ソフトはStockfishに習いLazy SMPという並列化技術により並列探索をしているが、これは10コアや20コアの時代のものであり、現在のように64コア、128コアと言った多コアのCPUを想定したアルゴリズムではなく、スケールが飽和しつつあると言う向きがある。

*11:並列化のアドバンテージ込みで。

*12:思っていたのより１～２年早かった。