It can be used to demonstrate the concept of covering radius in coding theory.
The equipment for playing the game consists of a room containing rectangular array of lightbulbs, of dimensions
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.
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.
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.
Berlekamp worked at Bell Labs in Murray Hill, New Jersey from 1966 to 1971.
[4] While there, he constructed a physical instance of this game for the case
[1][2] David Gale also invented the game independently, some time prior to 1971.
[5] Early research on related problems included publications by Andrew M. Gleason (1960), whose computer experiments can be interpreted as asking, for the
game, how well the second player can do against a first player who plays randomly,[6] and by J. W. Moon and Leo Moser (1966), 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
[7] Mathematically, one can describe the lights turned on by the first player's move as a set
, to determine its behavior as a function, or to calculate its value for as many combinations of
, setting up the question of how well computationally-limited players can play this game.
Similarly, the second player can obtain a value whose expected distance from
by playing randomly; this value might either be larger or smaller than
, but if it is larger the second player can flip all row switches to get a value that is smaller by the same amount.
[2][5][12] 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.
game that can find a choice for the second player that leaves only
times the minimum possible number of lit bulbs, for any
The elements of the subspace are called codewords, and the covering radius is the smallest number
describes all possible patterns of lit bulbs on the
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.
, because flipping all of the second player's switches has no effect on the pattern of lit bulbs.
The set of lit bulbs chosen by the first player, with best play, gives a point of
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.