CS 699 | Summer 2023

CS699. Combinatorial and Computational Aspects of Games

Summer 2023

About the Course

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.

Target Audience

You will find this course interesting if:

you enjoy playing games,
you enjoy logic puzzles like this one or probability puzzles like this one, or
you like box-stacking challenges.

Prerequisites

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

References

Winning Ways for your Mathematical Plays, the classic book that is an amazing ride through all parts of CGT.
Lessons in Play, an excellent text for upper level undergrads and grad students in math.
Combinatorial Game Theory, a great text for advanced mathematicians.
Playing with Discrete Math. This text is appropriate for undergrads who may or may not be math majors.
Games, puzzles and computation. This text, based on the thesis of Robert A. Hearn, explores computational aspects of games.
Is NP-hard, a compendium of games with a lot of information about their complexity status.
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.

Timings and Venue

Venue: Online
Lectures: Everyday at 11AM

TAs and Office hours

Not applicable.

We stopped recording after a couple of weeks, however, the topics pursued are listed for the record :)

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	08. Geography (1.1 in PWDM)
09 Jun, 2023	09. 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