CS 699 | Aug-Nov 2023

CS699. Combinatorial and Computational Aspects of Games

August — November 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.

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: TBA
  • Lectures: Mondays and Fridays 3:30PM — 5:00PM

Office Hours: By email.

TAs: TBA

  • Develop your own game and demonstrate a non-trivial analysis X 1 = 15 points
  • Develop new results about the complexity of an existing game = 15 points
  • Implement a known game in as an interactive JS application X 3 = 30 points
  • Three take-home exams = 45 points
  • Total capped at 100.

The use of assistance from tools like chatGPT or similar is permitted for the development of the interactive experiences.

  • For IITGN students, (pre-)register through IMS as usual.
  • Otherwise, please send me an email.
Date Lecture Slides Notes Video Recap
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
No matching items
Date Lecture Slides Notes Video
04 Aug, 2023 1. Introduction

Basic Setup, Terminology, and Examples.
07 Aug, 2023 2. TBA
11 Aug, 2023 3. TBA
14 Aug, 2023 4. TBA
18 Aug, 2023 5. TBA
21 Aug, 2023 6. TBA
25 Aug, 2023 7. TBA
28 Aug, 2023 08. TBA
01 Sep, 2023 09. TBA
08 Sep, 2023 10. TBA
11 Sep, 2023 11. TBA
15 Sep, 2023 12. TBA
18 Sep, 2023 13. TBA
22 Sep, 2023 14. TBA
25 Sep, 2023 15. TBA
29 Sep, 2023 16. TBA
06 Oct, 2023 17. TBA
09 Oct, 2023 18. TBA
16 Oct, 2023 19. TBA
20 Oct, 2023 20. TBA
30 Oct, 2023 21. TBA
03 Nov, 2023 22. TBA
06 Nov, 2023 23. TBA
10 Nov, 2023 24. TBA
13 Nov, 2023 25. TBA
17 Nov, 2023 26. TBA
20 Nov, 2023 27. TBA
24 Nov, 2023 28. TBA
No matching items

We will share user-developed content here.

Issued Assessment Problems Solutions Due
01 Aug, 2023 Coming Soon
No matching items

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos