まだ方策ネットワークもバリューネットワークも精度が低いが、精度を上げるのは一旦保留して、対局時の方法について検討する。
以前に考察したように、将棋は読みが重要なゲームであるため、探索を用いず方策ネットワークのみで指しても強くならないと思われる。
AlphaGoでは、モンテカルロ木探索をベースにして、方策ネットワークとバリューネットワークをうまく組み合わせている。
UCTアルゴリズム
代表的なモンテカルロ木探索のアルゴリズムであるUCTアルゴリズムでは、以下のように探索を行う。
毎回ルートノードからUCBが大きいノード（後手では小さいノード）を選択しながらツリーを下っていく。
末端ノードに到達したら、そこからrollout policyに従い終局までプレイする（これをプレイアウトと言う）。
プレイアウトの結果を、末端ノードからツリーを逆に上りながら、ノードの報酬として記録する（これをバックアップと言う）。
末端ノードは一定回数を訪問したら、合法手でノードを展開する。
最終的にルートの子ノードで最も訪問した手を選択する。
UCBは、以下の式で計算される。
は期待報酬、
は親が同じノードの訪問数の合計、
はノードの訪問数
この式は、(期待値)+(バイアス項)という構成になっており、期待報酬が高いところを選択するが、訪問数が少ないノードを優遇するという意味を持つ。
PUCTアルゴリズム
AlphaGoでは、UCTアルゴリズムの代わりに方策ネットワークとバリューネットワークを使ったPUCTアルゴリズム*1を採用している。
PUCTアルゴリズムでのノード選択の基準は、以下の式で計算される。
はバリューネットワークの出力とプレイアウトの結果の平均で、期待報酬を表す。
は、以下の式で表される。
は定数、
は方策ネットワークの出力を事前確率として使用する。
はノードaの訪問数を表す。
は親が同じノードの訪問数になる。
PUCTの値の役割は、UCBと同じだが、期待報酬にバリューネットワークの出力を使い、バイアス項に方策ネットワークの出力を使うことで、候補手選択の精度を高めている。
将棋への応用
将棋では囲碁のようにプレイアウトで終局までプレイしてもあまり精度が上がらないことが知られている。
将棋のように狭い読みが必要なゲームでは、プレイアウトで求めた期待報酬が実際の報酬と乖離することが多いためと考えられる。
そのため、PUCTアルゴリズムを将棋に適用する場合は、プレイアウトを使わずに、バリューネットワークの出力のみを期待報酬として用いた方が有効と考えられる。
ノードは1回訪問したら展開し、選択したノードのバリューネットワークの出力を上位のノードにバックアップする。
AlphaGoでは、方策ネットワークとバリューネットワークの計算中に、並列でプレイアウトを行うことで、効率を上げている。
プレイアウトを行わない場合は、各ノードで方策ネットワークとバリューネットワークの計算を待つ必要がある。
モンテカルロ木探索は、ルートノードから並列化を行うことで効果がある知られているため、GPUの処理限界まで並列化を行い効率を上げることが有効と思われる。
並列化を行っても、従来の評価関数ベースの探索に比べたら探索ノードはかなり少なくなると思われる。
そのため、方策ネットワークとバリューネットワークのモデルの精度が高くないと強いプログラムはできない。
モデルの精度向上は別課題として、次回からPUCTアルゴリズムの実装を試したい。
