Games and Computation

Professor: Tim Wylie
Meeting time: MW 2:00 - 3:15, EIEAB 2.203, F 4:00 Online
Lab time: W is the lab.
Syllabus: Escaping the class (pdf)
Final Exam: May 9, 2022, 1:15 - 3:00, EIEAB 2.203
Discord: Link on BB

Assignments

1. Group Grading Sheet(s) - Due at Final

Labs

Labs are W at 2:00 in EIEAB 2.203

1. (2/2) Hex, 3D TTT, Dots and Boxes, Yavalath, Domineering
2. (2/9) Celtic!, Input, Mijnlieff, Pentago, Santorini, Tak
3. (2/16) Tsuro, Gobblet, Niya, Azul, Hive, Quarto
4. (2/23) More games
5. (3/2) Focusing on 1 game
6. (3/9) Fun times
7. (3/16) - Spring Break
8. ()
9. ()
10. ()
11. ()
12. ()
13. ()
14. ()
15. ()
16. () - No Lab

Schedule and Class Notes

Week 1 (1/17-1/19): Intro to games! (notes 1/19)
Week 2 (1/24-1/26): Combinatorial Games (notes 1/24, 1/26)
Week 3 (1/31-2/4): Algebraic CGT (notes Week 3, 2/4)
Week 4 (2/7-2/11): Impartial Games (notes Week 4, 2/11)
Week 5 (2/14-2/18): Partizan Games (notes Week 5, 2/18)
Week 6 (2/21-2/25): Algorithmic Game Theory / Complexity (notes 2/25)
Week 7 (2/28-3/4): Constraint Logic (notes 3/4)
Week 8 (3/7-3/11): Advanced Topics
Week 9 (3/14-3/18): Spring Break
Week 10 (3/21-3/25): Advanced Topics (notes 3/25)
Week 11 (3/28-4/1): Advanced Topics (notes 3/25)
Week 12 (4/11-4/15): Advanced Topics
Week 13 (4/18-4/22): Advanced Topics
Week 14 (4/25-4/29): Advanced Topics
Week 15 (5/2-5/6): Play games
Week 16 (5/9-5/13): Final: May 9, 2022, 1:15 - 3:00, EIEAB 2.203

Free Resources

Books:

• Games, Puzzles, and Computation. Hearn, R. A., 2006.
• A Framework for Proving the Computational Intractability of Motion Planning Problems. Lynch, J., 2020.
• 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
• Rule sets of some games

Videos:

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

logos from: Horrible Logos

Bonus Material

Papers

• Paper List

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

• Constraint Logic Reference

Group Assignments

1. Notes (Group Assignment 1) - due one week after notes taken
2. Combinatorial Game Theory HW1 - due 2/28
3. Combinatorial Game Theory HW2 - due 3/9
4. Make a game! - due 4/20
5. Papers 1 and 2 - due 3/21
6. Paper 3 - due 3/25
7. Papers 4(postponned) and 5 - due 3/28
8. Paper 6 - due 4/1
9. Papers 7, 8 - due 4/4
10. Paper 9 (postponned) - due 4/8
11. Papers 4, 10 - due 4/11
12. Paper 11 (postponned) - due 4/15
13. Papers 9, 11 - due 4/18
14. Papers 12, 13 - due 4/22
15. Papers 14, 15 - due 4/25
16. Papers 16, 17 - due 4/29
17. Papers 18, 19 - due 5/2
18. Paper 20 - due 5/4
19. Papers 21, 22 - due 5/6

Lab Assignments

1. Lab 1 - due 2/9
2. Lab 2 - due 2/16
3. Lab 3 - due 2/23
4. Lab 4 - due 3/2