Sarsa-UCT(λ)の実装・実験

要約

　Sarsa-UCT(λ)のλを調整しても明確な性能向上は見られなかった。

背景

　以前の記事の通りMCTSにおける価値の漸進的更新を実装した。

　これにより単なる平均を求める手法とは異なる手法へ改造することが容易になった。特に以前紹介したSarsa-UCT(λ)は自然な形で導入ができるため、パラメータを調整しつつ性能を実験した。

実装

　バックアップの際、 $\lambda$ で現在の値とバックアップしていく値の内分を取っていく。これは実質的に表形式のSarsa( $\lambda$ )に相当する。つまり $\lambda = 1$ とするとモンテカルロ法(平均化)と同じことになり、通常のMCTSと一致する。更新ステップ幅alphaの調整も可能だが、今回はとりあえず平均化する場合と同じ値とした。

void backup(std::stack<int32_t>& indices, 
            std::stack<int32_t>& actions) {
    auto leaf = indices.top(); indices.pop();
    auto value = hash_table_[leaf].value;

    //Sarsa-UCT(λ)のλ
    static constexpr float LAMBDA = 0.9;

    while (!actions.empty()) {
        auto index = indices.top();  indices.pop();
        auto action = actions.top(); actions.pop();

        //手番が変わるので符号反転
        value = -value;

        //現在注目しているノード
        UctHashEntry& node = hash_table_[index];

        //探索回数の更新
        node.N[action]++;
        node.sum_N++;

        //値の更新
        auto curr_v = node.value;
        float alpha = 1.0f / (node.sum_N + 1);
        node.value += alpha * (value - curr_v);

        //現在の値との内分を取って次のノードへ
        value = LAMBDA * value + (1.0f - LAMBDA) * curr_v;
    }
}

実験

　 $\lambda = 1, 0.9, 0.75$ について技巧2(深さ制限5, 定跡オフ)と1手0.5秒(RTX 2080tiを使用)で300局対局を行った。

$\lambda$	勝率	相対Eloレート
1	52.0%	+13.9
0.9	56.7%	+46.6
0.75	54.3%	+30.2

　あまりはっきりとした差は出なかった。元論文では探索回数が少ない場合により顕著な差が出るとのことだったので、追加で技巧2(深さ制限4, 定跡オフ)と1手0.25秒(RTX 2080tiを使用)で500局対局を行った。

$\lambda$	勝率	相対Eloレート
1	53.9%	+27.9
0.9	56.0%	+41.6
0.75	50.2%	+1.4

　むしろ差が縮まった。プレイアウトの有無など元論文とは異なる点もあるため同じようにはいかないのかもしれない。