この記事は「データ構造とアルゴリズム Advent Calendar 2020」20日目の記事です。 19日目は@takilogさん; グラフ上の合流に関する問題とアルゴリズム , 21日目は@tmaeharaさんです。 概要 木探索と強化学習 バンディット問題 モデルベース強化学習 アルゴリズム 評価関数 UCB Crazy Stone AlphaZero MCTS疑似コード Selection: UCB score MuZero その他の応用 最後に References 概要 モンテカルロ木探索 (MCTS) は、木探索にモンテカルロ (ランダム) 要素を加味した評価関数を用いることで、効率よく探索を行うことのできるアルゴリズムです1。特に囲碁など2プレイヤーの完全情報ゼロサムゲームで使用されており、プロ囲碁棋士を破ったAlphaGO, AlphaZeroや、Atariゲーム、将棋、