AlphaGo Zero：します $Q(s_t, a)$ 支配する $U(s_t, a)$ 難しいゲーム状態では？

Dec 03 2020

AlphaGo Zero

AlphaGo Zeroは、選択フェーズが管理されるモンテカルロ木探索を使用します $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$、どこ：

悪用パラメータは $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ （つまり、値の平均 $v_i$ エッジを通過するすべてのシミュレーションの $(s_t, a)$）。
探索パラメータは $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ （つまり、事前確率 $P(s_t, a)$、定数で重み付け $c_{puct}$、通過するシミュレーションの数 $(s_t, a)$、および通過するシミュレーションの数 $s_t$）。

事前確率 $P(s_t, a)$ とシミュレーション値 $v_i$ どちらもディープニューラルネットワークによって出力されます $f_{\theta}(s_t)$：

このニューラルネットワークは、位置とその履歴の生のボード表現sを入力として受け取り、移動確率と値（p、v）=fθ（s）の両方を出力します。移動確率のベクトルpは、各移動a（パスを含む）を選択する確率を表します。pa= Pr（a | s）。値vはスカラー評価であり、現在のプレーヤーが位置sから勝つ確率を推定します。

私の混乱

私の混乱はそれです $P(s_t, a)$ そして $v_i$ 異なる分布に正規化された確率であり、結果として $v_i$ 約80倍大きい $P(s_t,a)$ 平均して。

ニューラルネットワークの出力 $(p, v)$、どこ $p$ 与えられた確率ベクトルです $s_t$、そのターンのすべての可能なアクションに対して正規化されます。 $p_a = P(s_t, a)$ アクションを選択する確率です $a$ 与えられた状態 $s_t$。囲碁のゲームは1ターンあたり約250の動きがあるので、平均して各動きには確率があります$\frac{1}{250}$、すなわち $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$

一方、 $v$ 与えられた状態に勝つ確率です $s_t$、考えられるすべてのエンドゲーム条件（勝ち/引き分け/負け）で正規化されます。簡単にするために、仮定しましょう$\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$、ゲームがランダムにプレイされ、各結果が同じように発生する可能性があります。

これは、の期待値が $v_i$ の期待値より少なくとも80倍大きい $P(s_t, a)$。これの結果はそれです$Q(s_t, a)$ 少なくとも80倍大きい $U(s_t, a)$ 平均して。

上記が当てはまる場合、選択段階は $Q(s_t, a)$ したがって、AlphaGo Zeroは、シミュレーションのないエッジ（エッジが $Q(s_t, a) = 0$）すべてが存在しない限り $Q(s_t, a)$ 用語は非常に小さい（$< \frac{1}{250}$）、またはMCTSには非常に多くのシミュレーションがあるため、 $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ の用語 $U(s_t, a)$2つの項の大きさを均等にします。AlphaGo Zeroは使用するだけだと私は信じているので、後者は起こりそうにありません$1,600$ 動きごとのシミュレーションなので、 $\sqrt{\sum_b N(s_t, b)}$ でキャップアウト $40$。

実行可能な動きのみを選択する

理想的には、MCTSは探索するために可能なすべての動きを選択するべきではありません。与えられた状態で実行可能な動きのみを選択する必要があります$s_t$、そしてすべての悪い動きを無視します。しましょう$m_t$ 状態の実行可能な移動の数です $s_t$、そして $P(s_t, a)$ = 0すべての動き $a$それは実行可能ではありません。また、MCTSが実行不可能な動きを決して選択しないと仮定しましょう。

次に、前のセクションが部分的に緩和されます。 $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$。結果として、$Q(s_T, a)$ する必要があります $\frac{m_t}{3}$ の倍の大きさ $U(s_t, a)$平均して。仮定$m_t \le 6$、それならあまり問題はないはずです

ただし、これは、AlphaGo Zeroが理想的に機能するのは、実行可能な移動の数が少ない場合のみであることを意味します。ゲーム状態で$s_t$ 多くの実行可能な動きがある場所（$>30$）（たとえば、多くの可能な選択肢がある困難なターン）、前のセクションで説明したように、MCTSの選択フェーズは悪化します。

質問

私の質問は次のとおりだと思います。

私の理解は正しいですか、それともどこかで間違いを犯しましたか？
しますか $Q(s_t, a)$ 通常支配する $U(s_t, a)$ゲームの状態に多くの実行可能な動きがある場合、実際にはこれだけですか？選択フェーズは通常、$Q(s_t, a)$ これらのゲーム状態の間に？
その事実は $Q(s_t, a)$ そして $U(s_t, a)$ （ゲームの状態に多くの実行可能な動きがある場合）このように異なる桁数であると、MCTSアルゴリズムの品質に影響しますか、それともMCTSはこの効果に対して堅牢であり、高品質のポリシーを生成しますか？
ゲーム状態がGoで多くの実行可能な動き（> 30）を持つことはどのくらい一般的ですか？

回答

2 DennisSoemers Dec 05 2020 at 03:08

私はあなたがあなたの計算またはそのような何かで必ずしも本当の間違いをしたとは思わない、それはすべて正確に見える。「Xは通常起こりますか？」という質問に自信を持って答えることはできません。または「Xはどのくらい一般的ですか？」、それを確認するために実験する必要があります。また、MCTSが堅牢であり、「はい」で高品質のポリシーを作成できるかどうかについての質問にも、自信を持ってすぐに答えることができると思います。これらの手法を使用した一連のゲームで、最先端の超人的な結果が得られるからです。。