Games, Puzzles, and Computation

Professor: Tim Wylie
Meeting time: MW 1:40 - 2:55
Lab time: R 11:45-1:30 or F 1:00-2:45
Syllabus: Escaping the class (pdf)
Final Exam: May 8, 2017, 1:15 - 3:00
Book:
  

Assignments

1. Complexity (Assign. 1) - Due Feb 27th
2. Paper Review (Assign. 2) - Due March 6th (guidelines)
3. CGT (Assign. 3) - Due March 27th
4. CGT 2 (Assign. 4) - Due April 10th
5. Books! (Assign. 5) - Due April

Labs

Labs are Thursday 11:45-1:30 in ASB 2.110 or Friday from 1:00-2:45 in the ENGR 1.262.

1. (1/26 or 1/27) - Hex, Dots and Boxes, 3D Tic Tac Toe
2. (2/2 or 2/3) - Mijnlieff, Hive, Arimaa
3. (2/9 or 2/10) - Celtic!, Nine/Twelve Men's Morris
4. (2/16 or 2/17) - Akron, Mambo, Nonads, Palago, Yavalath
5. (2/23 or 2/24) - Kamon, strategy group work
6. (3/2 or 3/3) - Free play
7. (3/9 or 3/10) - Making games
8. (3/16 or 3/17) - SPRING BREAK
9. (3/23 or 3/24) - Going digital
10. (4/6 or 4/7) - Generalizing group games
11. (4/13 or 4/14) - No official lab
12. (4/20 or 4/21) - Working on games
13. (4/27 or 4/28) - Tilings, etc.

Schedule and Class Notes

Week 1 (1/16-1/20): Hide and Seek, everyone lost
Week 2 (1/23-1/27): Complexity (prelim, notes)
Week 3 (1/30-2/3): Complexity (prelim, notes)
Week 4 (2/6-2/10): Intro to Combinatorial Games (prelim, notes)
Week 5 (2/13-2/17): Impartial Games (Group work starts) (prelim, notes)
Week 6 (2/20-2/24): Nimbers, Partizan Games (prelim, notes)
Week 7 (2/27-3/3): Partizan Games, Group Presentations
Week 8 (3/6-3/10): Group Presentations and CGT summary (prelim, notes)
Week 9 (3/13-3/17): SPRING BREAK
Week 10 (3/20-3/24): Game Complexities, Reductions, QBF (prelim)
Week 11 (3/27-3/31): QBF and DCL (prelim)
Week 12 (4/3-4/7): Constraint Logic Classes (prelim)
Week 13 (4/10-4/14): CL Reductions, AI (MCTS/Q-Learning) (prelim)
Week 14 (4/17-4/21): Group Work! (no notes)
Week 15 (4/24-4/28): Special Topics
Week 16 (5/1-5/5): Special Topics (prelim)
Week 17 (5/8-5/12): Final, May 8, 2017, 1:15 - 3:00

Free Resources

Books:

• Games, Puzzles, and Computation. Hearn, R. A., 2006.
• Introduction to Theory of Computation. Maheshwari, A. and Smid, M., 2016.
• Game Theory. Ferguson, T. S., 2014.
• Combinatorial Games, Theory and Applications. Milvang-Jensen, Brit C. A., Masters Thesis, 2000.
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. E. Demaine and R. Hearn, a survey from 2008

Websites:

• Board Game Geek - Game reference and print-and-play versions
• Complexity Zoo
• Game Complexity Reference
• Eppstein's combinatorial games reference
• Hex reference
• Hex Theory
• Why Arimaa is hard
• Rule sets of some games
• MCTS tutorial in Python
• Overview of MCTS

Videos:

• High-level P and NP
• Rubik's cube using intuition
• Demaine's Lectures

Bonus Material

• Logicomix
  A graphic novel about Bertrand Russell
• The Thrilling Adventures of Lovelace and Babbage
  A (mostly fictional) graphic novel about Ada Byron (Lady of Lovelace) and Charles Babbage. Several parts of this book are on the website as well for free.
• Note that attending Xtreme Algorithms counts as bonus. ENGR 2.248 @ 3:00 pm

Game Papers

• Generalized HEX is PSPACE-complete
• HEX is PSPACE-complete
• Tetris is hard
• Variant of Tetris is hard
• Some Nintendo games are NP-hard
• Minesweeper is NP-complete
• Sudoku is NP-complete
• Havannah and Twixt are PSPACE-complete
• Portal and some 3D games
• Bust-a-Move is NP-complete
• Zig Zag Numberlink is NP-complete
• Scrabble is PSPACE-complete
• Complexity of UNO
• Coin moving puzzles
• Solitaire Clobber
• PushPush is NP-hard in 2D
• PushPush and Push-1
• Phutball Endgames are hard

The template for the final project, notes, etc. is here: gpctemplate.tex. You may want to use the in-browser latex editor at Overleaf if it's new to you.

Reference Papers

• A Simple Proof for the NP-Hardness of Edge Labeling
  Nice planar 3-SAT reduction
• Some Chess Endgames
• Some Domineering Positions
• Some Go endgames
• Constraint Logic Reference

Games for projects

• Group A (MicroPi) - Nonads
• Group B - Nine Men's Morris - Including generalizations like Pentagonia
• Group C - Akron
• Group D - Gobblet (also Gobbler)
• Group E - Palago
• Group F - Niya - simpler Kamon
• Group G - Quantum Tic-tac-toe
• Group H - Mijnlieff
• Group I - Celtic!
• Group J - Kamon
• Group K - Yavalath
• Group Z - ?
• Mambo
• Hive
• Arimaa

SVG Files for Games

• Celtic
• Kamon
• Mijnlieff
• Nonads
• Palago
• Yavalath

Group Assignments

1. Notes (Group Assignment 1) - Due one week after notes taken
2. Strategies (Group Assignment 2) - Due March 3rd
3. Making a game (Group Assignment 3) - Due April 26th
4. Making an interface (Group Assignment 4) - Due April 7th
5. Finding Gadgets! (Group Assignment 5) - Due April 17th
6. A.I. (Group Assignment 6) - Due May 5th
7. Final Project - Due Finals Week
8. Group Grading Sheet(s) - Due at Final