cmput 396   topics in cs: games, puzzles, algorithms

topics   about   faq   code   asn   lec  
announcements

topics

about

  • an intro to algorithms that solve puzzles or play games

  • aimed at general science students, open to anyone

  • prereq: any CMPUT 2xx course

  • 396 is the first of the two-course stream 396-496

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

FAQ

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

code

assignments

lectures

  • 23 review

  • 22 alphago

  • 21 alphago

  • 20 alphago

  • 19 mcts improvement: RAVE, prior knowledge

  • 18 mcts improvement: exploration   go review: int.way2go 11-19   solving go   linear go

  • 17 quiz

  • 16 pure mcts

  • 15 solving hex? mcts

  • 14 improving ttt solver: minimax, alphabeta, isomorphisms, transposition

  • 13 hex knowledge: inferior cells, virtual connections

  • 12 hex game: no draw, 1pw, nx(n+1) short 2pw, hard

  • 11 quiz

  • 10 nim game: checkers, formula, cgt, quiz review

  • 9 alpha-beta review, nim game: tree vs dag, memoisation

  • 8 tictactoe: alpha-beta

  • 7 scoring Go positions, tictactoe, minimax

  • 6 sliding tile puzzle: details of Dijkstra, A*; rules of Go

  • 5 sliding tile puzzle, guided search via A*

  • 4 sliding tile puzzle, exhaustive search via bfs

  • 3 maze traversal: bfs, dfs, maze.py

  • 2 eclass course outline, prologue, maze traversal: random walk, rmaze.py

  • 1 eclass course outline, topics, prologue (start)