Assignment 3 - Search

Objectives

• to implement a game-tree search function with pruning

Introduction

See the Wikipedia article on Kalah.

Assignment

Create a Python 3 module called search (so this must be in a file called search.py) that implements two functions match_minimax_search_strategy and free_response_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 match_minimax_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) as well on how many times it calls the heuristic function compared to minimax.

The free_response_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 non-zero probablity that a test with few games will incorrectly return "FAIL"; this false negative rate will increase the closer to the expeected expected value the tests get. 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;
• 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); and
• winner to determine the winner at a terminal position, where the return value is 1 for player 0 winning, -1 for player 1 winning, and 0 for a draw.

You can see the minimax function in the minimax module for examples of using these functions and read their documentation in the kalah module.

You have freedom in choosing your search method, but scout with an appropriate move ordering and a transposition table will perform as well as minimax and will call the heuristic function about 6-7% as often when searching to a depth of 6 and when 10% of moves are random. That will be used as a benchmark for success. (Alphabeta alone will call the heuristic about 13% as often and scout without a transposition table will call the heuristic about 9% as often.)

Additional Requirements

• You may not use global variables or class variables (or any other construct that results in a variable whose lifetime is the entire execution of the program) in any of your modules. (Global constants are allowed and encouraged where appropriate.)
• Tests will be executed with pypy3, so write your code for Python 3.5 and only use modules are available for pypy3 on the Zoo (this excludes numpy).

Graduate Credit

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 should improve the results of minimax and should not examine any positions other than the one passed to it. 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.

Files

In /c/cs474/hw3 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

Examples

  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -move 4 0 4 4 4 4 4 4 0 4 4 4 4 4 4 0
  5
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -move 4 1 4 4 4 4 4 0 1 5 5 5 4 4 4 0
  8
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -move 4 0 4 4 4 4 4 0 1 5 0 6 5 5 5 1
  2
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -move 4 0 0 0 0 10 0 1 17 0 2 8 0 1 0 9
  5
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -move 4 1 1 0 0 0 1 2 18 1 3 9 1 2 1 9
  12
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -game:match 100 4 0.1 0.4 0.4
  PASS
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -game:match 100 4 0.1 0.4 0.33
  PASS
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -game:free 100 4 0.1 0.4 0.4
  PASS
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -game:free 100 4 0.1 0.4 0.33
  PASS
  [jrg94@hawk Kalah]$ pypy3 test_kalah.py -game:free 100 6 0.1 0.4 0.07
  PASS

Submissions

Submit just your 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.