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
• Lecture 3, St. Petersburg Paradox
• Lecture 5, Trees and DAGs
• Lecture 6, Profiling and Optimization
• Go2, optimized version of Go1
• 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)
• Go3
• Lecture 12, Simulation methods
• (No new code for Lecture 13)
• Lecture 14, Probabilistic simulation policies and Bernoulli experiments
• Lecture 15 and 16, MCTS
• Lecture 18, Go4 and Go5 programs
• Lecture 19, Introduction to Neural Networks and Neural Net for TicTacToe

First Go programs - Go0 and Go1

See First Go programs - Go0 and Go1 and Sample Session with the Go1 Program.

Lecture 2, 2d Go board

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

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

• Use profile_Go1.py in your go0and1 folder to profile the Go1 program.

Go2, optimized version of Go1

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.

Simulation-based Go player Go3

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

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? binomial-select-experiment-calculation.txt, a detailed explanation for the first result computed by the program and shown in binomial-select-experiment.txt
• ucb.py UCB algorithm and two test cases from slides, with a small experiment varying the exploration constant C

Go4 and Go5 programs

• Simulation-based Go player with probabilistic playout policy Go4
• MCTS-based Go player Go5

Lecture 19, Introduction to Neural Networks (NN) and Neural Net for TicTacToe

• nn.py Two layer neural net from iamtrask blog
• nn3.py Three layer neural net from iamtrask blog
• New Oct 29: Code and data for learning neural net for TicTacToe. Download tictactoe_nnet.tgz .
  Code and data are in a directory tictactoe_nnet. There are python files for training and play, and two data files with the training examples (all solved TicTacToe positions) and a trained network. The most important files are:
  • README.md in markdown format (simple html like text)
  • multilayer_perceptron.py - implementation of the network
  • tic_tac_toe_train_nnet.py - training the network
  • nn_player.py - a player using the trained neural net data/tic_tac_toe_NN.npz
  • db_player.py - a perfect player using the ttt database in data/tic_tac_toe_DB
  • data/tic_tac_toe_DB - perfect play database
  • data/tic_tac_toe_NN.npz - neural net trained for TicTacToe
  • Some more python files to support standalone GTP-based players

Last modified: Oct 30, 2022, Martin Müller