Michael Albert responded to my last post by mentioning the game Phutball as a classic result in exactly what I was looking for. Luckily, it is Friday and I haven't done a "game description" post in a while. Here goes!
Phutball is short for Philosopher's Football and is played on the intersections of a 19 x 15 grid (though other sizes are often used). On either end of the long side are the "end zones". There is one ball on the field and any number of "men" (I'll call them athletes). All of these objects reside on the intersections of the grid (see the wikipedia page for nice pictures). The goal of each player is to end a turn with the ball inside the opponents' end zone.
A turn consists of either creating a new athlete in any unoccupied intersection or moving the ball. The ball is moved by "jumping" one or more athletes, removing those athletes, then moving the ball again if the current player wishes. Each jump consists of moving the ball in any of the 8 cardinal directions as long as there is one or more neighboring athlete in that direction (diagonal intersections are considered adjacent). The ball is moved to the next open space in that direction (it may not be moved if no adjacent spaces are available) and the athletes that were jumped are then removed.
I have never played this game, so I have no idea how game play goes. Luckily, I have found some people here to play games with over lunch and this week have played my first ever games of Domineering and Cram! I think next week will consist of some Phutballing!
It relates to Tuesday's post because it is a game where figuring out whether you can win this turn is NP-complete. Furthermore, the game has been shown to be PSPACE-hard to determine which player is winning.
I am looking forward to giving this game a try!
My Last Visit with John Conway
4 weeks ago