到達可能なチェス局面で218手を超える合法手を持つものは存在しない

 (lichess.org)
1 ポイント 投稿者 GN⁺ 2025-09-27 | 1件のコメント | WhatsAppで共有
  • 1964年にNenad Petrovićが発表した218手のチェス局面より多くの手を指せる局面は存在しない
  • すべての局面を探索することは現実的に不可能なため、数学的最適化とコンピュータによるモデリング手法を用いて上限を証明した
  • 不要な駒の除去、部分的な駒配置の許容、キャスリングの単純化などにより探索空間を効果的に削減した
  • 最終的にGurobi最適化ツールで218手が最大であることを確認し、144手（プロモーション除く）などの記録も追加で検証した
  • この研究により、チェスエンジンや圧縮の開発者は最大手数制限に関する不確実性を解消できるようになった

序論: 218手チェス局面をめぐる論争

1964年にチェス作曲のグランドマスターNenad Petrovićが218手の局面を発表して以来、この記録を破ろうとする試みが続いてきた。筆者は計算機科学者として、あらゆる局面をコンピュータで分析し、この問いに決着をつけようとした。到達可能なチェス局面は約4.8 × 10^44個存在するが、それほど膨大な探索は現実的ではない。

数学的最適化の導入

不要な駒および組み合わせの最小化

  • チェス盤上で黒駒が追加的に手数を増やすケースは限られている
    • 白ポーンが取れるようになる場合や、相手キングへのチェック状態を回避する場合など
  • ほとんどの黒駒は取り除いても最大手数に影響しない
  • 駒数が許す限り、黒駒を弱い駒に置き換えることや、一部の制約条件（ピンなど）の下で配置を調整することができる
  • 一方で白駒については、最適局面を作るためにクイーンなどの強い駒にすべて置き換えると非合法局面になる可能性があるため、細かな調整が必要である

チェック状態と手数の制限

  • 黒キングがチェックされている状態は合法局面ではないため、考慮する必要がない
  • 白キングがチェックされている場合は動きが大きく制限され（最大120手）、218手には絶対に到達できない
  • したがって、チェックのない局面だけを対象に探索すればよい

部分的な駒配置と数学的モデリング

組み合わせの複雑さを減らすため、部分的（fractional）な駒配置や移動、さらに一部のチェス規則を緩和したモデルでアプローチした。

  • たとえば、ある駒が27.3%の確率でe4にあり、72.7%は別の位置に存在するという形で表現する
  • この方法により、Gurobiなどの最新の最適化ツールで**整数計画法（ILP, Integer Linear Programming）**として実装した
  • 当初はメモリと時間の限界（約5万5千秒後にメモリ不足）に直面した
  • 探索空間を簡素化するため、キャスリング規則、チェックの無視、ピンの無視、アンパッサン条件の単純化などの追加措置を適用した

最適化と結論

最終的に、不要な組み合わせ探索を遮断する補助制約条件の導入などでモデルを改善し、Gurobiプログラムによって最適化を完了した。

  • 305手 → 271.67手 → 218手と上限を段階的に絞り込んだ
  • 代表的な12個の218手可能局面だけが到達可能であることを確認した
  • これらの局面は、証明ゲーム（proof game）によって無理なく到達可能な合法局面であることも証明された

また、プロモーションなしの最大144手、非合法局面での最大288手、到達不能な合法局面での271手という記録も検証を完了した。

結果と意義

  • この研究結果により、チェスエンジン開発者や圧縮アルゴリズム研究者は、メモリ設計などで256手制限で十分だと確信できる
  • 合法的な経路で218手以上を指せる局面は存在しないことが数学的に証明された

FAQ要約

  • チェスの対局自体は218手より長くなりうるが、本研究が扱うのは「1ターンで可能な選択肢」の最大数である
  • 一部の局面が到達不能に見えるとしても、直前の手が取りで終わる場合など複数の経路があると述べている
  • この研究手法は、膨大な組み合わせ空間において「絶対に不可能な組み合わせ」を素早くふるい落とす数学的オラクルの手法を適用している
  • 使用したコードと導出された証拠の数学的妥当性まで公開し、信頼性を確保した

今後の課題と追加研究の提案

この手法を応用すれば、「最多捕獲手数」「最多ステイルメイト」「最多チェック」「最多チェックメイト」「最多2手メイト」など、さまざまなチェス問題に挑戦できる。ただし、一部のケースでは別個の創造的な最適化アルゴリズムが必要になる可能性がある。

結論

  • 218手が、チェス局面において1ターンで指せる最大の公式手数である
  • 実用面では、チェスソフトウェアや研究者は218（または256）に合わせて構造を設計できる
  • 関連コードと最適化結果はGitHubで公開されている

参考

  • Nenad Petrovićの218手局面、Jenő Bánの144手（プロモーションなし）など、証明ゲームと局面へのリンクを含む
  • 詳細な説明とコードはGithubリポジトリで確認できる

関連記事

1件のコメント

 
GN⁺ 2025-09-27
Hacker Newsのコメント
  • 彼らは明示的にはそう書いていないが、ここで言っているのは「この局面でプレイヤーが選べる合法手が218手ある」という意味だ
    • これまでこの記事をずっと読み違えていたことに驚いた、ありがとう。私は「あるチェス局面に到達するまでに必要な最大手数が218手だ」と理解していた。だから、なぜこの記事がまったく理解できなかったのか不思議だった
    • 私も「この局面に到達するには対局で何手必要なのか？」と考えていた
    • そう、記事中で "possible moves"（可能な手）という表現が一度も出てこないのは本当に奇妙だ。キーワードは "possible" だ。記事ではずっと "have moves" のように書いているが、一般の人にはなじみのない言い方だ（チェス用語ではより一般的なのかもしれない）
    • ありがとう。この記事について混乱していて、唯一「最も多くの手数を必要とする局面」の話だと思っていた
  • Lichessはぜひ称賛したい。素晴らしいサービスとコンテンツを無料で提供していて、Chess.comで有料の機能も無料で使える。さまざまな変則ルールのゲームも本当に多い
    Lichessでは960やCrazyhouseのような変則チェスのプレーレベルはChess.comよりずっと高い
    • 無料で、商用サーバーと同等の機能を備え、オープンソースで開発者フレンドリーだ。広告もなく（無料アカウントにも一切広告がない）、フランス法の下で透明な組織構造を持っている
      文字どおりばかげているほど素晴らしい。可能なら寄付を勧める
  • https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow の記事では、著者が初期段階で複雑なルールの一部を外し、必要になった場合（解の結果がそのルールに違反した場合）に再導入する意思があると説明している
    興味深いことに、混合整数線形計画法（MILP）ソルバーはすでにこうした処理をサポートしている。専門用語では 'row generation' と呼ばれ、通常はこの問題を行列形式で書いたときに、行が制約条件、列が変数であることからそう呼ばれる
    （動的に）新しい行を追加することは、違反が起きた場合にだけ制約条件を導入するのと同じだ
    この方法は主に巡回セールスマン問題（Traveling Salesman Problem）の解法で使われる
    （ちなみにWikipediaには Column generation はあるが row generation はない）
    • こんにちは、Lichessの記事の著者です
      チェスルールを緩和したり省略したりすることは、変数選択にも影響しました。数理モデリングに入る前に、lazy constraints のようなものも試しましたが、有意な速度改善はありませんでした。たとえば白のキングがチェックされているかどうかを考慮しないだけでも、多くの単純化が起きました
    • こういうやり方は、普通は lazy constraints と呼ばれることのほうが多いです（説明）
    • MILPソルバーが（この途方もない探索空間で）本当に終了できるのか気になる。私の予想では無理だ
  • 純粋な興味からの質問です。Gurobiの整数計画ソルバーが218より良い解を見つけられなかった場合、それは218を上回るより良い解が存在しないことを保証するのだろうか？ そして、それは数学的証明と同等なのだろうか？
    （前提として、Gurobiにバグがなく、著者の問題定義と実装にもバグがないとする）
    Gurobiが局所最適に陥っている可能性があるのか、それとも本当に大域的最適解であることを証明したのかが気になる
    • Gurobiは、これまでに見つかった最良の整数解だけでなく、可能な最適解の境界値も提供する。この境界値には、問題の線形緩和やカッティングプレーンなど、さまざまな手法が使われる。だからソルバーにバグがなければ、本当に最適解だ
    • 著者です！
      Gurobiと私のコードが意図どおりに動作し、チェスモデルの簡略化の過程に論理的誤りがなかったなら、私の結果は「初期局面から合法な手順で到達可能なチェス局面における合法手数の最大値について、上界も下界も218である」ことを証明したことになる。つまりGurobiが探索空間全体について、これ以上良いものはないと境界によって立証したわけだ
    • Gurobiが具体的にどう適用されたのかは分からないが、一般にこうした組合せ最適化ソルバーは、どんな変数割り当ての場合でもそれ以上良い解は見つからないことを示す証明木を構築する。単純な場合なら、実際にその木を自分で確認して背理法の流れを追うこともできる。この記事のケースでは、その証明木は途方もなく大きいはずだ。望むなら検証は可能だ
    • 理論上は証明ではないが、実際には証明とほとんど同じだ

  • 到達可能なチェス局面のうち、218を超える手はない
    「次に指せる合法手は218手以下である」と書いたほうがずっと明確だろう

約8.7x10^45個の到達可能なチェス局面をすべて確認？
この数値は実際には過大評価だ
https://github.com/tromp/ChessPositionRanking では、合法なチェス局面数を約4.8x10^44と、より正確に見積もっている

  • その推定値って、単に20倍くらいの違いじゃない？ このスケールでは大差ない気もする
  • 片方は「合法な」局面で、もう片方は「問題空間全体」だ
    計算の観点では、問題空間全体のほうが重要だ。合法かどうかを判定する前に、まず全部を「計算」しなければならないからだ。合法な局面だけを単純に列挙する方法はない
  • みなさんこんにちは
    知人からの連絡で、私の記事がここで議論されていることを知りました
    分かりにくいタイトルを付けてしまってすみません。今はもう明確になっているとよいのですが。フィードバックと温かい言葉に感謝します
    この手のチェスに関する事実の証明について、ほかにも質問があればお答えできます ^^
    ありがとうございます
    Tobi
    • では確認ですが、すべての盤面局面について、選べる手は218を超えないという意味ですか？ これで正しい理解でしょうか？
  • 到達可能なチェス盤面を表現するのに必要な最小ビット数はいくつだろう？
    更新: 記事では到達可能なチェス局面は約8.7x10^45個あるとされており、https://github.com/lechmazur/ChessCounter はこれを上界としている
    （これは約153ビットに相当する）
    • 約4.8x10^44なら、それを log2(4.8x10^44) で計算すると149ビットだ
      ただし効率よくデコードするには、ChessPositionRankingプロジェクトが推奨する数値（8726713169886222032347729969256422370854716254）の log2 の切り上げ値として153ビットが必要になる。ChessCounterは効率的なデコードコードを提供していない
    • キングは64マスのどこにでも行ける
      ルーク／クイーン／ナイトも同様だが、チェスでは取られている可能性があるので、各5個の駒ごとに計65状態が必要だ
      ビショップはその半分の色のマスにしか行けないので、それぞれ33状態
      ポーンは4種類のプロモーション、取られた状態、さらに状況によるがだいたい20〜30ほどの位置候補があるので、全体としてポーン1個あたり約290状態になる
      これで片方の色の駒配置を表すのに約112ビット、丸めると両側合わせて224ビット必要になる
      アンパッサン（En Passant）やキャスリング制約（キャスリング不可など）は、丸め方次第では追加ビットなしで、各駒に数状態加えるだけで済む
      これがおそらく固定長の盤面表現としては最も圧縮された形だ
      疎な表現なら、2つのキングは常に存在するので、生き残っている駒を n 桁の10進数と n+2 個の64ビット数で位置表現し、キャスリングやアンパッサンなどは少し追加情報が必要になる。駒の半分程度が消えている平均的な場合、盤面状態の表現には約180ビットかかる
      手の履歴も1手あたり約10ビット必要（黒白1組、1 ply は5ビット）なので、18手程度までなら持てる。これは平均的なチェスの対局長の中間点よりやや短い
      さらに圧縮するには、とてつもなく大きな辞書を実装する必要がありそうだ
    • 駒の種類と色は4ビットで表現できる
      だから盤面全体を固定長でエンコードするなら 644=256ビット=32バイトだ
      あるいは駒だけの可変長表現なら、各64マスのインデックスを6ビットとして、駒数      10ビットになる
      たとえば初期配置は 32*10=320ビット=40バイトだ
    • そのGitHubの 8.7e45 の "restricted" 値は、一部のポーン昇格パターンを制限している
      5.68e50 の "general" が真の上界で、あらゆる可能な昇格を許している
  • b2にいる黒ポーンが、ほかの駒の可能な手をかなり減らしている
    そのポーンにはたった1つの手（隣のナイトを取ること）しかない。もしそのポーンがなければ、4つの白クイーンとナイトがb2に入れる。だが実際には黒キングはすでにチェックメイトなので、そのような手は実際には存在しえない
    e5のクイーンを別の場所に置いて即座にチェックメイトにならないようにしつつ、b2マスをもっと開放したくなる
    追記: そのポーンはステイルメイトを防ぐためにそこに生き残っていなければならない気がする
    • b2の黒ポーンは、White to move（白番）の局面では動けない
      黒番だとしても、e5の白クイーンによってキングがピンされているので、やはり動けない。もしピンされていなければ4通り動ける。アンダープロモーションも可能だ
    • 私も「黒の駒が役に立たない」という表現で混乱した。クイーン2枚を向かい合わせにする代わりに、片方を黒にして互いに取り合える手を作れそうだと思ったが……結局「動けるのは片側だけだ」と気づいた
    • 著者です
      この局面は White to move です。たとえb2のポーンが白クイーンによってキングをピンしていなかったとしても、黒ポーンは動けません
      b2のポーンは、黒キングをチェックから守るために絶対に必要です。そうでなければ局面自体が合法ではありません
      すべて本当に入念に確認したので安心してください。白の手数を218超にしようとする試みは不可能でした。それでも多くの方が私の記事に関心を持ってくれて驚き、感謝しています、はは ^^
    • 白番です。黒がチェックされている状態で白番なら、その局面は合法ではなく到達不能だ。直前の黒番で合法的にその状態を作ることができない
      黒ポーンの1つを白ナイトに変えて手数を増やせそうだが、すでにナイトは2枚ともあり、すべてのポーンが昇格済みなので不可能だ。（両方のポーンを変えると、黒が前の手でこの状態に到達することが不可能になる）
  • 混乱している。271手のモデルのあと、どんな変更で最適解が得られたのか気になる。「この改善されたモデルで…」としか書かれていない
    • 著者です！
      記事全体を読みましたか？
      271ではなく 271.666... です :) この値は、すべての決定（0か1か）を連続値（0.0〜1.0やその間の値）に緩和したモデルから出ています。つまり、ある駒が0.23個存在すると仮定できるわけです。ある手を指せる確率も0.843のように扱えます。
      こうした一種の「ブラックマジック」を使うと計算がずっと速くなり、実際より多い手数を出せます。
      そのため、この方法を使えば、見込みのない部分空間を素早く排除できます。こういうテクニックがなければ、探索空間全体を総当たりするのは不可能です
  • 私が何か見落としているのでしょうか。それとも最初に示された局面自体、実際には到達不能なのでは？ 白番なのに、黒ポーンが開始位置にあり、キングには隣接する空きマスもなく、駒とポーンに囲まれているので、この局面には到達できないように見える
    • その局面が実際に到達可能である証明はこちらにある: https://lichess.org/study/PLtuv3v5/zWPNxbSA
      ちなみに、黒ポーンが開始位置にあると誤解しているようだが、実際には黒ポーンは盤の反対側まで進んでいる（白陣側）
    • 黒ポーンは白陣（1〜2段目）にいる