218手を超える到達可能なチェスの局面は存在しない

概要

・チェスで「最も多くの手数が可能な局面」を探す試みについて解説・218手という記録が1964年にPetrovićによって発表され、それ以上の局面は存在しないと証明・計算量の膨大さから直接全探索は不可能、数学的最適化とアルゴリズムを駆使・Gurobiなどのソルバーを利用し、上限を厳密に証明・他の関連記録や今後の課題にも言及

チェスの「最大手数局面」探求の歴史と証明

1964年、 Nenad Petrović が 218手 のチェス構成問題を発表
以来、多くの研究者が より多い手数の局面 を探してきたが、記録更新はなし
近年、 コンピュータサイエンティスト として 計算機 を用いてこの問題に挑戦
全ての到達可能な局面 （約8.7×10^45）を調べるのは現実的に不可能
数学的最適化 の手法を活用し、現実的なアプローチを模索

無駄な駒・強すぎる駒・弱すぎる駒の扱い

黒駒は通常、白の手数増加に寄与しないため、除外可能
- 例外：白ポーンが取れる、黒王を守る、ピン解除など
強すぎる駒 （例：黒クイーン）は、より弱い駒に置換しても手数は減らない
白駒は逆に、強い駒（クイーン等）に単純に置換できない場合あり
- 王手回避や合法性維持のため、慎重な配置が必要
チェック状態 の局面は最大手数に到達不可と論理的に証明

部分的な駒配置と「チェスでチート」

全探索回避のため、 部分的な駒配置 や 分数的な駒の存在 を仮定
整数計画問題 としてモデリングし、Gurobi等のソルバーで最大手数を探索
最初の試行は メモリ不足 や 計算時間（推定6年） で断念
ルール簡略化（キャスリング条件緩和、ピン無視、チェック無視等）で再挑戦
それでも進捗遅く、 さらなる制約追加 で探索空間を削減

証明された結果と代表局面

最適解 として、 218手 が最大であることを証明
代表的な12局面を公開（リンク参照）
1つの局面について 到達可能性証明ゲーム も提示
144手（昇格なし） の記録も最適と確認
非合法局面 では288手、 合法だが到達不可局面 では271手が上限と判明

今後の課題と展望

コードは GitHubで公開、さらなる発展や応用に期待
今後の研究課題例
- 最多キャプチャ数局面
- 最多ステイルメイト局面
- 最多チェック・チェックメイト局面
- その他特殊条件下での最大値
整数線形計画法 だけでは困難な課題も多く、 創造的な数学的洞察 と 新アルゴリズム が必要
興味ある方は 挑戦を推奨

まとめ

218手 が到達可能なチェス局面の最大手数であり、これを超える局面は存在しないことが証明された
膨大な計算量を 数学的最適化 と アルゴリズム で乗り越えた成果
今後も チェス問題 や 計算機科学 分野での新たな挑戦が期待される

Hackerたちの意見

https://lichess.org/@/Tobs40/blog/there-is-no-reachable-ches... では、著者が最初の段階でいくつかの複雑なルールを削除したことが説明されていて、必要なら再導入する意向があるみたい。つまり、見つかった解がそれらのルールに違反した場合ね。面白いことに、混合整数線形計画法のソルバーはすでにこれをサポートしてる。これを「行生成」と呼ぶんだ。通常、これらの問題は行列形式で書かれるから、行は制約に、列は変数に対応してるんだよ。（動的に）行を追加することは、違反している場合に限り、制約を導入することに相当する。このアプローチは、旅行セールスマン問題によく使われるんだ。（変なことに、ウィキペディアには https://en.wikipedia.org/wiki/Column_generation があるけど、行生成については何も書いてない。）

└

MILPソルバーが終了するかどうか、すごく気になるな（広大な探索空間を考えると）。私の予想では、無理だと思う。

└

これに最もよく使われる用語は「怠惰な制約」です。

彼らははっきり言わないけど、「この位置からは218通りの合法的な手が選べる」という意味だね。

└

「この位置に到達するのにゲームで何手かかるか」と思ってた。

└

ああ、ありがとう。この記事を読んで、最も多くの手数で到達するユニークな位置についてだと思って混乱してた。

└

ありがとう、記事全体を誤解してた。素晴らしい文章だね！

└

そう、この記事には「可能な手」というフレーズが一度も出てこないのがすごく変だね。キーワードは「可能」なんだ。この記事は一貫して「手がある」という表現を使ってるけど、これは一般の人には分かりにくい表現だと思う（ただ、チェス用語ではもっと一般的だと思うけど）。

└

どんなチェスの位置からも、8.7 × 10^45 の可能なチェスの手があるなんて明らかじゃないよ。全ての駒は1つの駒につき32手未満だし、19個の駒があるから608手未満になる。

└

そうそう、「到達可能」というのは、通常の（とはいえ明らかに意図的に選ばれた）手の系列を通じてこのボードの位置に到達することが理論的に可能だってことを意味してるんだ。

└

もし記事の見出しに「選ぶための」と付け加えてたら、最初から明確だったのに。

└

うん、彼が解決しようとしてる問題が理解できないって気づいたときに諦めたよ。

└

ああ、すごい、今まで記事を読み間違えてた、ありがとう。彼らが「どんなチェスのポジションに到達するためにできる最大の手数は218だ」と言ってると思ってたから、記事が全然意味不明だったんだ。

└

218手以上のゲームはできないって意味だと思ってた。三重の繰り返しでゲームが終わるから、上限があるのは想像できるけど、218よりはずっと高いよね。

218手以上の到達可能なチェスの位置はない。「218通りの次の手が可能」と言った方がずっと分かりやすいね… > 約8.7x10^45の到達可能なチェスの位置をチェックすることで？それは大きな過大評価だよ。 https://github.com/tromp/ChessPositionRanking は合法的なチェスの位置の数を約4.8x10^44と正確に推定してる。

└

その推定値って、ただ20倍大きいだけじゃない？それって、規模を考えると大した違いじゃないよね。

何か見落としてるのかな？最初に示されている配置は実際には到達できないんじゃない？白が先手なのに、黒のポーンはスタート位置にいて、黒のキングは隣に空いてるマスがないし、ポーンと白のビショップに囲まれてるから、その配置には到達できないはずだよ。

└

黒のポーンが白の側にいるんだよね。

└

ここにその一つの証拠があるよ：https://lichess.org/study/PLtuv3v5/zWPNxbSA ただ、君はその位置を誤解してる。黒のポーンはスタート位置にはいないよ。全部ボードの向こう側まで移動してるから。あれは白のポーンのスタート位置だよ。

└

黒のポーンは7段目にいるんであって、2段目じゃないよ。一般的なルールとして、選択肢が a) あなたが何か見落としてなくて、問題の記事が馬鹿げてて間違ってるけど誰も言ってない、または b) あなたが何か見落としてる、なら (b) を仮定して、何が足りないのかを突き止めるために全力を尽くすべきだよ。

到達可能なチェスボードを記述するのに必要な最小ビット数はどれくらい？更新：記事によると、約8.7x10^45の到達可能なチェス位置があるって言ってて、https://github.com/lechmazur/ChessCounter ではこれが上限だって。これに相当するのは約153ビットだね。

└

駒の種類と色は4ビットで収まるよ。だから、全体のボードを固定長でエンコードするなら、64 * (4ビット) = 256ビット = 32バイト。もしくは、駒だけのスパース可変長エンコードなら、64マスそれぞれをインデックスするのに6ビット、= 10ビット * 駒の数。例えば、初期位置は32*10 = 320ビット、つまり40バイトかかるよ。

└

それは ceil(log2(~4.8x10^44)) = 149 ビットだね。でも、効率的にデコードできるようにするには、他のコメントでリンクした ChessPositionRanking プロジェクトの ceil(log2(8726713169886222032347729969256422370854716254)) = 153 ビットの表現を使うべきだよ。ChessCounter プロジェクトは効率的にデコードできるコードを提供してないからね。

└

あのリポジトリにある8.7e45の「制限された」数は、特定のポーン昇格のパターンを除外しています。5.68e50の「一般的な」数が真の上限のようで、可能な昇格をすべて許可しているみたいです。

混乱してるんだけど、271手モデルの後に何を変えたら最適な解を出せるようになったの？「この改善されたモデルで」としか書いてないけど…。

教えてもらいたいんだけど、Gurobi の整数プログラミングソルバーが218より良い解を見つけられなかった場合、それは218より良い解が存在しないことの保証になるの？それは数学的な証明と同じことなの？（議論のために、Gurobi のソルバーにバグがなくて、著者の実装にもバグがないと仮定しよう。）つまり、Gurobi が局所的な最大値にハマってしまった可能性があるのか、それともこれは決定的な普遍的解と見なせるのかを聞いてるんだ。

└

これまでに見つかった最良の整数解の価値に加えて、Gurobiは問題の線形緩和を使って計算された最良の可能な解の価値の上限も提供してるんだ。だから、ソルバーにバグがなければ、これは本当に最適な解だよ。

b2 の黒ポーンは他の駒の可能な動きをたくさん制限してるね…合法的な動きは c1 のナイトを取るだけだよ。そのポーンがなければ、4つの白いクイーンとナイトのためにそのマスが空くのに。でももちろん、黒のキングはすでにチェックメイトされてるから、これらの動きは実際にはできないんだよね。その e5 のクイーンをどこかに移動させて、すぐにチェックメイトにならないようにして b2 のマスを他の駒に使えるようにするのも魅力的だね。編集: そのポーンも、引き分けを避けるためにその位置まで生き残る必要があると思う。

└

b2の黒いポーンは、白が先手の場合、動ける手がないんだ。もし黒が先手だったとしても、e5の白いクイーンにピンされてるから、動ける手はないよ。もしピンされてなかったら、4つの手があったんだけど、アンダープロモートもできるからね。

ここでLichessに感謝を伝えたいな。すごく素晴らしいし、コンテンツも充実してる。Chess.comでお金を払わないといけないものが無料で使えるし、バリエーションもめっちゃ多い。しかも、960やクレイジーハウスみたいなバリエーションのレベルは、Lichessの方がChess.comよりもずっと高いんだよね。

└

無料で、商業サーバーと同じ機能があって、オープンソースで開発者にも優しい。広告もないし（無料アカウントでも）、フランス法の下で透明な企業構造を持ってる。ほんとに信じられないくらい良いよ。できれば寄付してね！

一方、囲碁の19x19の標準ボードでのゲームでは、次の手の最大数は361だよ。これは初期の空の状態でしか起こらない。361の最も到達が難しいポジションは、360の白い石と1つの空点があるポジションだね。これに到達するには、黒がすべてのターンをパスして、2*361 = 722手かかるんだ。これらの答えは、208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935の法的ポジションをすべてチェックせずに見つけたものだよ :-)

└

それから白が1石を置いて、黒の石を一気に全部取っちゃう。実質的にゲームをリセットして、360点のリードを得ることになるんだ。（黒が先手で、白はコミがあるから、実際には260+コミのリードだね）

└

囲碁のゲームは、再捕獲によって合法的に無限になることがあるよ。（プレイヤーが360回パスしてから、ボード全体を取って、また最初から始まる）。コウが最善手になることもあるから、自然に無限のゲームでもあるんだ。これを防ぐためには、追加のルールが必要なんだよ。（コウ、スーパコウ、トリプルコウなど）

ハクソク