com.antelmann.game
Class GameUtilities

java.lang.Object
  com.antelmann.game.GameUtilities

public final class GameUtilities
extends Object

The class GameUtilities 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.

Author:

Holger Antelmann

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)
static boolean	matchInArrays(int[] a, int[] b)
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

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.

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:

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

move - the move to be evaluated

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

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

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:

move - the move to be evaluated

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

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

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()

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:

move - the move to be evaluated

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

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

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

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.

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.

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.

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.

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.

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.

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.

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 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:

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;

Throws:

OutOfMemoryError

breadthFirstSearch

public static GamePlay breadthFirstSearch(GamePlay game,
                                          int[] roles,
                                          int numberOfMoves,
                                          Monitor monitor)
                                   throws 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.

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:

OutOfMemoryError - if too many game positions are to be searched

matchInArrays

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

isInArray

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