org.jscience.computing.game
Class GameUtils

java.lang.Object
  org.jscience.computing.game.GameUtils

public final class GameUtils
extends java.lang.Object

The class GameUtils provides several algorithms for operating on GamePlay objects. These algorithms include several game tree searches such as MinMax or AlphaBeta, depth-first-search, breadth-first-search and best-first-search with GamePlay objects as nodes. These algorithms are commonly used by AutoPlay or Player objects. In addition, there are also some other convenience functions that ease standard operations GamePlay objects.

See Also:

GamePlay, AutoPlay, Player

Method Summary

static double	alphaBetaSearch(GamePlay game, GameMove move, Player player, int[] role, int level, boolean orderMoves) This function implements Alpha-Beta Search algorithm (intelligently pruned MinMax algorithm) and returns the evaluation given by the player's heuristic functions at the leaves; limited only by deepening level.
static double	alphaBetaSearch(GamePlay game, GameMove move, Player player, int[] role, int level, double alpha, double beta, boolean orderMoves) This function is usually just called by the other corresponding alphaBetaSearch function.
static double	alphaBetaSearch(GamePlay game, GameMove move, Player player, int[] role, int level, double alpha, double beta, long time, boolean orderMoves) This function is usually just called by the other timed alphaBetaSearch function.
static double	alphaBetaSearch(GamePlay game, GameMove move, Player player, int[] role, int level, double alpha, double beta, Monitor monitor, boolean orderMoves) This function is usually just called by the other corresponding monitored alphaBetaSearch function.
static double	alphaBetaSearch(GamePlay game, GameMove move, Player player, int[] role, int level, long time, boolean orderMoves) This function implements Alpha-Beta Search algorithm (intelligently pruned MinMax algorithm) and returns the evaluation given by the player's heuristic functions at the leaves - timed version (search cut off at given time).
static double	alphaBetaSearch(GamePlay game, GameMove move, Player player, int[] role, int level, Monitor monitor, boolean orderMoves) This function implements Alpha-Beta Search algorithm and returns the evaluation given by the player's heuristic functions at the leaves (intelligently pruned MinMax algorithm) - monitor version (search is cut off when monitor disabled).
static GamePlay	bestFirstSearch(GamePlay game, int[] roles, int maxNumberOfNodes, Player player, Monitor monitor) A 'best-first-search' algorithm that looks for a path to win the game according to the given roles.
static GamePlay	breadthFirstSearch(GamePlay game, int[] roles, int numberOfMoves, Monitor monitor) breadthFirstSearch() is a 'breadth-first-search' puzzle-solver.
static int	checkForWin(GamePlay game, int[] role) This convenience function checks whether there is a winner in the game corresponding to one of the given roles in the array; if so, it returns 1 in case the Player is among the winners, and -1 if that's not the case; a zero is returned if there are no winners or if GamePlay.getWinner() returns null.
static GamePlay	depthFirstSearch(GamePlay game, int[] roles, int numberOfMoves, Monitor monitor) depthFirstSearch() is a 'dfs puzzle-solver' that tries to find a path to a winning game position defined by the given roles within the given number of moves.
static GamePlay	depthFirstSearch(GamePlay game, int[] roles, int numberOfMoves, Player player, Monitor monitor) This depthFirstSearch() variant sorts the moves according to their heuristics provided by the given player before performing its otherwise 'depth-first-search' algorithm.
static GameMove[]	getLegalMovesSorted(GamePlay game, Player player, int[] roles, boolean descending) getLegalMovesSorted() sorts the legal moves of the given game descending or ascending by their heuristic calculated by the given player based on the roles.
static boolean	isInArray(int[] array, int element) DOCUMENT ME!
static boolean	matchInArrays(int[] a, int[] b) DOCUMENT ME!
static double	minMaxSearch(GamePlay game, GameMove move, Player player, int[] role, int level) implements MinMax Search algorithm and returns the evaluation given by the player's heuristic functions at the leaves; limited only by a deepening level
static double	minMaxSearch(GamePlay game, GameMove move, Player player, int[] role, int level, long time) implements MinMax Search algorithm and returns the evaluation given by the player's heuristic functions at the leaves; will only run as deep as given by the level and only as long as given time is less than System.currentTimeMillis().
static double	minMaxSearch(GamePlay game, GameMove move, Player player, int[] role, int level, Monitor monitor) implements MinMax Search algorithm and returns the evaluation given by the player's heuristic functions at the leaves; tracking is enabled tracking through a Monitor object.
static JGamePlay	selectJGamePlay() returns a JGamePlay based on a GUI-popup selection

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

selectJGamePlay

public static JGamePlay selectJGamePlay()

returns a JGamePlay based on a GUI-popup selection

Returns:

DOCUMENT ME!

getLegalMovesSorted

public static GameMove[] getLegalMovesSorted(GamePlay game,
                                             Player player,
                                             int[] roles,
                                             boolean descending)

getLegalMovesSorted() sorts the legal moves of the given game descending or ascending by their heuristic calculated by the given player based on the roles.

Parameters:

game - DOCUMENT ME!

player - DOCUMENT ME!

roles - DOCUMENT ME!

descending - DOCUMENT ME!

Returns:

the sorted array of the legal GameMove objects for the game

minMaxSearch

public static double minMaxSearch(GamePlay game,
                                  GameMove move,
                                  Player player,
                                  int[] role,
                                  int level,
                                  Monitor monitor)

implements MinMax Search algorithm and returns the evaluation given by the player's heuristic functions at the leaves; tracking is enabled tracking through a Monitor object. Use of the Monitor (suitable for multi-threaded environments): minMaxSearch() - provided that the game level is also still greater than 0 - only deepens the search further if the monitor is still enabled. When player.heuristic() is called by this function, it will also call monitor.increment() to indicate to an observing thread how many times a leaf node has been examined. Note that if a search is cut off prematurely by disabling the monitor, the returned value may reflect an unbalanced result due to the depth-first-search nature of the algorithm.

Parameters:

game - the GamePlay containing the game state information with the ability to create its children

move - the move to be evaluated

player - used to call the Player's heuristic function if node is a leaf

role - an int[] containing the roles the given Player plays in the game; this is used to determine whether it's the Player's or the opponent's move

level - the game level used to limit the tree search

monitor - used to cut off search externally and provide running feedback to a listening thread

Returns:

DOCUMENT ME!

See Also:

Player, Monitor

minMaxSearch

public static double minMaxSearch(GamePlay game,
                                  GameMove move,
                                  Player player,
                                  int[] role,
                                  int level,
                                  long time)

implements MinMax Search algorithm and returns the evaluation given by the player's heuristic functions at the leaves; will only run as deep as given by the level and only as long as given time is less than System.currentTimeMillis(). Note that searches that are limited by time may only be as 'valuable' as a 0-level search if the search is cut off prematurely, as some tree branches may only be searched as deep as 0 - due to the depth-first-search nature of the algorithm.

Parameters:

game - the GamePlay containing the game state information with the ability to create its children

move - the move to be evaluated

player - used to call the Player's heuristic function if node is a leaf

role - an int[] containing the roles the given Player plays in the game; this is used to determine whether it's the Player's or the opponent's move

level - the game level used to limit the tree search

time - used to cut off search when the given time is before System.currentTimeMillis()

Returns:

DOCUMENT ME!

See Also:

Player

minMaxSearch

public static double minMaxSearch(GamePlay game,
                                  GameMove move,
                                  Player player,
                                  int[] role,
                                  int level)

implements MinMax Search algorithm and returns the evaluation given by the player's heuristic functions at the leaves; limited only by a deepening level

Parameters:

game - the GamePlay containing the game state information with the ability to create its children

move - the move to be evaluated

player - used to call the Player's heuristic function if node is a leaf

role - an int[] containing the roles the given Player plays in the game; this is used to determine whether it's the Player's or the opponent's move

level - the game level used to limit the tree search

Returns:

DOCUMENT ME!

See Also:

Player

alphaBetaSearch

public static double alphaBetaSearch(GamePlay game,
                                     GameMove move,
                                     Player player,
                                     int[] role,
                                     int level,
                                     Monitor monitor,
                                     boolean orderMoves)

This function implements Alpha-Beta Search algorithm and returns the evaluation given by the player's heuristic functions at the leaves (intelligently pruned MinMax algorithm) - monitor version (search is cut off when monitor disabled). Parameters passed and monitor usage are identical to corresponding minMaxSearch function with the addition of the boolean orderMoves, which - if enabled - will order the legal moves according to their heuristic (best heuristic value first) before continuing the search in the next level (to improve tree pruning). Using the parameter orderMoves trades off between faster tree search (orderMoves = false) vs. potentially more effective tree pruning (orderMoves = true). Note that if a search is cut off prematurely by disabling the monitor, the returned value may reflect an unbalanced result due to the depth-first-search nature of the algorithm. The function simply calls the other alphaBetaSearch function by appending Double.NEGATIVE_INFINITY and Double.POSITIVE_INFINITY as values for alpha and beta.

See Also:

Monitor

alphaBetaSearch

public static double alphaBetaSearch(GamePlay game,
                                     GameMove move,
                                     Player player,
                                     int[] role,
                                     int level,
                                     double alpha,
                                     double beta,
                                     Monitor monitor,
                                     boolean orderMoves)

This function is usually just called by the other corresponding monitored alphaBetaSearch function. This function can be called directly if one wishes to set initial values for alpha and beta explicitly. The use of the monitor is equivalent to corresponding minMaxSearch()'s use of the monitor. Note that if a search is cut off prematurely by disabling the monitor, the returned value may reflect an unbalanced result due to the depth-first-search nature of the algorithm.

See Also:

Monitor

alphaBetaSearch

public static double alphaBetaSearch(GamePlay game,
                                     GameMove move,
                                     Player player,
                                     int[] role,
                                     int level,
                                     long time,
                                     boolean orderMoves)

This function implements Alpha-Beta Search algorithm (intelligently pruned MinMax algorithm) and returns the evaluation given by the player's heuristic functions at the leaves - timed version (search cut off at given time). The function simply calls the other alphaBetaSearch function by appending Double.NEGATIVE_INFINITY and Double.POSITIVE_INFINITY as values for alpha and beta.

Parameters:

game - DOCUMENT ME!

move - DOCUMENT ME!

player - DOCUMENT ME!

role - DOCUMENT ME!

level - DOCUMENT ME!

time - DOCUMENT ME!

orderMoves - DOCUMENT ME!

Returns:

DOCUMENT ME!

alphaBetaSearch

public static double alphaBetaSearch(GamePlay game,
                                     GameMove move,
                                     Player player,
                                     int[] role,
                                     int level,
                                     double alpha,
                                     double beta,
                                     long time,
                                     boolean orderMoves)

This function is usually just called by the other timed alphaBetaSearch function. This function can be called directly if one wishes to set initial values for alpha and beta explicitly. Search is cut off when level is reached or when System.currentTimeMillis() is larger than given time. Note that searches that are limited by time may only be as 'valuable' as a 0-level search if the search is cut off prematurely, as some tree branches may only be searched as deep as 0 - due to the depth-first-search nature of the algorithm.

Parameters:

game - DOCUMENT ME!

move - DOCUMENT ME!

player - DOCUMENT ME!

role - DOCUMENT ME!

level - DOCUMENT ME!

alpha - DOCUMENT ME!

beta - DOCUMENT ME!

time - DOCUMENT ME!

orderMoves - DOCUMENT ME!

Returns:

DOCUMENT ME!

alphaBetaSearch

public static double alphaBetaSearch(GamePlay game,
                                     GameMove move,
                                     Player player,
                                     int[] role,
                                     int level,
                                     boolean orderMoves)

This function implements Alpha-Beta Search algorithm (intelligently pruned MinMax algorithm) and returns the evaluation given by the player's heuristic functions at the leaves; limited only by deepening level. Parameters passed are identical to corresponding minMaxSearch The function simply calls the other alphaBetaSearch function by appending Double.NEGATIVE_INFINITY and Double.POSITIVE_INFINITY as values for alpha and beta.

Parameters:

game - DOCUMENT ME!

move - DOCUMENT ME!

player - DOCUMENT ME!

role - DOCUMENT ME!

level - DOCUMENT ME!

orderMoves - DOCUMENT ME!

Returns:

DOCUMENT ME!

alphaBetaSearch

public static double alphaBetaSearch(GamePlay game,
                                     GameMove move,
                                     Player player,
                                     int[] role,
                                     int level,
                                     double alpha,
                                     double beta,
                                     boolean orderMoves)

This function is usually just called by the other corresponding alphaBetaSearch function. This function can be called directly if one wishes to set initial values for alpha and beta explicitly.

Parameters:

game - DOCUMENT ME!

move - DOCUMENT ME!

player - DOCUMENT ME!

role - DOCUMENT ME!

level - DOCUMENT ME!

alpha - DOCUMENT ME!

beta - DOCUMENT ME!

orderMoves - DOCUMENT ME!

Returns:

DOCUMENT ME!

checkForWin

public static int checkForWin(GamePlay game,
                              int[] role)

This convenience function checks whether there is a winner in the game corresponding to one of the given roles in the array; if so, it returns 1 in case the Player is among the winners, and -1 if that's not the case; a zero is returned if there are no winners or if GamePlay.getWinner() returns null.

Parameters:

game - DOCUMENT ME!

role - DOCUMENT ME!

Returns:

DOCUMENT ME!

depthFirstSearch

public static GamePlay depthFirstSearch(GamePlay game,
                                        int[] roles,
                                        int numberOfMoves,
                                        Monitor monitor)

depthFirstSearch() is a 'dfs puzzle-solver' that tries to find a path to a winning game position defined by the given roles within the given number of moves. The search is done recursively in 'depth-first-search' manner with backtracking, i.e. the method is not guaranteed to find the shortest path. If the given monitor is not null, it can be used to cut off the recursive calls by disabling the monitor from a different thread; also, monitor.increment() is called for every time the function is entered - counting the number of nodes examined. This function doesn't check for who is making the moves; it's really more intended to solve 'puzzles' that are represented by a GamePlay.

Parameters:

game - DOCUMENT ME!

roles - DOCUMENT ME!

numberOfMoves - DOCUMENT ME!

monitor - DOCUMENT ME!

Returns:

null if no win can be found or the GamePlay that represents the winning position that can be reached within the given number of moves; with GamePlay.getMoveHistory() one can then examine the winning path included in the game status.

depthFirstSearch

public static GamePlay depthFirstSearch(GamePlay game,
                                        int[] roles,
                                        int numberOfMoves,
                                        Player player,
                                        Monitor monitor)

This depthFirstSearch() variant sorts the moves according to their heuristics provided by the given player before performing its otherwise 'depth-first-search' algorithm. If the given monitor is not null, it can be used to cut off the recursive calls by disabling the monitor from a different thread; also, monitor.increment() is called for every time the function is entered - counting the number of nodes examined. This function doesn't check for who is making the moves; it's really more intended to solve 'puzzles' that are represented by a GamePlay.

Parameters:

game - DOCUMENT ME!

roles - DOCUMENT ME!

numberOfMoves - DOCUMENT ME!

player - DOCUMENT ME!

monitor - DOCUMENT ME!

Returns:

null if no win can be found or the GamePlay that represents the winning position that can be reached within the given number of moves; with GamePlay.getMoveHistory() one can then examine the winning path included in the game status.

bestFirstSearch

public static GamePlay bestFirstSearch(GamePlay game,
                                       int[] roles,
                                       int maxNumberOfNodes,
                                       Player player,
                                       Monitor monitor)
                                throws java.lang.OutOfMemoryError

A 'best-first-search' algorithm that looks for a path to win the game according to the given roles. Note that the given player must return a heuristic value that is consistent with the GamePlay's equals() method, i.e. if two GamePlay objects are the same according to the equals() method, they must return the same heuristic by the player. Use of monitor (if not null): monitor.increment() is called for every node examined. A call to this function uses high amounts of memory due to maintaining an open and closed list.

Parameters:

game - DOCUMENT ME!

roles - DOCUMENT ME!

maxNumberOfNodes - the maximum number of nodes to be examined; since this function does not go strictly breadth or depth first, this number does not correlate with the number of moves away from the initial game status;

player - DOCUMENT ME!

monitor - DOCUMENT ME!

Returns:

DOCUMENT ME!

Throws:

java.lang.OutOfMemoryError - DOCUMENT ME!

breadthFirstSearch

public static GamePlay breadthFirstSearch(GamePlay game,
                                          int[] roles,
                                          int numberOfMoves,
                                          Monitor monitor)
                                   throws java.lang.OutOfMemoryError

breadthFirstSearch() is a 'breadth-first-search' puzzle-solver. The method is guaranteed to find the shortest path if one exists; the drawback is that it uses extensive resources (any non-leaf game status needs to be kept in memory). If the given monitor is not null, it can be used to cut off the recursive calls by disabling the monitor from a different thread; also, monitor.increment() is called for every time the function is entered - counting the number of nodes examined. Additionally, monitor.runTask() is called when a new level is reached (i.e. when the number of moves is increased). This function doesn't check for who is making the moves; it's really more intended to solve 'puzzles' that are represented by a GamePlay.

Parameters:

game - DOCUMENT ME!

roles - DOCUMENT ME!

numberOfMoves - DOCUMENT ME!

monitor - DOCUMENT ME!

Returns:

null if no win can be found or the GamePlay that represents the winning position that can be reached within the given number of moves; with GamePlay.getMoveHistory() one can then examine the winning path included in the game status. Note that this function can easily throw an OutOfMemoryError, if the number of game positions to be searched grows too large (since the bfs algorithm needs to maintain the list of moves to be followed up on), so keep the numberOfMoves in reasonable limits.

Throws:

java.lang.OutOfMemoryError - if too many game positions are to be searched

matchInArrays

public static boolean matchInArrays(int[] a,
                                    int[] b)

DOCUMENT ME!

Parameters:

a - DOCUMENT ME!

b - DOCUMENT ME!

Returns:

DOCUMENT ME!

isInArray

public static boolean isInArray(int[] array,
                                int element)

DOCUMENT ME!

Parameters:

array - DOCUMENT ME!

element - DOCUMENT ME!

Returns:

DOCUMENT ME!