cmput 396   topics in cs: games, puzzles, algorithms

carlsen over caruana     guardian     armageddon looms in chess

prologue   AlphaGo, the end of an era

go   rules, learn

maze traversal puzzle   random walk, bfs, dfs

sliding tile puzzle   bfs, knowledge, A*

2-player games minimax, αβ

tic-tac-toe game   αβ-negamax

nim game   dynamic programming, knowledge

chess game

hex game   properties, tips, solving

solving go

monte carlo tree search   pure mcts, improvements

AlphaGo  

epilogue   AlphaGoZero, AlphaZero and beyond

Sarah Hoven has kindly agreed to share these lecture notes, created fall 2018. Copyright Sarah Hoven 2018.

1. prologue

2. go   tromp-taylor rules

3. maze traversal

4. sliding tile puzzle

5. two player games

6. tic-tac-toe

7. nim game

8. hex game

9. solving go

10. mcts

11. alphago

12. epilogue

intro to alg'ms/theory behind computer programs that solve puzzles (mazes, peg solitaire, etc.) or play games (chess, Go, Hex, etc.)

aimed at general science students, open to anyone

prereq: any CMPUT 2xx course

396 is the first of the two-course stream 396-496 (but not a 496 prereq)

496 starts winter 2017, will cover many of the ideas behind AlphaGo

are there labs or seminars?     no

is knowing how to code a prerequisite?     no, but you will learn

what will the quizzes and final be like?     long answer, short answer, fill in the blank, possibly multiple choice

course resources?     these webnotes

evaluation ?     assignments, quizzes, final, cutoffs 90 85 … 40 for A+ A ... D.

calendar description?     (3-0-0) CMPUT 396: Topics in CS. For a general audience, an introduction to algorithmic problem solving for puzzles such as Rubik's cube or the sliding-tile puzzle, and games such as chess, Hex, Go, backgammon.

python3 code on github

a5   a5.tex (if you want, modify this file and run latex to generate your submission)   a4   +   a3   +   a2   +   a1   +     q4   +   q3   +   q1+  

old quizzes, old quiz reviews, old final

• WARNING material covered changes from year to year

• coverage of quizzes, reviews, and final this year will differ

• q1 rvw     q1     q2 rvw     q2     sol     final16    

24 alphago

23 alphago

22 asn5 program demos

21 mcts

20 mcts

19 solving go

18 quiz (class will start 08:20)

17 quiz review, hexnotes (part2)

16 solving go (tromp's 2x2 code, 2x2 proof tree), hex knowledge (hexnotes part 1, inferior cells, virtual connections)

15 hex game   intro talk: no draw, 1pw, nx(n+1) short 2pw, hard

14 quiz

13 nim formula, checkers, hex

12 nim game, memoization

11 negamax, search space dag

10 solving tic-tac-toe with alpha-beta negamax

9 minimax, alpha-beta

8 A*, sliding tile puzzle

7 quiz

6 sliding tile puzzle, beyond bfs: Dijkstra, A*

5 maze traversal review, sliding tile puzzle, exhaustive search via bfs

4 prologue review, maze traversal: walk, bfs, dfs, rmaze.py, maze.py

3 go: rules, learn

2 prologue

1 eclass course outline, topics, prologue

read 2016 AlphaGo Nature paper

watch AG movie trailer (and watch the movie if you can)

learn Tromp-Taylor rules

do all exercises in interactive way to go

practise 5x5 go