UTTT（Ultimate Tic-Tac-Toe）でMCTS（モンテカルロ木探索）の勉強
binomialsheep概要
codingameのUittimate Tic-Tac-Toeを題材にMCSTを学ぶ。
とりあえず自分用なのでルール概要とかは書かない
落ち着いたらQiitaにまとめるかも
Twitterのツリー
binomialsheep教材、リンク集
書籍
『ゲームで学ぶ探索アルゴリズム実践入門』
『AlphaZero 深層学習・強化学習・探索 人工知能プログラミング実践入門』
論文
まずは日本語の博士論文を読む典型。導入が詳しい。
モンテカルロ木探索の改善に関する研究
記事
ツイート
MCTS
高速化tips
その他
コドゲ
直前の対戦の統計が見れる便利サイト。
binomialsheep高速化
vectorをarrayにする
before
const int pow_4_9 = 262144;
vector<int> big_winning_status(pow_4_9);
vector<int> small_winning_move_map_o(pow_4_9, -1);
after
constexpr int pow_4_9 = 262144;
array<int, pow_4_9> big_winning_status_map = {};
array<int, pow_4_9> small_winning_move_map_o = {};
// -1埋めはfill(small_winning_move_map_o.begin(), small_winning_move_map_o.end(), -1);
bit board
32bit整数を9個（＋big board用の1個）持つ。
2桁ごとに1マスを当てて、00が.、01がx, 10がo, 11が引き分け（big board用）のように持つ。
board[i] |= 2 << (桁数 * 2)のように使えるので便利。
binomialsheepMCTS
テンプレ
サンダー本を使う。
パラメータ調整
大差なし。
c 1.0 EXPAND_THRESHOLD = 10 210位
c 1.2 EXPAND_THRESHOLD = 10 226位
c 0.8 EXPAND_THRESHOLD = 10 225位
c 1.0 EXPAND_THRESHOLD = 15 201位
c 1.0 EXPAND_THRESHOLD = 20 210位
binomialsheep順位情報
Woodはminimaxでよい。
Bronzeからモンテカルロ。バグなく原始モンテカルロすればゴールドまでは上がるはず。ブロンズで勝てない場合は何かがおかしい。
原始モンテカルロ
620/8940位（Gold 283/1132位）
原始モンテカルロ高速化
594/8940位
MCTS
555/8941位
前計算改善
540/8941位
root_nodeを作り直さずに張り替えで再利用
506/8941位
MCTS-solver（枝刈りしただけ）
515/8949位
bit board
446/8951位
↑を高速化
428/8951位
binomialsheepTODO
- 終盤をalphabetaにする
- 異常高速化
- 序盤を定石化・単純多腕バンデット化する
- 論文のtranspotision入れる工夫を試す
- MCTS-solverの更なる活用を試す
- 次同じ盤面になる手はグループ化する
binomialsheep論文リスト
モンテカルロ木探索の改善に関する研究
日本語の博士論文。
イントロで基本知識がすごく解説されていて良い。
MCTS-Solverの改善やハイブリッドMCTSの考察も試しやすそう。
A Survey of Monte Carlo Tree Search Methods
2012年までのMCTSの包括的なサーベイ。
Monte Carlo Tree Search A Review of Recent
2012年から2021年までのMCTSの包括的なサーベイ。かなり込み入った内容かも。
Transpositions and Move Groups in Monte Carlo Tree Search
転置テーブルや指し手のグループ化をどう取り入れるか。実装上重要そう。
Revisiting Move Groups in Monte Carlo Tree
グループ化再考。
Monte-Carlo Tree Search Solver
MCTS-Solverの提案論文。実装上は『モンテカルロ木探索の改善に関する研究』だけでいいかも。
binomialsheepKaggleで始まったやつ、何らかのヒントになりうる？まだ不明。