# BERT-MCTS 紹介

## TL; DR

プロ棋士の谷合四段（東京大学博士課程在籍中）がヨビノリとのコラボ企画のために将棋ソフトを作成

ウォーズ四段（らしい）のヨビノリたくみさんと熱戦（結果は動画を見て）

ソフトの手法は BERT-MCTS という谷合四段独自のもの。

その名の通り、BERT と MCTS（モンテカルロ木探索）を用いる。

将棋ソフトに transformer が用いられてそこそこ強くなった（アマチュア初段以上？）、おそらく初めての例。

[nyoki-mtl/bert-mcts-youtube](https://github.com/nyoki-mtl/bert-mcts-youtube)

[https://www.youtube.com/watch?v=2Vl6Ao4GaSQ](https://www.youtube.com/watch?v=2Vl6Ao4GaSQ)

## モンテカルロ木探索（MCTS）

ゲーム木（局面がノード、指し手がエッジ、現局面がルートノードの根付き木）を探索して良い指し手を選択するアルゴリズム。

"なんらかの基準" で手を選択していき、ある程度の深さまで潜ったらプレイアウト（弱いソフト等高速な方法で終局まで指す）をして、その勝敗を記録する。これを何度も繰り返し、勝率の高い手を出力する。

"なんらかの基準" は、「良い指し手をたくさん選択する・まだあまり探索していない手を探索する」の両方をバランス良く満たすよう設計する。

### PUCT アルゴリズム

[https://github.com/nyoki-mtl/bert-mcts-youtube/blob/main/src/player/mcts_player.py#L112](https://github.com/nyoki-mtl/bert-mcts-youtube/blob/main/src/player/mcts_player.py#L112)

終局までプレイアウトするのは大変だし、弱いソフトでのプレイアウトでは信頼性が低いため、プレイアウトの代わりに**当該局面での勝率をニューラルネットワークで予測**する。ここで使うニューラルネットワークを**バリューネットワーク**という。

この予測結果をもとに手を選択する。

また、探索開始時にも良い手を選びやすくするため、指し手の選択に関する事前分布として、「今見ている局面で可能な指し手それぞれを選ぶ確率」をニューラルネットワークで計算する。ここで使うニューラルネットワークを**ポリシーネットワーク（方策ネットワーク）** という。

将棋のルールに違反しない手（合法手）のみ選択するようにフィルタリングされている。

よく分かる解説：[https://tadaoyamaoka.hatenablog.com/entry/2017/06/03/235918](https://tadaoyamaoka.hatenablog.com/entry/2017/06/03/235918)

BERT-MCTS においては、バリューネットワークとポリシーネットワークが共に BERT になっている。

[https://github.com/nyoki-mtl/bert-mcts-youtube/blob/main/src/model/bert.py#L34](https://github.com/nyoki-mtl/bert-mcts-youtube/blob/main/src/model/bert.py#L34)

具体的には、事前学習済み BERT モデルの出力を、バリューヘッドとポリシーヘッドに入力し、バリュー（評価値を表すスカラー）とポリシー（指し手の選択確率を表すベクトル）を出力する。（厳密には、ポリシー出力はこの時点では softmax されていない）

## BERT の使い方

### BERT の入力

BERT-MCTS では、dlshogi 開発者の山岡氏が開発した cshogi という Python 将棋ライブラリが用いられている。

[https://github.com/TadaoYamaoka/cshogi](https://github.com/TadaoYamaoka/cshogi)

cshogi で盤面情報を取得すると、１一（右上）から９九（左下）まで、縦向きに、盤面の情報を表す長さ 81 の数列が得られる。値は駒を表す ID か空欄を表す ID となっている。

さらに、持ち駒情報を取得すると、各プレイヤーの持ち駒に各駒（7種類）が何枚あるかを表す長さ 7 の数列が得られる。

これらを結合して、 81+7+7=95 の長さの配列が局面を表す数列となる。これを、95 単語の文のように BERT に入力する。

なお、後手番のときは盤面を回転させ、持ち駒を入れ替えて、後手番目線での情報を扱う。

### BERT の学習

事前学習には、コンピュータ将棋対戦サーバー [floodgate](http://wdoor.c.u-tokyo.ac.jp/shogi/floodgate.html) の棋譜や複数の開発者によって作成された互角局面集による MLM (Masked Language Model) が用いられた。

互角局面集は、24 - 36 手程度指された局面で、最初から評価値が互角を維持していた局面を集めたもの。序盤の良い形が学習できる。

[https://github.com/tttak/ShogiGokakuKyokumen](https://github.com/tttak/ShogiGokakuKyokumen)

転移学習には、GCT という将棋ソフトの自己対戦棋譜集が用いられた。

[https://drive.google.com/drive/folders/14FaqqIHRctTQIY6hScCFXWQQZ_pSU3-F](https://drive.google.com/drive/folders/14FaqqIHRctTQIY6hScCFXWQQZ_pSU3-F)

前述のモデルにこの棋譜の局面を入力し、バリューを MSELoss、ポリシーを CrossEntropyLoss で学習した。

つまり、GCT の指し手が正解であるとして、それを学習しようとした。

将棋は良質な棋譜がたくさんあるため、事前学習の有効性は限定的かもしれないとのこと。

## コード読みたい人向け

USI プロトコル、SFEN 記法、HCPE (HuffmanCodePos and Eval) 、Zorbist Hashing およびその[改良](https://yaneuraou.yaneu.com/2015/12/16/%E9%80%A3%E8%BC%89%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%A7%E9%81%8A%E3%81%BC%E3%81%86%EF%BC%817%E6%97%A5%E7%9B%AE/)、などのコンピュータ将棋専門概念が出てきます。

- USI (Universal Shogi Interface) プロトコル
- コンピュータ将棋で通信を行うためのプロトコル。[MCTSPlayer](https://yaneuraou.yaneu.com/2015/12/16/%E9%80%A3%E8%BC%89%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8Bmini%E3%81%A7%E9%81%8A%E3%81%BC%E3%81%86%EF%BC%817%E6%97%A5%E7%9B%AE/) が持つメソッドの `go` や `isready` などはこれに基づく命名。 `readyok` などの出力もこれに基づく。USI プロトコルで動作するコンピュータ将棋エンジンは「将棋所」という GUI ソフトで動かせる。
- SFEN 記法
- 将棋の局面を表す記法。駒を 1 文字で表し、盤の左上から右下まで文字列で表す。空マスは連続する個数を整数で記述。
- チェスのために考案された [Forsyth-Edwards Notation](https://ja.wikipedia.org/wiki/Forsyth-Edwards_Notation) を将棋用にアレンジしたもの。
- USI プロトコルと SFEN 記法の解説 [http://shogidokoro.starfree.jp/usi.html](http://shogidokoro.starfree.jp/usi.html)
- HCPE (HuffmanCodePos and Eval)
- 局面をハフマン符号で圧縮したもの（HCP）と、評価値、指し手、勝敗をまとめた、教師局面を表すデータ構造。
- 解説1：[https://tadaoyamaoka.hatenablog.com/entry/2017/05/28/164444](https://tadaoyamaoka.hatenablog.com/entry/2017/05/28/164444)
- 解説2：[https://tadaoyamaoka.hatenablog.com/entry/2018/05/10/230851](https://tadaoyamaoka.hatenablog.com/entry/2018/05/10/230851)
- Zorbist Hashing
- 局面をハッシュ値に変換する手法
- 「あるマスにある駒が存在するときの乱数」を事前に作成しておき、すべての駒に対する当該値の XOR をハッシュ値とする。
- 一手では高々 2 駒しか変化しないので、この手法により差分計算が高速。
- 将棋においては、持ち駒の枚数という概念があるため、XOR ではなく ADD が用いられることがある。
- 後述の置換表や、千日手（同一局面が4回発生したら強制終了になるルール）の判定に用いられる。
- transposition table（置換表）
- ある局面に対する計算済みの評価値を記録する表。Zorbist Hash をキーとし、計算済みの情報を値をするハッシュテーブル。
- 複数の手を指す順番が入れ替わっただけで同一局面に行き着くこと（手順前後）があるので、そういうときに計算の手間を省ける。
- transposition は手順前後を意味する言葉で、「置換表」という訳は誤訳っぽいが定着している（参考：[置換表は何故置換表と言うのか？](http://yaneuraou.yaneu.com/2015/12/14/%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%81%AF%E4%BD%95%E6%95%85%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%81%A8%E8%A8%80%E3%81%86%E3%81%AE%E3%81%8B%EF%BC%9F/)）

## 感想

思ったより普通に指せててすごい。破綻するか大悪手指すかになると思ってた。

「従来のDL系将棋ソフトは局面を画像として扱って ResNet 等に入れるもの（画像処理の枠組みで解くもの）が多い」という話があったけど、これは Visual Transformer っぽいね。

DL系将棋ソフトは今まさに盛り上がっているところなので、新しいアイデアが出てきて楽しい。

AlphaZero と同じ枠組みなので、強化学習もできる。この手法で強化学習しまくってどこまで強くできるか誰か調べてほしい。

詰将棋は弱いらしいので、df-pn 等の詰将棋ルーチンを積んだバージョンで floodgate に放流してほしい。

動画企画のために 2 日でこれ作るの強い。

2 日でこれが作れるすごい世の中。