飛車は縦横に動き、角は斜めに動く。通常の将棋では駒の種類が初めから決まっているが、量子将棋では、どの駒も最初は王、飛車、角、金、銀、桂馬、香車、歩のすべてになり得る。指し手を重ねると可能性は絞られ、離れた位置にある別の駒の動きまで制限される。この現象には、20 枚の駒を一つの割当問題として扱う数学的な理由がある。
片側の初期陣営には飛車が 1 枚、香車が 2 枚ある。仮に 3 枚の駒の候補がいずれも飛車か香車だけになれば、この 3 枚の正体が個別には決まっていなくても、ほかの 17 枚から飛車と香車の可能性が消える。駒の移動という局所的な操作から、全体の枚数制約を介して候補が伝播するためである。
この関係を、候補集合、実現可能な割当集合、Hall の定理、容量付き二部マッチングで定式化する。個々の駒の可能性を正確に求める条件を導き、組合せを列挙せずに収束を計算する方法を示したうえで、盤面と持ち駒を含む対局状態の遷移まで定義する。量子将棋は、未確定な変数を含むゲームを、確定した制約によって動かす具体的なモデルになる。
1. 量子将棋とは何か
1.1 普通の将棋と何が違うのか
量子将棋は、さまざまな変則将棋をオンラインで対局できるウェブサービス「将棋ったー」に収録されているゲームの一つである。盤面は通常の将棋と同じ 9 × 9 マスで、先手と後手が交互に指し、それぞれ 20 枚の駒を使う。ただし、初期配置にある駒はすべて「量子駒」と呼ばれる同じ種類の駒である。量子駒は、それぞれ王、飛車、角、金、銀、桂馬、香車、歩の 8 種類の可能性を持っている。どの種類であるかは対局開始時点では確定しておらず、駒の移動や成り、ほかの駒の動きなどによって候補が変化していく[1]。
普通の将棋では、駒の種類によって移動可能な範囲が決まる。例えば、歩を選択したときは前方 1 マスが移動先となり、飛車なら障害物のない縦横の直線上を移動できる。量子将棋では、この関係が候補集合を介して決まる。歩と飛車の可能性が残っている駒なら、歩として前方 1 マスへ進む動きも、飛車として横へ進む動きも候補になる。ただし、実際に横へ動かせば歩の可能性が除外され、それまでの移動履歴と両立する種類だけが残る。
この違いを整理すると、量子将棋では駒の位置と移動履歴に加え、現在残っている駒種の候補が局面を構成する情報になる。同じマスに置かれている量子駒でも、それまでに前進だけを繰り返した駒と、横方向へ大きく動いた駒では、以後に可能な指し手が異なる。さらに、ほかの駒が特定の種類に確定すると、まだ一度も動いていない駒の候補まで変化する場合がある。
| 観点 | 普通の将棋 | 量子将棋 |
|---|---|---|
| 開始時の駒種 | 各駒の種類が初期配置によって決まっている。 | すべての駒が 8 種類の可能性を持って開始する。 |
| 移動できる範囲 | 各駒に定められた移動能力で決まる。 | 残された候補のいずれかが実現できる移動を選べる。ただし、全体の枚数制約とも両立する必要がある。 |
| 移動後の状態 | 駒の位置が変わり、必要に応じて成り状態が変化する。 | 位置や成り状態に加え、その移動と両立する駒種へ候補が絞られる。 |
| 他の駒への影響 | 駒の位置が変わることで、利きや移動経路が変化する。 | 位置関係の変化に加え、駒種の枚数制約を通じて、直接動かしていない駒の候補も変化する。 |
| 相手の王将 | 王将の位置と種類が分かっている。 | 王将になり得る駒が複数存在し、対局中に候補が絞られていく。 |
| 枚数の条件 | 初期配置に王将 1 枚、飛車 1 枚などの構成が反映されている。 | 初期陣営の 20 枚全体に対して、同じ枚数構成を満たす割当が要求される。 |
| 持ち駒 | 取った駒の種類が分かっており、その種類の駒として打つ。 | 取った駒にも未確定の候補が残る場合があり、元の初期陣営の枚数制約に属し続ける。 |
例えば、ある駒が飛車に確定したとき、同じ初期陣営の残り 19 枚から飛車の可能性が消える。通常の将棋でも飛車が 1 枚しかないことは同じだが、駒種が最初から確定しているため、このような候補の更新処理は必要ない。量子将棋では、枚数配分という既知の情報と、駒種という未確定の情報が同時に存在する。その組合せによって、盤上の離れた駒の状態が互いに制約される。
1.2 どうやって指すのか
量子駒の移動は、現在残っている駒種のいずれかが実現できる動きを候補とする。初期状態では 8 種類すべての可能性が残っているため、それらの駒が持つ移動能力を利用できる。ただし、途中に別の駒がある場合は通常の将棋と同様に移動経路が制限される。また、動かした結果として駒種の割当に矛盾が生じる指し手は認められない。盤面上の移動条件と、駒種全体の割当条件の両方を満たすことが必要になる。
最も簡単なのは、初期状態の量子駒を前へ 1 マス動かす場合である。歩、金、銀、香車、飛車、王将は、この移動を実現できる。一方、角と桂馬は前方 1 マスへ直接移動できない。そこで、最初は 8 種類あった候補から角と桂馬が除外され、移動後の候補は「王・飛・金・銀・香・歩」の 6 種類になる[2]。
同じ駒を、途中に障害物のない状態で前方へ 2 マス動かす場合は結果が異なる。成っていない駒で、この移動を実現できるのは飛車と香車である。移動後の候補は「飛・香」の 2 種類に絞られる。この時点で飛車と香車のどちらかが抽選されるわけではなく、両方の可能性が残る。さらにその駒を横方向へ 2 マス動かせば、香車は横方向へ移動できないため、飛車に確定する。このように、異なる方向への指し手を組み合わせることで、候補を段階的に限定できる。
| 移動の例 | その移動が可能な駒種 | 候補が絞られる理由 |
|---|---|---|
| 前方へ 1 マス | 王・飛・金・銀・香・歩 | 角と桂馬は前方へ 1 マス進む移動能力を持たないため、候補から除外される。 |
| 前方へ 2 マス | 飛・香 | 飛車と香車だけが、前方の直線上を 2 マス以上進めるため、この 2 種類が残る。 |
| 横方向へ 2 マス | 飛 | 成っていない駒で横方向へ 2 マス進めるのは飛車だけなので、飛車に確定する。 |
| 斜め方向へ 2 マス | 角 | 成っていない駒で斜め方向へ 2 マス進めるのは角だけなので、角に確定する。 |
この表は、移動する駒が成っておらず、移動経路に障害物がない場合の基本的な対応を示している。実際に指せるかどうかは、それまでの移動履歴から残っている候補と、初期陣営全体の枚数制約にも依存する。例えば、まだ一度も動いていない駒には、移動履歴による制約がないため角の可能性が残る。しかし、同じ初期陣営の別の駒が角に確定すれば、未移動の駒からも角の可能性が除外される。駒自身の移動履歴から得られる局所候補 \(D_i\) と、ほかの駒の確定による枚数制約まで反映した正確な候補 \(P_i(D)\) を区別する必要がある。
もう一つ注意すべき点は、ある移動を実現できる駒種が残っていることが、必ずしもその指し手を保証するわけではないことである。例えば、飛車 1 枚と香車 2 枚の枚数を、すでに別の 3 枚の駒の候補が使い切っている場合を考える。このとき、4 枚目の駒が前方へ 2 マス動こうとすると、その駒も飛車か香車である必要が生じる。しかし、飛車と香車を割り当てる余地は残っていないため、その指し手は許されない。各駒の移動能力を調べる処理に加えて、全体の枚数構成と矛盾しないかを確認する処理が必要になる。
1.3 駒を取る、成る、打つ
量子将棋でも、相手の駒を取って持ち駒とし、後から盤上へ打つことができる。ただし、取られた駒の種類が確定しているとは限らない。例えば、取られる直前に「王・飛・銀」の 3 種類の可能性が残っていた駒について考える。王将であると確定していなければ、その駒を取ることで王将の可能性が除外される。ほかの条件と矛盾しなければ、取られた駒は「飛・銀」の可能性を残した持ち駒になる。取った時点で飛車か銀のどちらか一方を選択する必要はなく、以後の指し手によって候補がさらに絞られる。
持ち駒になった駒について、現在の所有者と初期陣営を区別することが重要である。例えば、先手が後手の量子駒を取って自分の持ち駒にした場合、その駒を動かす権利は先手に移る。しかし、駒種の枚数制約では、その駒は最初に属していた後手の 20 枚の一部であり続ける。先手がその駒を盤上へ打ち、飛車に確定させれば、後手の初期陣営に由来するほかの駒から飛車の可能性が消える。一方、先手が最初から所有していた 20 枚の飛車の可能性には、この確定による直接の影響はない。現在の所有者と枚数制約上の所属を別々に管理することで、この関係が成立する[2]。
成りも通常の将棋と同じように、移動元または移動先が相手陣の 3 段以内にある場合に選択できる。ただし、量子駒を成ることを選んだ場合、その操作によって新しい制約が加わる。金と王将は成る能力を持たないため、成った駒からは金と王将の可能性が除外される。例えば、成る直前に「王・飛・金・銀」という候補が残っていれば、成ること自体の条件では王と金が除外される。ただし、実際に残る候補は移動方向や距離などの条件にも依存し、「飛・銀」の両方が残るとは限らない。以後は成り駒の移動能力と、それまでの駒種候補の両方を満たすように指すことになる。
また、通常の将棋には、これ以上前へ進めなくなる位置に歩、香車、桂馬を成らずに進めたり、その種類の持ち駒を打ったりすることを認めない規則がある。量子将棋では、該当する位置に置いた駒から、行きどころのなくなる駒種を除外する。例えば、相手陣の最奥段に不成で進入した駒からは歩、香車、桂馬の可能性が消え、その 1 段手前では桂馬の可能性が消える。これは盤面上の位置によって、成立可能な駒種が限定される例である。
| 操作 | 追加される条件 | 局面への影響 |
|---|---|---|
| 相手の駒を取る | 取られた駒から王将の可能性を除外する。 | 王将以外の可能性が残れば持ち駒となる。王将に確定している場合は勝敗が決まる。 |
| 取った駒を打つ | 打った位置に関する制約と、それまでに残された候補を満たす。 | 現在の所有者は取った側だが、駒種の枚数制約には元の初期陣営を使う。 |
| 成る | 金と王将の可能性を除外する。 | 成った状態での移動能力と、残った駒種候補によって以後の合法手が決まる。 |
| 最奥段へ不成で進入する | 歩・香車・桂馬の可能性を除外する。 | その位置では前進できなくなる駒種が候補から消える。 |
| 最奥段の 1 段手前へ不成で進入する | 桂馬の可能性を除外する。 | 桂馬としての前方への跳躍が成立しなくなる位置の制約が反映される。 |
このように、量子将棋で候補を絞る操作は駒の移動だけではない。取る、成る、打つという操作や、駒を置く位置も候補集合の更新条件になる。これらの条件が重なった結果、ある駒に割り当てられる種類が一つも残らなくなる場合がある。そのような指し手は、王将の捕獲による勝利の場合を除いて認められない。局面の更新後も、すべての駒について矛盾しない種類の割当が存在することが、対局を継続するための条件である。
1.4 王将も未確定なゲームの勝敗
通常の将棋では、王将がどこにいるかを両者が把握し、王将を取られないように守りながら相手を詰ませる。量子将棋では、王将も最初は 20 枚のうちのどれかという状態から始まる。王将になり得る駒は複数存在するが、初期陣営ごとに王将として割り当てられるのは 1 枚だけである。対局中の移動や捕獲によって王将の可能性が絞られ、ある駒が王将に確定する場合がある。
勝利条件は、王将に確定した相手の駒を取ることである。例えば、ある駒に「王・飛」の可能性が残っていて、その駒を取る操作を行ったとする。飛車として成立する割当が残るなら、王将の可能性を除外したうえで捕獲が成立する。一方、その駒が王将にしかなれない状態で取られた場合は、王将を取った側の勝利となる。ここでは、取られた駒から王将の可能性を除外できるかという条件が、通常の捕獲と勝利を分けている。
王手放置も認められている。通常の将棋では、王将が相手の利きにさらされる指し手を禁止するが、量子将棋では王将の候補が複数の駒に分散している。仮に王手放置を禁止すると、王将の候補を持つ駒と、相手の飛車や角などの候補を持つ駒の位置関係から、新しい制約が発生する。しかも、その制約は先手と後手の両方の候補の組合せに関係する。現行ルールでは王手放置を許容することで、この種の制約を合法手判定から除外している[2]。
二歩についても、通常の将棋とは異なる規則がある。2026 年 3 月から適用されている「確定二歩禁」では、同じ筋に自分の歩に確定した駒がある場合、別の歩に確定した持ち駒を打つことは禁止される。一方、最初は歩以外の可能性も持っていた駒が、その後の収束によって歩に確定し、結果として同じ筋に 2 枚の歩が並ぶことは認められる[1]。
この区別には、枚数制約との関係がある。もし初期状態から通常の二歩禁止をすべての可能性に適用すると、同じ筋に並ぶ駒同士の候補が相互に制限される。さらに、各陣営に歩が 9 枚必要であることから、初期配置そのものに多数の制約が発生する。確定二歩禁は、すでに歩と確定している駒を打つ操作を制限する規則であり、収束によって後から成立する歩の配置は許容する。この違いによって、駒種の未確定性を保持したまま対局を進められる。
量子将棋の局面は、駒の位置、現在の所有者、成り状態、駒種候補、元の初期陣営という情報によって構成される。指し手はこれらの状態を更新し、更新後の条件を満たす駒種の組合せが存在する場合に成立する。王将の捕獲では勝敗が決まり、それ以外の指し手では矛盾のない割当が維持される。この規則によって、駒の正体が未確定なままでも、合法手と勝利条件を判定できる将棋が成立している。
2. 指し手を候補集合の更新として定義する
2.1 局所的な条件を集合で表す
駒種全体を集合 \(K\) とし、初期陣営 \(s\) に属する駒の識別子集合を \(I_s\) とする。先手と後手についてそれぞれ \(|I_s|=20\) である。駒 \(i\) に時刻 \(t\) までの操作から許される種類を、候補集合 \(D_i(t)\) に記録する。初期状態ではすべての駒について \(D_i(0)=K\) となる。
\[K=\{王,飛,角,金,銀,桂,香,歩\},\qquad D_i(0)=K\]
指し手 \(u_t\) が駒 \(i\) に新しい条件を課すとき、その操作と両立する駒種集合を \(E_i(S_t,u_t)\) とする。\(S_t\) は指す直前の局面を表す。移動方向、距離、成り状態、移動先、捕獲の有無によって \(E_i\) が定まり、その駒についての条件を次のように更新する。
\[\boxed{D_i(t+1)=D_i(t)\cap E_i(S_t,u_t)}\]
\(\cap\) は共通部分であり、すでに残っている候補のうち、今回の操作も満たせる種類だけを残す。例えば成っていない駒について、経路が空いた前方への 2 マス移動なら \(E_i=\{飛,香\}\) であり、その駒が成る操作を選べば \(E_i=K\setminus\{王,金\}\) という条件も課される。操作が複数の条件を同時に与える場合は、それらの集合の共通部分を取ればよい。
たとえば、最初に候補が 8 種類あった駒を前へ 1 マス動かすと、王・飛・金・銀・香・歩の 6 種類が残る。その後、同じ駒を横へ 2 マス動かすことが盤面上で可能なら、残っている候補と「横へ 2 マス動ける種類」の共通部分は飛車だけになる。この 2 手を別々の操作と考えても、候補集合の更新は一連の共通部分として書ける。
\[D_i(t+2)=D_i(t)\cap E_i(S_t,u_t)\cap E_i(S_{t+1},u_{t+1})\]
共通部分には結合法則があるため、いくつかの条件を順に適用しても、すべてを同時に満たす種類だけが残る。この性質は、過去の移動履歴を毎回最初から読み直す代わりに、候補集合という形で蓄積できる根拠となる。ただし、盤面に依存する条件集合 \(E_i\) の内容自体はその時点の位置と成り状態から決まるので、すべての指し手を順序なしに入れ替えられるという意味ではない。
候補集合が空になれば、その操作を満たす基本種類は存在しない。例えば「飛・香」まで絞られた成っていない駒に斜め 2 マスの移動条件を課すと、\(\{飛,香\}\cap\{角\}=\varnothing\) となる。この局所矛盾は全体の枚数を調べる前に検出できる。一方、局所候補が空でなくても枚数制約で矛盾する場合があるため、合法性判定を局所条件だけで完結させることはできない。
2.2 局所更新が持つ単調性と限界
集合の共通部分は元の集合に含まれるため、いったん候補から消えた種類は、同じ駒の後続の操作では復活しない。局所更新は次の包含関係を満たす。
\[D_i(t+1)\subseteq D_i(t)\]
ただし、これはその駒についての移動・成り・捕獲の条件だけを反映した関係である。例えば飛車に確定した駒が現れれば、同じ初期陣営の残り 19 枚は、その駒自身が何もしていなくても飛車の候補を失う。全体の枚数を守る条件を導入しなければ、この変化を説明できない。
開発者の公開した収束処理も、指し手による候補の絞り込みと、初期陣営全体の使い切りによる候補の絞り込みを区別している[3]。数学的には、\(D_i\) を操作から直接得られる条件、全体の割当を考慮した正確な候補を \(P_i\) と区別すると、この二つの処理の役割が明確になる。
局所更新と全体の更新の違いは、同じ初期陣営の別の駒に注目すると明確になる。番号 1 の駒が横方向への長距離移動で飛車に確定したとき、番号 2 の駒が一度も動いていなくても、番号 2 に飛車を割り当てる解は消える。\(D_2\) を直接更新する操作を行っていなくても、全体の制約から導かれる正確な候補集合は減少する。この区別を保つため、操作の直接条件を \(D_i\)、全体の整合性まで反映した候補を \(P_i\) と記す。
この関係は、データの保持方法にも影響する。局所条件 \(D_i\) は、指し手によって追加された制約の記録として扱える。\(P_i\) は同じ初期陣営に属するほかの駒の状態によって変わるため、局所条件と枚数保存則から計算される結果となる。両者を区別すれば、駒を動かした事実と、全体から推論された候補削除を混同せずに説明できる。
3. 20 枚全体の可能世界を定義する
3.1 離散変数と枚数保存則
初期陣営を一つ固定し、その 20 枚を \(I=\{1,2,\ldots,20\}\) と記す。各駒 \(i\) の基本種類を離散変数 \(X_i\in K\) で表す。この変数は秘密の駒種が最初から抽選されているという意味ではなく、与えられた条件を満たす割当を記述する数学上の変数である。成り状態や現在の所有者は、基本種類とは別に管理する。
種類 \(k\) に必要な枚数を \(c_k\) とする。王、飛車、角は各 1 枚、金、銀、桂馬、香車は各 2 枚、歩は 9 枚であり、\(\sum_{k\in K}c_k=20\) が成り立つ。指示関数 \(\mathbf 1[X_i=k]\) は、駒 \(i\) に種類 \(k\) を割り当てたとき 1、それ以外のとき 0 となる。枚数保存則は次の等式で表せる。
\[\boxed{\sum_{i\in I}\mathbf 1[X_i=k]=c_k\qquad(k\in K)}\]
| 駒種 | 必要枚数 | 数理的な意味 |
|---|---|---|
| 王・飛車・角 | 各 1 枚 | それぞれの値を取る変数は、初期陣営につき一つずつである。 |
| 金・銀・桂馬・香車 | 各 2 枚 | それぞれの値を取る変数は、初期陣営につき二つずつである。 |
| 歩 | 9 枚 | 歩という値を取る変数は、初期陣営につき九つである。 |
枚数の条件をベクトルで表すと、\(K\) の順序を王、飛、角、金、銀、桂、香、歩としたとき、\(c=(1,1,1,2,2,2,2,9)\) である。この要素を足し合わせると \(1+1+1+2+2+2+2+9=20\) になる。20 枚をそれぞれどれか一種類に割り当て、各種類の枚数を正確に満たせば、余分な駒も不足する駒も生じない。
この保存則は駒の現在位置と独立である。例えば後手由来の飛車を先手が取って打ち直した場合、その駒の現在の操作主体は先手だが、飛車の容量は後手由来の集合の中で消費される。仮に捕獲のたびに枚数制約の所属まで変更すると、先手由来の集合に飛車が 2 枚、後手由来の集合に飛車が 0 枚という状態を許すことになり、規則が定めた初期陣営ごとの枚数保存則と一致しなくなる。
基本種類と成り状態も別変数として扱う。成った飛車は龍として移動するが、枚数を数える際には飛車 1 枚のままである。候補集合の値は基本種類、盤上での移動能力は基本種類と成り状態の組から決まる。こうして、駒の種類を保存する条件と、盤上で何ができるかを判定する条件を分離できる。
3.2 実現可能な割当集合
駒の番号に種類を一つずつ割り当てる関数を \(\omega:I\to K\) とする。\(\omega(i)\) は駒 \(i\) に割り当てた種類、\(\omega^{-1}(k)\) は種類 \(k\) を割り当てられた駒の集合である。局所条件 \(D=(D_1,\ldots,D_{20})\) と枚数保存則を同時に満たす割当の集合を \(\Phi(D)\) と定義する。
\[\boxed{\Phi(D)=\left\{\omega:I\to K\ \middle|\ \omega(i)\in D_i\ (\forall i\in I),\quad |\omega^{-1}(k)|=c_k\ (\forall k\in K)\right\}}\]
\(\Phi(D)\) の一要素は、20 枚すべてについて矛盾しない種類の割当を表す。個々の候補に飛車が含まれる駒が何枚あっても、同じ割当の中で飛車になれるのはちょうど 1 枚である。実現可能な割当が一つもない状態は \(\Phi(D)=\varnothing\) と表し、通常の指し手については矛盾として扱う。
初期状態ではすべての \(D_i=K\) であるため、種類ごとの枚数配分だけが割当数を制限する。区別された 20 枚に同じ種類の駒を所定の枚数だけ割り当てる組合せ数は、多項係数で計算できる。
\[\boxed{|\Phi(D(0))|=\frac{20!}{9!\,(2!)^4}=419{,}026{,}608{,}000}\]
分子は 20 枚の並べ方、分母は歩 9 枚と各 2 枚の 4 種類の入替えによる重複を表す。約 4,190 億通りというのは片側の初期陣営の基本種類の割当数であり、盤面の配置や手番を含めた局面数ではない。この大きさが、可能世界を逐一列挙する計算より、制約そのものを解く計算を選ぶ理由になる。
初期割当数の式は、実際には種類ごとの枠を順に選ぶ計算でも導ける。20 枚から歩に割り当てる 9 枚を選び、残り 11 枚から金 2 枚、残り 9 枚から銀 2 枚というように選んでいく。選択数を掛け合わせれば、階乗が打ち消し合って同じ多項係数になる。
\[\binom{20}{9}\binom{11}{2}\binom{9}{2}\binom{7}{2}\binom{5}{2}\,3!=\frac{20!}{9!(2!)^4}\]
最後に残る 3 枚は王、飛車、角へそれぞれ 1 枚ずつ割り当てるので \(3!\) を掛けている。\(\binom{a}{b}\) は \(a\) 個から \(b\) 個を選ぶ組合せ数を表す。この計算で区別しているのは、個体としての各量子駒に、どの基本種類を対応させるかという割当である。初期割当数が多いのは、一つの駒が何種類も動けることそのものより、20 個の変数が同じ個数制約を満たしながら多様な組合せを作れるためである。
対局中には候補 \(D_i\) が削減されるため、利用できる組合せは初期状態の部分集合へ縮小する。例えば、ある駒に飛車だけが残った瞬間、その駒が飛車である割当に限定され、飛車を別の駒へ割り当てる組合せは消える。必要なのは組合せの総数を毎回再計算することより、どの割当がまだ存在するかを見分ける条件である。
3.3 正確な候補は可能世界の射影になる
局所条件として残っている種類が、全体の枚数保存則と両立するとは限らない。\(\Phi(D)\) に含まれるいずれかの割当で実際に現れる種類だけを、駒 \(i\) の正確な候補集合 \(P_i(D)\) とする。
\[\boxed{P_i(D)=\{\omega(i)\mid\omega\in\Phi(D)\}}\]
例えば \(D_i=\{飛,香\}\) でも、飛車を割り当てる完全な組合せが存在しなければ、\(P_i(D)=\{香\}\) となる。これが全体の割当集合から一つの変数の値だけを取り出す射影である。式から \(P_i(D)\subseteq D_i\) が直ちに分かる。また、\(\Phi(D)\neq\varnothing\) であれば、どの駒についても \(P_i(D)\neq\varnothing\) となる。
ここで二つの性質を証明できる。まず、\(D’_i\subseteq D_i\) がすべての駒で成り立つとき、\(\Phi(D’)\subseteq\Phi(D)\) である。なぜなら、強い条件 \(D’\) を満たす割当は、弱い条件 \(D\) も必ず満たすからである。したがって、射影についても \(P_i(D’)\subseteq P_i(D)\) が成り立つ。局所的な候補の削除が、別の駒の正確な候補を増やすことはない。
次に、すべての \(D_i\) を正確な候補 \(P_i(D)\) に置き換えても、可能世界は変化しない。
\[\boxed{\Phi(P(D))=\Phi(D),\qquad P(P(D))=P(D)}\]
証明は、\(\Phi(D)\) のどの割当も、各駒でその射影に含まれる値を使っていることによる。\(D_i\) から実現不可能な候補だけを取り除いても、もともと成立していた割当は一つも失われない。逆に、候補を増やしていないため、新しい割当も生まれない。後半の等式は、一度正確な候補まで絞った後に同じ計算を繰り返しても結果が変わらないという冪等性を示す。
射影 \(P(D)\) は、条件を正確な候補まで絞る演算とみなせる。その性質を整理すると、\(P(D)\subseteq D\) は候補を増やさないこと、\(D’\subseteq D\Rightarrow P(D’)\subseteq P(D)\) は入力条件を強めるほど結果も狭まること、\(P(P(D))=P(D)\) は一度正確に絞れば同じ計算を重ねても変わらないことを意味する。いずれも、現実の盤面を動かす処理とは独立に、割当問題の数学的性質として導ける。
具体的には、飛車 1 枚、香車 2 枚という 3 枠だけを取り出し、3 枚の候補を \(D_1=\{飛\}\)、\(D_2=D_3=\{飛,香\}\) とする。このとき、この 3 枚への割当は \((飛,香,香)\) の一つだけに定まる。局所候補が \(\{飛,香\}\) のままの番号 2 と 3 でも、射影すれば \(P_2=P_3=\{香\}\) となる。元の集合から現れなかった値だけを取り除いても唯一の割当は残るため、射影後の再計算では候補は変わらない。
4. Hall の条件から制約伝播を証明する
4.1 使い切りを集合の容量として表す
先手の初期陣営に属する 3 枚について、\(D_1=D_2=D_3=\{飛,香\}\) となったとする。飛車は 1 枚、香車は 2 枚なので、この 3 枚の中で飛車を選ぶ方法は 3 通りあるが、どの場合も飛車と香車の割当枠はすべて埋まる。したがって残り 17 枚に飛車と香車を割り当てる完全な組合せは存在しない。開発者はこれを駒種の「使い切り」と説明している[3]。
任意の駒種集合 \(T\subseteq K\) に対し、\(T\) の中の種類にしかなれない駒の集合 \(I_T(D)\) と、その種類の割当容量 \(c(T)\) を定める。
\[\boxed{I_T(D)=\{i\in I\mid D_i\subseteq T\},\qquad c(T)=\sum_{k\in T}c_k}\]
\(T=\{飛,香\}\) なら \(c(T)=3\) である。\(I_T(D)\) の駒には必ず \(T\) のいずれかを割り当てなければならない。その枚数が容量を超えれば、全体の割当は不可能になる。これが最初の必要条件である。
\[\boxed{|I_T(D)|\leq c(T)\qquad(\forall T\subseteq K)}\]
使い切りで確定しているのは、個々の駒ではなく駒の集団が占める種類の総数である。3 枚とも \(\{飛,香\}\) なら、飛車を担当する駒は 3 通り考えられる。しかし、どの割当でも飛車と香車の 3 枠はこの 3 枚が独占する。残り 17 枚の候補から飛車と香車を取り除く処理は、3 通りのどれを選ぶかを先に決めずに実行できる。
同じ原理は金と銀にも成り立つ。金 2 枚と銀 2 枚を合わせた容量は 4 枚である。ある 4 枚すべての候補集合が \(\{金,銀\}\) に等しければ、その 4 枚の内部では金と銀の割当方法が \(\binom{4}{2}=6\) 通り残る一方、残り 16 枚からは金と銀の候補が消える。駒種ごとの容量を足し合わせるという操作により、飛車と香車に固有だった例を任意の駒種の集まりへ一般化できる。
4.2 必要条件であるだけでなく十分条件でもある
この不等式をすべての駒種集合について満たすことは、20 枚の割当が存在するための必要十分条件になる。証明には Hall の結婚定理を用いる。Hall の定理は、各対象に許された割当先があるとき、すべての対象へ異なる割当先を与えられる条件を表す[4]。
飛車のように容量が 1 枚の種類には 1 個の枠、香車のように容量が 2 枚の種類には 2 個の枠、歩には 9 個の枠を用意する。枠の総数は 20 個である。駒 \(i\) は \(D_i\) に含まれる種類の枠すべてへ接続できる。任意の駒の集合 \(U\subseteq I\) が利用できる枠の個数は、\(U\) に属する駒の候補の和集合 \(N(U)=\bigcup_{i\in U}D_i\) を使って \(c(N(U))\) と表される。
Hall の定理によれば、すべての \(U\) について \(|U|\leq c(N(U))\) が成り立つことが完全な割当の存在条件である。ここで \(T=N(U)\) とおくと、すべての \(i\in U\) は \(D_i\subseteq T\) を満たすので \(U\subseteq I_T(D)\) となる。仮定した不等式から、
\[|U|\leq |I_T(D)|\leq c(T)=c(N(U))\]
が従う。よって Hall の条件が成立し、20 枚すべてを異なる割当枠に対応させられる。枠数の合計も 20 なので、各駒種の枠は過不足なく使われ、枚数保存則が満たされる。逆向きは、\(I_T(D)\) のすべての駒が \(T\) の枠を使わざるを得ないことから従う。これで必要十分性が示された。
Hall の定理を使う理由は、容量不足の検出を十分な条件へ引き上げられる点にある。候補が空の駒がないとしても、すべての駒へ種類を割り当てられるとは限らない。飛車と香車の容量が合計 3 枚であるのに、4 枚の駒がその 2 種類にしかなれない場合、各駒の候補は非空でも、4 枚を 3 枠へ収めることは不可能である。任意の部分集合について容量を検査する Hall の条件は、この局所的には見えない矛盾を捉える。
逆に、不等式がすべての \(T\) について成立するときは、候補が限定された駒の数が、その種類集合の容量を超えない。証明では、駒種を必要枚数だけの個別の枠へ展開している。例えば香車は別々の 2 枠を持つが、どちらの枠へ割り当てても種類としては香車である。この展開によって、容量付きの割当を通常の「各駒に異なる枠を一つ与える」問題へ変換でき、Hall の必要十分条件を適用できる。
ここで使う \(I_T(D)\) は、候補集合が \(T\) に完全に含まれる駒をすべて集める点が重要である。\(D_i=\{飛\}\) の駒も \(D_i=\{飛,香\}\) の駒も、\(T=\{飛,香\}\) に対する \(I_T(D)\) に入る。候補がちょうど \(T\) と等しい駒だけを数えると、飛車に確定した駒が容量を消費している事実を見落とす。部分集合による判定が正しいのは、候補の包含関係をこのように数えるからである。
4.3 容量を使い切ったときに候補を消せる理由
割当が実現可能な状態で、ある集合 \(T\) について \(|I_T(D)|=c(T)\) が成立したとする。このとき \(I_T(D)\) の駒だけで \(T\) の枠はすべて埋まる。\(I_T(D)\) に入っていない別の駒へ \(T\) の種類を割り当てると、容量が超過する。したがって次の候補削除は、成立する割当を一つも失わない。
\[\boxed{|I_T(D)|=c(T)\ \Longrightarrow\ D_j\leftarrow D_j\setminus T\quad(j\notin I_T(D))}\]
実は、全体の割当が一つ以上存在する場合、この形の使い切りをすべて調べれば、実現不可能な候補を漏れなく取り除ける。その逆向きを示す。\(k\in D_i\) にもかかわらず、駒 \(i\) を種類 \(k\) に固定すると残り 19 枚を割り当てられないと仮定する。固定によって種類 \(k\) の残り容量は 1 減る。残り 19 枚の割当が存在しないので、Hall の条件を破る駒種集合 \(T\) が存在し、その集合は \(k\) を含む。
固定前の局面は実現可能なので、残り 19 枚のうち候補が \(T\) に限られる駒数は高々 \(c(T)\) である。一方、\(k\) の容量を 1 減らすと割当不能になるため、その駒数は \(c(T)\) に等しい。したがって、固定対象の駒 \(i\) は \(I_T(D)\) の外におり、\(|I_T(D)|=c(T)\) かつ \(k\in T\) となる。候補 \(k\) は、まさにこの使い切りによって除外される。
これにより、次の等式が得られる。左辺は全体の可能世界から射影した正確な候補集合、右辺は使い切りの条件だけを使って局所候補から残す種類を計算した結果である。
\[\boxed{P_i(D)=D_i\setminus\bigcup_{\substack{T\subseteq K:\ |I_T(D)|=c(T)\\i\notin I_T(D)}}T\qquad(\Phi(D)\neq\varnothing)}\]
これは使い切りによる候補削除が正しいというだけでなく、容量と候補だけからなる割当問題では、使い切りを全種類集合について検査すれば正確な候補を計算できることを示す。例えば「飛・香」「飛・香」「飛」という 3 枚なら、まず飛車に確定している 1 枚が飛車の容量を埋めるため、残りの 2 枚は香車に確定する。この計算は全割当を列挙することなく成立する。
実現不可能な候補が必ずどれかの使い切りによって除外されることを、もう少し具体的に確認する。駒 \(i\) の候補 \(k\) を仮に採用すると、残りの駒が使える種類 \(k\) の容量は 1 減る。そこで残りの駒の割当が不可能になったなら、Hall の不等式に違反する集合 \(T\) がある。元の状態では割当可能だったので、この違反を生んだのは種類 \(k\) の容量を 1 減らしたことだけである。
そのため \(k\in T\) であり、\(i\) 以外で候補が \(T\) に限られる駒の枚数は、元の容量 \(c(T)\) とちょうど等しい。このとき \(i\) 自身の候補が \(T\) に完全に含まれていたら、元の状態ですでに容量超過となる。よって \(i\notin I_T(D)\) である。結局、\(T\) は \(i\) を除く駒だけで容量が使い切られた集合であり、\(i\) の候補 \(k\) を除外する条件に一致する。この逆向きの議論により、全種類集合を調べた使い切り検査には候補削除の漏れがない。
この証明の適用範囲は、各駒が一つの基本種類を取り、種類ごとに固定された枚数を割り当てる制約である。移動経路、手番、成り可能な位置といった盤面上の規則は、候補を更新する入力条件として別に扱う必要がある。したがって、使い切り検査が完全であるという結論は、ゲームのあらゆる合法手を枚数制約だけで判定できるという意味ではない。
5. 収束を計算するアルゴリズムと計算量
5.1 0-1 変数による制約充足問題
前章で示した条件を計算機で扱う一つの方法は、各駒にどの種類を割り当てるかを 0 または 1 の変数で表すことである。\(x_{ik}=1\) は駒 \(i\) を種類 \(k\) に割り当てること、\(x_{ik}=0\) は割り当てないことを意味する。20 枚の駒と 8 種類の組合せについて、合計 160 個の変数を置く。
\[\boxed{\begin{aligned}x_{ik}\in\{0,1\}\\\sum_{k\in K}x_{ik}=1 (i\in I)\\\sum_{i\in I}x_{ik}=c_k (k\in K)\\x_{ik}=0 (k\notin D_i)\end{aligned}}\]
最初の等式は各駒へ一種類だけ割り当てる条件、次の等式は駒種の必要枚数を守る条件、最後の式は候補から消えた種類を使わない条件である。すべてを満たす 0-1 変数の組が存在することと、\(\Phi(D)\neq\varnothing\) は同値である。さらに \(x_{ik}=1\) を追加しても解が存在するなら、\(k\in P_i(D)\) となる。解の存在を判定する問題と、正確な候補集合を求める問題は、このように区別できる。
0-1 変数の表現では、ある駒について 8 個の値のうちちょうど 1 個を選び、ある種類について 20 枚のうち必要枚数だけを選ぶ。この二方向の等式が同時に成立する必要がある。例えば 3 枚の小さな例で飛車 1 枚、香車 2 枚に限定すれば、割当を表す 3 行 2 列の変数表を考えられる。
\[\begin{pmatrix}x_{1,飛}&x_{1,香}\\x_{2,飛}&x_{2,香}\\x_{3,飛}&x_{3,香}\end{pmatrix}\]
各行の合計は 1、飛車列の合計は 1、香車列の合計は 2 である。すべての候補が \(\{飛,香\}\) なら、飛車列でどの行を 1 にするかの 3 通りが残る。これらの変数は確率を示す値ではなく、完全な割当の一つを表すための選択である。実際の候補の確定には、一つの解だけでなく、可能な解全体に現れる値を調べる必要がある。
この定式化は整数線形計画としても書けるが、駒と種類の間の辺しか持たず、各種類に容量があるという構造を利用すれば、一般の整数計画問題を解くより単純なネットワーク流の問題に変換できる。割当が存在するかという問いと、各候補が完全な割当に参加するかという問いを分ければ、どちらにも明確な判定手続きを与えられる。
5.2 最大流による実現可能性と候補の判定
同じ制約を、駒と駒種からなる二部グラフに変換する。入口から各駒へ容量 1、駒から候補に含まれる種類へ容量 1、各種類から出口へ容量 \(c_k\) の辺を置く。すべての駒へ種類を割り当てるには、入口から出口まで合計 20 単位の流れが必要である。
\[\boxed{\Phi(D)\neq\varnothing\ \Longleftrightarrow\ F_{\max}(D)=20}\]
\(F_{\max}\) はこのネットワークの最大流量である。流量が 20 なら全 20 枚に割当先があり、種類側の容量の総和も 20 なので各種類の必要枚数がちょうど満たされる。逆に完全な駒種割当があれば、割り当てた種類への辺に 1 単位ずつ流せるので最大流量は 20 となる。容量が整数のネットワークでは整数値の最大流が得られ、個々の流れを 0-1 変数の割当へ対応させられる。
候補 \(k\in D_i\) の実現可能性を確かめるには、駒 \(i\) を \(k\) に固定して容量を 1 消費し、残り 19 枚を割り当てられるかを判定すればよい。残りの最大流量が 19 なら候補を残し、19 未満なら候補を除外する。これは第 3 章の射影を、実際に計算する方法になっている。
最大流へ変換したグラフでは、入口 1 個、駒の頂点 20 個、種類の頂点 8 個、出口 1 個で、合計 30 個の頂点を用いる。候補がすべて残っている場合、入口から駒への辺が 20 本、駒から種類への辺が最大 160 本、種類から出口への辺が 8 本である。全部で最大 188 本の有向辺に、各段の容量を設定する。対局が進んで候補が減れば、駒から種類への辺の本数も減る。
最大流量 20 が得られれば完全割当が存在する理由は、各駒から流れる量が 1 を超えず、種類側の容量の合計が 20 である点にある。整数容量の最大流では、各辺の流量を整数に選べるため、駒から種類への流量 1 をそのまま割当として読める。一方、駒を特定の種類へ固定した場合には、その種類の容量を一つ消費する。残る 19 枚について最大流量 19 が得られるかを調べれば、候補一つの実現可能性が分かる。
候補一つごとに最大流を解き直す方法は構造が明快である。初期状態では候補の組合せは最大 160 個なので、基本となる完全割当の判定と、候補ごとの固定判定を行えばよい。ただし、そのまま実装すると最大流計算を何度も繰り返す。大域的な個数制約を対象とするアルゴリズムは、残余グラフなどの構造を利用し、候補の支持をまとめて調べることで重複計算を減らす。
5.3 全 255 種類の集合を検査する正確な収束計算
駒種は 8 種類なので、空集合を除く部分集合は \(2^8-1=255\) 通りである。候補集合が空である駒は、あらかじめ局所矛盾として検出する。それ以外については、第 4 章の必要十分条件と候補削除の式により、次の手順で実現可能性と正確な候補集合を計算できる。
| 工程 | 計算内容 | 数学的な判定 |
|---|---|---|
| 集合を選ぶ | 駒種の非空部分集合 \(T\) を 255 通りすべて調べる。 | 空候補があれば矛盾とし、なければ容量 \(c(T)\) と候補が \(T\) に限られる駒の集合 \(I_T(D)\) を求める。 |
| 矛盾を調べる | \(|I_T(D)|>c(T)\) を満たす集合を探す。 | 一つでも存在すれば、Hall の条件により完全な割当は存在しない。 |
| 使い切りを集める | \(|I_T(D)|=c(T)\) となるすべての集合を記録する。 | 集合外の駒には、\(T\) の種類を割り当てる余地がない。 |
| 候補を更新する | 各駒について、参加していない使い切り集合の種類を候補から除外する。 | 第 4 章で証明した等式により、正確な候補集合 \(P_i(D)\) が得られる。 |
この方法は、全割当の約 4,190 億通りを走査する計算とは異なる。駒種数を \(m\)、駒数を \(n\) とすると、各集合について全駒の候補がその集合に含まれるかを調べる素朴な実装でも \(O(2^m nm)\) 時間で済む。8 種類を 8 ビットの集合として表し、包含判定をビット演算で行えば、固定長の機械語上では \(O(2^m n)\) 回程度の基本操作で各集合を検査できる。\(m=8\)、\(n=20\) では 255 集合の走査が中心となる。
正確な候補 \(P(D)\) を一度求めれば、同じ局面に対する再計算は結果を変えない。第 3 章の冪等性がその理由である。一方、候補削除を使い切り一件ずつ逐次適用する実装では、削除後に別の使い切りが見つかることがあるため、更新が止まるまで繰り返す方法もある。全候補は最大 160 個であり、実現可能な局面では各駒に少なくとも 1 候補が残るので、候補を厳密に減らす更新は高々 140 回で停止する。これは同じ局面に対する候補削除の回数の上限であり、対局の手数の上限を意味しない。
空候補の有無を最初に検査したうえで行う 255 通りの検査では、各候補集合を 8 ビットで表せる。例えば飛車と香車のビットだけを立てた集合 \(T\) について、駒 \(i\) の候補がその集合に完全に含まれるかを調べるには、\(D_i\cap T=D_i\) を判定すればよい。これにより、候補が \(T\) に限られる駒数 \(|I_T(D)|\) を数えられる。容量 \(c(T)\) も 8 種類の必要枚数から計算できる。
例えば \(T=\{飛,香\}\) のとき、候補が \(\{飛\}\)、\(\{香\}\)、\(\{飛,香\}\) の駒はすべて \(I_T(D)\) に数えられる。合計が 3 枚なら使い切り、4 枚なら矛盾となる。使い切りの場合、その集合に含まれていない各駒から飛車と香車を除外する。候補集合の全組合せを列挙する処理ではなく、固定された 255 集合について包含判定と個数比較を繰り返す処理である。
計算量の \(O(2^m nm)\) は、駒種数 \(m\) を変化させたときの上限である。種類数が固定された量子将棋では \(m=8\) なので、検査対象は最大 255 集合に固定される。駒数 \(n=20\) も固定されているため、通常の計算複雑性における入力規模の増大とは事情が異なる。約 4,190 億通りの割当という数値と、255 集合の検査という数値を比較するときは、前者が完全割当の個数、後者が制約を調べる集合の個数であることを区別する必要がある。
5.4 公開実装と大域的な個数制約
開発者が 2025 年 11 月に公開した解説に掲載された実装では、動きと成り・捕獲による候補の絞り込みに続いて、候補が同じ駒をグループ化し、使い切りを検出して候補を再構築する。駒種 8 種類の非空部分集合 255 通りをすべて直接調べる代わりに、局面に実際に現れている候補集合から検査対象を構成する方式が採られている。具体的な処理は、開発者の公開コードとその解説で確認できる[5]。
制約プログラミングでは、各値の出現回数に下限と上限を指定する条件を大域的な個数制約と呼ぶ。量子将棋の枚数保存則は、各種類の下限と上限をともに \(c_k\) とした場合に相当する。Régin は 1996 年、フローに基づいて大域的な個数制約の一般化アーク整合性を実現する方法を示した[6]。ここでいう整合性は、残された各候補について、その候補を採用する完全な割当が少なくとも一つ存在する性質である。
三つの方法は同じ割当問題の異なる計算表現である。使い切りの列挙は容量が埋まる部分集合を直接調べ、最大流は完全な割当の存在を判定し、大域的な個数制約のフィルタリングは全候補の実現可能性を効率的に評価する。一般の制約充足問題はより広い構造を扱うが、量子将棋の駒種配分だけを取り出すと、容量付き二部マッチングという解きやすい形になる。
2025 年 11 月に解説された実装が候補集合のグループ化を利用するのは、実際の対局で現れている候補の種類だけを計算の対象にできるためである。例えば 20 枚のうち 15 枚がまだ初期状態の候補のままで、残る 5 枚だけに制約が付いているなら、情報を持つ候補の組合せを中心に処理できる。ただし、これは検査対象を作る方式の違いであって、使い切りが正しい理由は Hall の容量条件にある。
収束計算で混同しやすいのは、完全割当を一つ見つけたことと、各駒の種類が決まったこととの違いである。飛車と香車の 3 枚に対して、最大流は例えば \((飛,香,香)\) という一つの解を返せる。しかし \((香,飛,香)\) と \((香,香,飛)\) も成立するなら、どの駒も自分の種類を一つに確定できない。正確な収束には、すべての候補が少なくとも一つの完全割当で支持されているかを判定する必要がある。
6. 盤面と持ち駒を含む状態遷移を定式化する
6.1 状態に必要な情報
駒種の割当だけでは、実際の対局の合法手を判定できない。盤上の駒の位置、持ち駒、成り、手番が移動の可否を左右するからである。40 枚の駒に一意な識別子を付け、駒 \(i\) の初期陣営を \(\sigma(i)\in\{先,後\}\) とする。この値は対局を通じて固定する。一方、現在の所有者、盤上の位置または駒台上の所在、成り状態は指し手ごとに変化する。
時刻 \(t\) の対局状態を次の組で定義する。\(B_t\) は盤上の配置と各駒の所有者、\(H_t\) は持ち駒とその所有者、\(R_t\) は各駒の成り状態、\(\tau_t\) は手番、\(D_t\) は 40 枚の候補集合である。初期陣営情報 \(\sigma\) は駒の識別子に固定して保持する。
\[\boxed{S_t=(B_t,H_t,R_t,\tau_t,\sigma,D_t)}\]
先手由来の駒に関する可能世界は \(\Phi_{先}(D_t)\)、後手由来の駒に関する可能世界は \(\Phi_{後}(D_t)\) とする。両者はそれぞれ 20 枚と所定の枚数配分を用いて計算する。持ち駒に移った後手由来の駒も、\(\Phi_{後}\) の変数として扱い続ける。正確な候補 \(P_i(D_t)\) は、所属する初期陣営の可能世界から射影して求める。
盤上の駒を 40 枚の固定された識別子で追跡する理由は、捕獲と打ち直しによって位置と所有者が変わるためである。例えば、後手が最初に持っていた番号 \(j\) の駒を先手が取ったとき、\(B_t\) からその駒が消え、\(H_t\) では先手の持ち駒として現れる。ただし \(\sigma(j)=後\) は維持される。このとき番号 \(j\) の基本種類の候補は後手由来の 20 枚に課された制約によって決まり、先手の 20 枚の必要枚数を消費しない。
成り状態 \(R_t\) を別に持つことで、同じ基本種類でも移動できる方向を区別できる。成っていない飛車と龍では、斜め 1 マスへの移動能力が異なる。候補の更新では基本種類が何であるかと、現在の成り状態でその手を実現できるかを組み合わせて判定する。また、持ち駒を打つときには通常の駒として盤へ戻すので、成り状態の更新も必要となる。こうした規則を状態の各成分へ割り当てることで、数学上の変数の意味が指し手ごとに変わらないようにできる。
状態 \(S_t\) に含まれる \(D_t\) は、その時点までに操作から得られた候補制約である。そこから初期陣営別に計算する \(\Phi_{先}\) と \(\Phi_{後}\) は、全体の割当が存在するかの判定に用いる。したがって、盤上の位置を変更する処理と、基本種類を制約する処理を別々に記述しても、それらは同じ指し手 \(u\) の入力を使って連動する。
6.2 指し手が加える条件を定義する
指し手 \(u\) を、駒の識別子、移動元または駒台、移動先、成りの選択、捕獲対象によって表す。盤面上の障害物、手番、持ち駒の所有権、成りを選択できる位置に加え、現在の正確な候補集合 \(P_i(D)\) に基づく確定二歩禁など、指し手の受理に必要な規則を \(G(S,u)\) とまとめる。さらに、指し手に伴って各駒へ追加される基本種類の条件を \(E_i(S,u)\subseteq K\) とする。影響しない駒では \(E_i(S,u)=K\) である。
例えば、前方へ 2 マス動いた駒には \(E_i=\{飛,香\}\)、取られた駒には \(E_j=K\setminus\{王\}\) が課される。成りを選んだ駒には \(K\setminus\{王,金\}\) が加わる。同じ指し手で複数の条件が生じる場合には、その共通部分を \(E_i\) とする。こうして更新後の候補集合 \(\widetilde D\) を定義する。
\[\boxed{\widetilde D_i=D_i(t)\cap E_i(S_t,u)\qquad(\forall i)}\]
ここでの更新は駒の初期陣営をまたぐことがある。移動する駒 \(i\) の条件は、その駒の初期所属 \(\sigma(i)\) に対応する \(\Phi_{\sigma(i)}\) で評価し、捕獲対象 \(j\) の条件は \(\Phi_{\sigma(j)}\) で評価する。例えば先手が後手から取った駒を盤上へ打つ場合も、その駒の候補更新は後手の初期陣営に属する 20 枚の制約に反映される。所有者だけを見て候補をまとめると、二つの初期陣営の容量制約が混ざってしまう。
具体例として、先手が先手由来の駒 \(i\) を前方へ 2 マス動かし、その移動先にある後手由来の駒 \(j\) を取る場合を考える。成りを選ばないなら、移動する駒へ \(\{飛,香\}\) という条件が加わり、取られた駒へ \(K\setminus\{王\}\) という条件が加わる。更新後には先手由来の 20 枚について \(\Phi_{先}(\widetilde D)\) を、後手由来の 20 枚について \(\Phi_{後}(\widetilde D)\) をそれぞれ計算する。
移動経路が空いていても、先手側で飛車と香車の枠がすでに使い切られていれば、その指し手は成立しない。同時に、後手由来の駒 \(j\) が王の候補しか持たなければ、捕獲は終局の条件として評価される。反対に、\(j\) に王以外の種類が残るなら、後手側の候補から王を除いた後でも完全割当が成立するかを確認する。局所条件を二つの初期陣営に適用するという計算は同じでも、王に確定した駒の捕獲だけは結果が終局になる。
操作を構成する各判定の順序にも意味がある。手番や盤面の基本的な禁止条件を満たしたうえで、指し手による候補集合を更新し、王に確定した駒を取ったかどうかにより終局と通常遷移を分ける。通常遷移なら両初期陣営の可能世界が非空であることを要求する。王の捕獲なら、捕獲対象について王の候補を除外した状態を作らず、移動側の成立性を確認して勝利を返す。これらの条件を組み合わせることで、\(S_{t+1}=F(S_t,u_t)\) を、合法性と終局を区別する状態遷移の数理的な枠組みとして具体化できる。
6.3 合法手・終局・次状態の分岐
通常の指し手が成立する条件は、盤面上の操作が許されることと、更新後も先手由来・後手由来の双方について完全な駒種割当が存在することである。現行ルールの確定二歩禁も \(G(S,u)\) の一部として判定する。更新後の必要条件をまとめると、
\[\boxed{\operatorname{Legal}_{通常}(S,u)\ \Longleftrightarrow\ G(S,u)\ \land\ \bigwedge_{s\in\{先,後\}}\Phi_s(\widetilde D)\neq\varnothing}\]
となる。ただし、王に確定している駒を取る操作は終局の分岐で処理する。捕獲対象を \(j\)、指している側を \(\tau\) とすると、指し手前の正確な候補が \(P_j(D_t)=\{王\}\) であれば、その駒を取った側が勝利する。この場合、取られた駒から王の可能性を除外すると矛盾になるため、終局判定ではその除外条件だけを適用しない。一方、捕獲する側の駒については、移動能力や成りの条件と矛盾しないことを確認する必要がある。
そこで、\(\widehat D\) を今回の移動と成りによる条件を適用した候補集合とし、捕獲対象から王を除く処理だけを保留したものとする。王の確定した駒を合法に捕獲できる条件は、盤面条件 \(G(S,u)\)、\(P_j(D)=\{王\}\)、および \(\Phi_s(\widehat D)\neq\varnothing\) が両初期陣営で成立することである。相手の駒が王に確定していても、自分の駒がその位置へ合法に移動できなければ勝利とはならない。
王捕獲の合法性は、次の条件で定義する。
\[\boxed{\operatorname{Legal}_{王取}(S,u)\ \Longleftrightarrow\ G(S,u)\land\operatorname{Capture}(u,j)\land P_j(D)=\{王\}\land\bigwedge_{s\in\{先,後\}}\Phi_s(\widehat D)\neq\varnothing}\]
公式ルールの個別条件を \(G\) と \(E_i\) に集約すると、状態遷移 \(F\) の数理的な骨格は次の場合分けで定義できる。\(\operatorname{Apply}\) は盤上の駒の移動、持ち駒への移動、成り状態、所有者、手番の更新をまとめた関数である。
\[\boxed{F(S,u)=\begin{cases}\operatorname{Win}(\tau), & \operatorname{Legal}_{王取}(S,u)\\\operatorname{Apply}(S,u,\widetilde D), & \operatorname{Legal}_{通常}(S,u)\\\bot, & \text{それ以外}\end{cases}}\]
ここで \(\operatorname{Legal}_{王取}\) は直前に定義した王捕獲の条件を表し、\(\bot\) は指し手が成立しないことを表す。最初の分岐では捕獲した側の勝利が確定し、通常の収束判定には進まない。二番目の分岐では盤面と持ち駒を更新し、手番を交代した次状態が得られる。第三の分岐では、移動経路の違反、成りの条件違反、候補の矛盾などを理由に指し手を受理しない。ここで \(G\) と \(E_i\) は公式の個別規則を集約した関数であり、上の式はそれらを組み合わせる状態遷移の数理的な骨格を与える。
状態遷移を数学的に定義すると、通常遷移を受理するための論理式と、終局のための論理式が分離される。\(\operatorname{Legal}_{通常}\) は、移動・捕獲後の局所条件をすべて反映した \(\widetilde D\) について、両初期陣営の可能世界が非空であることを要求する。これに対して \(\operatorname{Legal}_{王取}\) は、捕獲対象の王確定を指し手前の正確な候補で判定し、王を除外する前の \(\widehat D\) について移動側の成立性を確認する。
例えば、後手由来の駒 \(j\) が王に確定していた場合、通常捕獲と同じように \(K\setminus\{王\}\) を \(D_j\) へ適用すると、候補が空になる。これは通常遷移としては矛盾だが、量子将棋の勝利条件に該当する局面である。そのため、終局分岐では \(j\) への王除外を保留する。反対に、移動した自分の駒の候補が空になるような手は、相手の王を取る形に見えても合法な移動として受理できない。勝利条件の判定と、自分の移動能力の判定を両立させる必要がある。
6.4 更新に伴う数学的性質と適用範囲
通常の指し手で追加される駒種条件は候補集合との共通部分として定義される。そのため、初期陣営 \(s\) の割当集合について \(\Phi_s(D_{t+1})\subseteq\Phi_s(D_t)\) が成立する。取った駒を別の側が操作しても、初期所属が固定されている限り、この包含関係は維持される。一方、盤面配置 \(B_t\)、持ち駒 \(H_t\)、手番 \(\tau_t\) は移動や捕獲によって変化し、単調減少する対象ではない。
このモデルが直接表している未確定性は駒の基本種類に関するものである。移動経路や駒の位置といった盤面の規則は \(G\) に、種類に応じた動きや成り・捕獲による候補の制約は \(E_i\) に置かれる。実際の対局では王手放置を許し、二歩は確定二歩禁の範囲で判定するため、両陣営の駒種割当そのものは初期所属ごとの二つの制約系に分けて計算できる。ただし、捕獲の可否や移動経路は盤面を介して両者の操作に関係する。駒種の割当問題と、対局のすべての合法手を表す問題は、同一ではない。
状態の成分ごとに、どの性質が保存されるかは異なる。初期所属 \(\sigma\) と各駒種の必要枚数 \(c_k\) は対局を通じて不変である。局所候補 \(D_i\) と、そこから得られる正確な候補 \(P_i\) は、追加された条件によって縮小する。一方、盤面 \(B_t\) と持ち駒 \(H_t\) は、取る、打つ、動かすという操作によって内容が増減する。候補集合の単調性を盤面上の利きや手番にまで広げて理解することは適切ではない。
この区別は、ゲームの「収束」という語の範囲を明確にする。基本種類の候補は一度削除されると復活しないが、成った駒が取られれば打ち直しにより移動能力は変化する。盤上で可能な移動は局面によって増減しても、基本種類に関する可能世界の更新は包含関係に従う。これら二つの変化を別の状態成分として持つことで、実装の挙動と数理モデルの性質を取り違えずに済む。
7. 未確定な駒種と確定した制約から何が導けるか
量子将棋の数理モデルでは、指し手が局所候補 \(D_i\) を絞り、その条件が初期陣営 20 枚の割当集合 \(\Phi(D)\) を縮小させる。正確な候補 \(P_i(D)\) は、その割当集合の射影である。これにより、盤面上で直接動かしていない駒の可能性が減る理由を、共有された枚数制約から説明できる。
数学的に得られた結果は三つある。第一に、指し手によって追加された駒種の条件は、可能世界と正確な候補を単調に縮小させる。第二に、Hall の条件は駒種の割当が存在するための必要十分条件であり、容量を使い切る集合が候補削除の根拠になる。第三に、全種類集合について使い切りを検査すれば、実現不可能な候補をすべて取り除ける。そのため、約 4,190 億通りの初期割当を列挙せず、8 種類の候補と容量の関係を計算すればよい。
これらの性質は、未確定な値を確率的に選ぶ処理を必要としない。\(\Phi(D)\) は成立する割当の集合であり、個々の割当に確率を付与したものではない。現行ルールで行われるのは、新しい条件を満たす割当だけを残す決定論的な更新である。初期所属の枚数は固定され、駒の正体だけが未確定という非対称性が、連鎖的な収束を生む。
同じ構造は、担当可能な仕事が人ごとに異なり、仕事ごとの必要人数が固定された配置問題にも現れる。候補集合が一つに確定する前に、担当者の集団が特定の仕事の枠を使い切る場合がある。既稿「未整理の条件を、判断できる形に変える」は、条件を判断可能な形式へ落とし込むという観点で、この数理化と接続する[7]。また、既稿「知能を成立させる情報の置き場所を設計する」で扱った、与えられた構造が取り得る解を制限するという論点にも関係する[8]。ただし、量子将棋で示した容量付き割当の定理を直接適用できるのは、各対象に一つの値を割り当て、値ごとの容量を共有する構造である。
量子将棋を特徴付けるのは、駒の基本種類が未確定でも、初期陣営の枚数配分が確定していることである。飛車と香車にしかなれない 3 枚が、飛車 1 枚と香車 2 枚の全容量を占めた瞬間、ほかの 17 枚はそのどちらにもなれなくなる。これは単なる例示ではなく、Hall の定理から導かれる必然的な帰結である。各駒が何になれるかを決めるのは、個々の移動履歴と、20 枚全体で何が同時に成立し得るかという二つの条件の交点なのである。
参考文献
- 将棋ったー, 量子将棋. https://shogitter.com/rule/108
- na2hiro, 量子将棋のルール詳解 (2025-10-31). https://na2hiro.hatenablog.com/entry/2025/10/31/量子将棋のルール詳解
- na2hiro, 量子将棋の収束アルゴリズム (2025-11-08). https://zenn.dev/na2hiro/articles/10fc62c3141c55
- P. Hall, On Representatives of Subsets (1935-01). https://doi.org/10.1112/jlms/s1-10.37.26
- na2hiro, 量子将棋アルゴリズムのコード. https://gist.github.com/na2hiro/af70792beb897c092a970904b8d3db25
- Jean-Charles Régin, Generalized Arc Consistency for Global Cardinality Constraint (1996). https://cdn.aaai.org/AAAI/1996/AAAI96-031.pdf
- id774, 未整理の条件を、判断できる形に変える (2026-07-04). https://blog.id774.net/entry/2026/07/04/4935/
- id774, 知能を成立させる情報の置き場所を設計する (2026-10-04). https://blog.id774.net/entry/2026/10/04/5695/