独立な数ゲームの和
概要
全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。
数としての評価はminimaxの終端得点とは異なる。左の全選択肢より大きく、右の全選択肢より小さい数のうち最も単純な二進有理数を選ぶ。空の片側には不等式制約がなく、両側が空の値は0。例えば{0|1}=1/2だが、{0|0}は数でなく、この規則で0にしてはいけない。
ABC229 Hでは列間で手が干渉しない独立和と、全ての列局面が数である条件を先に確かめる。浮動小数の誤差で符号を変えず、共通の2冪分母などで厳密に加算する。ABC265 Exへの応用では整数の数成分だけをこの技能で扱い、Nim成分はGrundy数のXORとして別に保持する。数成分とNim成分を一つの実数へ潰さない。
考え方
simplest-number規則を計算手順にする
LeftとRightで合法手が異なる有限・非循環のnormal play(手を打てない側が負け)を扱う。局面を{左の後続集合 | 右の後続集合}と書く。全後続が既に数として評価でき、左の値全てが右の値全てより小さいとき、この局面も数となる。
Lを左値の最大、Rを右値の最小とし、左が空ならL=−∞、右が空ならR=∞とする。局面値xは開区間L<x<Rの最も単純な二進有理数で、次の順で選ぶ。
- 区間に整数があれば、絶対値が最小の整数を選ぶ。有限な境界なら許される整数範囲は⌊L⌋+1,…,⌈R⌉−1となる。範囲に0があれば0、全て正なら最小、全て負なら最大を取る。
- 整数がなければ、t=1,2,…の順に、
L<m/2^t<Rを満たす整数mがあるか調べ、最初に見つかったものを取る。有限なL,Rに対しm=⌊2^t L⌋+1を作り、m<2^t Rかを厳密に比較する。この最初の分母では分数は既約で一意になる。二進有理数は任意の開区間に存在するので探索は停止する。
後続から評価していけば、{ | }=0、{0 | }=1、{ | 0}=−1、{0 | 1}=1/2、{1/2 | 1}=3/4となる。境界は等号を含まないので{0 | 0}は数として評価できない。これはGrundy値1のゲームにも現れるが、数0とは異なる。未定義の後続を持つ場合も、間の実数を適当に割り当てて先へ進めない。
独立和の符号から勝敗へ戻す
一手で一成分だけを動かし、他成分の合法手へ影響しない和では、全成分が数であれば合計Xは通常の数の和となる。Leftを正の側とすると、X>0なら先手・後手によらずLeftが勝ち、X<0ならRightが勝ち、X=0なら後手が勝つ。Leftが先手に固定されている問題では、X>0のときだけLeftの必勝である。
この対応は「Leftの手で値は厳密に下がり、Rightの手で厳密に上がる」ことと、simplicity規則による安全な手の存在から得る。X=0でLeftが動くと負、Rightが動くと正となり、相手が有利になる。X>0でLeftの手番なら、和を非負に保つ手を選べる。全成分が整数なら正の成分に値の減少が1以内のLeft手があり、非整数の成分があるなら最大分母2^tの成分に減少が1/2^t以内のLeft手がある。そうした手がなければ元の値より単純な数が区間に入るため、値の選択規則と矛盾する。Xは1/2^tの整数倍なのでその減少を吸収できる。Rightの手番なら全ての手がXを増やす。有限性と負の場合の対称性により、上記の勝敗になる。
例えば{0 | }と{ | 0}の和は1+(−1)=0で後手必勝、{0 | 1}の二つの和は1/2+1/2=1でLeft必勝となる。ABC229 H公式解説へ進むときは、各列が数となることと列同士の独立性を先に示し、その後でこの符号判定を使う。
成立条件と計算量
S局面・T合法遷移に対し、後続の評価、左右の最大・最小の取得はO(S+T)回の比較。最小分母を逐次探索する上記の方法では、局面vの指数をt_vとして追加O(Σ_v(t_v+1))回の厳密算術を要する。整数部・分子・分母のbit数と合法手生成の費用も含める。全成分を共通の2冪分母へ揃えて整数で加算すれば符号を正確に判定でき、浮動小数の近似による勝敗の反転を避けられる。
全ての到達可能局面で数の条件を満たすことが必要で、一般のpartizan gameへ実数加算を拡張できない。Nim成分を持つ問題では数の和とGrundy数のXORを別々に保持し、両者の混合の勝敗規則をその問題の条件から導く。
問題一覧
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC265 Ex「No-capture Lance Game」 公式問題
技能・出典
主題: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 独立な数ゲームの和(全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。) / 分離可能線形変換・Walsh–Hadamard変換(Kronecker積で表される多次元線形変換を各軸の小変換へ分離し、stride走査で正変換または逆変換を計算できる。)。主タグ: 畳み込み・相互相関 / 補助タグ: 独立な数ゲームの和、game状態・Grundy DP、分離可能線形変換・Walsh–Hadamard変換
前提・学習成果・出典
習得対象の目安: 赤色(2800以上)。partisan gameが数になる条件と数の独立和を理解し、Grundy数との違いを扱う。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-conway-number-games
独立な数ゲームの和
習得する技能
- 全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: minimax・得点差・局面値を評価するゲームDP。
このUnitを直接前提とする単元: なし。
有限局面DAGのminimaxで得た考え方と実装を再利用し、独立な数ゲームの和の発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- 独立な数ゲームの和の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。