All papers/articles are on eClass. See the button "Readings page - local copies and links for papers" near the top of the main eClass page.
Read around Lecture 1, before Quiz 2
Read around Lecture 1
Do around Lecture 1, and later review as needed.
Review before Lecture 2
python3 go2d.py
Do around Lecture 2
Download go.tgz from the Python code page
and unpack it. See
First Go programs - Go0 and Go1
for instructions and explanations.
Do around Lecture 2
Get familiar with the Go0 and Go1 program codes which you downloaded in activity 2b. Study the data structure for the Go board, and the algorithms for playing a move, checking legality, and capturing stones.
Do around Lecture 2, finish before Lecture 3
Download and install the GoGui user interface. You can use it for Go and other games that use similar game pieces.
board.pyDo after Lecture 2
In class we discussed the code which implements a floodfill (dfs) to find blocks. Is this efficient? Can you think of a faster way?
Read before Lecture 3: Heingartner, Maybe We Should Leave That Up to the Computer
(Activities 3a and 3b are not used this term)
Do after Lecture 2. See Assignment 1 for details.
Do before Lecture 4:
Play a game of Go against a colleague, against the Go1 program, or against an online opponent. See resources - Go.
Do before Lecture 4:
Analyze the algorithm to identify captured stones which is implemented in
go/board.py, functions
_detect_and_process_capture and _has_liberty.
Is it efficient? Can it be improved?
Watch before Lecture 4.
Do around Lecture 4:
Get familiar with the gogui-regress tool
for automated testing.
See
Regression testing with gogui-regress.
Watch around Lecture 4.
Read around Lecture 5: O'Neil, How algorithms rule our working lives.
Do around Lecture 5:
Given a game tree with constant branching factor b=10 and constant depth d=8. What is the total size of the tree? First, use the exact formula. Then, use the simple approximation bd. How large is the approximation error, in percent (of the exact value)?
Do around Lecture 5:
Same as activity 5a, but with b=8 and d=10. Which tree is bigger, the one in 5a or this one? How much bigger?
Do around Lecture 5:
Given a DAG with constant branching factor b=10 and constant depth d=8. Let the root be at level 0. Assume that for nodes n at levels 2 and higher, there are two different ways to reach n from the previous level. This means that two different parent nodes p1 and p2 on the previous level both have a move that leads to n.
What is the number of nodes on level 8 of the DAG?
What is the total size of this DAG? How many times smaller is it than the tree from 5a?
Do after Lecture 5:
See the description of Activity 5d in the Lecture 5 slides.
Do after Lecture 5:
Compute the effective branching factor bd, as explained in Lecture 5 slides, for all levels of the Tic-Tac-Toe DAG from Activity 5d.
Do around Lecture 6:
Use profile_Go1.py
in your go0and1 folder to profile Go1.
Try out some changes/optimizations and profile it again.
Do after Lecture 6:
Using Activity 6a as a starting point, now profile your own program from the assignment. Note that this activity is not required for Assignment 1. However it will help you prepare for the upcoming assignment 2.
Read around Lecture 7: Greenemeyer, 20 years after Deep Blue. Scientific American, 2017.
This is an optional activity and extends beyond the material of the course. For example, you can review the slides on Blind Search Extras in the resources.
blind_search_on_tree.pyDo around Lecture 7:
Re-run the sample code blind_search_on_tree.py and change the parameters b and d.
Under which conditions does random sampling do well, or poorly?
blind_search_on_tree.pyDo around Lecture 7:
The sample code blind_search_on_tree.py uses 1000 tries.
Change this value and re-run.
How does the number of successful runs change with this limit?
This is an optional activity and is more challenging than usual activities.
Analyze the expected number of steps of random sampling as discussed in the slides. Read and follow the hints there.
This is an optional activity and is more challenging than usual activities.
Implement the version of random sampling without repetition as discussed in the slides. Measure the performance of this new code in the framework
from blind_search_on_tree.py.
Read around Lecture 8: Schaeffer et al, Checkers is solved. Science, 2007.
Do after Lecture 8:
Given a uniform (b,d) tree, where the root is an OR node. Assume we can win. Find a closed formula for the total number of nodes in the proof tree in the best case. Hint 1: The counts of nodes per level are: 1, 1, b, b, b^2, b^2, b^3, b^3,.. Hint 2: consider the difference between even and odd depths d
Do after Lecture 8:
In the same setting as activity 8a, now find the best case size of the disproof tree, if the root is a loss. Hint 1: The nodes per level are now: 1, b, b, b^2, b^2, b^3, b^3,.. Hint 2: there is a very simple relation between the solution of the previous problem and this one. Find and use it.
Do after Lecture 8:
Run the solvers in boolean_minimax_test_tictactoe.py and
boolean_negamax_test_tictactoe.py.
Set up other opening positions and solve them.
Do after Lecture 9:
Given a board of size n times n, a komi k, and a player color. What is the minimum number of points that the player needs to win the game?
Do after Lecture 9:
Implement your solution from 9a in a Python function.
Do after Lecture 10:
See discussion in Lecture 10 slides.
Do after Lecture 10:
Add a case in alphabeta_tictactoe_test.py to solve TicTacToe
with your new heuristic. What is the speed difference?
Do after Lecture 10:
Modify naive_negamax.py and alphabeta.py
to return the number of nodes searched as well as the search result.
Then run the experiments in alphabeta_tictactoe_test.py with your new
instrumented code. What is the tradeoff between adding a heuristic in 10b
in terms of nodes searched vs time per node?
Read before Lecture 11: Van der Werf et al, Solving Go on small boards.
Read after Lecture 12: Computing Elo Ratings of Move Patterns in the Game of Go. Rémi Coulom, Computer Games Workshop 2007, Amsterdam.
Do after Lecture 12:
Run estimate_pi.py to estimate the value of pi using simulation. Increase the number of simulations and see if the value becomes more accurate.
Implement a shape different from a quarter circle, for example a triangle or a quarter ellipse, and re-run the code. Compare with the exact area computed using math.
Then, estimate the volume of a unit ball in 3d centered at (0,0,0) (formula x^2 + y^2 + z^2 < 1) and compare with the exact volume.
Do after Lecture 12:
Re-run the experiment Sim(1000) vs Perfect TicTacToe player with more games. Does Sim(1000) lose any games?
Do after Lecture 12:
Read simulation code in tic_tac_toe4.py and
tic_tac_toe_simulation_test.py
Run tic_tac_toe_simulation_test.py and
vary the number of simulations in the call
to randomTTT at the end
Do after Lecture 12:
Read simulation code for Go in Go3 and Go4,
especially function play_game in board_util.py
and the move generation functions called by it.
Write a perfect player with simulation-based tiebreaking, as discussed in the lecture 12 slides. Run the experiments from that slide with this player to see if it performs better against random.
No Readings or Activities.
bernoulli.pyDo after Lecture 14
Using the code in bernoulli.py, experiment with different settings
for p and limit. Study how many simulations you need
to get different levels of accuracy.
mystery-bernoulli.pyDo after Lecture 14
Play several rounds of mystery-bernoulli.py.
How close is your guess? How many simulations did you choose?
Program your own simulation-based game. It works similar to Go3, but you chose the winrates of different moves randomly.
Read before Lecture 15:
Parts of Browne et al, A Survey of Monte Carlo Tree Search Methods, as follows:
No Readings or Activities.
Read before Lecture 17: A Few Useful Things to Know about Machine Learning. Pedro Domingos, Communications of the ACM 55 (10), October 2012, Pages 78-87.
No Readings or Activities.
Watch before Lecture 19:
Watch this series of animations about neural networks by Grant Sanderson of 3Blue1Brown. This is a little bit longer than usual activities (10-21 minutes per video), but I believe that these videos are an excellent resource.
Do around Lecture 19:
Explore the demos (briefly shown in class) on Michael Nielsen's page A visual proof that neural nets can compute any function. Understand in detail the intuition behind the "visual proof".
Read before Lecture 20:
Maddison, Huang, Sutskever and Silver, Move Evaluation in Go using Deep Convolutional Neural Networks.CoRR abs/1412.6564.
Optional additional reading: Clark and Storkey, Training Deep Convolutional Neural Networks to Play Go. ICML 2015.
Watch before Lecture 21:
Rich Sutton, RL tutorial
Read before Lecture 22:
Read Silver, Huang et al, Mastering the game of Go with deep neural networks and tree search. Nature 529, 484-489 (28 January 2016). The "first AlphaGo" paper.
Read around Lecture 23:
Silver, Schrittwieser et al, Mastering the game of Go without human knowledge. Nature 550, 354-359. The "AlphaGo Zero" paper.
Silver, Hubert et al, A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. The "Alpha Zero" paper.
Optional reading: Supplementary Materials for this paper.
Optional reading Lecture 24: Schrittwieser, Antonoglou, Hubert, T. et al., Mastering Atari, Go, chess and shogi by planning with a learned model, Nature 588, 604609 (2020).
Last reviewed: Sep 4, 2023, Martin Müller