The Quest | The Free Press of Reed College

Cool Thesis of the Week: Andy Malkin

Some games, maybe one played on a paper tablecloth waiting for food at a restaurant, don’t seem like they were meant to be taken seriously.

But Andy Malkin ’13, of Ojai, California, says there’s a lot behind even some simple games. Andy is writing his math thesis with professors Joe Roberts and Jamie Pommershein on the math behind one such game, dots and boxes. His thesis will use game-theoretic analysis to explore the mathematics behind the game and develop winning strategies.

The rules of dots and boxes are simple. A grid of dots is drawn, and two players take turns drawing lines between two dots. When a player closes a square by drawing the last line to connect four dots, they win a point, and go again. When all the possible lines are drawn, the player with the most points wins. Dots and boxes is impartial, meaning that all moves are available to both players, and it is combinatorial, meaning players have perfect information and move in defined ways to reach a defined goal. This means the game is fairly simple in the beginning, says Andy. It gets interesting when long chains open up where each closed box leads to another. Eventually, the game board reaches a “post-saturated” state, when “every play you make opens up a chain for someone else,” says Andy.

“The last person in [dots and boxes] who goes, loses.”

At this point, the game becomes about opponents trading points with each other. When a player knows that each move will give away a chain, a simple strategy is to look for the smallest chain, and give that one away. However, says Andy, there are better ways. One more effective strategy is called the double-cross: As a player runs down a chain, they don’t take all the available boxes. Instead, they leave the last two or three boxes open. Though they have gotten less points immediately than they could have, the player can then use their next move to give this smaller chain to their opponent, rather than a bigger one elsewhere on the board. The game can continue in this way, with one player taking the majority of big chains, and leaving the ends to the other, until the more strategic player wins. “There are other ways” too, says Andy. He will work out more in the course of researching his thesis.

Andy will also bring in lessons from other games. He will study Nim, a game in which players take turns dividing piles of objects into uneven groups. The last person who can no longer divide any pile into uneven groups loses. Like Nim, Andy says, “the last person in my game who goes, loses.” Andy will work out a proof for this claim as part of his thesis.

Andy says he likes his thesis because it is game theoretic and because of its usefulness. As he puts it, “I’m going to fucking own at this game.”

Each week, The Quest profiles the thesis of one senior whose work is worth sharing with the Reed community. The purpose of this column is to increase awareness among Reedies of the work being done in various academic fields and to make disparate forms of scholarship accessible and understandable to all. Do you have or know of a thesis that compels attention? Just want to see your face in the Quest? Email ablum@reed.edu with “Cool Thesis” in the subject line.

Leave a Reply