ガイスターの完全情報版endgame tablebaseを構築するコード、それを使うGATクライアント対応ソフト、およびtablebaseそれ自体を公開しました。
tablebaseはDistance To Win (DTW)でして、seekable zstd (8KiBチャンク、圧縮レベル22)で圧縮済みです。
canonical rank/unrank関数の設計について
ガイスターは左右対称なので、対称な盤面を同一視するcanonicalizeの余地があります。このコードで行っているcanonicalizeの方法について説明します。
（余談ですが、このcanonicalizeについてはChatGPT5.2Pro（当時）が思いつけなくて、わたしが自分で思いついてチャッピーに説明した思い出があります）
まず前提として、ガイスターの駒の種類は、完全情報なら4種類（自分赤、自分青、相手赤、相手青）、observation基準なら3種類（自分赤、自分青、相手）です。どちらにせよ、基本方針としては「盤面を左右に分けて、左右のpopcountが違っていればそれを基準にcanonicalizeする。左右のpopulationが全種類同じ場合に限りtie-breakingを別途考慮する」というものです。具体的には以下のとおりです：
(1)駒の種類になんでもいいから優先順位を与える。例えば「自分赤、自分青、相手赤、相手青」の順で優先順位が高い、とする。
(2)優先順位の高い駒種から順に、「盤面の左側の駒数＜盤面の右側の駒数」であればcanonicalではない、と定義する。具体的な処理手順を例示すると、
(a)自分赤に着目する。
(b)いま着目している駒の個数について、「左側＞右側」ならば現状をcanonicalとみなして左右反転せずにreturn。
(c)「左側＜右側」ならば左右反転してreturn。
(d)「左側＝右側」ならばtie-breakingが必要なので、優先順位が1個下の駒種に着目して(b)に戻る。（いま着目している駒種が優先順位最低なら下記(e)に進む）
ということにします。駒配置をbitboardで持っていれば駒数はビットマスク→std::popcountで求まるので、全部求めて表引きでいいですし、上記(a)～(d)をそのままfor文で書き下しても高速でしょう。
残る課題は、すべての駒種について「左側＝右側」だった場合の扱いです。この場合は駒種ではなく駒配置を整数に変換して比較する必要があります。といっても、駒配置をbitboardで持っていればpextで抽出するだけで一撃です。具体的な処理手順を例示すると、
(e)自分赤に着目する。
(f)いま着目している駒の個数について、「左側をpextした値＞右側を左右反転してpextした値」ならば現状をcanonicalとみなして左右反転せずにreturn。
(g)「左側をpextした値＜右側を左右反転してpextした値」ならば左右反転してreturn。
(h)「左側をpextした値＝右側を左右反転してpextした値」ならばtie-breakingが必要なので、優先順位が1個下の駒種に着目して(f)に戻る。いま着目している駒種が優先順位最低なら「完全に左右対称な局面」であることが確定するので、現状をcanonicalとみなして左右反転せずにreturn。
これでいいです。（補足ですが、canonicalizeだけ考えるなら64bit整数での比較さえできればいいのでpextする必要なくて、ビットマスクでいいです。しかし後段のrank/unrankのときにcombinadicで順序付ける必要があり、そこでpextを使うことになります）
rank/unrank関数については、「canonicalize後の盤面について、盤面の左右それぞれに存在する各駒種の数がかくかくしかじかであるときの駒配置の場合の数」はコンパイル時に高速に求まります。これの累積度数表を持っておけば、canonicalな盤面に対するrank/unrankは「累積度数表の値＋combinadicの値」で求まります。
"obsblk"について
完全情報tablebaseなら4種類の駒種が見えているので、エントリの順序付けの方針として最も素直なのは、4種類の駒種について上記の通りにcanonical rank/unrankを行うというものでしょう。一方ところで、対戦時の完全情報tablebaseの使い道としては、observationだけが与えられたもとで相手の可能な駒配置すべてについて「その駒配置を仮定したときの完全情報tablebase」を全部probeすることがほとんどでしょう。ゆえにメモリアクセスの局所性を高める観点からは、observation基準での各エントリに「相手の可能な駒配置のパターン数ぶんのバイト数」を確保しておき、その中の各バイト領域に完全情報 DTW tablebaseの値を入れておくという方針のほうが有利のはずです。この方針では完全な左右対称局面の扱いに関してほんのちょっとだけ冗長になりますが、高速性のベネフィットが上回ると思っています。この順序付け方針をobservation block (obsblk)と呼んでいます。
"repack"について
このコードベースの開発においては、tablebaseの構築をメインメモリ128GBのPCで行えることを必須要件としていました。盤上8駒以下のすべての駒割に関しては構築時のメモリ要求量が128GBにギリギリ収まることがわかったので、そこまではいいです。今回はそれに加えて、盤上赤2駒（すなわち自分も相手も赤1駒）の全局面についてtablebaseを作りたいと考えました。これは最大で盤上10駒になり、そのままだとメモリ128GBに収まりません。なので、「自分赤の位置18パターン（左右対称考慮）」*「相手赤の位置35パターン」=630パターンに局面集合を分割して、あるパターンを後退解析する際に参照する可能性のある少数のパターンだけをメモリに乗せておき、残りはストレージに退避させる方針を採用しました。これをやると、局面の順序付けがobsblkでない独特なものになるため、構築完了してからobsblkの順序に並べ替える処理が必要です。この並べ替え処理を"repack"と呼んでいて、"geister_perfect_information_tb_9_10_repack_obsblk"バイナリで行います。
