mcts
(so this must be in a file called
mcts.py
that implements a function called
mcts_strategy
that takes
a number of iterations and returns a function that returns a function
takes a position and
returns the move suggested by running MCTS for that number of iterations
starting with that position.
The positions passed to the search functions will be instances of Kalah.Position
from the kalah
module. Python does not have a mechanism to prevent access
to members, but your search will not be graded if it accesses members whose names
begin with an underscore (the Python convention for indicating members not intended for
use by client code). The functions you are allowed to use are
legal_moves
to return a list of legal moves from a position, where the
moves are given as the indices of the pits to sow from, numbered counterclockwise
starting with 0 for P1's leftmost pit;
next_player
to determine which player is to make the next move;
result
to return the position that results from making a move;
game_over
to determine if a position is terminal;
winner
to determine which player won at terminal positions; and
is_initial
to determine if a position is the starting position.
minimax
function in the minimax
module for
examples of using these functions and read their documentation in the kalah
module.
heuristic
in your search
module that takes a Position
as its argument
and returns an estimate of the value of that position.
It may use the "private" members of the Kalah.Position
class using their
names as given in the kalah.py
module. Describe your
heuristic in your log file.
/c/cs474/hw5
are three Python 3 modules:
kalah.py
that defines classes that implement the rules of Kalah
minimax.py
that defines functions that implement minimax
test_mcts.py
the implements the test drivers
[jrg94@chameleon Kalah]$ pypy3 test_mcts.py -game 100 4 0.1 0.5 1000 PASS [jrg94@chameleon Kalah]$ pypy3 test_mcts.py -game 100 4 0.1 0.65 10000 PASSNote that the first test takes about four minutes and the second test takes the better part of an hour. This is the cost of using a search technique that doesn't require any domain knowledge.
mcts.py
module along with any other supporting modules
and your log.
There is no need to submit a makefile or executable; the test scripts create an executable
called MCTS
that is used to run the test drivers
using pypy3
. If you want to override the default makefile
then you can submit one named GNUmakefile
.
The time limit for the single public test is set to allow 1000 iterations per move. The private test cases may use more iterations and the time limit will be set proportionally higher.
Submissions must implement Monte Carlo Tree Search, so submissions that use a different search will not be graded even if they meet the performance requirements automatically checked by the grading scripts.