iPadのNeural Engineで将棋AI part09 Swiftで将棋エンジンを書く

前回記事から1.5か月空いてしまいましたが地道に対局エンジンのコア部分を開発していました。本記事までの実装をして、選手権の練習を1つの目的として開催された「電竜戦さくらリーグ2022」に参加し、B級で18チーム中7位(ソフト名ねね将棋)となりました。

Swift言語初心者なので実装手段に悩みつつ、盤面表現、合法手生成から始めてMCTSの実装まで進めました。ソースコードを公開しています。

github.com

実装順序

各ステップの成果が確認しやすいように、次のような順序で実装を進めました。

USI通信
- 盤面は理解せず、初手で76歩を返すだけ。
盤面表現・合法手生成
ランダムプレイヤー
- USI通信で受け取った局面に対して合法手を生成し、そのうちランダムなものを選択して出力する。これで対局が最低限成立する。
DNNの実行・入出力の生成
- 評価関数となるDNNを組み込み、盤面から入力となる特徴量および各合法手に対応する出力ラベルの生成を行う
方策関数だけで指すプレイヤー
- USI通信で受け取った局面をDNNに与えて、出力の方策が最大となる手を選択して出力する。意味のある指し手が出せるようになる。
MCTS実装
- 探索を行う
- 一定の回数探索したら終了する（経過時間で探索を打ち切る機能は後回し）
接続先を指定するUI
- Mac上のシミュレータで動かすときは、将棋所へのTCP接続先が127.0.0.1固定でよかったが、iPad実機で動かすにあたりMacのIPアドレスを手入力するUIを追加。
時間制御
- USIで与えられた残り時間をもとに、デフォルトでは10秒、残り時間が12秒以下の時は残り時間-2秒だけ思考するようにした（2秒は思考を打ち切ってから指し手をネットワークで送信し終えるための予備の時間）
- タイマー用のスレッドを作成
- 局面の複雑さに応じた制御は未実装
ponder機能
- 相手の手番中に思考するponder機能を実装する。思考をしながら相手の手が来るのを待機する必要がある。そのため、goコマンドを受け取る通信スレッドでそのまま思考するのではなく、別スレッドで思考する機構を実装。
バグ取り

実装方針

合法手生成は、2017年にC++とPython複合で自前実装したものを移植。
- テストケースもあったのでテストを実施。
- 簡単に書けることを重視しており、速度が遅いため詰み探索などを実装することが困難
- 経路依存（＝千日手）のテストケースはなかったのでテストできていない。
- 入玉宣言、千日手判定はバグ取りのフェーズで追加した。（数局面確認しただけでまともにテストできていない）
MCTSの実装は「強い将棋ソフトの創りかた」を参考にSwiftで実装しやすいようにデータの取り回し方等を変更。
探索とDNN評価は同じスレッドで実行。
- DNN評価のコストが80～90%程度を占めるため別スレッドにしても得られるメリットはわずか。
- 詰み探索を搭載しようと思うと分ける必要が生じてくる。
評価関数は、「強い将棋ソフトの創りかた」の学習コードでデフォルトで学習される10ブロック192チャンネルのものを当初利用していたが、本家で使われている15ブロック224チャンネルのものを自前で学習して利用。
- 探索部の速度があまりよくないので、できるだけ評価関数が重いほうが得と考えた。

Swiftテクニック

defer文で、スコープを抜けるときに局面を戻す

再帰的な探索で、一手進めた後関数の最後で元に戻すという処理が生じる。Swiftでは、defer { position.undoMove() } という記述で、関数などのスコープを抜けるときに特定の処理を実行できる。途中にreturnがあるような場合でも実行されるため便利。

思考と探索スレッドの分離

DispatchQueueにより、クロージャをそのキューに紐づいた特定のスレッドで実行できる。別のスレッドで特定の処理をさせるという記述が容易で、しかも同じDispatchQueueに対する処理は同時に走らないのでデータ構造を壊す恐れがない（同時に走るかどうかはDispatchQueueのオプション次第）。思考用、通信用でそれぞれDispatchQueueを持つことでスレッドの分離を実現。

具体的な実装はこのあたりに。

https://github.com/select766/NeneShogiSwift/blob/c64767b53ca3092297a7f30cbc35a00924753987/NeneShogiSwift/USIClient.swift#L175

ハマったところ

メモリを大量に食う

探索が終了するまで、途中で確保したメモリが解放されず1GB以上消費し、クラッシュするという問題が生じた。Swiftは参照カウント式のGCなので、参照が切れればその場で開放されるはずなのだが、解放されないメモリもある模様。 autoreleasepoolというメソッドを介して1回の探索を呼び出すようにすれば、そのメソッドが終了するときにメモリが解放されることが分かった。 https://github.com/select766/NeneShogiSwift/blob/c64767b53ca3092297a7f30cbc35a00924753987/NeneShogiSwift/MCTSPlayer.swift#L362 入門書にこのメソッドのことは書かれておらず、「CoreML memory leak」などで調べるうちに判明した。

UCB値の計算ミス

探索中に子ノードを選択する際に利用するUCB値の計算で、sqrt(moveCount)/(1+childMoveCount)とすべきところをsqrt(moveCount/(1+childMoveCount))と書いてしまった。バグっている状態でもそれなりに動作するのが厄介で、floodgateでレート2200程度だった。探索速度が低いしそんなものかと思って気にしていなかったのだが、dlshogiのブログで、dlshogiのモデル（サイズは不明）でたった4ノード読んだだけでレート2556と書かれていた。数千ノード探索しているのにそれより弱いというのはさすがに何か問題があると思い調べることにした。python-dlshogi2を改造し、

ねね将棋に組み込んだものと同じ評価関数を使う
探索ノード数を固定
詰み探索、過去の探索ノードの再利用機能を削除し、ねね将棋と同じ探索条件にする
ねね将棋側は、DNNの誤差が大きくなるNeural EngineではなくCPUで評価するモードに変更

ことにより、探索結果が同じになるかを検証した。探索結果が一致しない局面があったため、詳しく調べるため、UCB値の計算結果をデバッグプリントしてゲーム木をスキャンする手順を比較した。その結果、UCB値が若干ずれていることに気づき、冒頭のミスが発覚した。

この修正を施したところ、floodgateでレート3300のgikou2_1cに勝利することができた。

wdoor.c.u-tokyo.ac.jp

今後

以上の実装をしたところで、2022年4月2日の電竜戦さくらリーグ2022に臨みました。

今後は、CSAプロトコルを実装してiPad単独でサーバと通信できるようにすることが最優先です。同時に局面の表示なども必要となりますが、その実装にはSwiftでのグラフィックス描画の知識をつける必要があります。棋力的な向上をする余裕はありませんが、自前学習した15ブロック224チャンネルの評価関数が72エポックではまだ学習の余地が残っているようなので、学習を続けたものに差し替えることで少々改善するかもしれません。