Berlekamp switching game

The equipment for playing the game consists of a room containing rectangular array of lightbulbs, of dimensions $a\backslash times\; b$ for some numbers $a$ and $b$. A bank of $ab$ switches on one side of the room controls each lightbulb individually. Flipping one of these switches changes its lightbulb from off to on or from on to off, depending on its previous state. On the other side of the room is another bank of $a+b$ switches, one for each row or column of lightbulbs. Whenever any of these switches is flipped, every lightbulb in the row or column that it controls changes from off to on or from on to off, depending on its previous state. When flipping more than one switch, the order in which the switches are flipped does not make a difference to the outcome: the same lightbulbs will be lit at the end of the sequence of flips no matter what order they are flipped.

The game is played in two rounds. In the first round, the first player uses the switches that control individual lights, to set the lights on or off arbitrarily. In the second round, the second player uses the switches that control rows or columns of lights, changing the pattern of lights set by the first player into another pattern (or, possibly, leaving it unchanged). The goal of the first player is to have as many lights remaining lit at the end of the game as possible, and the goal of the second player is to have as few lights remaining lit as possible. Therefore, the first player should choose a pattern of lights for which the second player cannot turn off many lights.

Berlekamp worked at Bell Labs in Murray Hill, New Jersey from 1966 to 1971.{{cite web|url=https://news.berkeley.edu/2019/04/18/elwyn-berlekamp-game-theorist-and-coding-pioneer-dies-at-78/|title=Elwyn Berlekamp, game theorist and coding pioneer, dies at 78|work=Berkeley News|first=Robert|last=Sanders|date=April 18, 2019|publisher=University of California, Berkeley}} While there, he constructed a physical instance of this game for the case $10\; \backslash times\; 10$ in the Mathematics Department commons room. David Gale also invented the game independently, some time prior to 1971.{{cite journal | last1 = Brown | first1 = Thomas A. | last2 = Spencer | first2 = Joel H. | doi = 10.4064/cm-23-1-165-171 | journal = Colloquium Mathematicum | mr = 307944 | pages = 165–171, 177 | title = Minimization of $\backslash pm\; 1$ matrices under line shifts | volume = 23 | year = 1971| doi-access = free }}

Early research on related problems included publications by {{harvs|first=Andrew M.|last=Gleason|authorlink=Andrew M. Gleason|year=1960|txt}}, whose computer experiments can be interpreted as asking, for the $15\backslash times\; 15$ game, how well the second player can do against a first player who plays randomly,{{cite conference | last = Gleason | first = Andrew M. | authorlink = Andrew M. Gleason | editor1-last = Bellman | editor1-first = Richard | editor1-link = Richard E. Bellman | editor2-last = Hall | editor2-first = Marshall Jr. | editor2-link = Marshall Hall (mathematician) | contribution = A search problem in the $n$-cube | location = Providence, Rhode Island | mr = 0114323 | pages = 175–178 | publisher = American Mathematical Society | series = Proceedings of Symposia in Applied Mathematics | title = Combinatorial Analysis | volume = 10 | year = 1960}} and by {{harvs|first1=J. W.|last1=Moon|first2=Leo|last2=Moser|author2-link=Leo Moser|year=1966|txt}}, who address Gleason's question theoretically, showing that for almost all choices of the first player, in the limit of large game board sizes, the optimal game value is close to $\backslash tfrac\{1\}\{2\}n^2$.{{cite journal | last1 = Moon | first1 = J. W. | last2 = Moser | first2 = L. | author2-link = Leo Moser | issue = 37 | journal = Matematički Vesnik | mr = 207570 | pages = 209–211 | title = An extremal problem in matrix theory | url = https://eudml.org/doc/259432 | volume = 3(18) | year = 1966}}

Mathematically, one can describe the lights turned on by the first player's move as a set $S$, and the smallest number of lights that can be achieved by the best play for the second player as a number $f(S)$. The best play for the first player is to choose a set $S$ that maximizes $f(S)$. Therefore, one can describe the largest number of lights that can be achieved by the best play for the first player as a number $R\_\{a,b\}\; =\; \backslash max\_S\; f(S)$. Beyond the question of how to play well in an individual game, a broader question that has been the object of mathematical research is to characterize the value of $R\_\{a,b\}$ in general, as a function of $a$ and $b$, to determine its behavior as a function, or to calculate its value for as many combinations of $a$ and $b$ as possible.

The case of a square $n\; \backslash times\; n$ array has been solved for $n\; \backslash leq\; 12$. Additionally, lower bounds for $R\_\{n,n\}$ have been found for $n\; \backslash leq\; 20$.{{cite journal |last1=Carlson |first1=Jordan |last2=Stolarski |first2=Daniel |title=The correct solution to Berlekamp's switching game |journal=Discrete Mathematics |date=October 2004 |volume=287 |issue=1–3 |pages=145–150 |doi=10.1016/j.disc.2004.06.015|doi-access=free|mr=2094708 }}{{cite OEIS|A005311|Solution to Berlekamp's switching game (or lightbulb game) on an n X n board}}{{cite journal |last1=Pellegrino |first1=D. |last2=Raposo Jr |first2=A. |year=2022 |title=Constants of the Kahane–Salem–Zygmund inequality asymptotically bounded by 1 |journal=Journal of Functional Analysis |volume=282 |issue=2 |page=109293 |arxiv=2006.12892 |doi=10.1016/j.jfa.2021.109293 |s2cid=231895733}}{{Cite arXiv|last1=Pellegrino |first1=D. |last2=Raposo Jr |first2=A. |title=Upper bounds for the constants of Bennett's inequality and the Gale-Berlekamp switching game |year=2021 |class=math.CO |eprint=2111.00445v3}} These numbers are:

Asymptotically, these numbers grow as $\backslash tfrac\{n^2\}\{2\}-\backslash Theta(n^\{3/2\})$.{{cite conference | last1 = Komlós | first1 = J. | author1-link = János Komlós (mathematician) | last2 = Sulyok | first2 = M. | contribution = On the sum of elements of $\backslash pm\; 1$ matrices | mr = 0299500 | pages = 721–728 | title = Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969) | year = 1970}}

Because there are exponentially many choices for which switches to flip, an exhaustive search for the optimal choice is not possible for large $n$, setting up the question of how well computationally-limited players can play this game.

The first player can cause the expected game value to be $\backslash tfrac\{n^2\}\{2\}-O(n^\{3/2\})$ by playing randomly. Similarly, the second player can obtain a value whose expected distance from $\backslash tfrac\{n^2\}\{2\}$ is $\backslash Omega(n^\{3/2\})$ by playing randomly; this value might either be larger or smaller than $\backslash tfrac\{n^2\}\{2\}$, but if it is larger the second player can flip all row switches to get a value that is smaller by the same amount. This random strategy for the second player can be made non-random using the method of conditional probabilities, giving a polynomial time algorithm that obtains the same solution value guarantees. A different derandomization gives a parallel algorithm in the complexity class NC.{{cite journal | last = Berger | first = Bonnie | authorlink = Bonnie Berger | doi = 10.1137/S0097539792240005 | issue = 4 | journal = SIAM Journal on Computing | mr = 1460721 | pages = 1188–1207 | title = The fourth moment method | volume = 26 | year = 1997| s2cid = 14313557 }}

Finding the optimal choice for the second player in the game, once the first player has chosen which bulbs to light, is an NP-hard problem.{{cite journal | last1 = Roth | first1 = Ron M. | last2 = Viswanathan | first2 = Krishnamurthy | doi = 10.1109/TIT.2007.915716 | issue = 3 | journal = IEEE Transactions on Information Theory | mr = 2445050 | pages = 1050–1060 | title = On the hardness of decoding the Gale–Berlekamp code | volume = 54 | year = 2008}} However, there is a polynomial-time approximation scheme for the $n\backslash times\; n$ game that can find a choice for the second player that leaves only $(1+\backslash varepsilon)$ times the minimum possible number of lit bulbs, for any $\backslash varepsilon>0$, in time $O(n^2)+2^\{O(1/\backslash varepsilon^2)\}$.{{cite conference | last1 = Karpinski | first1 = Marek | author1-link = Marek Karpinski | last2 = Schudy | first2 = Warren | editor-last = Mitzenmacher | editor-first = Michael | editor-link = Michael Mitzenmacher | contribution = Linear time approximation schemes for the Gale–Berlekamp game and related minimization problems | doi = 10.1145/1536414.1536458 | pages = 313–322 | publisher = ACM | title = Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 | title-link = Symposium on Theory of Computing | year = 2009| arxiv = 0811.3244 }}

The Berlekamp switching game can be used in coding theory as a demonstration of the covering radius of a certain binary linear code. A binary linear code of length $n$ and dimension $d$ is defined as a $d$-dimensional linear subspace of the $n$-dimensional vector space $\backslash mathbb\{F\}\_2^n$ over the finite field with two elements, $\backslash mathbb\{F\}\_2$. The elements of the subspace are called codewords, and the covering radius is the smallest number $r$ such that every point of $\backslash mathbb\{F\}\_2^n$ is within Hamming distance $r$ of a codeword.

Let $n\; =\; ab$ and $d\; =\; a\; +\; b\; -\; 1$. For these parameter values, the vector space $\backslash mathbb\{F\}\_2^n$ describes all possible patterns of lit bulbs on the $a\backslash times\; b$ array of lightbulbs, with a vector addition operation that combines two patterns by lighting the bulbs that appear in exactly one of the two patterns (the symmetric difference operation on the sets of lit bulbs). One can define a linear subspace consisting of all patterns that the second player can turn completely off, or equivalently of all patterns that the second player could create starting with a board that is completely off. Although the second player has $2^\{a+b\}$ choices for how to set the second bank of switches, this subspace has $2^\{a+b-1\}$ elements, giving it dimension $a+b-1$, because flipping all of the second player's switches has no effect on the pattern of lit bulbs.

Then $R\_\{a,b\}$ is the covering radius of this code. The set of lit bulbs chosen by the first player, with best play, gives a point of $\backslash mathbb\{F\}\_2^n$ that is as far as possible from the linear subspace. The set of bulbs whose state is changed by the second player, with best play, gives the closest point in the linear subspace. The set of bulbs that remain lit after these choices are the ones whose number defines the Hamming distance between these two points.

• Lights Out (game), a different puzzle involving turning off lightbulbs using switches that control multiple bulbs

Category:Coding theory

Category:Mathematical games