Atropos: The Sperner Game


In ancient Greece, twin sons played a game to escape the whim of the Fates... Read the whole story here. (Thanks to Niky Riga and Michalis Potamias for revisions on the myth!)

This is the homepage for Atropos, a game played on the Sperner Triangle. Although this page is currently sparse, we will continue to add to it. Most importantly, we have a working Java applet of the game, which can be played here. Java 1.2 is required in your browser to play (this used to be 1.6, but this was changed). The rules of the game are simple: two players take turns coloring white circles one of the three available colors. The first player may choose to play wherever they wish. Further plays must be adjacent to the last possible play, if possible. A player loses when they create a three-colored triangle: each vertex of the triangle is colored a different color. Now you can challenge your skills against the computer! An option in the game lets you set the second player to be a drone. See if you can beat the computer on the default board size of 7. If you can, then try 9 (it's harder)! Size 6 is harder still, and 5 is the hardest available in the applet. We prove that Atropos is a PSPACE-complete game in this paper. Any and all feedback is welcome! Please email us at .

click the picture to play

Updates!
Sept 24, 2008: Added the Atropos Myth!

Aug 15, 2008: There might be a problem playing the game with Firefox on Mac OS X.

Aug 14, 2008: Lots of updates to the applet! Fixed the problem on Mac OS: the button names for colors can be read. Also, players can now play the unrestricted version of Atropos!

Atropos Presentations and Appearances
Atropos will continue to be presented at my job interviews during the Fall 2008 and Spring 2009 semesters.

Atropos was presented at Dartmouth in the Combinatorics Seminar on December 4, 2008.

Professor Herb Scarf used Atropos in a talk at the 19th Summer School in Theoretical Economics on The Economics of Kenneth J. Arrow at the Institute for Advanced Studies at the Hebrew University in Jerusalem on June 30, 2008. The Institute for Advanced Studies graciously provides a .mov of the talk. (The use of Atropos starts about 25 minutes into the video.) If that takes too long to load, the Institute for Advanced Studies has graciously allowed us to host a copy here (video taken down, looking for another host option).

Atropos was presented at WINE 2007 on December 14, 2007. (Proceedings) (Paper from WINE.)

Atropos was described at the CCS weekly seminar at Boston University on April 13, 2007. (Talk Page)

Atropos and the PSPACE-complete proof was presented at Colby College on Feburary 19, 2007 as part of the Math Department Colloquium. (Talk Page)

A poster of the game (.odp, .pdf, .ppt) was presented at the Boston University CS Department 2007 IAP Day and Open House and at the 2007 Boston University Science and Engineering Research Symposium. A .pdf of the slides for a version of the talk "Games on the Sperner Triangle" can be found here.

Atropos is copyright 2007 to present, Kyle Burke, Shang-Hua Teng and Boston University.