Games and Computation

Professor: Tim Wylie
Meeting time: TR 2:00 - 3:15, EMAGC 2.206
Lab time: F 2:00-3:30, EIEAB 1.208
Syllabus: Escaping the class (pdf)
Final Exam: Dec 10, 2019, 1:15 - 3:00, EMAGC 2.206
Discord: https://discord.gg/5j6vDTQ

Assignments

1. Paper Review (Assign. 1) - Cancelled :)
2. Group Grading Sheet(s) - Due at Final

Labs

Labs are Friday 2:00-3:35 in EIEAB 1.208, or Thursday 11:30-1:00 EIEAB 1.200.

1. (8/29, 8/30) - Hex, Dots and Boxes, 3D Tic Tac Toe
2. (9/5, 9/6) - Mijnlieff, Celtic!, Yavalath
3. (9/12, 9/13) - Santorini, Tsuro, Kamon, Micropul, Input, Pentago
4. (9/19 or 9/20) - Hive, Splendor, All Queens
5. (9/26 or 9/27) - Group strategies
6. (10/3 or 10/4) - Group strategies
7. (10/10 or 10/11) - CGSuite or open play
8. (10/17 or 10/18) - CGSuite or open play
9. (10/24 or 10/25) - GUIs
10. (10/31 or 11/1) - GUIs
11. (11/7 or 11/8) - Gadgets
12. (11/14 or 11/15) - Gadgets

Schedule and Class Notes

Week 1 (8/26-8/30): Intro to games! (n01)
Week 2 (9/2-9/6): Combinatorial Games (p02,n02)
Week 3 (9/9-9/13): Impartial Games, Nimbers (p03)
Week 4 (9/16-9/20): Partizan Games (p04,n04)
Week 5 (9/23-9/27): Partizan Games
Week 6 (9/30-10/4): Group Presentations
Week 7 (10/7-10/11): CGSuite Work
Week 8 (10/14-10/18): CGSuite Work
Week 9 (10/21-10/25): Constraint Logic (p05)
Week 10 (10/28-11/1): Group Reductions (prelim)
Week 11 (11/4-11/8): Gadgets/GUIs
Week 12 (11/11-11/15): Reduction Work
Week 13 (11/18-11/22): AI (MCTS/Q-Learning), Gadget Presentations
Week 14 (11/25-11/29): Game Work
Week 15 (12/2-12/6): Play games
Week 16 (12/9-12/13): Final: Dec 10, 2019, 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.
• Attending Xtreme Algorithms counts as bonus. TBD
• Attending Hack Research counts as bonus. TBD

Note Papers

• Computational Complexity of Motion Planning of a Robot through Simple Gadgets
• A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
• CGSuite stuff
• MCTS stuff

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 C - Mijnlieff
• Group E - Santorini
• Group F - Pentago
• Group K - Yavalath
• Group L - Splendor
• Group M - Yinsh
• Group N - Rock Me Archimedes
• Group Q - Input
• Group R - Tsuro
• Group Y - Niya - simpler Kamon
• Group Z - All Queens

Group Assignments

1. Notes (Group Assignment 1) - Due one week after notes taken
2. Combinatorial Game Theory HW1 - Due 9/19
3. Combinatorial Game Theory HW2 - Due 9/27
4. Strategies (Group Assignment 2) - Due 10/4
5. Making a game (Group Assignment 3) - Due 12/3
6. Using CGSuite, CGT HW3 - Due 10/18
7. Making an interface (Group Assignment 4) - Due 11/1
8. Finding Gadgets! (Group Assignment 5) - Due 11/15
9. A.I. (Group Assignment 6) - Due 12/6
10. Final Project - Due Finals Week