Python Sample Code

All sample code is written in Python 3. Code is used for activities and assignments. Code includes a series of Go programs, starting from the basics and leading up to simple re-implementations of many of the techniques used by AlphaGo.

Contents

• First Go programs - Go0 and Go1
• Lecture 2, 2d Go board
• Assignment 1 starter code
• Lecture 3, St. Petersburg Paradox
• Lecture 5, Trees and DAGs
• Lecture 6, Profiling and Optimization
• Go2, optimized version of Go1
• Assignment2 Starter Code
• Lecture 7, Search
• Lecture 8, Minimax
• Lecture 9, Minimax and Alphabeta part 2
• Lecture 10, Minimax and Alphabeta part 3
• (No new code for Lecture 11)
• Lecture 12, Simulation methods
• Solutions for Selected Activities
• Assignment 3 starter code
• Go3
• (No new code for Lecture 13)
• Lecture 14, Probabilistic simulation policies and Bernoulli experiments
• Lecture 15 and 16, MCTS
• Go4 and Go5 programs
• Lecture 19, Introduction to Neural Networks

First Go programs - Go0 and Go1

Download go.tgz and unpack it. The go directory contains the following files:

• Go0.py - the Go0 class and the main function of program Go0
• Go1.py - the Go1 class and the main function of program Go1
• board.py - the class GoBoard implementing a basic Go board
• board_util.py - board-related utility functions
• test_board.py - INCOMPLETE but functional - unit tests for board.py
• gtp_connection.py - the class GtpConnection implementing a Go Text Protocol (GTP) connection
• gtp_connection_go1.py - example for how to extend a GTP connection with more commands

Lecture 2, 2d Go board

• go2d.py Small code fragment for Go board implemented as "2-dimensional" list-of-lists.

Assignment 1 starter code

Download assignment1.tgz and unpack it. For description of contents, see Assignment 1

Lecture 3, St. Petersburg Paradox

• petersburg-demo.py Play the St. Petersburg Paradox one round at a time.
• petersburg.py Play the St. Petersburg Paradox 1000 times.
• petersburg2.py Play the St. Petersburg Paradox and print statistics after every 2^n rounds.

Lecture 5, Trees and DAGs

• count_dag.py Count nodes at each level of a Tic-Tac-Toe-like DAG.
• generate_tree.py Generate trees of given b and d.
• generate_tree_test.py Test cases for generate_tree.py.

Lecture 6, Profiling and Optimization

• profile_Go1.py Add to your go folder and profile Go1 with it.

Go2, optimized version of Go1

• Download go2.tgz and unpack it. The go2 directory contains the program Go2, which is the optimized version of Go1 as discussed in Lecture 6. You can run profile_Go2.py and compare it with the Go1 profile.

Assignment2 Starter Code

• Download assignment2.tgz and unpack it.
• Also see Assignment 2

Lecture 7, Blind Search

• blind_search_on_tree.py Treasure hunt demo program from class. Dfs, bfs and random simulations.
• heuristic_search_on_tree.py Treasure hunt demo program from class. Adds a heuristic of varying strength to sampling.

Lecture 8, Minimax and Alphabeta part 1

• game_basics.py Some basic definitions for games
• tic_tac_toe.py TicTacToe board and rules. Requires game_basics.py
• boolean_minimax.py Boolean minimax, try to find win for BLACK
• boolean_negamax.py Boolean minimax, negamax version
• boolean_minimax_test_tictactoe.py Solve TicTacToe with boolean minimax and measure the time used
• boolean_negamax_test_tictactoe.py Same with negamax

Lecture 9, Minimax and Alphabeta part 2

• search_basics.py Basic definitions used by minimax/negamax and alphabeta search codes
• minimax_sample_tree.py and minimax_sample_tree_data.py Create an artificial game tree to illustrate minimax and alphabeta
• tic_tac_toe_integer_eval.py TicTacToe with integer-valued evaluation, suitable for alphabeta search
• naive_minimax.py Naive minimax without any pruning
• naive_negamax.py Naive negamax without any pruning
• naive_minimax_negamax_test.py Tests the naive minimax and negamax codes on the sample tree
• alphabeta.py Alphabeta algorithm.
• alphabeta_depth_limited.py Alphabeta algorithm with depth limit.
• alphabeta_test.py Test alphabeta.py on the sample tree
• alphabeta_tictactoe_test.py Alphabeta vs naive negamax for solving TicTacToe
• alphabeta_depth_limited_tictactoe_test.py Tests for depth-limited alphabeta searches in TicTacToe.

Lecture 10, Minimax and Alphabeta part 3

• tic_tac_toe.py New version of TicTacToe board adds code() method for hash code
• transposition_table_simple.py Simple transposition table for TicTacToe, uses dictionary and encoding of the full board state
• boolean_negamax_tt.py Boolean negamax with transposition table
• tic_tac_toe_solve_with_tt.py Boolean negamax with transposition table for solving TicTacToe
• tic_tac_toe_estimate_tree.py Estimate size of TicTacToe state space with simple tree formula
• tic_tac_toe_count_tree.py Enumerate TicTacToe state space as tree
• tic_tac_toe_count_dag.py Enumerate TicTacToe state space as DAG
• tic_tac_toe_solve_all.py Solve all possible TicTacToe states
• alphabeta_trace.py Alphabeta with printouts tracing function calls, best move changes, and returns
• alphabeta_trace_test.py Call alphabeta_trace.py for the sample tree.

Lecture 12, Simulation methods

• estimate_pi.py Estimate pi with Monte Carlo sampling
• numerical_integration_MC.py Numerical Integration with Monte Carlo sampling
• tic_tac_toe.py and tic_tac_toe_integer_eval.py Tic Tac Toe board with support for simulations
• tic_tac_toe_simulation_test.py Run simulations from empty TicTacToe board and report statistics on winner and game length
• simulation_player.py Simulation-based "Flat Monte Carlo" player, 1 ply search, then evaluation by simulation rollouts
• random_player.py Random player, plays a random legal move
• perfect_player.py Perfect player, uses solver to generate a move
  alphabeta_with_move.py Modified alphabeta to return both score and move, used in perfect_player
• play_match.py Play a match between different TicTacToe players

Solutions for Selected Activities

• Activities Lecture 5 some solutions: count_dag_solution.py Calls count_dag.py to compute and print the answers.
• Activities 8a and 8b solutions: min_proof_tree.py Compute size of minimal proof trees for (b,d) tree model. Counts level by level in a loop, does not use a closed formula.

Go3

• go3.tgz The Go3 program, FlatMC simulation-based Go player
• Go3 documentation - command line options, GTP commands etc.

Assignment 3 starter code

• assignment3.tgz Includes Gomoku random player and public gtp test file
• Also see the Assignment 3 specification

Lecture 14, Probabilistic simulation policies and Bernoulli experiments

• prob_select.py Probabilistic selection from a list
• bernoulli.py Run repeated Bernoulli experiments
• mystery-bernoulli.py Guess the unknown parameter p of a repeated Bernoulli experiment

Lecture 15 and 16, MCTS

• binomial-select.py and binomial-select-experiment.txt How often do bandits based on Bernoulli experiments make the wrong choice?
• ucb.py UCB algorithm

Lecture 19, Introduction to Neural Networks (NN)

• nn.py Two layer neural net from iamtrask blog
• nn3.py Three layer neural net from iamtrask blog

Go4 and Go5 programs

• go4.tgz - probabilistic playout policy
• go5.tgz - MCTS

Created: Jan 3, 2018 Last modified: Nov 16, 2020

Martin Müller and Ting-Han Wei