CS64: Computation For Puzzles And Games
General Info
CS64 is a class about using computers to solve, write, analyze, and otherwise
more deeply enjoy puzzles and games. It is intended to be laid-back and fun,
and I hope to get you (even more) excited about various aspects of CS theory
and AI.
Instructor: Ian Tullis (please call me Ian instead of Mr./Prof.
Tullis!) I'm a Master's student in CS (Theory, backed with AI/ML). Prior to
this, I worked at Google on Search and Code Jam, but I decided to leave to
try to be a CS lecturer; this is my final quarter at Stanford, after which I
will work for The Art of Problem Solving as a curriculum designer.
Please feel free to email me anytime at itullis@.
Weekly class meetings: In most weeks, we will have two 50-minute
meetings. The Wednesday meeting is a lecture (with some interactive
components). The Friday meeting is purely for fun -- I will bring various
problems / puzzles to solve. Both of these run from 4:30-5:20 PM in room
380-380W (the basement of the Sloan Math Department building, which is at
the northeast corner of the Main Quad).
Expectations/Grading: The class is graded Satisfactory / No Credit.
To earn a Satisfactory grade, do at least one of the following:
- Attend at least 6 of the 9 Wednesday lectures in person. (Again, the
Friday meetings are just for fun and are completely optional in every
way.)
- Carry out a small investigation / project in which you explore a
topic of interest to you that pertains to puzzles/games. The project
should involve writing at least some code. You do not have to write a
formal report; a 1-page summary of what you found would be fine. (Of
course, if you want to write more, I will happily read it!) The
main goal is to encourage you to explore something that you're
passionate about, and that you will benefit from and remember long
after the class is over.
Later in the quarter, I will send a Google form where you can indicate
which lectures you've attended so far and which of the above options you
want to choose.
Ed: We have a course Ed forum where you can ask questions about
material pertaining to the class (or in the class's general orbit), share
puzzles/games or observations thereupon, share the optional projects
mentioned above, etc.
OAE accommodations: If you have a letter from the Office of
Accessible Education, and/or if you have particular needs/circumstances
that I should be aware of (or if there's anything else I can do to help),
please email me.
Tentative lecture schedule
- September 28 (Slides): How to win (and lose) at Scrabble. Didn't get to it in class but: "Ghost" and tries.
- Quackle (Scrabble AI that you can download and play against)
- A paper on opponent modeling in Scrabble (i.e., trying to infer the opponent's tiles)
- A great recent article arguing that Scrabble AIs still have a long way to go
- An example of sports teams incentivized to play to lose
- An even sillier example in which a soccer team was trying to score on its own goal
- October 5 (Slides): The obligatory chess day! Cheating at chess, since it's on everyone's mind right now. The Stockfish and Leela AIs.
- The two currently dominant Chess AIs: Stockfish, Leela
- A paper with an overview of Stockfish vs. Leela, showing that the latter fails on a complex chess puzzle
- A clever scam (don't watch this before Wednesday's class or you'll spoil the intro puzzle!) Presented in a kinda bombastic way, but does involve the Stanford Chess Club (circa the early 2010s)...
- Elo World: Tom7 creates a bunch of chess AIs that are intentionally weird and bad. Well worth a watch.
- Quantum chess: Paul Rudd faces off against Stephen Hawking, for some reason. Quantum chess itself is an interesting premise.
- This is just funny (especially starting around 2:00)
- Documentary on AlphaGo: I've watched this now! Heavier on the human elements than on the details of Go or the AlphaGo algorithm, but still a good watch. One nice insight is that we tend to think of how far we are ahead in a game as a proxy for how likely we are to win, but it's an imperfect estimator and sometimes it's better to pursue a path that wins by just a small margin.
- Incidentally, here is a very recent example of humanity beating DeepMind. Let's enjoy these wins while we can, folks!
- October 12 (Slides): Sudoku and Nikoli-style logic puzzles, part 1. Construction of a novel puzzle type.
- Nikoli's website. Has good examples of (and instructions for) their various puzzle types. You can also order issues of their magazine (and books specific to one puzzle type) online, though it's shipped from Japan, so you may want to get a bunch at once to make the shipping worth it.
- The Sudoku solver mentioned in lecture. Most of these techniques (past Swordfish) are very uncommon in puzzles intended to be solved by humans. The site also has Sudoku to solve.
- A Masyu generator with a good solving interface. Beware: the Hard ones (and sometimes the Medium ones) may require some guessing, pretty much...
- The mini-project I did that led to the 1-2-3-4 frequency square fillomino puzzle, in case anyone wants a bit more detail.
- Grandmaster Puzzles has handcrafted puzzles by Sudoku masters, including the author of the U.S. state sudoku from lecture and the puzzle set. Also see the book Sudoku Masterpieces.
- Another Sudoku variant from a puzzlehunt I played in
- The "Cracking the Cryptic" videos feature experienced solvers attacking beautiful constrained constructions sight-unseen. This one is an interesting variety Sudoku with simple rules and just two givens. There are other videos in the series feqturing equally wild Sudokus.
- October 19 (Slides): Nikoli-style logic puzzles, part 2. Minilecture delivered Friday; no class Weds (Ian wasn't feeling well but is fine now).
- A Kakuro generator (same site as the Masyu generator above, same caveats). Hit Shift to toggle the mode for filling in candidates.
- A Nonogram site with a good solving interface. Can't comment on puzzle quality since I don't use this one. If you like this puzzle type and have a good recommendation, let me know! Also has links to a whole family of sites for various Nikoli-style puzzles.
- October 26 (Slides): Lights Out via BFS, greed, and linear algebra over the finite field F_2.
- November 2 (no slides): Unstructured Q&A with a very special guest (Don Knuth)... polyomino / cover puzzles, Dancing Links
- Wikipedia page on Dancing Links
- Fascicles 5b and 5c of The Art of Computer Programming are perhaps THE authoritative sources on solving this type of puzzle.
- Which pentomino ragdolls down a stairway the fastest? Guess in advance and see if you're right!
- November 9 (Slides): Technology of escape rooms, with another very special guest (Dan Egnor) who works on this stuff!
- Morty, the escape room directory app that Dan mentioned in class.
- TERPECA: an endeavor to identify the best escape rooms out there
- Brett Kuehner's list of design links (see the technology section)
- Some (mostly) local escape rooms I would recommend (this is me speaking personally, not endorsing on behalf of Stanford!) Some of these are pretty expensive, but worth it. In alphabetical order by company:
- Some escape room movies that I would recommend:
- None of them, and that's not for a lack of having suffered through them -- I have seen no fewer than five movies with "Escape Room" in the title and they were all conceptually lazy ("what if the room were like Saw?"), utterly joyless, or (usually) both.
- An excellent movie that is vaguely in this space is The Game (1997). No link, because it's one of those that you should just watch without spoilers.
- The EXIT: The Game series of boxed escape rooms are clever and occasionally do unexpected things with the medium.
- If you like puzzle hunts and trying to guess puzzle answers from 3 out of 16 letters, check out Nutrimatic, which Dan created and maintains.
- November 16 (Slides): The 15-puzzle (and how it briefly drove America to madness), and the Rubik's Cube. A very small taste of group theory.
- One of many 15-puzzle implementations
- The 15 Puzzle Book: How it Drove the World Crazy, by Jerry Slocum. I haven't read this book, but it looks like the authoritative source on this puzzle!
- A really nice solver for the Rubik's Cube.
- Herbert Kociemba's homepage has lots of info on the Rubik's Cube and the 15-puzzle.
- A cube being solved in 0.38 seconds
- A cube not being solved in 0.38 seconds
- Info on the Rubik's Contraption robot
- A (parody) tutorial for the 1x1x1 Rubik's Cube (you saw an example of one in class!) Much funnier if you've watched a video on solving the 3x3x3.
- November 23: No Wednesday lecture or Friday puzzleday (Thanksgiving holiday week)
- November 30 (Slides): Video game AIs and speedruns. Some final words and class recommendations.
- December 2 (Friday):
Playtest for the puzzlehunt (see Ed if you want to sign up). (canceled due to unavailability of playtesters)
- December 7: First run of the puzzlehunt (starts 3:30 at Tresidder).
- December 9 (Friday): Second run of the puzzlehunt (starts 3:30 at Tresidder).
Resources
- Erik Demaine's book Games, Puzzles, and Computation, or pretty much anything he does, tbh; see his site.
- Donald Knuth's The Art of Computer Programming (especially Volumes 4A and 4B), and Selected Papers on Fun And Games
- Winning Ways For Your Mathematical Plays, by Berlekamp, Conway, and Guy
- Pretty much every video this guy makes. I may ask him to be a guest speaker...
- This class at Simon Fraser University
- More to come!
- A secret reason why this course is CS64 (the other reasons are that courses with numbers 60-69 modulo 100 are usually theory courses, and that there are 64 squares on a chessboard)
This website looks like it is from the dawn of computing
I know, I know... and if you took CS109A with me, you are already familiar
with my Web design style :D To be honest, any time I might spend trying to
make the site look better would probably be better spent on designing/improving
the course content itself.
Nothing on this page is a puzzle.