Python Sample Code

For the Python code, it works best to put it all into the same directory. There are some imports between them. For example, game rules and search algorithms are imported by code which tests or runs them.

Some of the code may be marked as CMPUT 655 or 455 since it was originally developed for those courses.

Boolean Minimax and Negamax
Alphabeta
Alphabeta Enhancements
Clobber - Rules and Solver
proof number search

Boolean Minimax and Negamax

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

Alphabeta

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.
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.

Alphabeta Enhancements

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 in tree model
tic_tac_toe_solve_all.py Solve all possible TicTacToe states in DAG model

Clobber - Rules and Solver

clobber_1d.py Rules of Clobber on a one-dimensional (1 x n) board
test_clobber_1d.py A few unit tests for clobber_1d.py (incomplete but functional)
boolean_minimax_test_clobber_1d.py Examples showing how to solve Clobber positions with boolean_negamax. This code requires game_basics.py, boolean_negamax.py and clobber_1d.py (see above).
clob_tt.py Solve Clobber positions with simple transposition table.

proof number search