数学者が150年前のチェス問題を解く

家にチェスセットがいくつかあるなら、次の練習を試してみてください。盤上に8つのクイーンを並べ、互いに攻撃しないようにします。一度成功したら、2つ目の配置は考えられますか？3つ目は？全部でいくつありますか？

この難問は150年以上も前から存在しています。これは、ハーバード大学数学科学応用センターのポスドク研究員であるマイケル・シムキン氏が7月に投稿した論文でその解答に着目した、 nクイーン問題と呼ばれる数学的問題の最も初期のバージョンです。標準的な8×8のチェス盤（有効な配置は92種類）に8個のクイーンを配置する代わりに、この問題はn × nの盤にn個のクイーンを配置する方法が何通りあるかを問うものです。23×23の盤に23個のクイーンを配置することも、1,000×1,000の盤に1,000個のクイーンを配置することも、あるいは対応するサイズの盤に任意の数のクイーンを配置することも可能です。

「誰にでも説明するのはとても簡単です」と、ミュンヘン工科大学とスイス連邦工科大学ローザンヌ校のマリー・スクウォドフスカ・キュリー研究員であるエリカ・ロルダン氏は語った。

シムキンは、多数のクイーンを持つ巨大なチェス盤の場合、約(0.143 n ) ⁿ通りの配置が存在することを証明しました。つまり、100万×100万の盤上で、脅威とならないクイーンを100万個並べる方法の数は、約1個とそれに続く約500万個のゼロの組み合わせとなります。

8×8のチェス盤に関する最初の問題は、1848年にドイツのチェス雑誌に初めて掲載されました。1869年には、nクイーン問題が続きました。それ以来、数学者たちはnクイーンに関する結果を少しずつ発表してきました。シムキンが発見した結果を推測するために、これまでの研究者たちはコンピューターシミュレーションを用いてきましたが、実際に証明したのは彼が初めてです。

「彼は基本的に、これまで誰も成し遂げられなかったほど鋭くこれを成し遂げた」とケンブリッジ大学の博士研究員ショーン・エバーハード氏は語った。

nクイーン問題を解く上での障壁の一つは、それを単純化する明確な方法がないことです。比較的小さな盤面であっても、クイーンの配置の数は膨大になる可能性があります。盤面が大きくなると、必要な計算量は膨大になります。このような状況で、数学者はしばしば、計算をより扱いやすい小さな部分に分割できる、何らかの根本的なパターンや構造を見つけたいと考えます。しかし、nクイーン問題にはそのような方法は見つからなかったようです。

「この問題で注目すべき点の一つは、少なくとも深く考えなければ、何の構造も存在しないように見えることだ」とエバーハード氏は語った。

これは、ボード上のすべてのスペースが同じように作成されているわけではないという事実に起因します。

その理由を理解するために、もう一度、8つのクイーンの配置を自分で構築することを想像してみてください。最初のクイーンを中央付近に配置すると、同じ列、同じ行、または盤面の最も長い2つの対角線に沿った任意のマスを攻撃できます。つまり、次のクイーンが攻撃できないマスは27マスになります。しかし、最初のクイーンを盤の端に配置すると、関連する対角線が短いため、攻撃できるマスは21マスになります。つまり、中央のマスと端のマスは明確に区別されており、その結果、盤面には対称的な構造がないため、問題をより単純化できる可能性があります。

この構造の欠如こそが、シムキンが4年前にスイス連邦工科大学チューリッヒ校の数学者ツア・ルリアを訪ね、この問題の共同研究を始めた理由である。当初、彼らはより対称的な「トーラス状」のnクイーン問題に取り組んだ。この改良版では、チェス盤はトーラスのように端で「巻き付く」。つまり、右に落ちても左に現れるのだ。

ドーナツ盤問題は、その対称性ゆえにより単純に見えます。従来の盤とは異なり、対角線の長さはすべて同じで、すべてのクイーンが同じ数のマス、つまり27マスを攻撃できます。

シムキンとルリアは、2つの手順からなるレシピを用いて、ドーナツ盤上に様々な配置を構築しようと試みました。各ステップで、彼らはクイーンをランダムに配置し、空いている限り、等確率で任意のマスを選びます。そして、クイーンが攻撃できるマスをすべてブロックします。各ステップでいくつの選択肢があるかを記録することで、配置の数の絶対的な最小値、つまり下限値を計算しようとしました。彼らの戦略はランダム・グリーディ・アルゴリズムと呼ばれ、組合せ論の分野における他の多くの問題の解決に用いられてきました。

ドーナツ盤の対称性は、シムキンとルリアにこの問題への足掛かりを与えた。しかし、ドーナツ盤は自由度を犠牲にして対称性を獲得し、最終的に彼らを窮地に追い込む。クラシック盤では、ほとんどのクイーンは27マス未満しか攻撃しないため、より柔軟な構成を構築できる。

「本物のチェス盤の隅々まで見通すのが本当に役に立つ」とエバーハード氏は語った。

シムキンとルリアのトーラス問題への取り組みは、与えられた配置で最後の数個のクイーンを配置するスペースが見つからなかったことで最終的に行き詰まりました。壁にぶつかった彼らは、他のプロジェクトに移りました。しかし最終的に、シムキンはトーラス問題で失敗したアプローチが、実際には通常のチェス盤に適していることに気づきました。

「諦めてから2、3年後、古典的な問題の場合、実はこれがずっと簡単だということに気づいた」とシムキン氏は語った。

そこでシムキンとルリアは、通常のチェス盤（どんな大きさでも）上で構成を完成させようと試みました。そして、すでに配置した駒の一部を調整することで、たいていは成功できることを発見しました。

「女王蜂を数匹移動させて、新しい女王蜂を2匹入れて、古い女王蜂を1匹取り除くだけでいいのです」とモナシュ大学のニック・ワーモルド氏は説明した。

しかし、古典的な問題における対称性の欠如は、研究者たちを苦しめる結果となりました。ランダム・グリーディ・アルゴリズムは盤上のすべてのマスを平等に扱い、すべてのマスが同じであるような高度に対称的な問題に最適です。標準的な盤上にクイーンをランダムに配置する場合、このアルゴリズムは中央のマスとサイドのマスを区別しません。

この制限により、シムキンとルリアは問題の既知の下限値を改善することしかできませんでした。彼らは昨年5月にその結果を発表しました。

しかし、シムキンはエルサレムのヘブライ大学で博士号を取得し、昨年秋にイスラエルからボストンへ移住した後も、この疑問について考え続けた。そしてついに、ランダム・グリーディ・アルゴリズムを標準的なn × nチェス盤の非対称環境に応用できることに気づいた。彼が気づいた重要な点は、 nクイーン配置では、クイーンが特定のマス目を占める可能性が他のマス目よりもはるかに高いということだった。つまり、彼とルリアが用いた、すべてのマス目を等確率で選ぶ戦略は意味をなさないということだ。

「実はこうした非対称性を有利に利用できることに気づいた」と彼は語った。

盤面中央のクイーンは最も多くのマスを攻撃するため、ほとんどの構成では、盤面中央付近よりも盤面側面にクイーンが多く配置されます。盤面の各辺に100マス程度でも配置すると、シムキン氏はこれらの効果が他の可能性を圧倒し始めることを発見しました。ほぼすべての構成において、クイーンは特定の配置方法を採用しており、盤面中央付近のクイーンは少なく、側面のクイーンは多く配置されています。シムキン氏は、クイーンをランダムに配置する際に、各マスに正確に重み付けする方法を見つけるだけで済みました。

「例えば、女王蜂の群れを全部集めて、一つずつ重ねてみます。すると、この特定の位置はどれくらいの頻度で占有されているかが分かります」と、ヘブライ大学の教授でシムキン氏の博士課程の指導教官でもあるナティ・リニアル氏は言う。

シムキンは、クイーンがどのように配置されるかを大まかに把握するために、n × nのチェス盤を数千個のマス目からなるセクションに分割しました。そして、チェス盤上のどのマス目にクイーンが配置されているかを正確に特定するのではなく、より広い視野で捉えました。つまり、各セクションにはクイーンがいくつあるか、ということです。

区画ごとに女王蜂を配置する方法を解明すると、彼はルリアと使った手法に戻った。今回はより正確に女王蜂を配置できた。女王蜂を完全にランダムに配置するのではなく、女王蜂がより多く、より頻繁に存在する区画を選んだのだ。これにより、有効な配置の最小数を求める式を導き出すことができた。

最終的に、シムキンはエントロピー法と呼ばれる戦略を使用して、この式が単なる最小値ではなく、ほぼ正確な記述であることを証明しました。

有効なnクイーン構成を持っていて、それを誰かと共有したいとします。相手が構成の大まかな形を知っている場合、正確に再現するにはどれくらいの情報を共有する必要があるでしょうか？

シムキンは、新たなクイーンの位置が明らかになるごとに、攻撃を受けていないマスの数を追跡することで、配置の最大数を計算することに成功した。この最大値は彼が求めた最小値とほぼ完全に一致し、シムキンはnクイーン配置の実際の数をほぼ正確に特定したと結論づけた。彼の証明は、長年探し求められていた古典的な問題に明確な答えをもたらした。

シムキンの結果によって、問題の謎の大部分は解明されたが、数学者たちはおそらくこの問題に取り組み続け、これらの境界をさらに近づけようと試みるだろう。

エバーハード氏は「これはまさに期待通りのリアルさだ」と語った。

シムキン氏の論文は、最近活発化している類似の問題研究の一環だ。実際、先週、オックスフォード大学のキャンディダ・ボウテル氏とピーター・キーヴァッシュ氏は、トーラス状 nクイーン問題に対する類似の解を発見した。この論文は発表されたばかりで、まだ十分な検証は行われていない。また、これらの論文のアイデアから恩恵を受けられる可能性のある、組合せ論における未解決の問題は他にも数多く存在する。シムキン氏は、自身の研究によって、こうした新たな応用の可能性が高まることを期待している。

「興味深いのは、その手法です」とシムキン氏は語った。「私たちは常にツールの強化を模索しています。ここでそれが実現できたことを願っています。」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

WIREDのその他の素晴らしい記事

• 📩 テクノロジー、科学などの最新情報: ニュースレターを購読しましょう!
• レインブーツ、潮の流れ、そして行方不明の少年の捜索
• イベルメクチンに関するより良いデータがついに登場
• 深刻な太陽嵐は「インターネットの終末」を引き起こす可能性がある
• ニューヨーク市は21世紀の嵐に備えて建設されたわけではない
• いつまでも遊べるPCゲーム9選
• 👁️ 新しいデータベースで、これまでにないAIを探索しましょう
• 🎮 WIRED Games: 最新のヒントやレビューなどを入手
• 🏃🏽‍♀️ 健康になるための最高のツールをお探しですか？ギアチームが選んだ最高のフィットネストラッカー、ランニングギア（シューズとソックスを含む）、最高のヘッドフォンをご覧ください