ガイスターの紫駒版endgame tablebaseを公開しました

前回の記事では完全情報版tablebaseを公開したことをお知らせしましたが、今回はそれに紫駒版endgame tablebaseを構築するコードを追加しました。GATクライアント対応ソフトにもそれを使う機能を追加し、tablebaseそれ自体もHuggingFaceに追加しました。

GATクライアント対応ソフトについて

https://github.com/eukaryo/Unweaver-TwoColorEscapeBoardGameAI/blob/main/geister_stdio_baseline_player.cppgithub.com

このcppファイルがGATクライアント対応ソフトのエントリーポイントです。tablebaseをprobeする方法、必勝法を検出するアルゴリズム、クライアントとやりとりするプロトコル実装なんかを紹介するためだけのソフトという位置付けで作っています。大会に出たときより弱いです。現在の行動パターンは以下の通りです：

1. 即座に脱出勝利可能な場合は脱出勝利の手を指します。
2. proven_escape_move関数。自分の青駒のうちどれかを最速で脱出させれば必ず勝てる局面を、alpha-beta探索とかではなくDijkstra法のようなアルゴリズムで高速に判定します。false positiveはありません（この関数が指し手を返した場合は必ずその指し手で勝てます。200手引き分け以外は）false negativeは許容します。std::nulloptが返されたら次に進みます。
3. purple_winning_move関数。紫駒tablebaseをprobeして、現在局面が紫駒必勝だった場合は2手読みして、最短で勝てるとされる指し手を求めて返します。2手読みする理由は、「紫駒側のtablebase」を見ないからです。（構築はしますが、probeはしません）std::nulloptが返されたら次に進みます。
4. confident_player関数。1手読みした先の局面について完全情報tablebaseをprobeして、相手駒の色配置のうち1つ以上の色配置パターンで必勝であるような指し手が存在する場合、必勝であるような色配置パターンの数が最大の指し手を返します。同率タイの手が複数ある場合は全て返します。指し手が返されたら、その中からランダムに1手選びます。std::nulloptが返されたら次に進みます。
5. random_player関数。全合法手のなかから完全ランダムに指し手を選びます。

module:private; について

このGitHub repoのコードではC++20のmoduleという機能を多用しています。C++20 moduleは昔からあるヘッダとソースファイルに分離する慣習の代替を目指す仕組みです。わたしがC++20のmoduleを試している理由は、module:private;という言語機能があるからです。module:private;を書くと、そこからファイル末尾までの全てがprivate module fragmentになります。private module fragmentはそのモジュールをimportする他の翻訳単位からは全く見えず、到達不能になることが言語仕様により完全に保証されます。加えて、private module fragmentを含むモジュールユニットはそのモジュール唯一のモジュールユニットでなければならないので、このケースでは同じnamed moduleに属する別のmodule unitやpartitionがどこか別ファイルに存在する可能性も排除されます。
これってすごくて、今回わたしはLLMによるvibe codingで可能な限りやっていくことにしているんですが、LLM目線で「ファイル先頭から順番に読み進めていったとき、module:private;が出たらその後ろを読まなくても、少なくともimporterから到達可能なインターフェースは100%把握できる」ことが確定します。これは他の言語機能では代替できません。例えば無名名前空間では対応するカッコ閉じまでしか保証されませんから、"namespace {" のカッコ開きに対応する閉じカッコがどこにあるのか確認する手間が少なくとも生じるでしょう。言語仕様によってLLMのコンテキストが無駄に食い潰されないことでLLMのポテンシャルを引き出せるかもしれないと思い採用しています。（注：真偽不明な個人の感想です）
C++20 moduleの現状最大の欠点はVS Codeの支援機能が不安定なところです。そのために一時期採用を躊躇していたんですが、重要な事実を見落としていました。コードエディタの支援機能が役に立つのは、自分の指でコードを書くか、自分の目でコードを読むときだけです。わかりますね？

ガイスターの完全情報版endgame tablebaseを公開しました

ガイスターの完全情報版endgame tablebaseを構築するコード、それを使うGATクライアント対応ソフト、およびtablebaseそれ自体を公開しました。

github.com

tablebaseはDistance To Win (DTW)でして、seekable zstd (8KiBチャンク、圧縮レベル22)で圧縮済みです。

huggingface.co

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"バイナリで行います。

ガイスターのendgame tablebaseについて

GAT2026のガイスターAI部門に参加してきました。
第11回GAT2026 - GAT@UEC
動機は、
不完全情報ゲーム「ガイスター」のエンドゲームの研究
この論文が面白かった一方でツッコミどころがあると思ったからです。

（わたしはGPW-25に参加していないので、現地で質疑とかでツッコまれていたかどうかはわかりませんが）私が気付いたツッコミどころを挙げると大きなものは4点あります。具体的には下記の通りです。
（注：以下ツッコミどころばかりいっぱい書きますが、わたしはこの論文はすごくinspiringだと思っていますし皮肉抜きで大好きです。だからこそ読み込んで以下の点に気付けたのです）：

(1)図6の 4000TB は lower bound ではなく、ある保存方式での容量見積もり

　論文では（引用）「最も多い残り駒数16までのデータベースすべてをディスクに保持すると約4000TBのディスク容量が必要であることが確認された」とありますが、『必要である』は誤りで、正しくは『あれば十分である』でしょう。(1)uniqueなobservationが 4000 trillion 通りあることと、(2)4000 trillion entries保持する必要があることと、(3)その保持に4000TB必要であることは一致しません。特に(2)→(3)のギャップが（1 Byte/entryを暗黙に仮定したもとでもなお）存在することの具体例として、バイト列を可逆圧縮しつつバイト単位でランダムアクセスする方法が、私がパッと思いつく限りでも大まかに4通りあります。

(a)チャンクで圧縮する方式

　ゲーム情報学界隈でおそらく最も有名な実例として、チェスの盤上7駒以下全局面に関するSyzygy tablebaseはチャンクごとに圧縮してあります。そのうえでエントリへのアクセスクエリに対してはそのエントリを含むチャンクだけを途中まで展開して、クエリ対象のエントリが展開できたらそれを即座に返して展開自体を中断する、みたいな仕組みになっています。またzstdという圧縮コーデックにはseekable formatが定義されています。これも「チャンクごとに圧縮しておいて、ランダムな1バイトを読み出すクエリに対してそのエントリを含むチャンクだけを展開する」をサポートするものです。（seekable zstdを扱う実際のコーディングや依存ライブラリの準備などのビルド手順など諸々が気になる人は、ChatGPT5.2Pro（執筆時点）とかに聞けば全部やってくれます、たぶん）
　以下余談ですが、seekable zstdに「途中まで展開して必要な部分を取り出したら中断する」機能があるかはわかりません。多分無いと思っていますが、だとしてもチャッピープロやクロードオーパスとかに相談すれば依存ライブラリの改造をできるかもしれません。Syzygyは一点物の工芸品みたいなものなので、そもそもこれをコーデックの拡張機能として実用普及レベルに持っていく仕事には価値があるかもしれません。

(b)ファイルシステムの透過的圧縮機能

　これは(a)を勝手にやってくれるというのに近いのですが、WindowsのNTFSやLinuxとかで使えるZFSを含む一部のファイルシステムには「透過的圧縮」というオプションがあります。Windows11の場合、フォルダを右クリックしてプロパティ→詳細設定→チェックボックス「内容を圧縮してディスク領域を節約する」をオンにすると、（圧縮が刺さるようなファイルが入ってるフォルダなら）プロパティ直下の「サイズ」と「ディスク上のサイズ」が大きく乖離する（ディスク上のサイズが1/3とかに縮むこともある）はずです。にもかかわらず、ユーザーはファイルを開いたりコピー・移動などの操作を普段通りに行えるのです。ZFSの場合は圧縮が刺さればdfコマンドとduコマンドの値が乖離します。ZFSのpoolの設定方法など諸々が気になる人は、チャッピー（中略）などの激強LLMに相談しましょう。
　余談ですが、個人的な感想としてはWindows/NTFSの透過的圧縮はCPUをドカ食いする割にレスポンスが割と体感できるレベルで遅くなるのであまりおすすめしません。Cドライブがカツカツなときはすごく助かることもありますが。

(c)簡潔データ構造

　Succinct Data Structure Library(SDSL)という堅いライブラリがあります。
github.com
https://simongog.github.io/assets/data/sdsl-cheatsheet.pdf
　このなかのwt_huffという機能は、雑に言えばバイト列をハフマン木の形のウェーブレット木で表現するものです。これはハフマン符号化に近い圧縮率を期待できる一方で、ウェーブレット木なので当然バイト単位のランダム読み出しが可能です。更に、wt_huffはバックエンドにbitvectorを必要としていて指定可能なのですが、これにRRRとかsd_vectorみたいな「ある特徴を持つビット列を効果的に可逆圧縮したままaccess/rank/selectクエリできる簡潔データ構造」を指定することで、場合によっては更に圧縮できます。

(d)バイト単位で高速にランダムアクセスできる圧縮コーデック

　LZ-End parsingが古典的に有名です。最近ではHeight-Bounded Lempel-Ziv(LZHB)
arxiv.org
　なんかもあります。ただ、これは著者実装が圧縮時にバイト列全体のSuffix Tree(またはArray)を作るようになっていて2^32Bを超える100GB級のバイト列とかが想定されてなかったり、LZのフレーズ列へのエントロピー符号化が実装されていなかったり、そもそもランダムアクセス機能が生えていなかったりしていて、終わってる、というかまだ始まっていない感じになっています（著者実装はprototypeと但し書きされている点も含め）。
　以下余談ですが、だいたい、たとえばLZ77→LZSS→Deflate→ZIPはそれぞれ別の概念で、人々は圧縮コーデックを必要としているのに研究者はLZ77をこねくり回してるみたいな図式がずっと続いてるように見えます。生物学と医学の間でもbench to bedsideといった概念があって、translational research（橋渡し研究）が長らく重要視されていますが、そういう図式はどこにでもあるのでした。

話を戻します。

(2)Algorithm2は、観測盤面に対して hidden completion を量化したときの「必敗」概念を閉じた形で伝播できていないように見える（ことが図10で示されているのかもしれない）

　論文のAlgorithm2では、筆者らの定義した必敗ラベルを正しく振ることが必ずしもできません。そのことは筆者らもlimitationとして認識していて、図10で説明されています。とはいえAlgorithm1は必勝と負有を正しく振ることができます（たぶん）。で、必勝を正しく振ることさえできていれば、それを使って必敗を正しく振ることは後退解析を1 iterationだけ回せば可能です。（3/12追記：考え直したらそうとは限らない気がしてきました）

(3)効率的なcanonical rank/unrank関数は作れる

　駒割（すなわち、盤上に残っている自分と相手の青駒・赤駒の数）が与えられた下で、uniqueな局面数は初歩的な組合せ論で求められます。それがN通りだとします。tablebaseを作るためには、局面と整数[0,N)の間を相互変換する全単射の関数が必要です。局面→整数はrank関数、逆はunrank関数と呼びます。筆者らはZDDを使ってこれを作ったと書いていますが、もっとシンプルに、KnuthがThe Art of Computer Programming 4.Aなどで整理している階乗進法（Factorial Number System / factoradic）とか組み合わせ進法（combinatorial number system / combinadic）とか呼ばれるテクニックを使って高速かつ小さいメモリフットプリントで定義できます。左右対称な局面を同一視するcanonical rank/unrank関数も頑張れば定義できます。
　（すなわち、左右対称な局面を同一視したときのuniqueな局面数をMとします。局面pとqが同一または左右対称である ⇔ canonicalize(p)=canonicalize(q)であるような「canonicalize関数」が準備されているとします。N>Mのとき、局面→[0,M)の全射だけど単射でない関数fと、その逆をやる単射だけど全射でない関数gとをcanonical rank/unrankと呼んでいます。もちろん任意の局面pに対してf(p)=f(canonicalize(p))ですし、かつcanonicalize(p)=canonicalize(g(f(p)))です）具体的な設計については別の記事かなにかで今後書くかもしれません。

The Art of Computer Programming Volume 4A Combinatorial Algorithms Part1 日本語版 (アスキードワンゴ)

(4)ゲーム的に重要な駒割はパターン数が少ないがちかも

　論文では「盤上i駒以下の全局面のtablebaseを扱うのに必要な計算機リソースの見積もり」をすべてのiに対して考察するとともに、盤上7駒以下の全局面のtablebaseを作っていました。逆に言えば盤上8駒の全局面のtablebaseは研究のスコープ外でした。しかし、仮に盤上8駒の全局面のtablebaseは無理と判断してたとしても、例えば自分が赤駒献上を積極的にやるドクトリンならば、「片方のプレイヤーが赤1の場合に限る盤上8駒tablebase」だけは作れるかもしれません。そういう限定的なtablebaseが実際に有効なのか（言い換えると、そういうカバー範囲が歪なtablebaseと組み合わせて強いようなドクトリンが存在するのか）は仮説としてはplausibleな気がしますが非自明なのでやってみる価値がありそうだと思いました。

AVX512のbitshuffleのオセロAIへの応用

The most underutilized #AVX512 instruction, VPSHUFBITQMB, is actually very useful for generating masks from arbitrary b[5:0]-based criteria — e.g., selecting special characters for parsing — using a broadcasted 64-bit 2nd operand where the ones represent the searched values https://t.co/YD8cewi7DJ pic.twitter.com/5iikDGLzmA

— InstLatX64 (@InstLatX64) 2025年6月10日

このツイートで紹介されている命令は、挙動をC++で書き下すと以下のようになります。

uint64_t _mm512_bitshuffle_epi64_mask(
    const std::array<uint64_t, 8> &b,
    const std::array<uint8_t, 64> &c)
{
    uint64_t dst = 0;
    for(int i = 0; i < 8; ++i) {
        for(int j = 0; j < 8; ++j) {
            const uint8_t m = c[i * 8 + j] % 64;
            if (b[i] & (1ULL << m)) {
                dst += 1ULL << (i * 8 + j);
            }
        }
    }
    return dst;
}

第二引数cを8bit整数64個の配列と見なします。第一引数bを64bit整数8個の配列と見なします。返り値は64bit整数で、長さ64のビットベクトルと見なします。bの中の64bit整数たちから1bitずつ抜き出して、返り値に順番に詰めていくのを、bの64bit整数1個あたり8回ずつ行います。抜き出すビット位置は完全に自由に指定できまして、具体的にはcの8bit整数たちの下位6bitで指定します。

上記ツイートで紹介されている文字列解析関連の利用法とは異なるかもですが、_mm512_set1_epi64を使って64bit整数xを第一引数の8要素すべてに入れれば、あらかじめ用意した第二引数によって64bit整数xを自由な順番に入れ替えられます。しかも厳密なシャッフルが可能なだけでなく、入力箇所1つを複数の出力箇所にコピーできますし、ビットマスクあり版の命令(_mm512_mask_bitshuffle_epi64_mask)を使えば任意の出力箇所をゼロにすることもできます。

Zen5(9950X)ではLatencyは可変でThroughputは0.5(クロック/命令)のようです。Intel Intrinsics GuideによるとSapphire RapidsではL6T1だそうです。

ユースケース

64bit整数型のビットの順番を予め決められたグチャグチャな順番にシャッフルしたい、しかも重複やゼロ埋めが自由にできることで嬉しいユースケースってなんでしょうか？　様々な分野の細々とした箇所で嬉しさがあるとは思いますが、オセロソフトに関してぱっと思いつく可能性を以下に書いてみました。

bitboardの反転・行列転置

ビット演算を色々組み合わせて頑張ってたやつが一撃でできます。
2048みたいに盤面が4*4で16bitの場合は4パターンの変換を一撃でできますし、タイルの種類を4bitで書き込んである64bit表現の場合も一撃でできます。

Logistello型評価関数のパラメータを読むための添字を求めるやつ

オセロソフトにおいて現在でもよく使われている所謂Logistello型評価関数では、盤面中の特定の局所領域、例えば「四隅の3*3マス」の全パターン（この場合は3^9通り）の有利不利について機械学習でスコアリングして評価関数を作っています。局面評価の際には3^9要素のパラメータ配列に添字アクセスを4回やります（四隅は4箇所あるので）。別の例でいうと「四隅の2*5マス」の全パターンならば3^10通りのパラメータ配列があり、添字アクセスを8回やります（ひとつの隅ごとに縦と横の2*5マスを個別に評価するので合計8回）。

ここで面倒ポイントがありまして、4箇所の四隅は「bitboardにおけるビット位置の順序」と「パラメータ配列の添字を三進法で表すときの桁の順序」がグチャグチャに食い違うので、単にpextで3*3マスを取ってくるみたいな簡単な話には落ちないのです。

このポイントへの対処として、Edaxでは探索中の盤面更新のたびに添字リストを差分更新していたはずですが、上記のbitshuffleがあればこれを完全に不要にできる可能性があります。
（うろ覚えですみませんが、この差分更新はそんなに軽い処理ではなかったはずで、でも関連する処理がコード中に分散していたかなんかで、パフォーマンスプロファイリングしても「添字リストを差分更新するというコンセプトに起因する処理全体」が計算時間のどれくらいを占めているのか、昔調べようとしたけどよくわかんなかった覚えがあります）
端の2*5とか斜めの8マスとか、複数の評価項目に関して同時に並べ替えるためには重複が許されるとすごく便利です。

ただし、添字は三進数である一方で本手法では白石の有無と黒石の有無がバラバラに（いわば"四進数"で）得られるだけなので、これを三進数に変換しないと既存の添字アクセスに繋ぎ込めません。

添字を三進数で持っておくのが本当に最速なのかちょっと疑う余地があるかもしれません。というのも、パラメータ配列を"四進数"の添字で持っておく場合は絶対にアクセスされない無駄な領域がもちろん生まれますが、その領域は割と固まって存在しています（例えば四進数表現で下から5桁目が3であるような領域は256ワード連続します）。そのためキャッシュヒット率がそれほど低下しない可能性はあるかもしれません。

水ダウの電気イスゲームのナッシュ均衡戦略

note.com
この記事が面白かったのと、実際にテレビ番組を見てみたらそれも面白かったのでちょっと考察と解析コードの実装をしてみました。以下に書き残しておきます。

背景

水曜日のダウンタウンというテレビ番組で「電気イスゲーム」というゲームが行われていました。ルールは以下の通りです。

• ゲーム開始時点では12脚の椅子が場に存在していて、1～12の数字が振られている。
• プレイヤーは2人。回ごとに攻撃側と守備側に分かれて、交互に交代して進行する。（野球みたいな感じ）
• 1つの回の進行：
  • 守備側は場に存在する椅子のうち一つを指定して、"電流"を仕掛ける。
  • 攻撃側は場に存在する椅子のうち一つに座る。
    • "電流"が仕掛けられていなければ、攻撃側は椅子を獲得し、椅子に書かれている数字の得点を得る。獲得された椅子は場から撤去される。
    • "電流"が仕掛けられていれば、攻撃側は電流を食らい、現時点で持っている得点をすべて失う。椅子は場に残る。
  • "電流"を解除して回を終了する。
• ゲームの終了条件：
  • 40点以上を持っているプレイヤーはその時点で勝利する。
  • "電流"が仕掛けられた椅子に累計3回座ったプレイヤーはその時点で敗北する。
  • 場に存在する椅子が残り1脚になった時点でゲーム終了とし、その時点でより多くの得点を持つプレイヤーが勝利する。

テレビで実際に行われた企画は芸人8人によるトーナメント形式になっていて、優勝者には今まで獲得した点数*1万円が与えられます。「それなら結託して賞金山分けすればいいのでは？」といった（ライアーゲーム事務局VS参加者みたいなノリの）アイデアも浮かんできますが、そのへんを考え出すと話が複雑になるのでさておき、勝敗のみに着目したゼロサムゲームとして考察します。

また、テレビで行われた実際のゲームプレイを見ると、当然ですが芸人たちの表情の読み合いが生まれており、それが面白いです。でも本考察ではそのへんもさておきます。

ゲームの大きさと解き方の概略

回が始まった直後の時点を「局面」と呼ぶことにします。すべての局面は、（攻撃側の持ち点、守備側の持ち点、攻撃側が電流を食らった回数、守備側が電流を食らった回数、撤去された椅子の集合）という5つの値によって一意に定まります。5つの値のうち後者3つは単調増加であり、また後者3つの値が完全に同じ局面たちの中で前者2つの値は単調増加なので、千日手のような「局面のループ」は発生しません。ゆえに、過去の履歴は局面に影響しません。

uniqueな局面数の自明な上界は40*40*3*3*2^12=58,982,400と小さめです。

2人のプレイヤーは一つ一つの回ごとにゼロサムの同時ゲームを行い、結果の情報を全て公開してから次の回に進みます。ゆえに、初期局面から到達可能なすべての局面について、その局面で行われる同時ゲームのナッシュ均衡戦略を求めることができれば、ゲーム全体を解決したことになります。

同時ゲームについては選択肢が最大12通りと十分に小さいので、線形計画法でナッシュ均衡戦略を求めることができます。「攻撃側が椅子iを選び守備側が椅子jを選んだ場合における、その直後の局面の状態価値」を(i,j)成分とする行列を作れれば、線形計画法ソルバーに投げるだけです。

すべての局面を辿る方法としては、2人がどう選んでもその直後に終局となる局面からDAGトポ順に遡っていく必要があります。動的計画法でもいいですし、メモ化再帰の要領で「『局面(=上記5つの値)を引数に取って状態価値を返す関数f』を用意して、上記の行列を作るときに再帰的にfを呼び出す」でもいいです。

実装

ChatGPTとかに聞きながらPython+メモ化再帰で書いてみました。ゲームが小さそうだったのでメモ化にはfunctoolsのlru_cacheを使っています。椅子の集合についてはメモリを節約するためビットベクトルで表現しています。
水曜日のダウンタウンの電気イスゲームのナッシュ均衡 · GitHub

結果

上記コードを実行すると以下のように出力されるはずです。

1回表について
攻撃側は、
椅子8に 23.20％、
椅子9に 21.38％、
椅子10に 19.87％、
椅子11に 18.41％、
椅子12に 17.14％
の確率で座るとナッシュ均衡になります。
守備側は、
椅子12に 31.45％、
椅子11に 26.35％、
椅子10に 20.53％、
椅子9に 14.48％、
椅子8に 7.19％
の確率で電流を仕掛けるとナッシュ均衡になります。
攻撃側視点の価値: 0.0656477523176959
――――――――――――――――――――
1回表で8の椅子を取れた場合、直後の1回裏について
攻撃側は、
椅子9に 28.31％、
椅子10に 25.98％、
椅子11に 23.83％、
椅子12に 21.88％
の確率で座るとナッシュ均衡になります。
守備側は、
椅子12に 34.35％、
椅子11に 28.50％、
椅子10に 22.07％、
椅子9に 15.08％
の確率で電流を仕掛けるとナッシュ均衡になります。
攻撃側視点の価値: -0.14042066741357417
――――――――――――――――――――
1回表で7の椅子を取れた場合、直後の1回裏について
攻撃側は、
椅子8に 23.46％、
椅子9に 21.57％、
椅子10に 19.88％、
椅子11に 18.25％、
椅子12に 16.83％
の確率で座るとナッシュ均衡になります。
守備側は、
椅子12に 32.67％、
椅子11に 27.02％、
椅子10に 20.47％、
椅子9に 13.70％、
椅子8に 6.14％
の確率で電流を仕掛けるとナッシュ均衡になります。
攻撃側視点の価値: -0.10023001151346164
――――――――――――――――――――
1回表で電流を食らった場合、直後の1回裏について
攻撃側は、
椅子7に 19.41％、
椅子8に 18.22％、
椅子9に 17.09％、
椅子10に 16.07％、
椅子11に 14.99％、
椅子12に 14.21％
の確率で座るとナッシュ均衡になります。
守備側は、
椅子12に 28.93％、
椅子11に 25.05％、
椅子10に 19.64％、
椅子9に 14.55％、
椅子8に 8.90％、
椅子7に 2.93％
の確率で電流を仕掛けるとナッシュ均衡になります。
攻撃側視点の価値: 0.41672270939727646

考察

まずそもそもの話として以下のような考察ができます。

• 攻撃側は椅子を獲得できれば勝率が高まる。
  • 獲得した点数が高いほど、それを獲得した直後の勝率もより高くなる。
• 攻撃側は電流を食らうと勝率が下がる。
  • 電流を食らうならば、そのときに座っていた椅子の番号がどれであっても、その直後の勝率は同じ値となる。
• 守備側は混合戦略を取りうる：すなわち、実際には守備側が電流を仕掛けているかどうかは確率的である。
  • 攻撃側が椅子X(Xは椅子に書かれている数字)に座ろうとしているとする。攻撃成功してX点獲得した直後の攻撃側勝率をv_success、攻撃失敗して電流を食らった直後の攻撃側勝率をv_failure、守備側がXに電流を仕掛けている確率をp_Xと表すと、攻撃側がXに座る場合、その直後の勝率の期待値はv_success*(1-p_X)+v_failure*p_Xとなる。

守備側のナッシュ均衡戦略は、概要としては「『椅子の数字が大きいほど、それに電流を仕掛ける確率が高い』という感じで電流を仕掛けることで、攻撃側の勝率の期待値の最大値最小化を行う」ことです。

上記の出力を見ると、（解析コードがバグってなければ）ゲーム開始時点における、先手プレイヤー（1回表で攻撃側になるほう）の勝率は約53%です。
1回表で電流を食らうと、先手プレイヤーの勝率は約29.2%になります。
1回表で8の椅子に座れた場合、先手プレイヤーの勝率は約57.0%になります。
1回表で7の椅子に座れた場合、先手プレイヤーの勝率は約55.0%になります。

後手がナッシュ均衡戦略を取るならば、1回表で8の椅子に電流が仕掛けられている確率は約7.19%です。このとき、先手が8の椅子に座ることを選択するときの勝率は約55.0%になります。(57.0*0.9281+29.2*0.0719) これは7の椅子に座れた場合の勝率と同じかそれよりほんのちょっとだけ高いはずです。（数値誤差のせいで曖昧ですが）

1回表で先手が6以下の椅子に座れたとしても、その直後の勝率は55.0%より低くなるはずなので、後手から見ればそれは先手にとっての悪手だということになります。違う言い方をすると、後手としては先手が1回表で7以下の椅子に座ることを放置してでも、8以上の椅子を獲得することを確率的に防ぎ、結果として先手の勝率をできるだけ高くさせないという戦略がナッシュ均衡戦略となるのでした。

8x8 bitboardへの対称な変換の全列挙にグレイコードを応用する

以前の記事（↓）の続きです。
eukaryote.hateblo.jp
符号なし64bit整数を8x8 bitboardとみなして(1)横方向に鏡映 (2)縦方向に鏡映 (3)行列転置 という3つの処理をこの順番でやってもやらなくてもよいとしたとき、結果得られる最大8通りのbitboardのうち整数としての値が最小のものを得たいという問題を考えます。ベースラインとなるナイーブな実装は以下のようになります：

//horizontal_mirror, vertical_mirror, transposeの実装は省略
uint64_t get_unique_naive(const uint64_t b) {
	uint64_t answer = b;
	for (uint32_t i = 1; i <= 7; ++i) {
		uint64_t candidate = b;
		if (i & 1)candidate = horizontal_mirror(candidate);
		if (i & 2)candidate = vertical_mirror(candidate);
		if (i & 4)candidate = transpose(candidate);
		answer = std::min(answer, candidate);
	}
	return answer;
}

3種類の変換処理をやるかどうかの選択を「変数iを二進数として見たときの下位3桁のビットが立っているかどうか」と対応付けて、iをfor文で回して全通り作っています。

実際の使用例としては、Edaxというオセロソフトでは上記のような形で実装されています。
edax-reversi/src/board.c at 54578eefbb3fe5d734e02c0e6f6ffed11d1bad9e · abulmo/edax-reversi · GitHub

グレイコードの考え方を応用した実装

一方でEgaroucidという別の最強オセロソフトでは異なる実装になっています。
Egaroucid/src/engine/book_accuracy.hpp at 03f7c7df97ae01613f2c205758b76c9fbaa7156a · Nyanyan/Egaroucid · GitHub
この実装を模式的に書くと以下のような感じになります。
（厳密には違っていて、リンク先のEgaroucidの実装では行列転置（＝対角線を軸とする鏡映）を2回行っています。3種類の変換処理のうち行列転置が一番重いはずなので、行列転置を1回しかやらない以下のような順序付けのほうが少しだけ高速かもしれません）

uint64_t get_unique_graycode(const uint64_t b) {
	uint64_t answer = b;
	const uint64_t code001 = horizontal_mirror(b);
	answer = std::min(answer, code001);
	const uint64_t code011 = vertical_mirror(code001);
	answer = std::min(answer, code011);
	const uint64_t code010 = horizontal_mirror(code011);
	answer = std::min(answer, code010);
	const uint64_t code110 = transpose(code010);
	answer = std::min(answer, code110);
	const uint64_t code111 = horizontal_mirror(code110);
	answer = std::min(answer, code111);
	const uint64_t code101 = vertical_mirror(code111);
	answer = std::min(answer, code101);
	const uint64_t code100 = horizontal_mirror(code101);
	answer = std::min(answer, code100);
	return answer;
}

3種類の変換処理をやるかどうかの選択を3桁の二進数の各ビットの状態に対応付けるという発想はナイーブ実装と同じです。そのうえでこの実装では「直前のbitboardに対してどれか1種類の変換処理だけを行い次のbitboardを作る」を7回行うことで8通りのbitboardを網羅できています。このように「1ビットだけ逆転させる処理によって任意桁の二進数を巡回できること」やその順序自体については"グレイコード"という名前で広く知られており、様々な分野で応用されています。

ちなみに同様の実装は2048（ゲーム）を強化学習するソフトの実装でも見られます。
TDL2048/board.h at 665d470cd8790c88519352362f91f4209e0986a1 · moporgic/TDL2048 · GitHub
2048の場合は、1マスを4bitとみなして16マスの盤面全体を64bitとみなすことになります。その場合には転置操作をpext命令4回でゴリ押したりできて、縦鏡映や横鏡映と比べたときにどれが最も重い処理なのかはCPUアーキテクチャによって色々と話が変わってきます。

グレイコードの考え方を離れ、クリティカルパスを短くする

上記のグレイコードに基づくアルゴリズムは美しいですが、直前の変換が完了しないと次の変換を計算できない、すなわち計算グラフのクリティカルパスが長いのが欠点です。「変換処理を7回やるだけで8通りを網羅できる」「行列転置は1回しか行わない」という要件でクリティカルパスを短くしようとすると、例えば以下のように書くことができます。

uint64_t get_unique_notgraycode(const uint64_t b) {
	uint64_t answer = b;
	const uint64_t code100 = transpose(b);
	answer = std::min(answer, code100);
	const uint64_t code001 = horizontal_mirror(b);
	answer = std::min(answer, code001);
	const uint64_t code010 = vertical_mirror(b);
	answer = std::min(answer, code010);
	const uint64_t code101 = horizontal_mirror(code100);
	answer = std::min(answer, code101);
	const uint64_t code011 = horizontal_mirror(code010);
	answer = std::min(answer, code011);
	const uint64_t code110 = vertical_mirror(code100);
	answer = std::min(answer, code110);
	const uint64_t code111 = vertical_mirror(code101);
	answer = std::min(answer, code111);
	return answer;
}

この実装を含めた上記3つの実装はすべて同じ結果を返しますが、レイテンシ・スループットの面では一番下のコードが（私の環境では）最も高速でした。特にレイテンシに関しては前回の記事で紹介したAVX2版のものよりも高速でした。

オセロの最大分岐数は黒番も33

棋譜は f5f4e3d2d3c3f3e6b3g3f6d6e7g7c6d7f7g5c7b7c8b4b2b1c2f2 です。

オセロの局面。黒の手番、34マス空き、h1以外の33マスに着手可能。

経緯については前の記事を参照してください。
eukaryote.hateblo.jp