CS 699 | Summer 2023

Reading Group on Combinatorial and Computational Aspects of Games

Summer 2023

We are going to play some games! Here are some typical questions we will explore:

  • Who is going to win assuming optimal play?
  • What is the complexity of determining the winner (or a winning strategy) given the rules of a game?

If you are curious about how this typically goes, start with the excellent talks here and here.

If you want to play: here’s Subtraction, and here’s Sim.

This is an informal summer reading group.

You will find this course interesting if:

This course is self-contained and involves no pre-requisites.

  1. Winning Ways for your Mathematical Plays, the classic book that is an amazing ride through all parts of CGT.
  2. Lessons in Play, an excellent text for upper level undergrads and grad students in math.
  3. Combinatorial Game Theory, a great text for advanced mathematicians.
  4. Playing with Discrete Math. This text is appropriate for undergrads who may or may not be math majors.
  5. Games, puzzles and computation. This text, based on the thesis of Robert A. Hearn, explores computational aspects of games.
  6. Is NP-hard, a compendium of games with a lot of information about their complexity status.
  7. Math Games with Bad Drawings, another compendium of games, with — as the title suggestions — bad drawings and lots of trivia.

Note. The descriptions for the first four books are borrowed from the Sprouts 2023 website.

  • Venue: Online
  • Lectures: Everyday at 11AM

Note: We stopped recording after a couple of weeks, however, the topics pursued are listed for the record :) Some initial notes — to be developed further — are here. The handwritten slides from the videos are not currently available.

Date Lecture Video
22 May, 2023 1. Impartial Game Trees

(0.1, 0.2, 0.3 in PWDM)
23 May, 2023 2. Game Sums

(0.4, 0.5 in PWDM)
24 May, 2023 3. Game Equivalences

(0.4, 0.5 in PWDM)
25 May, 2023 4. Nimbers

(0.6, 0.7 in PWDM)
05 Jun, 2023 5. Nim Sums

(0.6, 0.7 in PWDM)
06 Jun, 2023 6. Other Impartial Games

(0.8 in PWDM)
07 Jun, 2023 7. Sequences of impartial game values

(0.9 in PWDM)
08 Jun, 2023 8. Geography

(1.1 in PWDM)
09 Jun, 2023 9. Undirected Edge Geography

(1.2 in PWDM)
10 Jun, 2023 10. Directed Geography

(1.3 in PWDM)
11 Jun, 2023 11. Partisan Game Notation

(2.1 in PWDM)
12 Jun, 2023 12. Game Trees and Outcome Classes

(2.2 in PWDM)
13 Jun, 2023 13. Partisan Game Sums

(2.3 in PWDM)
14 Jun, 2023 14. Negatives and Equality

(2.4 in PWDM)
15 Jun, 2023 15. Inequalities

(2.5 in PWDM)
16 Jun, 2023 16. Dominated Options

(2.6 in PWDM)
17 Jun, 2023 17. Integers

(3.1 in PWDM)
18 Jun, 2023 18. Simplest Numbers

(3.2 in PWDM)
19 Jun, 2023 19. Switches

(3.3 in PWDM)
20 Jun, 2023 20. Other rational game value

(3.4 in PWDM)
21 Jun, 2023 21. Infinitesimals

(3.5 in PWDM)
22 Jun, 2023 22. They-Love-Me-They-Love-Me-Nc

(4.1 in PWDM)
23 Jun, 2023 23. Determining Winnability

(4.2 in PWDM)
24 Jun, 2023 24. Which Move Should we Make?

(4.3 in PWDM)
25 Jun, 2023 25. More strategy stealing.

(4.4 in PWDM)
26 Jun, 2023 26. Card games

(5.1 in PWDM)
27 Jun, 2023 27. Dice and role-playing games

(5.2 in PWDM)
28 Jun, 2023 28. Birthdays

(6.1 in PWDM)
29 Jun, 2023 29. SUMMARY OF PART I
30 Jun, 2023 30. Introducing Complexity Classes and Constraint

Logic (1 in GPC)
01 Jul, 2023 31. Constraint Graphs

(2.1 in GPC)
02 Jul, 2023 32. Planar Constraint Graphs

(2.2 in GPC)
03 Jul, 2023 33. Constraint-Graph Conversion Techniques

(2.3 in GPC)
04 Jul, 2023 34. Zero-Player Games (Simulations)

(3.1 in GPC)
05 Jul, 2023 35. One-Player Games (Puzzles)

(3.2 in GPC)
06 Jul, 2023 36. Two-Player Games

(3.3 in GPC)
07 Jul, 2023 37. Team Games

(3.4 in GPC)
08 Jul, 2023 38. Bounded Games (Zero-Player)

(4.1 in GPC)
09 Jul, 2023 39. Unbounded Games (Zero-Player)

(4.2 in GPC)
10 Jul, 2023 40. Bounded Games (One-Player)

(5.1 in GPC)
11 Jul, 2023 41. Unbounded Games (One-Player)

(5.2 in GPC)
12 Jul, 2023 42. Bounded Games (Two-Player)

(6.1 in GPC)
13 Jul, 2023 43. Unbounded Games (Two-Player)

(6.2 in GPC)
14 Jul, 2023 44. No-Repeat Games (Two-Player)

(6.3 in GPC)
15 Jul, 2023 45. Bounded Games (Team)

(7.1 in GPC)
16 Jul, 2023 46. Unbounded Games (Team)

(7.2 in GPC)
17 Jul, 2023 47. TipOver

(9.1 in GPC)
18 Jul, 2023 48. Hitori

(9.2 in GPC)
19 Jul, 2023 49. Sliding-Block Puzzles

(9.3 in GPC)
20 Jul, 2023 50. The Warehouseman’s Problem

(9.4 in GPC)
21 Jul, 2023 51. Sliding-Coin Puzzles

(9.5 in GPC)
22 Jul, 2023 52. Plank Puzzles

(9.6 in GPC)
23 Jul, 2023 53. Sokoban

(9.7 in GPC)
24 Jul, 2023 54. Push-2-F

(9.8 in GPC)
25 Jul, 2023 55. Rush Hour

(9.9 in GPC)
26 Jul, 2023 56. Triangular Rush Hour

(9.10 in GPC)
27 Jul, 2023 57. Hinged Polygon Dissections

(9.11 in GPC)
28 Jul, 2023 58. SUMMARY OF PART II
No matching items