| [+] More Games. PSPACE-complete bounded 2-player games: Amazons, Konane, Cross Purposes. PSPACE-complete bounded 1-player stochastic games: SSAT. EXPTIME-complete unbounded 2-player games: formula games (G1, G2, G3, G4, G6), Peek, graph games (Ham, Block), Checkers, Chess, Go with Japanese ko rule, planar unbounded 2CL. APSPACE = EXPTIME. EXPSPACE-complete no-repeat unbounded 2-player games. 2EXPTIME-complete conditional no-repeat unbounded 2-player games. 2EXPTIME-complete private-information unbounded 2-player games. EXPSPACE-complete blind unbounded 2-player games. | |||||
|
In this class, we'll see a few examples of real bounded games proved PSPACE-complete via Constraint Logic: Amazons, Konane, and Cross Purposes. Then we'll work our way up the game hierarchy: unbounded two-player games are EXPTIME-complete (including Chess, Checkers, and Japanese Go); with a “no repeat” rule they become EXPSPACE-complete (conjectured to include USA/Chinese Go); and with a “no recent repeat” rule they become 2EXPTIME-complete. Impartial information among the players similarly increases the complexity of unbounded two-player games, and furthermore distinguishes two-player games from team games with more than two players. I'll also mention some results that random (stochastic) players, such as rolling the dice, can be just as adversarial as regular (optimal) players — so-called “Games Against Nature”. | |||||
|
Handwritten notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/9 • [previous page] • [next page] • [PDF] |
|
|
Slides, page 1/29 •
[previous page] •
[next page] •
[PDF]
Slide from Lecture 1. http://erikdemaine.org/papers/GPC/ Slides, page 1/29 • [previous page] • [next page] • [PDF] |
