アルゴリズムモンテカルロ木探索コンピュータ囲碁コンピュータ将棋機械学習

はじめに

モンテカルロ木探索と先読みを利用した、方策ベースの学習アルゴリズムに関するアイデアです。

アルゴリズム

モンテカルロ木探索で、方策を取得したい場合の「学習の一サイクル」は、以下のようになります。

乱数、既存の方策などを利用して、多数の状態を作成
作成した各々の状態から、モンテカルロ木探索を実行
モンテカルロ木探索で得られた結果(取り得る行動に対する分布)で、方策を学習

この際、モンテカルロ木探索は、探索木の子節点(スタートの状態から、ある行動を選んだ次の状態)から開始されますが、この開始時の子節点を「未来に進めてしまう」というアイデアです。
具体的には、全ての子節点に対し、既存の方策を使用して(場合によっては乱数も使用して)先の状態に進めます。
それによって得られた「先の状態」の節点を、モンテカルロ木探索を開始するときの子節点とみなして探索を実行するというものです。
どれくらい先の状態に進めるかを意味する「深さ」は、学習のサイクルごとに大きくしていく方式が考えられます。
例えば、方策が得られていない最初のサイクルは深さ0で実施し、次のサイクルでは前サイクルの方策を使用して深さ1で実施、その次は一つ前のサイクルの方策を使用して深さ2(または深さ3)で実施、といったように次第に深くしていきます。
このアイデア自体は、コンピュータ将棋の「雑巾絞り」から思い浮かびましたが、方向性としては、強化学習におけるTDLeaf(λ)と同様のように思われます。

メリットとデメリット

未来に進めてから探索することにより、効率よく将来の状況を見通して学習できる(可能性がある)というメリットが考えられます。
その一方、既存の方策に基づく先読みであり、特定の状態に決め打ちしてからの探索となってしまうため、学習が片寄るデメリットも考えられます。