intro to games, puzzles, algorithms

inspr   gpa   go   ttt   hex   go questions  

course inspired by ...

  • alphago (movie)

  • AlphaGo UAlberta connection

    • David Silver (Sutton, Mueller)

    • Aja Huang (Mueller, Hayward)

    • Alphastar UAlberta connection: Timo Ewalds (Hayward, Schaeffer)

  • UAlberta games experts

    • checkers: Schaeffer

    • chinese checkers: Sturtevant

    • go: Mueller

    • hex: Hayward

    • lines of action: Bjornsson

    • poker: Bowling et al.

    • reversi: Buro

games/puzzles/algorithms

  • puzzles: mazes, sliding tile

  • games: tic-tac-toe, hex, go, nim, rock-paper-scissors

  • math: discrete/recreational, combinatorial game theory, Von Neumann equilibria

  • algorithms: breadth-first search, depth-first search, dynamic programming, minimax search (negamax, alpha-beta), monte carlo tree search, convolutional neural networks

go

  • weiqi (China), baduk (Korea), go (Japan)

  • weiqi played from around 1000 BCE

  • around 2000 professional players

  • originated in China, played by upper-class   (xianqi – chinese chess – played by masses)

  • building superhuman go-bot longstanding AI challenge

  • 2016 AlphaGo

tic-tac-toe

  • played from around 100 BCE in Rome terni lapilli (3 pebbles at a time)

  • who wins? can you write a program to play perfectly?

hex

questions

  • does AlphaGo play perfectly?

  • what about small boards: can you write a program to play perfectly?