情報理論が私のワードゲームを救った経緯
How information theory saved my word game (motplot.app)
要約
この記事は、著者が構築しようとしていた、推論のみに頼るワードゲームが直面した困難と、その解決策として情報理論がいかに役立ったかについて説明しています。ゲームの設計思想である「推測させない」というルールが、実は通信理論における「混同可能性」の問題に深く関係していることを発見し、シャノンの研究がその突破口を開いた経緯が語られています。最終的に、単純に見えたゲームが、半世紀以上前の未解決問題に繋がっていたことが明らかにされます。
全文翻訳
The number nobody knows
Information theory · word games
時には、媒体とメッセージの関係は予想以上に複雑なものになります。誰しも、電話回線が悪くて「BはブラボーのBです」のように単語をスペルアウトしなければならなかった経験があるでしょう。B、D、Pは回線が途切れるとすべて同じような音になってしまうからです。ノイズとメッセージを区別するのは容易ではありません。
ノイズから信号をフィルタリングすることは、現代のコミュニケーションにおける一般的な問題です。それが、数百万キロメートル離れた宇宙船と地球との通信を可能にしています。クロード・シャノンは、この言葉が生まれるずっと前に、人間にはあまり関係のない応用分野で「媒体はメッセージである」のバージョンを考案しました。これらすべてが私の生まれる前に起こったことで、私の小さな個人的プロジェクトのまさに最中に、これらのアイデアの交差点がどのように現れたのかを知るのは fascinating でした。
私は数学者ではありません。ただ、頭をシャープに保ち、Rustのライティングスキルを向上させようとしているソフトウェアエンジニアです。私はワードゲーム、そして一般的にパズルが大好きなので、自分で一つ作ってみようと思いました。
これは、私がこれまで作った中で最もシンプルなものになるはずだったものが、情報理論における最も古い問題の一つについて私に教えてくれた物語です。
「シンプルな」もの
あなたは半分埋まったクロスワードグリッドと、空きマスに配置するための文字のキューを与えられます。文字は一度に一つずつ与えられ、主に推論(そして時には頭を悩ませたり、辞書でカンニングしたり)を使って、一つずつ配置または「プロット」していき、クリアを目指します…ただし、あまり多くの間違いをしない限り。
推論
ゲームが純粋に推論で解けるようにするには、2つの要素が必要だと考えました。それは、十分な語彙力を持つプレイヤーと、推測を強いることのないゲームです。同じ空きマスに複数の単語や文字が当てはまるような状況に陥ることはありません。もし私がこの状況のプレイヤーだったら、その場でゲームをアンインストールするでしょう。それは私が作りたい体験ではありませんでした。
正直、これは簡単な部分だと思っていました。クロスワードなので、難しいのは良い辞書を作り、良いグリッドを選ぶことだろうと考えていました。あの頃の自分に警告したいです…
壁
辞書の作成には数ヶ月かかりました。私の貴重な自由時間を使って「楽しみ」のために行った作業の中で、最も退屈なタスクの一つでした。しかし、それが準備できたので、私が作った小さなジェネレーターをアウトプットフォルダに向け、実行しました。いくつかの問題が発生することは予想していましたが、バグが修正されれば、たくさんのパズルが手に入り、残りの時間は最高のものをキュレーションするのに費やせるだろうとかなり自信がありました。
40個ほど生成したところで、ジェネレーターは停止しました。ボードを生成し続けても、ほとんどが推論可能ではなかったため、すべて破棄されました。数晩遅くまで起きてジェネレーターを書き直し、アプローチ全体を再考しましたが、それでも100個を超えることはありませんでした。
この時点で私は本当に途方に暮れていました。1万語以上の辞書からの単語のグリッドは、組み合わせの海です。可能なボードの空間は人間の理解を超えていますが、私のジェネレーターは推論で解けるものを100個も見つけられませんでした。
さらに悪かったのは、これは最適化問題ではなかったことです。高価なループを修正したり、ラップトップをアップグレードしたりして解決できるものではありませんでした。ジェネレーターは、推論可能なものが何も見つからないまま、文字通り何千ものグリッドを通過していました。この時点で、私は本当に自分自身を疑い始めていました。おそらく、全体的な判断を誤ったのだろう。夢見たゲームは実際には存在しないのかもしれない。数日間、プロジェクトは死んだと本気で思っていました。想像していた可能性のフィールドは、実際には行き止まりの迷路に過ぎなかったのです。
私を支えてくれた希望の光は、破棄されたボードと保持されたボードがどれほど似ていたかでした。失敗したボードの多くは、失敗したシーケンス文字が一つだけでした。つまり、もし一つか二つの異なる単語があれば合格していたということです。バックトラッキングや問題のある単語の再充填を試しましたが、それは無駄な努力でした。
“T” をサーブ → 2つの合法的なセル。推測が必要。
“T” をサーブ → 1つの合法的なセル。強制。
同じボード、一マス違い。最初: サーブされた「T」は2つの空きマスにフィットします。縦に TOWER、横に TRAM と綴れます。推測しなければなりません。二番目: 一マス明らかにする(ASKのK)、すると上の選択肢は ATK と横に綴れます。単語ではないので、Tは唯一の合法的な場所へと強制されます。
バグではなかった
プログラマーとしての訓練に影響を受け、私はこれをバグのように追いかけました。おそらくジェネレーターの欠陥だろう、辞書が薄すぎるのだろう、あるいはストリッピングパスの一つが削りすぎたのだろう。しかし、それらはどれも原因ではありませんでした。
それは、悪い電話回線から来るもの、古く有名なコミュニケーションの問題でした。パズルはチャネルです。私は送信者、プレイヤーは反対側にいて、私が文字を送信すると、プレイヤーはどのセルを意図したのかを突き止めなければなりません。
通常のクロスワードはノイズの多いチャネルであり、それは予想されることです。プレイヤーは通常正しく、間違った場合は肩をすくめ、バックトラックして修正します。そこでの少しの混乱が楽しさの半分です。しかし、私は推論を使用するゲームを作っていました、推測ではありません。これは、ノイズがあってはならない、混乱があってはならない、エラーはゼロでなければならないことを意味しました。
混同可能性
私がぼんやりとたどり着こうとしていた問題を視覚化する方法を以下に示します。クロスワードの各プレイ可能なセルは点であり、2つのセルが同じ文字を受け取ることができる場合はいつでも、それらの間に線を描きます。これは、それらが混同可能である場合です。数学者はそれを混同グラフと呼びます。私の目標は、それらの間に線がない点のグリッドを達成することでした。これは独立集合を表します。混同可能なペアがない、推測がない。
000 111
3ビットの文字列としての各信号は、キューブの角です。各エッジは、信号をその隣接信号に変えることができる1ビットの反転です。安全なコードは、単一のミスでは到達できない角にとどまります:000と111は3回の反転で隔てられています。
これは、「BはブラボーのB」の人間版のようなもので、そして面白い歴史の偶然により、それが由来するフォネティックアルファベットは、シャノンが問題を公表した1956年に最終決定されました。だから、50年以上の数学がすでにそこにあり、私のために待っていました。完成したボードが推論可能かどうかは判断できましたが、意図的にそれを作成することはまだできませんでした。そのためには、理論が実際に何を意味するのかを理解する必要がありました。
5対4
シャノンは何十年も前にこれを解明しました。時計の文字盤の周りに配置された5つの信号を想像してください。それぞれの信号は隣接する2つの信号に十分に近いため、線がそれらをぼかす可能性があります。それらを一度に1つずつ送信すると、確実に解釈できるのは2つだけです。これは、チャネルのノイズが近すぎるメッセージを識別できないほどぼかすためです。5つのうち2つはわずか40%であり、非常に信頼性の低い通信チャネルになります。
[画像: 時計の文字盤の周りの5つの信号。混同する信号は線で結ばれている。信号1と3が安全なペアとしてハイライトされている]
時計の上の5つの信号。混同可能な(隣接する)ペアは線で結ばれている。安全で非隣接なペアが緑色に光っている。1回の送信で2つを安全に運ぶことができる。
ここで、時計の周りに5つの信号を1から5まで番号付けすると、任意の番号は隣接する2つのうちのいずれかと間違えられる可能性があります。これは、一度に1つずつ送信すると、1と3、または2と4のように、1つ以上の数値離れているものしか区別できないことを意味します。メッセージに3番目の数値を追加すると、すでに使用されている他の数値の少なくとも1つにぼやけるため、曖昧さが生じます。したがって、1つのメッセージは2つの情報を持つことができます。したがって、2回の送信は2×2=4の価値があると想定されるでしょう。しかし、シャノンは実際に5つを管理できることに気づきました。これは、信号をペアで送信し、各ペアを単一のメッセージとして扱うことによって行われます:11、23、35、42、54。トリックは、2つのメッセージがその2つのスロットのうちの1つだけで安全に異なる必要があるということです。これは、単独で送信するにはリスクが高すぎる信号でも、メッセージ全体を区別可能に保つ限り、ペアの中ではより信頼性が高くなることを意味します。追加のメッセージは多くないように聞こえますが、それは雪だるま式に増えます。10回のメッセージで、一度に1つずつ送信するという考え方は1,024の安全なメッセージを与えますが、ペアにすると3,125になります。追加する各信号は、最終的にオプションを2ではなく約2.236倍に増やします。この数値は正確に5の平方根(√5 ≈ 2.236)です。理論についてはあまり深く掘り下げません。それは私が数学者ではないからでもあり、また、これだけが私をアンブロックするために必要だったすべてであり、ドーパミンが尽きたからです。
ボードに戻りましょう。推論可能なパズルとは、それらの間に混同可能なペアがない空きセルのセットであり、時計上の安全なメッセージは同じものです:混同グラフにおける独立集合。クロスワードは、すでにペアに構成されていたため、このソリューションの完璧なキャンバスになりました。各セルには信号のペア(2つの交差する単語)があります。実際の理論は単純なペアをはるかに超えていますが、これは私がソリューションを再考するために必要としたすべてでした。
フラッシュライト
これまでは、この問題を一方向から考えてきました。固定されたグラフが与えられ、その中に隠された独立集合を見つけるか、その大きさを計算するように求められます。それは検出器であり、より良い検出器は私を助けませんでした。なぜなら、私のジェネレーターはまだ盲目的にボードを作成し、ほとんどすべてを破棄していたからです。したがって、私が対処しなければならなかった残りの問題は、ボード生成の高度にランダムな性質でした。私はボードを正しい方向に成長させる必要がありました。最初の文字から、その空きセルが独立集合となるようにボードを構築したかったのです。当初、最初から推論可能なボードを構築する純粋に決定論的なジェネレーターの夢を追いかけましたが、それを実行するには私は十分なコンピューターサイエンティストではないことにすぐに気づきました。もしそれが可能だとしてもです。誰かが私がまだ深く興味を持っていることを知っているなら、ぜひ連絡してください。
そのため、私のジェネレーターはまだサイコロを振りますが、各ロールは今や有利なものです。各ステップで、ボードの下で形成されている混同グラフを確認し、エッジを追加する単語(つまり、2つの可能なホームを持つサーブされた文字、または同じタイルを取り得る2つの空きセル)を避けるように誘導します。
この新しいアプローチを適用すると、ボードは最終的に数千単位で生成されるようになりました。まだリトライ制限を上げたり、タイムアウトを緩めたり、再シードしたりする必要があるタイトな状況もありますが、十分に信頼性高く動作するため、現在9,000以上のプレイ可能なパズルのライブラリが用意されており、約10年分のデイリーパズルに相当します。
数字、再見
振り返ってみると、この投稿のタイトルは逆だと思います。誰も知らない数字は、数学の最前線にある遠い定数ではありません。それは、ミニチュアで、すべてのボードにここにあります。各動きは、単一の答えを持つ小さな質問です:この文字はどのセルに入るのか?ほとんどの場合、周囲の単語がそれを特定し、あなたは考えずに答えます。しかし、シャノンからのその洞察がなければ、私は両方のセルが同じ文字にフィットし、両方とも実際の単語を綴り、ボード上にはそれらを区別するものが何もないという状況に陥っていたでしょう。その瞬間、正しいセルは本当に知ることができないものになります。誰も知らない数字、あるいは文字。これの最終的な解決策は、多くの場合と同様に、コンテキストを追加することです。もう1つのタイルを明らかにする、もう1つの交差する単語を埋める、そして知ることができないものは単一の曖昧さのない選択になります。
アルフレッド・ノース・ホワイトヘッドはかつて、「単純さを求めよ、そしてそれを疑え」と言いました。これは私が何度も再学習することを運命づけられている教訓のようです。一方、あなたはそれを完全に信頼することができます:1つの文字、1つのセル、そして一度も推測することはありません。
これは実際のゲームです、Motplot。興味があれば試してみてください。