ベルレカンプのスイッチングゲーム

バーレカンプスイッチングゲームは、アメリカの数学者エルウィン・バーレカンプが提唱した数学ゲームである。^[1]このゲームは、独立して同じゲームを発見したデイビッド・ゲイルにちなんで、ゲイル・バーレカンプスイッチングゲームとも呼ばれている。^{[2 ] あるいはアンバランスライトゲーム[3]}このゲームでは、2列のスイッチで制御される電球のシステムがあり、一方のゲームプレーヤーは多くの電球を点灯させ、もう一方はできるだけ多くの電球を消灯させようとする。このゲームは、符号理論における被覆半径の概念を示すために使用できる。

このゲームで使う道具は、いくつかの数字との大きさの電球が長方形に並んだ部屋です。部屋の片側にあるスイッチ群は、各電球を個別に制御します。これらのスイッチの 1 つを切り替えると、電球は、以前の状態に応じて、オフからオンに、またはオンからオフに切り替わります。部屋の反対側には、電球の各行または列に対応する別のスイッチ群があります。これらのスイッチのいずれかを切り替えると、それが制御する行または列のすべての電球が、以前の状態に応じて、オフからオンに、またはオンからオフに切り替わります。複数のスイッチを切り替える場合、スイッチを切り替える順序は結果に影響しません。どの順序で切り替えても、切り替えのシーケンスの最後には同じ電球が点灯します。 ${\displaystyle a\times b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle ab}$${\displaystyle a+b}$

ゲームは 2 ラウンドでプレイされます。第 1 ラウンドでは、最初のプレーヤーが個々のライトを制御するスイッチを使用して、ライトを任意にオンまたはオフに設定します。第 2 ラウンドでは、2 番目のプレーヤーがライトの行または列を制御するスイッチを使用して、最初のプレーヤーが設定したライトのパターンを別のパターンに変更します (または、変更しない場合もあります)。最初のプレーヤーの目標は、ゲーム終了時に点灯しているライトをできるだけ多く残すことであり、2 番目のプレーヤーの目標は、点灯しているライトをできるだけ少なくすることです。したがって、最初のプレーヤーは、2 番目のプレーヤーが多くのライトを消すことができないライトのパターンを選択する必要があります。

バーレカンプは1966年から1971年までニュージャージー州マレーヒルのベル研究所で働いていた。 ^[4]在職中、彼は数学科の共用室でこのゲームの物理的な実例を構築した。 ^{[1] [2]}デビッド・ゲイルも1971年より前にこのゲームを独自に発明した。^[5]${\displaystyle 10\times 10}$

関連する問題に関する初期の研究には、 Andrew M. Gleason  (1960) の論文が含まれる。Gleason のコンピュータ実験は、ゲームにおいて、2 番目のプレーヤーがランダムにプレイする最初のプレーヤーに対してどれだけうまくやれるかを問うものと解釈できる。 ^[6]また、JW Moon とLeo Moser  (1966) の論文は、Gleason の疑問を理論的に解決し、最初のプレーヤーのほとんどすべての選択に対して、ゲームボードのサイズが大きいという限界において、最適なゲーム値が に近いことを示した。^[7]${\displaystyle 15\times 15}$${\displaystyle {\tfrac {1}{2}}n^{2}}$

数学的には、最初のプレーヤーの動きによって点灯するライトを集合 と表現でき、2 番目のプレーヤーの最善のプレイによって達成できるライトの最小数を数値 と表現できます。最初のプレーヤーにとっての最善のプレイは、を最大化する集合を選択することです。したがって、最初のプレーヤーの最善のプレイによって達成できるライトの最大数を数値 と表現できます。個々のゲームでどのようにうまくプレイするかという質問を超えて、数学的研究の対象となってきたより広範な質問は、一般に の値を および の関数として特徴付けること、関数としてのその動作を決定すること、またはとのできるだけ多くの組み合わせに対してその値を計算することです。 ${\displaystyle S}$${\displaystyle f(S)}$${\displaystyle S}$${\displaystyle f(S)}$${\textstyle R_{a,b}=\max _{S}f(S)}$${\displaystyle R_{a,b}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$

正方配列の場合はについて解かれています。さらに の下限値が見つかりました。^{[8] [9] [10] [11]}これらの数値は次のとおりです。 ${\displaystyle n\times n}$${\displaystyle n\leq 12}$${\displaystyle R_{n,n}}$${\displaystyle n\leq 20}$

漸近的に、これらの数は として増加します。^{[2] [5] [12]}${\displaystyle {\tfrac {n^{2}}{2}}-\Theta (n^{3/2})}$

どのスイッチを切り替えるかの選択肢は指数関数的に多いため、 が大きい場合、最適な選択肢を徹底的に探すことは不可能であり、計算能力に制限のあるプレイヤーがこのゲームをどれだけうまくプレイできるかという疑問が生じます。 ${\displaystyle n}$

最初のプレイヤーはランダムにプレイすることで、期待されるゲーム値を にすることができます。同様に、2 番目のプレイヤーはランダムにプレイすることで、 からの期待距離が である値を得ることができます。この値は より大きい場合も小さい場合もありますが、大きい場合は、2 番目のプレイヤーはすべての行スイッチを切り替えることで、同じ量だけ小さい値を得ることができます。^{[2] [5] [12] 2 番目のプレイヤーのこのランダム戦略は、}条件付き確率法を使用して非ランダムにすることができ、同じ解の値を保証する多項式時間アルゴリズムが得られます。異なるデランダム化により、複雑性クラスNCの並列アルゴリズムが得られます。^[13]${\displaystyle {\tfrac {n^{2}}{2}}-O(n^{3/2})}$${\displaystyle {\tfrac {n^{2}}{2}}}$${\displaystyle \Omega (n^{3/2})}$${\displaystyle {\tfrac {n^{2}}{2}}}$

最初のプレイヤーがどの電球を点灯するかを選択した後、2番目のプレイヤーにとって最適な選択を見つけることはNP困難な問題です。^[14]しかし、このゲームには多項式時間の近似スキームがあり、任意の に対して、時間 で点灯する電球の最小数の 倍だけを残す選択を2番目のプレイヤーに見つけることができます。^[15]${\displaystyle n\times n}$${\displaystyle (1+\varepsilon )}$${\displaystyle \varepsilon >0}$${\displaystyle O(n^{2})+2^{O(1/\varepsilon ^{2})}}$

ベルレカンプのスイッチングゲームは、あるバイナリ線形コードの被覆半径のデモンストレーションとして、符号理論で使用できます。長さと次元のバイナリ線形コードは、2 つの要素 、 を持つ有限体上の次元ベクトル空間の次元線形部分空間として定義されます。部分空間の要素はコードワードと呼ばれ、被覆半径はのすべての点がコードワードの ハミング距離内にある最小の数です。${\displaystyle n}$${\displaystyle d}$${\displaystyle d}$${\displaystyle n}$ ${\displaystyle \mathbb {F} _{2}^{n}}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle r}$${\displaystyle \mathbb {F} _{2}^{n}}$ ${\displaystyle r}$

およびと します 。これらのパラメータ値に対して、ベクトル空間は電球の配列上の点灯した電球のすべての可能なパターンを記述します。ベクトル加算演算は、2 つのパターンのうちの 1 つに現れる電球を点灯することによって 2 つのパターンを結合します (点灯した電球の集合に対する対称差演算)。2 番目のプレーヤーが完全にオフにできるすべてのパターン、または完全にオフになっているボードから始めて 2 番目のプレーヤーが作成できるすべてのパターンで構成される線形サブスペースを定義できます。2 番目のプレーヤーは2 番目のスイッチ バンクをどのように設定するかを選択できますが、このサブスペースには要素があり、次元が になります。これは、2 番目のプレーヤーのすべてのスイッチを切り替えても点灯した電球のパターンには影響がないためです。 ${\displaystyle n=ab}$${\displaystyle d=a+b-1}$${\displaystyle \mathbb {F} _{2}^{n}}$${\displaystyle a\times b}$${\displaystyle 2^{a+b}}$${\displaystyle 2^{a+b-1}}$${\displaystyle a+b-1}$

は、このコードの被覆半径です。最初のプレイヤーがベストプレイで選んだ点灯電球のセットは、線形部分空間から可能な限り遠い点になります。2番目のプレイヤーがベストプレイで状態を変更した電球のセットは、線形部分空間で最も近い点になります。これらの選択後も点灯したままの電球のセットは、その番号がこれら2つの点間のハミング距離を定義します。^[1]${\displaystyle R_{a,b}}$${\displaystyle \mathbb {F} _{2}^{n}}$

• ライトアウト（ゲーム）は、複数の電球を制御するスイッチを使用して電球を消すという別のパズルです。