情報理論が私のワードゲームを救った経緯

情報理論 · ワードゲーム 誰も知らない数字 私が作ったワードゲームの底からのメモ。時として、メディアとメッセージは予想以上に複雑な関係を持つことがあります。「BはBravoのB」。あなたはそれをやったのです。悪い電話回線で単語のスペルを伝え、文字を超えて単語全体に到達するのです。なぜなら、回線が途切れた瞬間、BとDとPはすべて同じ塊にぼやけてしまうからです。 それは受信状態の悪さによる癖ではありません。それは現代の通信における最も深いアイデアの一つであり、人間がリアルタイムで行う、数百万キロメートルのノイズを越えて宇宙船の信号を読み取り可能に保つトリックと同じものです。 マーシャル・マクルーハンは「メディアはメッセージである」という功績を称えられますが、クロード・シャノンは何年も前にそれのより冷徹なバージョンに到達していました。あなたの言葉を運ぶ機械にとって、意味はまったく重要ではありません。重要なのはメディアと、その信号のどれが識別できるかだけです。BravoとDeltaは悪い回線でも生き残りますが、BとDはそうではありません。あなたは考えもせずに耳でそれを整理しました。同じ本能を限界まで押し進めると（ノイズの多いチャネルをどれだけ押し通しても、完璧な確実性をもって理解されることができるか？）、シャノンが1956年に提起した質問にまっすぐにぶつかります。 私は数学者としてそこにたどり着いたわけではありません。私は数学者ではありません。私はまったく別の方向から来ました。私は手がかりではなく推論を使うワードゲームを作ろうとしていたのです。単純だと思っていたものです。私がこれまで出荷した中で、一見最も単純に見えたものが、そこにある最も古い未解決問題の一つに支えられていた経緯をお話ししましょう。 「単純な」もの これがゲームのすべてです。半分完成したクロスワードグリッド。配置を待つ文字のキュー。文字が提供され、それが属するセルをタップし、グリッドがいっぱいになるまで続けます。 一つのルール 私がそれから得たかったことは、ほとんど述べる価値もないほど小さなことに思えました。パズルは決して推測させてはならない。何もかも正しく行ったのに、論理が尽きて、ゲームがただセルを選んで希望することを求める瞬間があってはならない。すべての文字は推論のみによって配置可能であること。これは簡単な部分だと思っていました。クロスワードなので、最も難しい部分は良い辞書を作り、クロスワードを厳選することだろうと考えていました。私は時間を遡って、その時の私に警告したいものです... 壁 辞書には数ヶ月かかりました。それが最終的に良くなったとき、私は当然のことをしました。ジェネレーターを空のフォルダに向けて、ふるいにかけるために数千のボードを求めました。グリッドを実際の単語で埋め、一部を隠し、残りを一つずつ渡し、純粋な論理で人が完成できるボードだけを保持します。私は夜をかけて戦利品を厳選するつもりでした。 約40個ができました。それから停止し、ボードを次々と生成しては、ほとんどすべてが推論不可能であるため破棄し続けました。数晩遅くまで、ジェネレーターを書き直し、問題を再考しましたが、100個を超えることはありませんでした。それは私を完全に止めました。実際の単語を縦横にスペルしなければならない5x5のグリッドは、組み合わせの海です。可能なボードの空間は人間の理解を超えていますが、私のジェネレーターは人が解ける100個さえ見つけられませんでした。これは最適化で解決できる速度の問題ではありませんでした。それは壁であり、私には答えられない質問を投げかけました。推論可能なボードは本当にそれほど珍しいのか、ごくわずかなものしかプレイできないのか？私は構成をそんなにひどく見誤っていたのか、私が夢見ていたゲームは単に存在しなかったのか？ 数日間は、プロジェクトは死んだ、難しくも遅くもなく、不可能だと信じていました。私のジェネレーターは、私が想像していた広大なフィールドがデッドエンドの迷路に過ぎないと言い張っていました。私に一縷の希望を与え、前進し続ける十分なものとなったのは、捨てられたボードと残されたボードの間のわずかな違いでした。同じグリッド、同じ提供された文字、そしてたった一つの未発見のタイルが、推測と確実性の間の全距離でした。もしかしたら、問題に対する私の見方が問題だったのかもしれません。 「T」を提供 → 2つの有効なセル。推測するでしょう。 「T」を提供 → 1つの有効なセル。強制される。 同じボードで、たった一つのマスが違うだけです。最初のケースでは、提供された「T」は2つの開いたセルにフィットします。下向きにTOWER、または下部にTRAMという単語を形成します。推測しなければなりません。2番目のケースでは、ASKのKという一つのマスを明らかにするだけで、上のオプションは横向きにATKを形成します。これは単語ではないので、Tは唯一の有効な場所へと強制されます。 バグではなかった 何週間も私はバグのようにそれを追いかけました。ジェネレーターの欠陥、辞書が薄すぎる、削除パスが貪欲すぎる。どれも違いました。それはこのページの上部にある悪い電話回線の話（古くて有名な通信問題）であり、私はグリッドや辞書の中に深く入り込みすぎて、その形を認識できませんでした。 パズルはチャネルです。私が送信者、プレイヤーがデコーダー、私は文字を送信し、プレイヤーは私がどのセルを意図したかを回復しなければなりません。通常のクロスワードはノイズの多いチャネルです。デコーダーは通常正しく、そうでなければ肩をすくめて、やり直し、修正します。少しの混乱は問題ありません。日常のクロスワードではそれが楽しみの半分です。しかし、私は通常正しいよりも厳密なものを約束しました。私は決して間違えないことを約束しました。そして、「決して」は同じダイヤルをより厳しく設定するのではなく、異なる機械なのです。 混同可能性 暗闇の中で手探りでたどり着いた対象がこれです。開いているセルごとに点を描き、それらのセルが同じ提供された文字を受け入れられる場合、つまり混同可能な場合に、2つの点の間に線を描きます。このグラフには名前があります。「混同可能性グラフ」です。そして、パズルが推論可能であるのは、開いているセルが独立集合を形成している場合、つまり、どの2つの点の間に線も存在しない場合です。混同可能なペアがない。コインの裏表がない。私が自分に課したルールの正確な形が、私が存在を知らなかった言語で描かれていました。 000 111 すべての信号を3ビットの文字列と見なすと、それは立方体の角です。各エッジは、信号を隣接するものに変える可能性のある1ビットのフリップです。安全なコードは、単一の誤りがつなげない角に留まります。000と111は3回のフリップ離れています。「B as in Bravo」は人間版の同じアイデアであり、歴史の面白い偶然により、それが由来する表音文字体系は1956年、シャノンがその問題を発表したまさにその年に完成しました。半世紀以上の数学がすでにそこに、私を待っていたのです。完成したボードが推論可能かどうかは判断できましたが、意図的にそのようにボードを構築する方法はまだ分かりませんでした。その方法を学ぶには、まずシャノンが実際に何を発見したのかを理解する必要がありました。 5は4を打ち破る シャノンは何十年も前に、誰でも描ける最も単純なケースでこの形の研究を行っていました。時計の文字盤に5つの信号を想像してください。それぞれが隣接する2つの信号と非常に近く、線がそれらを混同させてしまう可能性があります。それらを一つずつ送信する場合、安全に使えるのは2つだけです。隣接しないペアを選べば、送信するものが他のものと間違われることはありません。5つのうちの2つ。小さく、きちんとまとまった、しかし期待外れの数字です。 時計の文字盤に5つの信号。混同可能な（隣接する）ペアごとに線が引かれ、安全な、隣接しないペアが緑色に点灯しています。1回の送信で安全に2つを運べます。 シャノンが気づいたのは、信号を一つずつ送信するのをやめて、それらを束ねて、一連の全体を一つのメッセージとして扱う方がはるかに良いということです。一つずつ送信すると、2回の送信で2×2＝4つのメッセージが、決して混同されることなく送られます。ペアを束ねて適切に選択すると、5つのメッセージを運ぶことができます。（5番目が収まるのは、2つの束が一方のスロットで混同可能な信号を共有しても、もう一方のスロットでは明確に離れていれば安全だからです。単独では危険すぎる信号も、パートナーがいれば安全です。）そして、その利得は複合的に増大します。一度に10個の信号を送ると、2の10乗で1,024個の安全なメッセージが得られます。束ねると3,125個になります。したがって、安全なメッセージの数は、追加する信号ごとに2倍ではなく、2.236倍になります。その正確な値は5の平方根（√5 ≈ 2.236）です。 ボードに戻りましょう。推論可能なパズルとは、混同可能なペアを含まない開いているセルの集合であり、時計の安全なメッセージも同じ構造です。混同可能性グラフ内の独立集合です。違いは範囲だけです。私は単一のボードが安全に出ることを必要としていましたが、シャノンは、束が無限に成長するにつれてチャネルが保持できる最良の乗数を求めており、それに名前を与えました。その容量