独立な数ゲームの和

概要

全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般の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の最も単純な二進有理数で、次の順で選ぶ。

  1. 区間に整数があれば、絶対値が最小の整数を選ぶ。有限な境界なら許される整数範囲は⌊L⌋+1,…,⌈R⌉−1となる。範囲に0があれば0、全て正なら最小、全て負なら最大を取る。
  2. 整数がなければ、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を別々に保持し、両者の混合の勝敗規則をその問題の条件から導く。

問題一覧

  • ABC229 H「Advance or Eat」 公式問題
    技能・出典
    主題: 独立な数ゲームの和(全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。

    主タグ: 独立な数ゲームの和

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 赤色(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では扱わないもの

  • 独立な数ゲームの和の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠