Cmput 455 Resources

Contents

• About Resources
• General Background
  • Background on Algorithms
  • Online AI Courses
• Specific Background
  • Python Bootcamp
  • Rules of selected games
• Lecture 1 - The game of Go and Computer Go
• Lecture 2 - Basic Data Structures and Algorithms for Computer Go
• Lecture 3 - Problem solving and Decision-making
• Lecture 4 - Formalizing Decision-making and Games
• Lecture 7 - Introduction to Search and Heuristic Search
• Lecture 8 - Minimax and Alphabeta Part 1
• Lecture 17 - Introduction to Machine Learning for Heuristic Search

About Resources

Links to external resources are provided as-is, for additional reading, watching and listening, without any guarantees that the material will stay accessible, be relevant for your needs, or match the contents of our course.
Resources include introductory books, articles, online courses, blog posts, demos and video clips.

General Background

Background on Algorithms

• Algorithms by Dasgupta, Papadimitriou and Vazirani. McGraw-Hill Higher Education, 2008. ISBN 978-0-07-352340-8.
• http://mitpress.mit.edu/books/introduction-algorithms CLRS - a classic large textbook covering many standard algorithms.
• UofA library guide for Computing Science

Online AI Courses

• Patrick Winston, MIT, Fall 2010 AI lecture videos

Python bootcamp

These notes cover some required background knowledge. I expect many of the students to know much of this material, so it is provided to enable you to fill in any "gaps".

Some of the activities and all of the assignments will require this knowledge.

• Python 3 language information
• Review material - basic Python idioms used in this class
• Python notes and sample code for this class

External links:

• PEP 8 -- Style Guide for Python Code
• pep8 - Python style guide checker

Rules of selected games

• TicTacToe (wikipedia)
• Game of Go - see Lecture 1
• Game of Gomoku or five in a row, and variants such as Ninuki wikipedia Gomoku page
• Chess-type games: Western chess, shogi and Xiangqi (all on wikipedia)
• Backgammon
• Binary Game - see Assignment 1
• NoGo
• Mancala games including Kalah, and Oware (Awari, Wari, ...)

Lecture 1 - The game of Go and Computer Go

• Wikipedia Go page
• American Go Association - many resources including introductions to Go
• Canadian Go Association
• Go Quest for iPhone, iPad and Android by Yasushi Tanase. Play quick games on small board against other humans and a few bots.
• Video Tutorial
  • Video Tutorial for the Game of Go - Part I, Overview by Goshawk Heron
  • Video Tutorial for the Game of Go - Part 2, Playing by Goshawk Heron
  • Video Tutorial for the Game of Go - Part 3a, Terminology by Goshawk Heron
  • Video Tutorial for the Game of Go - Part 3b, Concepts by Goshawk Heron

Lecture 2

Depth-first search (dfs) and Floodfill

• Depth-first search (dfs) on Wikipedia.
• Dfs implementation in Python from CMPUT 204 Algorithms. Sample graphs in undirected_graph_examples.py and directed_graph_examples.py
• Floodfill on Wikipedia. This does not mention the connection to dfs
• Floodfill on geeksforgeeks, including a dfs.

Go UI's, tools

• Gomill - Tools and Go library written in Python by Matthew Woodcraft

Open Source Computer Go Programs

• Cmput 455 Go programs. This series of simple Go programs is used to illustrate many of the concepts taught in this course.
• KataGo Strongest open source Go program, by David Wu. Trained using the AlphaZero algorithm, plus many Go specific and general enhancements to speed up the training process and improve playing strength.
  • See the KataGo paper Accelerating Self-Play Learning in Go.
• Darkforest
• Darkforest by Yuandong Tian and Yan Zhu of Facebook. DCNN and MCTS. Darkforest on github. Written in C and Lua.
• Fuego – C++ libraries and Go playing program. One of the strongest open source MCTS programs before DCNN. Developed mainly at Alberta. Currently not under active development, but still used for research.
• Pachi - one of the strongest open source MCTS programs before DCNN. Written in C. Pachi on github.
• Michi Minimalistic Go MCTS Engine, by pachi author Petr Baudis. Only about 500 lines of Python, MCTS and large patterns. No DCNN.
• Nochi Minimalistic AlphaGo Zero reimplementation, by pachi author Petr Baudis. Based on Michi.

Lecture 3

Decision-Making Case Studies

• How UPS Trucks Saved Millions of Dollars By Eliminating Left Turns
  • Article in The Independent.
  • Feature on ndtv.com.
  • Slashdot story.

Chances and Risks of Algorithms

• Mona Chalabi, Weapons of Math Destruction: Cathy O'Neil adds up the damage of algorithms. Guardian interview with Cathy O'Neil. Quote: "models are opinions embedded in mathematics".
• Lee Rainie and Janna Anderson, Pew Research Center. Code-Dependent: Pros and Cons of the Algorithm Age

Lecture 4

Human Decision-Making

• Read more about Herb Simon: wikipedia
• Kahneman and Tversky: How two trailblazing psychologists turned the world of decision science upside down. Michael Lewis, Vanity Fair, November 2016.

Lecture 7 - Search and heuristic search

Blind Search - Depth-first Search, Breadth-first search, etc.

• Dfs on wikipedia
• Bfs on wikipedia

Heuristic Search

• redblobgames.com very detailed A* introduction.
• redblobgames.com very detailed A* implementation.
• Shaul Markovitch algorithm animations: BFS, A*, GBFS, alphabeta and more.

Lecture 8

Solving Go

• Exploring Positional Linear Go. Noah Weninger and Ryan Hayward, Advances in Computers Games 2017.

Lecture 17

Machine Learning

• A Few Useful Things to Know about Machine Learning. Pedro Domingos, Communications of the ACM 55 (10), October 2012, Pages 78-87.
• Martin Zinkevich (Google, former UofA) Rules of Machine Learning: Best Practices for ML Engineering .

Lecture 19

• Andrew Trask, A Neural Network in 11 lines of Python (Part 1) and A Neural Network in 13 lines of Python (Part 2 - Gradient Descent)

Lecture 20

Neural Networks and Deep Learning

• Andrej Karpathy's blog, Deep Reinforcement Learning: Pong from Pixels.
• Krizhevsky, Sutskever and Hinton. ImageNet Classification with Deep Convolutional Neural Networks. The original DCNN paper.
• Russ Salakhutdinov Deep Learning talk from 2016
• CBC online article with interview of Geoff Hinton, sparse huge neural networks
• Zeiler and Fergus (2013), Visualizing and Understanding Convolutional Networks.

Residual Networks

• Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun. Deep Residual Learning for Image Recognition. The paper introducing Residual Networks, "resnets".

Lecture 21 Reinforcement Learning

• Artificial Intelligence’s Next Big Step: Reinforcement Learning. Mary Branscombe, The New Stack. Article about RL, not very technical.
• David Silver - Lecture 1: Introduction to Reinforcement Learning. First of a ten lecture class by Dave Silver on RL.

Lecture 22

AlphaGo as it Happened

• DeepMind AlphaGo page
• Exploring the Frontiers of Knowledge. Demis Hassabis about AI (and Alphago) and it's future
• AlphaGo and the Future of Computer Games: A Conversation at the University of Alberta Paul Lu, video with local UofA experts.
• Is AlphaGo Really Such a Big Deal? Article by Michael Nielsen in Quanta Magazine.

AlphaGo Matches

• All published Alpha Go Games
• 2016 vs Lee Sedol: Alpha Go movie

Lecture 23+24

AlphaGo Zero and Alpha Zero

• Silver, Hubert, Schrittwieser and Hassabis. AlphaZero: Shedding new light on chess, shogi, and Go, 2018
• DeepMind: AlphaZero and MuZero
• Surag Nair, A Simple Alpha(Go) Zero Tutorial, 2017

Programs giving handicap to professional players

• IGF news feed, Two stones! Fine Art defeated Ke Jie 9P after giving two stones handicap

Last modified: Aug 27, 2024

Martin Müller and Ting-Han Wei