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.

See also "Elwyn Berlekamp (1940-2019)."

Elwyn Berlekamp (1940-2019)

Elwyn R. Berlekamp, who died on April 9, 2019, was an accomplished computer scientist and an expert in combinatorial game theory. In 2000, I wrote about his book on the seemingly simple game of Dots and Boxes.

Dots and Boxes

The familiar pencil-and-paper game of Dots and Boxes sounds exceedingly simple.

Given a square or rectangular array of dots, two players take turns joining two adjacent dots with a horizontal or vertical line. When such a move adds the fourth side of a box, the player who did the deed claims the box (marking it with his or her initial) and must take an extra turn. If the same move closes two boxes, the player claims both boxes but still gets only one bonus move. A player who can complete a box is not obliged to do so. The game ends when all the boxes are taken. The player who closed more boxes wins.

Despite the simplicity of its rules, the game can be played on several different levels of sophistication.

"Like many other children, I learned to play the game of Dots-and-Boxes soon after I entered grade school," mathematician Elwyn R. Berlekamp of the University of California, Berkeley, noted in the preface to his book The Dots and Boxes Game: Sophisticated Child's Play (CRC Press, 2000). "That was in 1946."

"Ever since then I have enjoyed recurrent spurts of fascination with this game," he continued. "During several of these bursts of interest, my playing proficiency broke through to a new and higher plateau."

In Dots and Boxes, "each advance can be associated with a new mathematical insight," Berlekamp claimed. Indeed, "a surprisingly large amount of mathematics is very relevant to this game."

Berlekamp posited that the game can be played on at least four different levels. "Players at any level consistently beat players at lower levels, and do so because they understand a theorem which less sophisticated players have not yet discovered," he said.

Berlekamp's book serves as an eye-opening guide to Dots-and-Boxes strategies and an introduction to mathematical game theory.

Novice players tend to play at random. Before long, however, they typically begin to adopt rudimentary strategies to improve outcomes.

Initially, the idea is to keep adding lines while ensuring that no square in the grid has three filled-in edges. The result is a kind of maze with a number of chains, or sequences of connected boxes. You and your opponent then trade the rights to different chains of squares. Here's how to proceed:

• Make sure there are several long chains (three or more squares in length) and try to force your opponent to be the first to open one.
• When you have control by forcing your opponent to open a long chain, make sure you keep it by declining two boxes of every long chain except the last.
• To take control, the first player tries to make the sum of the number of dots in the array plus the number of moves in which a single stroke completes two boxes (a doublecrossed move) odd. The second player tries to make the sum even.

In simple games, the number of doublecrosses will be one less than the number of long chains.This leads to the "long chain rule": Try to make the number of initial dots plus the number of eventual long chains even if you play first, odd if you play second. Such a strategy leaves the doublecrossed moves to your opponent.

The rule also ensures that an alert layer starting second can always win a nine-box game.

Berlekamp's book presents a number of elementary chain-counting problems (with solutions), then proceeds to advanced chain counting, nimstring graphs, and other mathematical theory for expert play. He concludes his book with a set of unsolved problems--game situations on 5-by-5 grids that have so far escaped definitive solution.

Challenge: Find a move that will win this game.

Dots and Boxes is the sort of game for which it is relatively easy to find simple, effective strategies for improved play. At the same time, important aspects of the game continue to elude analysis. There are so many possible moves on even a 5-by-5 grid of squares that no computer can try all the possibilities to find a path to a guaranteed win and play a perfect game.

In fact, a 5-by-5 playing field is an ideal venue for testing strategies. A game on such a grid offers plenty of challenge yet can be played in a reasonably short time.

Originally posted October 30, 2000.

Hyperbolic Five

Dutch graphic artist M.C. Escher (1898-1972) devised many highly original schemes in his attempts to capture the concept of infinity visually. One strategy he often employed was to create repeating patterns of interlocking figures. However, although he could imagine how such arrays extended to infinity, the actual pattern he drew represented only a fragment of an infinite expanse.

Circle Limit III by M.C. Escher. Collection of the National Gallery of Art. Photo by I. Peterson

Another approach Escher tried was to draw replicas of a figure, such as a fish, that diminish in size as they recede from a point in the middle of a circular frame. In this case, he took advantage of the peculiarities of hyperbolic geometry to create an illusion of infinity.

If you draw any triangle on a sheet of paper and add up its three interior angles, the result is always 180 degrees. When you draw a triangle on a saddle-shaped surface, however, the angles add up to fewer than 180 degrees.

Just as a flat surface is a piece of the infinite mathematical surface known as the Euclidean plane, so a saddle-shaped surface can be thought of as a small piece of the hyperbolic plane. Picturing what the hyperbolic plane looks like on a larger scale, however, requires some mind-bending ingenuity.

To get a feel for what the hyperbolic plane is like, you could try to sew together pieces of cloth in the shape of pentagons, creating, in effect, a tiling of the hyperbolic plane. Mathematician and sculptor Helaman Ferguson has done that to fashion a persistently wrinkly hyperbolic quit by sewing the fabric so that four pentagons meet at each corner. He aptly describes his creation as an "unruly quilt that refuses to lie flat."

Helaman Ferguson's "unruly" hyperbolic quilt, sewn together from pentagons of cloth, refuses to lie flat. Photo: I. Peterson

Instructions for sewing a hyperbolic blanket, courtesy of Jeff Weeks.

Such constructions are not the only way to visualize the hyperbolic plane. More than a century ago, Henri Poincare (1854-1912) introduced a method for representing the entire hyperbolic plane on a flat, disk-shaped surface.

In Poincare's model, the hyperbolic plane is compressed to fit within a circle. The circle's circumference represents points at infinity. In this context, a straight line, meaning the shortest distance between two points, is a segment of a circular arc that meets the Poincare disk's circular boundary at right angles.

Poincare representation of a pentagonal tiling of the hyperbolic plane in which four pentagons meet at each vertex. Courtesy of Helaman Ferguson.

Although this model distorts distances, it represents angles faithfully. The hyperbolic measure of an angle is equal to that measured in the disk representation of the hyperbolic plane. A repeating pattern made up of identical geometric shapes in the hyperbolic plane, when represented in a Poincare model, transforms into an array of shapes that diminish in size as they get closer to the disk's bounding circle.

In his artwork Hyperbolic 5, Ferguson has created a particularly striking representation of the hyperbolic plane. It shows necklaces of pentagonal tiles going around a central pentagon in alternating gold fives and mirror images of gold fives.

Hyperbolic 5 by Helaman Ferguson. Courtesy of Helaman Ferguson.

The gold "5" is a reference to a famous painting by Charles Demuth (1883-1935) titled The Figure 5 in Gold. Demuth's painting was itself inspired by an imagist poem, "The Great Figure," by his friend and colleague William Carlos Williams (1883-1963).

"My particular inspiration for Hyperbolic 5 was both Williams and Demuth, especially Williams," Ferguson says. "Somehow I felt Williams' verbal images were even more powerful than the painting."

Watch and listen to William Carlos Williams present his poem "The Great Figure" (Quicktime video).

"We have a checkerboard of red and blue right-angled pentagons," Ferguson explains. "This is possible because the hyperbolic plane has uncountably many more triangles and consequently more pentagons than the Euclidean plane has."

In this representation, each necklace has five times a Fibonacci number of pentagons. The Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, and so on, where each successive number is the sum of the previous two numbers.

An infinite checkerboard like the one depicted in Hyperbolic 5 is a wonderful playground for the mind, Anyone interested in a game of hyperbolic chess or Go?

Originally posted Sept. 1, 2003.

See also "Hyperbolic Quilt," "Vonda McIntyre (1948-2019)," and "Bead Creatures."

Vonda McIntyre (1948-2019)

Vonda N. McIntyre, who died on April 1, 2019, was a noted author of science fiction. She also had a fascinating hobby: stringing beads into intricate structures, some with a mathematical basis. I wrote about her hobby in 2004.

Anatomy of a Bead Creature

Vonda N. McIntyre is best known as a writer of science fiction. Her 1997 book, The Moon and the Sun, won the Nebula Award for best novel. She also has an intriguing hobby: creating intricately crinkled creatures out of tiny beads.

"I always have to have a fiddly hobby," McIntyre says. She had done needlepoint and crocheting before being attracted to beadwork. But making patterns on essentially a flat surface was a little too mundane for her. Experimenting with various ways of stringing beads, she developed methods for producing objects with wavy or frilled edges.

McIntyre's bead creations resemble exotic sea creatures: sparkly sea anemones or colorful sea slugs.

Her anemones consist of concentric circles of circles of beads. Starting from the middle, each circles has twice as many beads as the previous circle. After just three or four circles, the nascent bead critter is already quite frilly. Her sea slugs (nudibranchs) start with a line of beads.

People can't resist picking up McIntyre's creations and playing with them. "They're irresistible," McIntyre says. "People enjoy the feel of the beads in their hands." To some, the bead creatures feel alive.

Inspired by an article on artistic representations of the hyperbolic plane, McIntyre tried a slightly different approach. Her basic unit consisted of five diamonds (rhombuses) meeting to form a star. Each pair of exposed edges then became the starting point of a new star unit.

The resulting creature can't lie flat. It automatically wrinkles, yet any part of the crinkled bundle can be flattened out to reveal the same five-diamond unit. It's McIntyre's own model of the hyperbolic plane, where the angles of a triangle always add up to fewer than 180 degrees.

From a distance, McIntyre's earlier anemones and her new creatures look similar, yet they have quite different structures. Together, her bead creatures offer a unique, hands-on experience with non-Euclidean geometry.

Originally posted April 19, 2004.

See also "Hyperbolic Quilt," "Bead Creatures," "Hyperbolic Crocheting," "Hyperbolic Five," and "Hyperbolic Rose."