---
Title: UTTT メモ
Author: noppo
Web: https://mimemo.io/m/qERa6lBZLklPb0v
---

# 概要

やっと [UTTT](https://www.codingame.com/multiplayer/bot-programming/tic-tac-toe) をクリア(Legend入り)したので自分がやった実装のメモを残します。
ざっくりした内容で、正確性についても保証できませんが、Legend 入りを目指す方の参考になれば幸いです。

今回、たくさんの先人の知恵を拝借しながら実装しましたが、特に以下の記事にはお世話になりました。この場を借りてお礼申し上げます。
https://inaniwa.hatenablog.com/entry/2020/07/05/102506
https://qiita.com/thun-c/items/058743a25c37c87b8aa4
 
---
 
# 探索アルゴリズム
- MCTS(-Solver?)
  - UCB1 の値とは別にノードごとの勝敗を4値で保持(不明、勝ち、負け、引き分け)
  - ノードの勝敗が確定した時
    - 次回以降そのノードを探索しない
    - 親のプレイアウトを書き換えて確定したノードの試行回数と利得の情報を抹消(なかったことにする)

# プレイアウト実装
精度と速度のバランスから以下の実装とした
- 合法手をランダムに選ぶ
- あと1手で勝てる場合はそこで打ち切る(1手読みをする)
 
# 手の固定
初手を固定することで1手目の探索の精度を上げる
## 先手の場合
- 初手 4,4 に固定してそこから探索木をつくる（4,4 が一番勝率高いっぽい）
## 後手の場合
- 相手が 4,4 に打ってきた場合、こちらの手を 3,3 に固定してそこから探索する
- 相手が 4,4 以外に打ってきた場合はその盤面から普通に木を構築する
 
# 探索木使いまわし
大半の結果は捨てられることにはなるものの、使い回しの実装自体は軽くデメリットがなさそうなのでやっておく
- 実装は木のルートを指す位置をずらすだけ
 
# 前計算
3x3 のパターンは 18bit で全パターン表せるのでそれらについて決着状態やそこから遷移しうる盤面（手のリスト）を前計算しておく

# 状態のデータ構造
- 3x3 を10個持つ
  - すなわち 32bit 整数10個とかが楽
- ＋αで、どちらの手番か？手を打てるボードはどれか？　などの情報
 
# コンパイルオプション
早くなりそうなものをつける
- O3
- unroll-loops
- avx
 
# メモリキャッシュを意識する
メモリアクセスパターンを考慮した処理順やデータ構造にすると速度アップすることがある
 
# メモリの動的確保をしない
木のノードや状態の構造を静的に配列で確保しておき先頭から順に使う
 
# 割り算を減らす
 
# float で十分なので double を使わない
 
# 2次元配列を1次元配列にしてみる
- 1次元にして [i * w + j] みたいな形でアクセスするようにすると速度が上がる場合がある
 
# デバッグ機能
時間ではなく探索回数で探索を打ち切る機能
- ログから通常の入力値＋探索回数の入力データを作り、デバッグ機能を有効にしたプログラムに流せばサーバで動作させた試合の状況再現が可能でデバッグが捗る
 
# ボトルネック調査
- gprof などを使う
-