Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

CS 699 | Aug-Nov 2023

CS699. Combinatorial and Computational Aspects of Games

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

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
  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.

Timings and Venue
  • Venue: TBA
  • Lectures: Mondays and Fridays 3:30PM — 5:00PM
TAs and Office hours

Office Hours: By email.

TAs: TBA

Evaluation policy
  • 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.

Register
  • For IITGN students, (pre-)register through IMS as usual.
  • Otherwise, please send me an email.
  • Recordings
  • Lectures
  • Assignments
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

×