April 17, 2019

Getting Clobbered

Clobber is a two-person game that's easy to learn and fun to play and, for the mathematically inclined, rife with analytical possibility.

The "standard" game is played on a rectangular grid of squares--say, a portion of a checkerboard. One player governs the movement of white pieces, or stones, and the other player moves black stones. Initially, each square is occupied by a white or black stone, arranged so that the colors alternate.

Initial placement of black and white stones on a 5 x 6 rectangular board.

Each player moves in turn, picking up one of his or her own stones and "clobbering" an opponent's stone on a vertically or horizontally adjacent square. (Diagonal moves are not allowed.) The clobbered stone is removed from the board and replaced by the stone that was moved.

White starts. The game ends when a player can't move because none of his or her remaining stones is adjacent to a stone of the opposite color and, hence, can't clobber an opponent's stone. That player loses.

Clobber was invented in 2001 at a combinatorial game theory conference in Halifax, Nova Scotia, by Michael Albert of the University of Otago, New Zealand, J.P. Grossman of the Massachusetts Institute of Technology, and Richard J. Nowakowski of Dalhousie University. The first competitive Clobber tournament was held in February 2002 at the Dagstuhl Seminar on Algorithmic Combinatorial Game Theory in Germany, where the games were played on a 5 x 6 board.

Clobber is an example of a combinatorial game--one in which two players move alternately and no chance or hidden information is involved. It ends in a finite number of moves, and the winner is the one who moves last.

As games of Clobber proceed, they typically decompose into smaller collections of pieces--or positions. Players can develop strategies for which moves to make to ensure a win in various situations.

"It's a fascinating game," Elwyn Berlekamp of the University of California, Berkeley, noted in 2002. "Clobber is full of opportunities for creating interesting positions to be solved."

Moreover, "nobody yet knows what constitutes a good opening for the game," Berlekamp said. "Even one-dimensional Clobber isn't fully understood." In one-dimensional Clobber, stones are arranged in a single row or column.

Clobber can be played on a rectangular grid of any size. Initially, mathematicians expected that positions on square boards would be relatively easy to solve, but that has proved not to be the case. "There seems to be no reason not to play on a square board," Berlekamp commented.

Moreover, you don't have to start with a board in which the stones alternate in color. In one Clobber variant, the players begin with a blank board, then take turns putting a stone on the board until the board is filled, creating their own starting configuration. Berlekamp called this phase "pre-Clobber."

Erik Demaine and Martin Demaine of the Massachusetts Institute of Technology and Rudolf Fleischer of the Hong Kong University of Science and Technology studied a solitaire version of Clobber.

"The rules are exactly the same, but ... the white and black players cooperate, becoming effectively a single player," Erik Demaine explained. The goal is to remove as many stones as possible from the board by alternating white and black moves.

It turns out that, for a rectangular board with at least two rows and two columns, you can get down to a single stone if the total number of stone is not divisible by 3. "If the number of squares is divisible by 3, you get down to exactly two stones," Erik Demaine said. In a one-dimensional game (a row of alternating white and black stones), you can remove only about three-quarters of the stones.

There's much more to learn, Time to go clobbering!

Originally posted April 29, 2002.

No comments: