# Ivars Peterson's MathTrek

April 29, 2002

## Getting Clobbered

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

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

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.

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 last summer at a combinatorial game theory conference in Halifax 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 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 they proceed, games 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," says Elwyn Berlekamp of the University of California, Berkeley. "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 says. "Even one-dimensional Clobber isn't fully understood." In one-dimensional Clobber, stones are arranged in a single row or column.

Berlekamp has offered a prize of \$1,000 (Canadian funds) for inventing the "best" Clobber problem. Each entry must specify a certain arrangement of pieces, which player is to move next, and what the final outcome should be. Each such position must be accompanied by a solution that indicates how to play it against all plausible opposing strategies to obtain the required result.

Entries should be submitted to Berlekamp. He will announce the names of the winners at the Third International Conference on Computers and Games, to be held July 25-27 in Edmonton, Alberta.

Clobber can be played on a rectangular grid of any size. Initially, mathematicians suspected 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 comments.

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 calls 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 have 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 explains. 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 stones is not divisible by 3. "If the number of squares is divisible by 3, you can get down to exactly two stones," Erik Demaine says. 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!

References:

Demaine, E.D., M.L. Demaine, and R. Fleischer. Preprint. Solitaire Clobber. Available at http://xxx.lanl.gov/abs/cs.DM/0204017 or http://www.cs.ust.hk/tcsc/RR/index_5.html.

The announcement of the Clobber problem composition contest can be found at http://www.cs.ualberta.ca/~cg2002/an_clobber.html. Additional information about Clobber is available at http://www.gustavus.edu/~wolfe/games/clobber/.

The Third International Conference on Computers and Games, July 25-27, 2002, in Edmonton, Alberta, has a Web page at http://www.cs.ualberta.ca/~cg2002/.

Information about "Combinatorial Games at Dalhousie 2001" can be found at http://www.mscs.dal.ca/~rjn/ECC/games2001.html.

Photos from the first international Clobber tournament at the Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, February 17-22, 2002, are available at http://www.cs.ust.hk/faculty/rudolf/Images/Dag_game_02/dag_game_02.html.

Anyone is welcome to play Clobber using Toby Gottfried's Java applet at http://www.gottfriedville.net/games/clobber/.