# 概要

やっと [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手読みをする)
 
# 手の固定
## 先手の場合
- 初手 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 使う