See the Wikipedia article on Kalah.
search (so this must be in a file called
search.py that implements two functions depth_limited_search_strategy
and depth_unlimited_search_strategy. Both of these functions take
a search depth and heuristic function and return a function that takes a position and
returns the move suggested by a search to that depth with the given heuristic function.
See the minimax_strategy function in the minimax module for an
example of such a function.
For depth_limited_search_strategy,
repeated moves by the same player count as separate moves for the purposes
of determining depth. That function will be evaluated based on whether it returns
the same move as minimax (with ties broken in favor of moves that appear earlier in the
list of legal moves).
Tests will be done on inputs for which no position
appears at different depths in multiple places in the search tree, so it is possible to
implement this function using a transposition table and then use that same implementation for
depth_unlimited_search_strategy.
The depth_unlimited_search_strategy
function will be evaluated based on both how often it wins
against minimax and how many fewer heuristic evaluations it applies compared to minimax.
The depth parameter to this function merely
determines the depth of the minimax search it is compared to
and need not be a strict limit on the depth of the search it implements.
The tests for this function
have a random element so there is a low but non-zero
probablity that a test with few games will incorrectly return "FAIL"; final grading will be done
with more games to reduce the variance.
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; and
game_over to determine if a position is terminal (in which case the
supplied heuristic will return a number with large magnitude that is positive
if the first player won and negative if the second player won).
minimax function in the minimax module for
examples of using these functions and read their documentation in the kalah module.
You have freedom in chosing your search method, but alpha-beta pruning with a transposition table that is kept between games will perform as well as minimax and will search call the heuristic function about 1/6 as often over the course of 100 games when 10% of moves are random and that will be used as a benchmark for success.
You may optionally create a new heuristic function that will be tested independently
from your search functions. To do so, create a function called heuristic
in your search module that takes a Position as its argument
and returns an estimate of the value of that position. Your new heuristic function
may use the "private" members of the Kalah.Position class using their
names as given in the kalah.py module.
/c/cs474/hw4 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_kalah.py the implements the test drivers
[jrg94@chameleon Kalah]$ python3 test_kalah.py -move 4 0 4 4 4 4 4 4 0 4 4 4 4 4 4 0 5 [jrg94@chameleon Kalah]$ python3 test_kalah.py -move 4 1 4 4 4 4 4 0 1 5 5 5 4 4 4 0 8 [jrg94@chameleon Kalah]$ python3 test_kalah.py -move 4 0 4 4 4 4 4 0 1 5 0 6 5 5 5 1 2 [jrg94@chameleon Kalah]$ python3 test_kalah.py -move 4 0 0 0 0 10 0 1 17 0 2 8 0 1 0 9 5 [jrg94@chameleon Kalah]$ python3 test_kalah.py -move 4 1 1 0 0 0 1 2 18 1 3 9 1 2 1 9 12 [jrg94@chameleon Kalah]$ python3 test_kalah.py -game 100 4 0.1 0.4 0.4 PASS [jrg94@chameleon Kalah]$ python3 test_kalah.py -game 100 4 0.1 0.4 0.2 PASS
search.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 Kalah that is used to run the test drivers.