【将棋AI】「将棋AIで学ぶディープラーニング」を読む♪～MCTS_playerでわかる将棋AIの理論

<img width="200" style="float: left;" alt="将棋AIで学ぶディープラーニング" src="https://qiita-image-store.s3.amazonaws.com/0/233744/ded117b9-37c7-1b41-033d-960e63ca5fe1.jpeg">
第十二夜は、いよいよ、念願のモンテカルロ木探索で動くMCTS_player.pyを動かしてみましょう。
これは、alphazeroに通ずるものです。
その構造を見ていくことにより、その理論を見ていき、より強い将棋AIを作成できると思います。
###説明したいこと
（１）MCTS_player.pyをテストしてみる
（２）肝心な部分のコード解説
###（１）MCTS_player.pyをテストしてみる
コードは以下を参照願います。
【参考】
・[TadaoYamaoka/python-dlshogi](https://github.com/TadaoYamaoka/python-dlshogi/tree/master/pydlshogi)
ディレクトリ構成は以下のとおりとします。

```
PJのディレクトリ
| setup.py
| ...
| kiflist_train_1000.txt
| kiflist_test_100.txt
├── model
|     model_policy_value
|── pydlshogi
|   |common.py
|   |features.py
|   |read_kifu.py
|   └── network 　 
|   |      policy_value.py
|   └── uct 　 
|   |      uct_noe.py
|   └── usi 　 
|   |      usi.py
|   |      usi_mcts_player_.py
|   └── player 　 
|          base_player.py
|          mcts_player.py
└── utils            
|      filter_csa.py
|      ...
└── bat            
      mcts_player.bat
```
まず動かしてみて、勘所を見たいと思います。


```
>python -m pydlshogi.usi.usi_mcts_player
isready
```
readyok

```
setoption name modelfile value C:\Users\tosio\fastText\path\to\corpus\AB\KerasExample\dlshogi\model\model_policy_value
position startpos
```
lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1
[この出力までは前回のテストと同じ内容です](https://qiita.com/MuAuan/items/eb2042ae78c79f0ba73b)。
そして、思考させると。。。

```
go
```
以下のように返ってきます。[これは以前は確率だけを返していたのとは全くことなり](https://qiita.com/MuAuan/items/eb2042ae78c79f0ba73b)、訪問回数などを返しています。
  0:9g9f  move_count:   1 nn_rate:0.00633 win_rate:0.47294
  1:8g8f  move_count:   0 nn_rate:0.00020 win_rate:0.00000に
  2:7g7f  move_count: 144 nn_rate:0.68336 win_rate:0.53161
  3:6g6f  move_count:   0 nn_rate:0.00472 win_rate:0.00000
  4:5g5f  move_count:   4 nn_rate:0.01883 win_rate:0.53999
  5:4g4f  move_count:   0 nn_rate:0.00393 win_rate:0.00000
  6:3g3f  move_count:   0 nn_rate:0.00441 win_rate:0.00000
  7:2g2f  move_count:  38 nn_rate:0.18533 win_rate:0.52896
  8:1g1f  move_count:   0 nn_rate:0.00233 win_rate:0.00000
  9:9i9h  move_count:   0 nn_rate:0.00013 win_rate:0.00000
 10:1i1h  move_count:   0 nn_rate:0.00001 win_rate:0.00000
 11:7i7h  move_count:   0 nn_rate:0.00153 win_rate:0.00000
 12:7i6h  move_count:   0 nn_rate:0.00398 win_rate:0.00000
 13:3i4h  move_count:   1 nn_rate:0.00965 win_rate:0.43366
 14:3i3h  move_count:   4 nn_rate:0.01792 win_rate:0.52637
 15:6i7h  move_count:   1 nn_rate:0.01411 win_rate:0.42402
 16:6i6h  move_count:   0 nn_rate:0.00003 win_rate:0.00000
 17:6i5h  move_count:   0 nn_rate:0.00109 win_rate:0.00000
 18:4i5h  move_count:   0 nn_rate:0.00549 win_rate:0.00000
 19:4i4h  move_count:   0 nn_rate:0.00027 win_rate:0.00000
 20:4i3h  move_count:   0 nn_rate:0.00122 win_rate:0.00000
 21:2h7h  move_count:   1 nn_rate:0.00927 win_rate:0.43401
 22:2h6h  move_count:   0 nn_rate:0.00220 win_rate:0.00000
 23:2h5h  move_count:   0 nn_rate:0.00523 win_rate:0.00000
 24:2h4h  move_count:   0 nn_rate:0.00044 win_rate:0.00000
 25:2h3h  move_count:   0 nn_rate:0.00282 win_rate:0.00000
 26:2h1h  move_count:   0 nn_rate:0.00013 win_rate:0.00000
 27:5i6h  move_count:   1 nn_rate:0.01218 win_rate:0.35891
 28:5i5h  move_count:   0 nn_rate:0.00270 win_rate:0.00000
 29:5i4h  move_count:   0 nn_rate:0.00016 win_rate:0.00000
info nps 87 time 2233 nodes 195 hashfull 46 score cp 75 pv 7g7f
bestmove 7g7f

その結果、訪問回数が１４４回と最も多い7g7f「７六歩」がbestmoveとして選ばれています。ゲーム開始から１０手以内は訪問回数に応じた確率で手を選択するため、7g7f以外の手が選ばれることもあります。nn_rateが方策ネットワークの予測確率を示しています。予測確率が高い手に探索時に多くのプレイアウトが割り当てられていることが確認できます。

```
quit
```
###（２）肝心な部分のコード解説
動きは少しわかったので、肝心な部分のコードだけ解説したいと思います。
全体はおまけに載せておきました。
ここでは、昨夜のAlphaGoのモンテカルロ木探索の
１．選択
２．展開と評価
３．バックアップ
のコードの説明をし、最後に
４．統合して探索するgo
のコードをみることとします。
####１．選択
選択は以下の量を計算して最大になる手を選択することでした。
「ルートノードからゲーム木を未展開のノードに達するまでたどります。各ノードでは以下の式が最大になる手を選択します。

```math
Q(s_t,a)+U(s_t,a)
```

```math
Q(s_t,a)；状態s_tにおける行動aの行動価値\Rightarrow 期待値項
```

```math
Q(s,a)=(1-\lambda)\frac{W_v(s,a)}{N_v(s,a)}+\lambda\frac{W_r(s,a)}{N_r(s,a)}
```
ここでAlpha Zeroではロールアウトをしないので、λ=０である。
※AlphaGoではロールアウトも利用していたのでλを使って加重平均していた

```math
U(s_t,a);探索回数が少ない手を探索回数が多い手よりも優先するための値を制御\Rightarrow ボーナス項
```

```math
U(s,a)=c_{puct}P(s,a)\frac{\sqrt{\sum_bN(s,b)}}{1+N(s,a)}
```
ここでP(s,a)は方策ネットワークにより予測した着手確率を使用する。」
これに対応するコードは以下のものです。

```py
    # UCB値が最大の手を求める
    def select_max_ucb_child(self, board, current_node):
        child_num = current_node.child_num
        child_win = current_node.child_win
        child_move_count = current_node.child_move_count

        q = np.divide(child_win, child_move_count, out=np.repeat(np.float32(0.5), child_num), where=child_move_count != 0)
        u = np.sqrt(np.float32(current_node.move_count)) / (1 + child_move_count)
        ucb = q + C_PUCT * current_node.nnrate * u

        return np.argmax(ucb)
```
####２．展開と評価
ノードを展開する処理はexpand_nodeメソッドで行います。

```py 
    # ノードの展開
    def expand_node(self, board):

        #割り当て済チェック
        index = self.node_hash.find_same_hash_index(board.zobrist_hash(), board.turn, board.move_number)

        # 合流先が検知できれば(割り当て済ならば), それを返す
        if not index == UCT_HASH_SIZE:
            return index
        #indexが見つからない場合、新たにindexを割り当てる
        # 空のインデックスを探す
        index = self.node_hash.search_empty_index(board.zobrist_hash(), board.turn, board.move_number)

        #割り当てたindexを初期化する
        # 現在のノードの初期化
        current_node = self.uct_node[index]
        current_node.move_count = 0
        current_node.win = 0.0
        current_node.child_num = 0
        current_node.evaled = False
        current_node.value_win = 0.0

        # （すべての）候補手の展開
        current_node.child_move = [move for move in board.legal_moves]
        child_num = len(current_node.child_move)
        current_node.child_index = [NOT_EXPANDED for _ in range(child_num)]
        current_node.child_move_count = np.zeros(child_num, dtype=np.int32)
        current_node.child_win = np.zeros(child_num, dtype=np.float32)

        # 子ノードの個数を設定
        current_node.child_num = child_num
```
ノードを展開したら、ノードを評価します。通常のモンテカルロ木探索は訪問回数が閾値を超えるまでノードの展開をしません。価値ネットワークを使う場合、ノードを訪問したら必ず展開を行うため、ノード展開と評価のタイミングは同時になります。そのため、expand_nodeメソッドのなかで評価も行っています。

```py
        # ノードを評価
        if child_num > 0:
            self.eval_node(board, index)
        else:
            current_node.value_win = 0.0
            current_node.evaled = True

        return index
```
ノードの評価はeval_nodeメソッドで行います。


```py
    # ノードを評価
    def eval_node(self, board, index):
        eval_features = [make_input_features_from_board(board)]

        x = Variable(cuda.to_gpu(np.array(eval_features, dtype=np.float32)))
        with chainer.no_backprop_mode():
            y1, y2 = self.model(x)

            logits = cuda.to_cpu(y1.data)[0]
            value = cuda.to_cpu(F.sigmoid(y2).data)[0]
```
y1, y2 = self.model(x)により、方策ネットワークと価値ネットワークを同時に出力するモデルで予測を行います。予測結果はミニバッチになっているため先頭の要素を取り出し、方策ネットワークと価値ネットワークの出力をlogitsとvalueに格納しています。

```py
        current_node = self.uct_node[index]
        child_num = current_node.child_num
        child_move = current_node.child_move
        color = self.node_hash[index].color

        # 合法手でフィルター
        legal_move_labels = []
        for i in range(child_num):
            legal_move_labels.append(make_output_label(child_move[i], color))
```
方策ネットワークで予測した手には合法手以外も含まれているため、合法手でフィルターをかけてlegal_move_labelsに格納しています。

```py

        # Boltzmann分布
        probabilities = softmax_temperature_with_normalize(logits[legal_move_labels], self.temperature)

        # ノードの値を更新
        current_node.nnrate = probabilities
        current_node.value_win = float(value)
        current_node.evaled = True
```
eval_nodeメソッドの最後で、ノードの情報に予測した候補手の確率と価値と評価済という意味のTrueを設定します。
以下のBoltzmann分布を利用して、probabilitiesとして候補手の可能性を温度パラメーターによって、励起して確率が小さい候補手まで可能性を広げている。 

```py
def softmax_temperature_with_normalize(logits, temperature):
    # 温度パラメータを適用
    logits /= temperature
    # 確率を計算(オーバーフローを防止するため最大値で引く)
    max_logit = max(logits)
    probabilities = np.exp(logits - max_logit)
    # 合計が1になるように正規化
    sum_probabilities = sum(probabilities)
    probabilities /= sum_probabilities
    return probabilities
```
####３．バックアップ
探索処理はuct_searchメソッドで行います。ここでは１つのノードについての処理を記述し、ゲーム木をたどる場合は再帰的に呼び出します。戻り値として勝率を返します。メソッドを呼び出すたびに手番が入れ替わるため戻り値の勝率は、（１－勝率）で相手の手番の勝率を返します。


```py
    # UCT探索
    def uct_search(self, board, current):
        current_node = self.uct_node[current]

        # 詰みのチェック
        if current_node.child_num == 0:
            return 1.0 # 反転して値を返すため1を返す

        child_move = current_node.child_move
        child_move_count = current_node.child_move_count
        child_index = current_node.child_index

        # UCB値が最大の手を求める
        next_index = self.select_max_ucb_child(board, current_node)
        # 選んだ手を着手
        board.push(child_move[next_index])

        # ノードの展開の確認
        if child_index[next_index] == NOT_EXPANDED:
            # ノードの展開(ノード展開処理の中でノードを評価する)
            index = self.expand_node(board)
            child_index[next_index] = index
            child_node = self.uct_node[index]

            # valueを勝敗として返す
            result = 1 - child_node.value_win
        else:
            # 手番を入れ替えて1手深く読む
            result = self.uct_search(board, child_index[next_index])
```
以下でバックアップを行います。
・勝率の合計にresultを加算する
・訪問回数を＋１する
・子ノードの勝率の合計にresultを加算する
・子ノードの訪問回数に＋１する

```py
        # 探索結果の反映
        current_node.win += result
        current_node.move_count += 1
        current_node.child_win[next_index] += result
        current_node.child_move_count[next_index] += 1

        # 手を戻す
        board.pop()

        return 1 - result
```
####４．統合して探索するgo
最後にgoメソッドは以下のとおりとなっています。

```py
    def go(self):
        if self.board.is_game_over():
            print('bestmove resign')
            return

        # 探索情報をクリア
        self.po_info.count = 0

        # 古いハッシュを削除
        self.node_hash.delete_old_hash(self.board, self.uct_node)

        # 探索開始時刻の記録
        begin_time = time.time()

        # 探索回数の閾値を設定
        self.po_info.halt = self.playout

        # ルートノードの展開
        self.current_root = self.expand_node(self.board)

        # 候補手が1つの場合は、その手を返す
        current_node = self.uct_node[self.current_root]
        child_num = current_node.child_num
        child_move = current_node.child_move
        if child_num == 1:
            print('bestmove', child_move[0].usi())
            return

        # プレイアウトを繰り返す
        # 探索回数が閾値を超える, または探索が打ち切られたらループを抜ける
        while self.po_info.count < self.po_info.halt:
            # 探索回数を1回増やす
            self.po_info.count += 1
            # 1回プレイアウトする
            self.uct_search(self.board, self.current_root)
            # 探索を打ち切るか確認
            if self.interruption_check() or not self.node_hash.enough_size:
                break

        # 探索にかかった時間を求める
        finish_time = time.time() - begin_time

        child_move_count = current_node.child_move_count
        if self.board.move_number < 10:
            # 訪問回数に応じた確率で手を選択する
            selected_index = np.random.choice(np.arange(child_num), p=child_move_count/sum(child_move_count))
        else:
            # 訪問回数最大の手を選択する
            selected_index = np.argmax(child_move_count)

        child_win = current_node.child_win

        # for debug
        for i in range(child_num):
            print('{:3}:{:5} move_count:{:4} nn_rate:{:.5f} win_rate:{:.5f}'.format(
                i, child_move[i].usi(), child_move_count[i],
                current_node.nnrate[i],
                child_win[i] / child_move_count[i] if child_move_count[i] > 0 else 0))

        # 選択した着手の勝率の算出
        best_wp = child_win[selected_index] / child_move_count[selected_index]

        # 閾値未満の場合投了
        if best_wp < RESIGN_THRESHOLD:
            print('bestmove resign')
            return

        bestmove = child_move[selected_index]

        # 勝率を評価値に変換
        if best_wp == 1.0:
            cp = 30000
        else:
            cp = int(-math.log(1.0 / best_wp - 1.0) * 600)

        print('info nps {} time {} nodes {} hashfull {} score cp {} pv {}'.format(
            int(current_node.move_count / finish_time),
            int(finish_time * 1000),
            current_node.move_count,
            int(self.node_hash.get_usage_rate() * 1000),
            cp, bestmove.usi()))

        print('bestmove', bestmove.usi())
```
ここで
`cp = int(-math.log(1.0 / best_wp - 1.0) * 600)`
については自明と云えるほどではないので、ググってみると山岡さんが考察されていた。
つまり、勝率と評価値の換算の妥当性である。
・ [将棋でディープラーニングする その22(評価値と勝率の関係) ](http://tadaoyamaoka.hatenablog.com/entry/2017/05/24/220807)
によれば、「回帰の結果、シグモイド関数のスケーリングのパラメータは、0.00132566 = 1/754.3となった。」また「100万局で再計測したので、sigmoidの値も掲載しておく。756.0864962951762 = 1/0.0013226」とのことなので、この辺りの値を使うのがより精度が高いと云えそうだ。またtanhでもフィッティングしているので参考にしたい。
###まとめ
・将棋AIであるmcts_player.pyを手で動かして振舞を見た
・mctsの主要なコードを理論と照らして解説した

・いよいよ次回は実際に対戦したいと思う
###おまけ
上記のtemperature=100としたときの手で動かしたときの結果

```
position startpos
lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1
go
  0:9g9f  move_count:   4 nn_rate:0.03367 win_rate:0.47787
  1:8g8f  move_count:   3 nn_rate:0.03253 win_rate:0.44369
  2:7g7f  move_count:  77 nn_rate:0.03528 win_rate:0.58752
  3:6g6f  move_count:   4 nn_rate:0.03357 win_rate:0.45876
  4:5g5f  move_count:  11 nn_rate:0.03404 win_rate:0.54889
  5:4g4f  move_count:   3 nn_rate:0.03351 win_rate:0.45515
  6:3g3f  move_count:   2 nn_rate:0.03355 win_rate:0.40284
  7:2g2f  move_count:  45 nn_rate:0.03482 win_rate:0.58166
  8:1g1f  move_count:   4 nn_rate:0.03333 win_rate:0.45932
  9:9i9h  move_count:   3 nn_rate:0.03239 win_rate:0.43669
 10:1i1h  move_count:   3 nn_rate:0.03156 win_rate:0.46084
 11:7i7h  move_count:   3 nn_rate:0.03319 win_rate:0.44851
 12:7i6h  move_count:  26 nn_rate:0.03351 win_rate:0.58966
 13:3i4h  move_count:   4 nn_rate:0.03381 win_rate:0.44309
 14:3i3h  move_count:  36 nn_rate:0.03402 win_rate:0.57787
 15:6i7h  move_count:   3 nn_rate:0.03394 win_rate:0.45715
 16:6i6h  move_count:   3 nn_rate:0.03186 win_rate:0.42268
 17:6i5h  move_count:   2 nn_rate:0.03308 win_rate:0.38380
 18:4i5h  move_count:   2 nn_rate:0.03362 win_rate:0.39495
 19:4i4h  move_count:   4 nn_rate:0.03263 win_rate:0.45794
 20:4i3h  move_count:   2 nn_rate:0.03312 win_rate:0.29688
 21:2h7h  move_count:   3 nn_rate:0.03380 win_rate:0.44275
 22:2h6h  move_count:   3 nn_rate:0.03331 win_rate:0.44407
 23:2h5h  move_count:   5 nn_rate:0.03360 win_rate:0.49688
 24:2h4h  move_count:   2 nn_rate:0.03278 win_rate:0.35826
 25:2h3h  move_count:   2 nn_rate:0.03340 win_rate:0.38922
 26:2h1h  move_count:   2 nn_rate:0.03239 win_rate:0.38124
 27:5i6h  move_count:   3 nn_rate:0.03389 win_rate:0.44397
 28:5i5h  move_count:   3 nn_rate:0.03338 win_rate:0.45257
 29:5i4h  move_count:   2 nn_rate:0.03244 win_rate:0.40322
info nps 111 time 2421 nodes 269 hashfull 65 score cp 117 pv 5g5f
bestmove 5g5f
```
結果全然違いますね。。。。これだと方策ネットワークの確率が生かされていない感じです。

```
temperature=2.0
go
  0:9g9f  move_count:   4 nn_rate:0.02799 win_rate:0.47787
  1:8g8f  move_count:   1 nn_rate:0.00504 win_rate:0.46547
  2:7g7f  move_count: 109 nn_rate:0.29091 win_rate:0.53348
  3:6g6f  move_count:   3 nn_rate:0.02418 win_rate:0.47630
  4:5g5f  move_count:  10 nn_rate:0.04829 win_rate:0.50262
  5:4g4f  move_count:   2 nn_rate:0.02205 win_rate:0.44055
  6:3g3f  move_count:   2 nn_rate:0.02337 win_rate:0.40284
  7:2g2f  move_count: 118 nn_rate:0.15150 win_rate:0.55964
  8:1g1f  move_count:   3 nn_rate:0.01699 win_rate:0.47973
  9:9i9h  move_count:   0 nn_rate:0.00407 win_rate:0.00000
 10:1i1h  move_count:   0 nn_rate:0.00111 win_rate:0.00000
 11:7i7h  move_count:   1 nn_rate:0.01378 win_rate:0.42205
 12:7i6h  move_count:   4 nn_rate:0.02220 win_rate:0.45717
 13:3i4h  move_count:   4 nn_rate:0.03457 win_rate:0.44309
 14:3i3h  move_count:   7 nn_rate:0.04711 win_rate:0.47794
 15:6i7h  move_count:   5 nn_rate:0.04181 win_rate:0.45566
 16:6i6h  move_count:   0 nn_rate:0.00178 win_rate:0.00000
 17:6i5h  move_count:   1 nn_rate:0.01160 win_rate:0.38668
 18:4i5h  move_count:   1 nn_rate:0.02606 win_rate:0.34976
 19:4i4h  move_count:   1 nn_rate:0.00582 win_rate:0.41181
 20:4i3h  move_count:   1 nn_rate:0.01230 win_rate:0.44081
 21:2h7h  move_count:   4 nn_rate:0.03388 win_rate:0.42502
 22:2h6h  move_count:   1 nn_rate:0.01650 win_rate:0.36892
 23:2h5h  move_count:   4 nn_rate:0.02546 win_rate:0.48154
 24:2h4h  move_count:   1 nn_rate:0.00742 win_rate:0.47294
 25:2h3h  move_count:   1 nn_rate:0.01868 win_rate:0.35517
 26:2h1h  move_count:   0 nn_rate:0.00402 win_rate:0.00000
 27:5i6h  move_count:   4 nn_rate:0.03884 win_rate:0.43497
 28:5i5h  move_count:   1 nn_rate:0.01828 win_rate:0.39618
 29:5i4h  move_count:   0 nn_rate:0.00439 win_rate:0.00000
info nps 111 time 2624 nodes 293 hashfull 68 score cp 143 pv 2g2f
bestmove 2g2f
```

２．以下のコードは本書で紹介しているpolicy_value_resnet.py用のコードからpolicy_value.pyを利用するように変更したものです。

```mcts_player.py
﻿import numpy as np
import chainer
from chainer import serializers
from chainer import cuda, Variable
import chainer.functions as F

import shogi

from pydlshogi.common import *
from pydlshogi.features import *
#from pydlshogi.network.policy_value_resnet import *
from pydlshogi.network.policy_value import *
from pydlshogi.player.base_player import *
from pydlshogi.uct.uct_node import *

import math
import time
import copy

# UCBのボーナス項の定数
C_PUCT = 1.0
# 1手当たりのプレイアウト数
CONST_PLAYOUT = 300
# 投了する勝率の閾値
RESIGN_THRESHOLD = 0.01
# 温度パラメータ
TEMPERATURE = 1.0

def softmax_temperature_with_normalize(logits, temperature):
    # 温度パラメータを適用
    logits /= temperature

    # 確率を計算(オーバーフローを防止するため最大値で引く)
    max_logit = max(logits)
    probabilities = np.exp(logits - max_logit)

    # 合計が1になるように正規化
    sum_probabilities = sum(probabilities)
    probabilities /= sum_probabilities

    return probabilities

class PlayoutInfo:
    def __init__(self):
        self.halt = 0 # 探索を打ち切る回数
        self.count = 0 # 現在の探索回数

class MCTSPlayer(BasePlayer):
    def __init__(self):
        super().__init__()
        # モデルファイルのパス
        #self.modelfile = r'H:\src\python-dlshogi\model\model_policy_value_resnet'
        self.modelfile = r'C:\Users\tosio\fastText\path\to\corpus\AB\KerasExample\dlshogi\model\model_policy_value'
        self.model = None # モデル

        # ノードの情報
        self.node_hash = NodeHash()
        self.uct_node = [UctNode() for _ in range(UCT_HASH_SIZE)]

        # プレイアウト回数管理
        self.po_info = PlayoutInfo()
        self.playout = CONST_PLAYOUT

        # 温度パラメータ
        self.temperature = TEMPERATURE

    # UCB値が最大の手を求める
    def select_max_ucb_child(self, board, current_node):
        child_num = current_node.child_num
        child_win = current_node.child_win
        child_move_count = current_node.child_move_count

        q = np.divide(child_win, child_move_count, out=np.repeat(np.float32(0.5), child_num), where=child_move_count != 0)
        u = np.sqrt(np.float32(current_node.move_count)) / (1 + child_move_count)
        ucb = q + C_PUCT * current_node.nnrate * u

        return np.argmax(ucb)


    # ノードの展開
    def expand_node(self, board):
        index = self.node_hash.find_same_hash_index(board.zobrist_hash(), board.turn, board.move_number)

        # 合流先が検知できれば, それを返す
        if not index == UCT_HASH_SIZE:
            return index
    
        # 空のインデックスを探す
        index = self.node_hash.search_empty_index(board.zobrist_hash(), board.turn, board.move_number)

        # 現在のノードの初期化
        current_node = self.uct_node[index]
        current_node.move_count = 0
        current_node.win = 0.0
        current_node.child_num = 0
        current_node.evaled = False
        current_node.value_win = 0.0

        # 候補手の展開
        current_node.child_move = [move for move in board.legal_moves]
        child_num = len(current_node.child_move)
        current_node.child_index = [NOT_EXPANDED for _ in range(child_num)]
        current_node.child_move_count = np.zeros(child_num, dtype=np.int32)
        current_node.child_win = np.zeros(child_num, dtype=np.float32)

        # 子ノードの個数を設定
        current_node.child_num = child_num

        # ノードを評価
        if child_num > 0:
            self.eval_node(board, index)
        else:
            current_node.value_win = 0.0
            current_node.evaled = True

        return index

    # 探索を打ち切るか確認
    def interruption_check(self):
        child_num = self.uct_node[self.current_root].child_num
        child_move_count = self.uct_node[self.current_root].child_move_count
        rest = self.po_info.halt - self.po_info.count

        # 探索回数が最も多い手と次に多い手を求める
        second, first = child_move_count[np.argpartition(child_move_count, -2)[-2:]]

        # 残りの探索を全て次善手に費やしても最善手を超えられない場合は探索を打ち切る
        if first - second > rest:
            return True
        else:
            return False

    # UCT探索
    def uct_search(self, board, current):
        current_node = self.uct_node[current]

        # 詰みのチェック
        if current_node.child_num == 0:
            return 1.0 # 反転して値を返すため1を返す

        child_move = current_node.child_move
        child_move_count = current_node.child_move_count
        child_index = current_node.child_index

        # UCB値が最大の手を求める
        next_index = self.select_max_ucb_child(board, current_node)
        # 選んだ手を着手
        board.push(child_move[next_index])

        # ノードの展開の確認
        if child_index[next_index] == NOT_EXPANDED:
            # ノードの展開(ノード展開処理の中でノードを評価する)
            index = self.expand_node(board)
            child_index[next_index] = index
            child_node = self.uct_node[index]

            # valueを勝敗として返す
            result = 1 - child_node.value_win
        else:
            # 手番を入れ替えて1手深く読む
            result = self.uct_search(board, child_index[next_index])

        # 探索結果の反映
        current_node.win += result
        current_node.move_count += 1
        current_node.child_win[next_index] += result
        current_node.child_move_count[next_index] += 1

        # 手を戻す
        board.pop()

        return 1 - result

    # ノードを評価
    def eval_node(self, board, index):
        eval_features = [make_input_features_from_board(board)]

        x = Variable(cuda.to_gpu(np.array(eval_features, dtype=np.float32)))
        with chainer.no_backprop_mode():
            y1, y2 = self.model(x)

            logits = cuda.to_cpu(y1.data)[0]
            value = cuda.to_cpu(F.sigmoid(y2).data)[0]

        current_node = self.uct_node[index]
        child_num = current_node.child_num
        child_move = current_node.child_move
        color = self.node_hash[index].color

        # 合法手でフィルター
        legal_move_labels = []
        for i in range(child_num):
            legal_move_labels.append(make_output_label(child_move[i], color))

        # Boltzmann分布
        probabilities = softmax_temperature_with_normalize(logits[legal_move_labels], self.temperature)

        # ノードの値を更新
        current_node.nnrate = probabilities
        current_node.value_win = float(value)
        current_node.evaled = True

    def usi(self):
        print('id name mcts_player')
        print('option name modelfile type string default ' + self.modelfile)
        print('option name playout type spin default ' + str(self.playout) + ' min 100 max 10000')
        print('option name temperature type spin default ' + str(int(self.temperature * 100)) + ' min 1 max 10000')
        print('usiok')

    def setoption(self, option):
        if option[1] == 'modelfile':
            self.modelfile = option[3]
        elif option[1] == 'playout':
            self.playout = int(option[3])
        elif option[1] == 'temperature':
            self.temperature = int(option[3]) / 100

    def isready(self):
        # モデルをロード
        if self.model is None:
            #self.model = PolicyValueResnet()
            self.model = PolicyValueNetwork()
            self.model.to_gpu()
        serializers.load_npz(self.modelfile, self.model)
        # ハッシュを初期化
        self.node_hash.initialize()
        print('readyok')

    def go(self):
        if self.board.is_game_over():
            print('bestmove resign')
            return

        # 探索情報をクリア
        self.po_info.count = 0

        # 古いハッシュを削除
        self.node_hash.delete_old_hash(self.board, self.uct_node)

        # 探索開始時刻の記録
        begin_time = time.time()

        # 探索回数の閾値を設定
        self.po_info.halt = self.playout

        # ルートノードの展開
        self.current_root = self.expand_node(self.board)

        # 候補手が1つの場合は、その手を返す
        current_node = self.uct_node[self.current_root]
        child_num = current_node.child_num
        child_move = current_node.child_move
        if child_num == 1:
            print('bestmove', child_move[0].usi())
            return

        # プレイアウトを繰り返す
        # 探索回数が閾値を超える, または探索が打ち切られたらループを抜ける
        while self.po_info.count < self.po_info.halt:
            # 探索回数を1回増やす
            self.po_info.count += 1
            # 1回プレイアウトする
            self.uct_search(self.board, self.current_root)
            # 探索を打ち切るか確認
            if self.interruption_check() or not self.node_hash.enough_size:
                break

        # 探索にかかった時間を求める
        finish_time = time.time() - begin_time

        child_move_count = current_node.child_move_count
        if self.board.move_number < 10:
            # 訪問回数に応じた確率で手を選択する
            selected_index = np.random.choice(np.arange(child_num), p=child_move_count/sum(child_move_count))
        else:
            # 訪問回数最大の手を選択する
            selected_index = np.argmax(child_move_count)

        child_win = current_node.child_win

        # for debug
        for i in range(child_num):
            print('{:3}:{:5} move_count:{:4} nn_rate:{:.5f} win_rate:{:.5f}'.format(
                i, child_move[i].usi(), child_move_count[i],
                current_node.nnrate[i],
                child_win[i] / child_move_count[i] if child_move_count[i] > 0 else 0))

        # 選択した着手の勝率の算出
        best_wp = child_win[selected_index] / child_move_count[selected_index]

        # 閾値未満の場合投了
        if best_wp < RESIGN_THRESHOLD:
            print('bestmove resign')
            return

        bestmove = child_move[selected_index]

        # 勝率を評価値に変換
        if best_wp == 1.0:
            cp = 30000
        else:
            cp = int(-math.log(1.0 / best_wp - 1.0) * 600)

        print('info nps {} time {} nodes {} hashfull {} score cp {} pv {}'.format(
            int(current_node.move_count / finish_time),
            int(finish_time * 1000),
            current_node.move_count,
            int(self.node_hash.get_usage_rate() * 1000),
            cp, bestmove.usi()))

        print('bestmove', bestmove.usi())
```