Chess-Ant 論文

author:

Akihiro Kuroiwa

date:

2021/12/25

abstract:

DeepMind が開発した AlphaFold のように、 MCTS は bioinformatics や cheminformatics へ応用できる。Chess-Ant では AlphaZero に影響を受けつつも、それとは異なる方法を試す。MCTS Solver と Genetic Programming の組み合わせが実用に耐えうるか、その可能性を示すのが目標だ。

AlphaZeroからの影響

AlphaGo ZeroやAlphaZeroで導入されたPolynomial Upper Confidence Tree (PUCT)の変種は事前確率 \(P(s,a)\) で定数 \(C(s)\) を補完している。Chess-Antでは従来のConventional Upper Confidence Tree (UCT)を用い、定数 \(C(s)\) の調整をGenetic Programming (GP)に置き換える [1]。\(1/\sqrt{1}\) から \(1/\sqrt{9}\) までGPは状況に応じて定数 \(C\) の値を選ぶ。定数 \(C\) の値により、 chess_ant.py は積極的に調べたり、消極的な調べ方をする。

AlphaZero's PUCT [2] [3] [4] [5]:

\[ \begin{align}\begin{aligned}a_{t} = arg\, max_{a}(Q(s_{t}, a) + U(s_{t}, a))\\U(s,a)=C(s)P(s,a)\frac{\sqrt{N(s)}}{{1+N(s,a)}}\\C(s)=log\frac{1+N(s)+c_{base}}{c_{base}}+c_{init}\end{aligned}\end{align} \]

Deep neural network \((p, v) = f_{\theta}(s)\) はパラメータ \(\theta\) により末端のノード \(s_{L}\) を評価する：

\[(p, v) = f_{\theta}(s_{L})\]

初期化：

\[ \begin{align}\begin{aligned}N(s_{L} , a) = 0\\W(s_{L} , a) = 0\\Q(s_{L} , a) = 0\\P(s_{L} , a) = p_{a}\end{aligned}\end{align} \]

更新：

\[ \begin{align}\begin{aligned}t \leq L\\N(s_{t} , a_{t}) = N(s_{t} , a_{t}) + 1\\W (s_{t} , a_{t}) = W(s_{t} , a_{t}) + v\\Q(s_{t} , a_{t}) = \frac{W(s_{t} , a_{t})}{N(s_{t} , a_{t})}\end{aligned}\end{align} \]

詳細

(s,a)

それぞれのstate-actionのペア

N(s)

親（ノード）の訪問数

N(s,a)

訪問数

W(s,a)

action-valueの合計

Q(s,a)

action-valueの平均

P(s,a)

s での a を選択する事前確率

C(s)

Exploration（とExploitation）の割合

p

（Deep neural networkにより予測された）手を選ぶ確率のベクトル

v

（Deep neural networkにより予測された）スカラー値

Chess-Ant's UCT [6] [7] [8] [9] [10]:

\[ \begin{align}\begin{aligned}a_{t} = arg\, max_{a}(Q(s_{t}, a) + C_{gp}\sqrt\frac{2lnN(s_{t})}{N(s_{t},a)})\\\begin{split}C_{gp} = \begin{cases} 1/\sqrt{1}, \\ 1/\sqrt{2}, \\ 1/\sqrt{3}, \\ 1/\sqrt{4}, \\ 1/\sqrt{5}, & \mbox{If the previously selected node state is under certain conditions} \\ 1/\sqrt{6}, \\ 1/\sqrt{7}, \\ 1/\sqrt{8}, \\ 1/\sqrt{9}, \end{cases}\end{split}\end{aligned}\end{align} \]

判断する条件は以下の通り：

条件

詳細

if_improvement

前回よりもUCTが増加したら

if_shortcut

move_stackが前回よりも短くなったら

if_result

前回のrolloutが勝ちか負けか引き分けか

if_pruning

UCTが無限大か無限小か、何れでもないか

if_is_check

前回選ばれたnodeでcheckだったか

また、GPは各generationにおいて、やり直すことができるので、訪問回数による検索初期のUCTの高評価を防げる。この論文のような効果を得られるかも知れない [11]。

MCTS Solver

MCTS Solver [12] [13] の導入により、高速化と誤答を減らす為の枝切りを行う。

論文の擬似コードを大幅に変更している理由は、継承クラスが参照する パッケージ のコードの書き方が異なるからだ。

さらに、Pythonでは goto が無いので、余計なコードがある。擬似コードではMCTS Solver内部で全て完結するが、 chess_ant.py では _executeRound() に分けて書いてある。 mctsSolver() 内でrolloutを実行し、枝切りなどの処理をし、rolloutと同様にrewardを出力し、 backpropogate() に入力する。

Negamaxと同様にMCTS solverも再帰関数であり、停止条件が必要だ。

並列処理

mcts-solver 0.0.5 から、OpenAIのChatGPTとGoogle Bardの助けを得てコードを変更し、並列処理 [14] [15] を行えるようにした。Tree並列化はroot並列化に比べて、locksを用いなければならないので作業が難しい。これらの変更が正しく動作しているか確証が持てないので、今後大幅に変更するかも知れない。Context managers は便利だけれども、使用法を誤ると大変なことになる。

変更履歴

chess-classification と chem-classification は同じアルゴリズムを用いているので、同時期に同じ変更を施している。

chess-classification 0.0.4 で fen を token に区切ってデータセットを作成するようにした。その fen は1文字ずつではなく、一列ごとに区切ってある。

chess-ant 0.0.5 までUCB1の数式に誤りがあったので math.sqrt(2) を追加し、訂正した。mcts の作者が、 mcts.py 内で explorationConstant = 1 / math.sqrt(2) を初期値としたのは、 math.sqrt(2) を打ち消すためと思われる。新たに selectNodeEphemeralConstant という terminal を chess-ant 0.0.6 で追加し、 ephemeral constant の代替とした。

Issues #658 によると、Deap は Python 3.10 で動作せず、version 3.11 で動作する。

~/.bashrc 或いは ~/.bash_aliases で：

# Python version
alias python3='/usr/bin/python3.11'

続いて source を実行する：

source ~/.bash_aliases

別の方法として、 update-alternatives がある。

update-alternatives --install /usr/bin/python3 python3 /usr/bin/python3.10 2
update-alternatives --install /usr/bin/python3 python3 /usr/bin/python3.11 1
update-alternatives --config python3
python3 --version

最優先に設定した元のヴァージョンに戻すには：

update-alternatives --auto python3

2022年12月現在、gnome-terminal は Ubuntu 22.04.1 LTS の Python 3.11 では起動しないことを覚えておいて欲しい。

より一般的な方法は venv を用いる：

sudo apt install python3.11-venv
python3.11 -m venv ~/.venv3.11
source ~/.venv3.11/bin/activate
which pip3

終了するには：

deactivate

chess-classification 0.0.5 から、保存したモデルの読み込みが出来る。

学習時間を短縮するために、 [16] checkpoint が google/electra-small-discriminator [17] の electra modelに変更した。

私が用意した pgn ファイルは chess problems と言うよりも寧ろ tactics [18] [19] に近いので、データセットは tactics から作成する方が効率が良い。正解率を高めるためには、モデルの学習とモデルの評価にそれぞれ300行以上の pgn データが必要だ。

開発予定

課題

別のプロジェクトとしてFENの勝敗評価に Natural Language Processing (NLP) 用の deep learning [20] [21] を導入する。

genPgn.py はstockfishで自動対局をし、PGN filesを出力する。ちなみに、Version 0.0.1の genPgn.py はウォルラス演算子を含むので、Python>=3.8でしか動作しない。 importPgn.py はPGN filesからデータセットを作成する。 chess_classification.py はSimple Transformersによる学習済みモデルを生成する。この学習済みモデルを用いて、AlphaZeroのように chess_ant.py のrolloutの代用とする予定だ。

参照

参考文献