Do by Sep 6
All papers/articles are on the eClass reading page
Do by Sep 6
All quizzes are on the eClass course page
Read by Sep 7 before class.
Do by Sep 7 before class, and later review as needed.
Do by Sep 13
python3 go2d.py
Do by Sep 13
Download go.tgz from the Python code page
and unpack it. See
First Go programs - Go0 and Go1
for instructions and explanations.
Do by Sep 13
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 by Sep 10
Download and install the GoGui user interface. You can use it for both Go and GoMoku. Then connect the Assignment 1 starter program.
board.pyIn class we discussed the code which implements a floodfill (dfs) to find blocks. Is this efficient? Can you think of a faster way?
Read by Sep 17: Heingartner, Maybe We Should Leave That Up to the Computer
Do by Sep 17. See Assignment 1 for details.
Do by Sep 20:
Play a game of Go against a colleague, against the Go1 program, or against an online opponent. See resources - Go.
Do by Sep 13:
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 by Sep 13.
Do by Sep 17:
Get familiar with the gogui-regress tool
for automated testing.
See
Regression testing with gogui-regress.
Watch by Sep 20.
Read by Sep 20: O'Neil, How algorithms rule our working lives.
Do by Sep 20:
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 by Sep 20:
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 by Sep 20:
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 by Sep 20:
See the description of Activity 5d in the Lecture 5 slides.
Do by Sep 20:
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 by Sep 24:
Add file profile_Go1.py to your go folder and profile Go1 with it. Try out some changes/optimizations and profile it again.
Do by Sep 24:
Using Activity 6a as a starting point, now profile your own GoMoku program. Note that this activity is not required for Assignment 1. However it will help you prepare for the upcoming assignment 2.
Read by Sep 27: 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 by Sep 27:
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 by Oct 4:
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 by Oct 4: Schaeffer et al, Checkers is solved. Science, 2007.
Do by Oct 4
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 by Oct 4
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 by Oct 4
Run the solvers in boolean_minimax_test_tictactoe.py and
boolean_negamax_test_tictactoe.py.
Set up other opening positions and solve them.
Do by Oct 11
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 by Oct 11
Implement your solution from 9a in a Python function.
Do by Oct 11
See discussion in Lecture 10 slides.
Do by Oct 11
Add a case in alphabeta_tictactoe_test.py to solve TicTacToe
with your new heuristic. What is the speed difference?
Do by Oct 11
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 by Oct 19: Van der Werf et al, Solving Go on small boards.
Just finish assignment 2.
Read by Oct 25: Computing Elo Ratings of Move Patterns in the Game of Go. Rémi Coulom, Computer Games Workshop 2007, Amsterdam.
Do by Oct 25
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 by Oct 25
Re-run the experiment Sim(1000) vs Perfect TicTacToe player with more games. Does Sim(1000) lose any games?
Do by Oct 25
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 by Oct 25
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.
Read by Nov 1
Parts of Browne et al, A Survey of Monte Carlo Tree Search Methods, as follows:
bernoulli.pyDo by Nov 1
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 by Nov 1
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 by Nov 15: A Few Useful Things to Know about Machine Learning. Pedro Domingos, Communications of the ACM 55 (10), October 2012, Pages 78-87.
Read by Nov 15:
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.
Do by Nov 22:
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 by Nov 22:
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".
By Nov 29:
Watch Rich Sutton, RL tutorial
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 by Dec 3:
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.
Created: Sep 21, 2017 Last modified: Aug 14/2021
Martin Müller, Ting-Han Wei, James Wright