|
||||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |
See:
Description
Interface Summary | |
Heuristic | A heuristic evaluating knockabout states |
SearchAlgorithm | Interface to be implemented by search algorithm used by SearcherPlayer |
Class Summary | |
AlphaBetaSearchAlgorithm | A real-time implementation of expected alpha-beta, with iterative deepening, move ordering and stochastic cut-off |
ConfigurableHeuristic | A weighted linear function-based heuristic |
DCMinMaxSearchAlgorithm | Bounded minmax algorithm using deep clone before each recursion |
ItMinMaxSearchAlgorithm | Iterative deepening, real-time expectiminimax search algorithm |
MCSearchAlgorithm | A Monte Carlo search algorithm implementation |
MinMaxSearchAlgorithm | A fixed depth expectiminmax search algo |
MoveComparator | Compare CompiledMove's according to their estimated utility |
SimpleHeuristic | This is the basic heuristic used for my first tests. |
Three search methods were tested: expected minimax, expected alpha-beta and Monte Carlo search. For high-level implementation information, see below, for specifications, check the javadoc of the corresponding classes. The default method used (the one running when GameClient is invoked without the third argument is EXPECTED ALPHA-BETA)
The class AlphaBetaSearchAlgorithm behaves just like the standard alpha-beta algorithm in the case of a deterministic node (see RUSSELL, 2003). In addition, it is encapsulated in an iterative deepening controlled by a separate time monitor thread, and it handles stochastic nodes in the following way:
(for stochasticMin, see the java source of AlphaBetaSearchAlgorithm) This cut-off is possible since all Heuristic used in this project are s.t. |heuristic(s)| <= 1 (for all knockabout state s). [Note that it is an implicit contract, see interface Heuristic]. So at each iteration, it is possible to find a lower bound for max value by assuming that all the remaining nodes (i.e. not explored yet) have a utility of -1.
Moreover, AlphaBetaSearchAlgorithm sorts the move based on a heuristic evaluation at each deterministic node using mergesort. This has the effect of slowing down the search (from order 100000 nodes/sec with minimax to order 10000 nodes/sec on my machine, but note that the way that the number of nodes/sec is calculated is unstable), but the reduction of the average branching factor b is considerable. With move ordering and stochastic cutoff, the average b goes from approx. 100 (with minimax) to approx. 20 (if counting the stochastic ramifications). This allows AlphaBetaSearchAlgorithm to "see" 3 or 4 moves ahead and execute basic attack and defense moves. Unfortunately, empirical tests have shown that this is not enough to make AlphaBetaSearchAlgorithm significantly better than expectiminimax (it is even worst than expectiminimax in some situations, and it is not yet clear why). (See below for testing methodology) Possible improvements that could make alpha-beta a more viable alternative include the use of transposition table, a database of pre-computed chance nodes (because the search is harder to cutoff there), guessing opponent's move and using his time period to start the search.
The class MCSearchAlgorithm evaluates a knockabout board position using a Monte Carlo search technique. For each successor state, k simulations of depth d are performed and averaged. The first version of MCSearchAlgorithm simulated trajectories completely randomly and at first, did not perform very well against the expected minimax implementation MinMaxSearchAlgorithm. Since this first version of MCSearchAlgorithm generates moves at random, it implies that less heuristic operations have to be done per node. Therefore it is expected to explore more nodes by units of time than MinMaxSearchAlgorithm but surprisingly, the opposite is observed (a drop from about 100000 nodes/second to 15000 nodes/second). (And 100% of the games lost over minimax-2) This problem is not yet solved in either the first or second implementation, but the latter is already much better. Instead of generating the trajectories completely randomly, it greedily chooses the best successor half the time and uses a random generator the other half.
The SimpleHeuristic class simply evaluates a board utility by the difference of the sum of the values of the dies not in the gutter for each player. This heuristic has the advantage of not being too computationally intensive (a fast access to a specified color's active dies has been added to the class Board). It prioritizes moves that knock enemy dies in the gutter while protecting its own. Unfortunately it also has many drawbacks due to its simplicity. For instance, a player should knock a D8 before a D4 if they have the same value, a feature not included in SimpleHeuristic. ConfigurableHeuristic, on the other hand, is a weighted linear function. It uses additional board features, namely the difference of the number of remaining D4, D6 and D8. The weight of the parameters are automatically and linearly normalized into the closed interval [-1,1]. Tests have shown the superiority of ConfigurableHeuristic over SimpleHeuristic
JUnit has been used for the primary tests. Unfortunately, because of time constraints, testing methods became lazier and less automated as the project evolved. In the last stages of development, the tests were run by bash shell scripts (see /tests/scripts/launchTest.sh and /tests/scripts/launchTest.sh) and the results, compiled with the grep, cat and wc UNIX commands (see /tests/compile.sh). When a lot of tests had to be ran, they were typically executed on remote machines with a common NFS home directory via ssh. All the search algorithm conform the SearchAlgorithm interface (and all heuristic, the Heuristic interface), so it was easy to modify the GameClient class so that an optional third command line argument can be added at invocation to specify which implementation of the search algorithm and heuristic should be used. This way, it was straightforward to organize "tournaments" between different search strategies and to gather statistics. See /tests for the results of various such tournaments (consult javadoc of class GameClient for naming conventions).
The package knockabout.search contains classes that perform the search in the game tree.
|
||||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |