架空伝統ゲーム「机戦」の AI を強くするため、盤面を効率よく保持する

この記事は筆兵無傾 Advent Calendar 2022 とボードゲーム・パズルプログラミング Advent Calendar 2022 の 7 日目の記事です。日本時間だと遅刻ですが、私はいまアメリカ合衆国にいるので遅刻ではありません（ズルい）。

経緯

さて、両アドベントカレンダーの 3 日目の記事である ↓ で、 id:primenumber が以下のような記事を書いてくれました。

primenumber.hatenadiary.jp

これをもとに作業していただいた結果、「1〜2桁くらい速くなるとできることだいぶ増えそう」と言われました。

そすうぽよ — 2022/12/04 20:43 「@hsjoihs 1〜2桁くらい速くなるとできることだいぶ増えそうなんですが、どれくらい頑張れそうな予感とかありますか？」hsjoihs — 2022/12/04 20:50
「『今月の前半は卒業のために必要な作業が存在し、その作業よりもたのしい最適化作業を頑張りすぎると、卒業のための作業が崩壊する』という点を抜きにすればめちゃめちゃ頑張れます。ところで、卒業は大事なので、今月の前半は頑張りをほどほどにするよう自らを律する必要があります」そすうぽよ — 2022/12/04 20:51「🆗🆗」

現状の実装は「まあ速いとうれしいけど、速さだけを求めるのは本当に速さが必要になってからでいいよね」というモチベで 2 年前に TypeScript 実装から手で移植したもののはずで、そんなに効率的な実装にはなっていませんでした。

github.com

この issue にあるように、「（将棋の角や飛車、チェスのルークやビショップのように）長距離移動する駒の動きを別の駒が妨げているかどうかを知りたい。どのマスを見ればいいか」というのを計算する関数が少し遅く、しかもこれは非常に呼ばれる回数が多いため、全体の実行時間をかなり占めてしまっていたとのことでした。

提案に基づきここを改善したところ、次は

そすうぽよ — 2022/12/05 02:17「これで全体が1桁速くなるというわけではなくて、様々な最適化をがんばって2桁ぐらい速くしませんか？という話です。次のボトルネックは順にrotate board, malloc, freeですね」hsjoihs — 2022/12/05 02:19「おー、rotate_board（たしかにあまりにも多そう）の次は malloc と free がボトルネックになる感じですか。了解です」

これはどういうことかというと、数年前に TypeScript 実装を書いたとき、「片側から見たときの駒の動きを実装し終えた。もう片側も実装するとなると面倒なので、逆側から入力が来たら、盤面を回転させて関数を呼んで結果をもう一回回転させよう」という横着をしたのが原因で、AI が手を計算しているあいだ盤面が一生クルクルしており、そのクルクルで全体の 27.24 % の実行時間を消費してしまっていたのでした。

「それぐらい予見できただろ、なんで横着をしたんだ」と思われるかもしれませんが、この「机戦」というゲームは

駒を踏んでそこからさらに移動する動きがあり、踏む駒の位置とそこから移動する目的地を順に指定させねばならない
指し手を決める途中でサーバーに乱数を問い合わせ、それに基づき可能な手の候補を削り、クライアント側に返す必要がある
到着地点が水色マスである場合、乱数を発生させ、出目不足なら指し手をキャンセル

などと、遷移する必要のある状態数がかなり多く、それらを全てバグらせずに組むのがあまりに面倒だったので、最大限に横着をしたかったのです。

そうは言っても、遅いせいで AI の開発の妨げになっているならよろしくない。ということで、コードを調べ、いろいろいじり、rotate_board を削除しました。

問題

とはいえ、そもそも速く実行できるようにすることを意識していないコードなので、それをリファクタリングしていって速度を上げていくというのにも限界があります。現状の遅い実装はリファレンス実装とし、「メモリへの優しさを最優先した構造へと書き換える」をやらないといかんという結論に至りました。

そすうぽよ — 昨日 05:29 「こっちの環境ではmalloc, cfree, ...の順になってて再現できてないんですよね」 hsjoihs — 昨日 05:52 「WSL で走らせてるのが変な影響出てるのかなぁ　まあとりあえずいずれにせよ『メモリへの優しさを最優先した構造へと書き換える』をやらないといかんのは容易に想像が付きますね」そすうぽよ — 昨日 06:04 「9*9の盤面に駒を並べるデータ構造にするか、49駒それぞれの位置と状態を記憶するか」

49 駒それぞれの位置と状態を記憶すると、49 バイトで必ず収まるというメリットがある一方で、このゲームのゲームロジック上では「特定のマスが空きマスかどうか」を判定する機会が多く、それがいちいち面倒となるデータ構造ではよろしくないと考えました。

一方、このゲームには持ち駒の概念があります。よって、そちらについては「48 駒それぞれについて*1、どちらかの持ち駒になっているか、それともどちらの持ち駒でもないのか」を保持する、という方針にしました。

紆余曲折

諸事情*2により、空マスを表す番号は 0 にしたかったので、最初はこのような駒番号割り当てを考えていました。

この番号の振り方は、伝統的事情とコンピュータ的事情を融合させた割り当てになっています。というのも、id:yasusho1020 が手作業で机戦の駒を彫るときには以下のような工程を経るのですが、

まずはでんぷんのりで字母紙を貼り付け pic.twitter.com/PQmQHd9vnr
— SY@架空世界創作者 (@S_Y15) 2022年2月17日

3Dプリンター製の治具（左奥）と手ノコで8つずつに切ります。この８つを１単位にして隊（ニェ）と呼びます。 pic.twitter.com/cQ2CZc5wFu
— SY@架空世界創作者 (@S_Y15) 2022年2月18日

この字母紙が以下のような配列になっているので、それを踏襲して順序を決めました。

また、赤黒を交互にして縦列の順で読んでいくというエンコーディングにすることで、

最下位ビットで色
不等式評価で役職

が手に入り、コンピュータにやさしい（素早く計算できる）、という考えがありました。

しかしながら、id:primenumber から「兵が1スタートでなく0スタートにした方がbit演算とか表引きとかに便利そうかなあと思いました」という意見がもたらされ、「そうだよなぁ、どうしようかな」と思っていたところ、非常に上手いアイデアが寄せられ、

そすうぽよ — 昨日 22:33「兵が1スタートでなく0スタートにした方がbit演算とか表引きとかに便利そうかなあと思いました」hsjoihs — 昨日 22:39「これ迷って、Option<NonZeroU8> で書けるように 1 スタートにしたんですけど、やっぱ 0 スタートのほうがいいですかね」そすうぽよ — 昨日 22:42「64スタートにして上位2bitが0b00→どちらも動かせない（空きマス） 0b01→IASideが動かせる 0b10→ASideが動かせる 0b11→どちらも動かせる（皇）にするとかもありかも」hsjoihs — 昨日 22:42「あ〜〜上手そう持ち駒情報の格納のしかたとも整合するわな」