LLMは45ビットクエリで16枚のカードを識別できるか？

LLMと数学研究の交差は魅力的なものです。数学は客観的で検証可能であり、今日の最先端モデルは数学の概念と方法論で広範囲に学習されています。LLMが、その能力の根源が驚くほど単純なメカニズムから生じていることを知りながら、以前は未解決だった（そして本当に難しい）問題を解決するのを見るのは、特別な喜びと驚きです。私にとって、これは人類が創意工夫、努力、そしてエンジニアリングを通じて集団で達成できることの驚くべき証です。 この分野で働く多くの人々のように、私も私自身の視点から、未解決の数学的問題に対するLLMの限界をテストすることに興味を持ちました。この記事はそのプロセスの物語です。 はじめに 標準的なカードデッキから4枚のカード（ハートのエース、キング、スペードのエース、キング：A♥, K♥, A♠, K♠）があります。カードを指さして、次の2つの質問のいずれか1つを尋ねることができます：このカードは赤ですか？このカードはキングですか？ これらの4枚のカードはシャッフルされます。各カードに質問をすることで、どのカードがどれかを簡単に特定できます（カードごとに8つの質問）。しかし、あなたの目標は、質問をいくつか行う戦略を考案し、常に5つ未満の質問でどのカードがどれかを特定することです。 以下のインタラクティブメディアで試してみてください。右側から質問を任意のカードにドラッグして、そのカードに関する1つの事実を学び、完全に配置を確信したら「わかった！」をクリックします。 24の配置が残っています 0回のクエリを使用しました 5情報のフロア カード：A♥ K♥ A♠ K♠ — 2つの質問（赤？、キング？） 目標：5回未満のクエリで完全な配置を特定する。 シャッフル＆プレイ わかった！ 質問 カードにドラッグ 赤スーツ？ (♥♦) このカードはキングですか？ クエリログ 位置 赤？ キング？ こちらも試してみてください：8枚のカードのバリエーション · 16枚のカードのバリエーション この記事は、この単純なパズルのスケーリングされたバージョンを中心に提起された未解決の数学的問題を解決するためにAIを使用することについてです。記事の残りは次のセクションに分かれています： 16枚のカードのバージョンは、最初の4枚のカードのパズルを16枚のカードに拡張し、未解決の数学的問題を提示します。大部分は最適な戦略の探索をカバーしています：LLMエージェントの実行設定、50回の反復でのパフォーマンスの進化、およびゲームのプレイ可能なブラウザバージョン（主な結果を見るにはここにジャンプしてください）。最後に、コラボレーションからの主要な学びと、最近反証されたドナルド・クヌースによる関連する未解決の推測へのつながりについて説明します[5]。 16枚のカードのパズル この小さな問題はより大きな空間に拡張でき、そこで興味深いことが起こります。16枚のユニークなカード（それぞれが4ビット値 (0,1,...,15) をエンコード）と4つのバイナリプロパティがあります。カードのプロパティ b をチェックすると、1つのビットが得られます：そのカードの隠された値のビット b。たとえば、プロパティ 3 はカードの最上位ビット (MSB) を明らかにし、プロパティ 0 は最下位ビット (LSB) を明らかにします。4つのプロパティチェックで任意のカードを完全に決定できることは明らかです。 ただし、カードはすべて裏向きにシャッフルされているため、どのカードがどれかわかりません。各カードの各プロパティをチェックする 64 回のチェックで、これを簡単に実行できます。パズルは、最悪の場合、50回未満のクエリで全体の配置（どのカードがどれか）を回復することです。できますか？（以下の小さなバリエーションで問題を試すことができます。） 未解決の問題 物語の下には興味深い順列ベースのパズルがあります。隠された順列 σ は {0,...,15} をスクランブルします。クエリは (カード, プロパティ) のペアを指定し、そのカードの隠された値 E(π) のそのビットを返します。これまでのすべての回答と矛盾しない順列が1つだけになった時点で停止します。 D(16) を、事実がまだ許容する限り、あらゆるクエリにできるだけ役に立たないように答える敵対者に対しても常に十分なクエリの最小数とします。私が尋ねる質問は、D(16) の正確な値は何かということです。 情報理論的分析。 セットはフロアを設定します。16! の可能な配置があり、各回答は1ビットなので、どの戦略も D(16) ≥ ⌈log₂ 16!⌉ = 45 を超えることはできません。そして、怠惰な戦略 — 16枚のカードすべての4つのプロパティをチェックする — は 16 × 4 = 64 を使用します。真の答えは [45, 64] のどこかにありますが、どこでしょうか？ 正式な記述と未解決の推測 n = 2^k とし、各値 0 ≤ i < n をその k ビット文字列 b(i) ∈ {0,1}^k として記述します。順列 π = (π₁, ..., πn) は、連結 E(π) = b(π₁)b(π₂)・・・b(πn) ∈ {0,1}^nk としてエンコードされます。クエリはインデックス t ∈ {1,...,nk} を選択し、E(π) の t 番目のビットを返します。D(n) を、最悪の場合（クエリはすべての以前のクエリと回答に依存する可能性がある、つまりクエリは適応可能である）に π を一意に識別する最小クエリ数とします。45 ≤ D(16) ≤ 64 であることがわかっています。D(16) を決定してください。 未解決の推測：D(16) = 46。 なぜこの問題なのか？ 適応的で逐次的な性質は、LLMエージェントが動作する方法と自然にマッピングされます：アイデアを提案し、それを実装し、実行し、読みます。 さらに、実際の計算リソースの制約下で働く独立した研究者として：GPUクラスターなし、単一のMacBook、有限のトークン予算、私は産業規模のコンピューティングなしで意味のある進歩が可能な問題が必要でした。D(16) の計算はこれに適合します：明確に述べられ、客観的に検証可能であり、単一のマシンでの総当たり攻撃の範囲外にあるため、すべてのアルゴリズムの改善が重要になります。この問題は多くの方法で定式化できることに注意してください。それぞれが異なる数学分野に関連しています：適応的なビットクエリ最適決定木として、二部グラフのマッチングとして、それは永久計算に結びついています。状態空間サイズを縮小するための自己同型性。動的計画法または総当たり探索戦略。 また、未解決の問題であるにもかかわらず、テレンス・タオが提唱した「注意を払わない」問題に分類します。 最適な戦略の探索 最適な戦略の計算を2つの側面からアプローチしました。まず、手作業で推論できる戦略のセット（各戦略は証明可能な上限）ですが、ペンと紙ではそれほど遠くまで行けませんでした。次に、メインの探索を開始しました：LLMエージェントに、メタハーネスを与えて研究ループ自体を実行させました。アイデアを提案し、実装し、実行し、読みます。 このセクションでは、その探索の結果を説明します。探索の前に、注意深い人間が試すことのできるもののレベルを段階的に見ていく価値があります（自分で試すことをお勧めします）–各戦略は証明可能な上限を提供します。 この記事の残りの部分は、AIを使用してこのパズルを試すことの探索と、その過程での学びについてです。 人間が導き出せる上限 すべて読む（64回使用）。4つのプロパティ × 16枚のカード。正しいですが、何も利用していません。 最後のカードをスキップ（60回使用）。15枚のカードを完全に特定します。残りは最後の1枚です。15 × 4 = 60。 再帰（49回使用）。16枚中15枚のカードでプロパティ3をチェックし、最後のカードのMSBを推測します。これにより、それぞれ8枚の2つの小さなグループが作成されます（15回使用）。それぞれのグループについて、1枚を除くすべてのカードでプロパティ2をチェックし、最後のカードを推測します（7 + 7回使用）。同様に、4つの小さなサブグループ（3 + 3 + 3 + 3回使用）でプロパティ1を繰り返し、最後に8つのサブグループの各ペアの1枚のカードでプロパティ0をチェックします（1 + 1 + ... + 1 = 8回使用）。合計49回使用。 人間+コンピューター（47回使用）。前のものからの改善です。以前と同様に、すべてのカードの最上位プロパティをチェックし、2つの8枚のカードのサブ問題に分割します。いくつかの異なる戦略により、D(8) = 16 が決定され、これを使用して16枚のカードの問題を 15 + 16 + 16 = 47 クエリで完了します。エントロピー分割（20の質問ゲームのような）が最適に見えるかもしれませんが、8枚のカードのゲームでの単純な実験は、最適性に到達しないことを示しています。ただし、未照会ブロックへのバイアスを伴うエントロピー分割のようなバリアントは、最適な境界を達成します。 実行設定 メタハーネスを構築し、LLMエージェントに研究ループ自体を実行させました：アイデアを提案し、実装し、実行し、読みます。