Abstract Strategy Games

Elements

Player

An abstract strategy game is generally played between two players. The aim of each player is to make their position in the game more favourable in an effort to achieve the objective of the game, whilst making the opponent's position less favourable. Applications using the strategy game framework will generally have one of the players controlled by the user and the other by the computer, or have both players controlled by the computer (for example, to assess the effectiveness of various evaluation methods).

Board

The board is the playing area where the two players meet. The rules of the game dictate the characteristics of the board and what moves each player can make on the board. At any particular time, it is the turn of one of the players to make a move.

Move

An abstract strategy game involves each player making a move in turn. A move may involve placing one or more pieces on the board, moving existing pieces to different positions on the board, removing pieces from the board, capturing opponent pieces, flipping opponent pieces, and so on. The rules of the game dictate which moves are valid based on the state of the board and which player's turn it is. The conditions for the end of the game may include one or both of the players not being able to make a move.

Objective

The objective of most abstract strategy games is to achieve a particular game state, such as the checkmate state in chess, or the removal of all the opponent's pieces from the board in nine men's morris (or mills). Some games may assign a score to each player, with the objective being to achieve the end-game state with a higher score than the opponent.

Game Trees

At any point in an abstract strategy game, the board is in a particular state and it is the turn of one of the players to make a move. There may be several possible moves that may be made. For each of these moves, the opponent will have a set of possible moves that they can play. This situation may be represented by a tree, with each state of the game represented as a node in the tree.

For example, in the diagram below, the game is initially in state A, with player 1 (the initial player) to play. There are two possible moves, the first of which changes the game state to state B and the second to state C with player 2 to play. There are three possible moves from state B, and two possible moves from state C.

The above game tree is only plotted two moves ahead. As the tree is plotted deeper, the number of nodes increases exponentially. Almost all algorithms for determining the best move to play in an abstract strategy game generate a game tree and evaluate the game states at the leaves (the nodes in the tree that have no successors) to determine which branch, and hence move, is the most advantageous to play. In a simple game such a tic-tac-toe a complete game tree could be quickly generated by a computer for the entire game; however in a more complex game, there are too many possible game states (a full game tree for connect-four has in the order of 10¹⁴ nodes, reversi 10²⁸ nodes and chess 10⁴⁶ - this is referred to as the state-space complexity of the game). As a result, a computer uses a subset of the full tree to a predetermined depth.

Evaluating the Game State

In order to determine if a move is a good one, a quantitative measure of the game state is required. Scoring the game state is a key aspect of searching game trees. Only the leaves of the tree are scored, as these represent the game state after each of the possible moves are played, up to the tree depth (or earlier if a particular game state results in the game ending - see No-Move Scenarios below). Scoring is done for a specific player as what is good for one player is usually not good for the other, with higher scores representing better positions.

Searching a Game Tree With Minimax

In an abstract strategy game with two players, the players make moves alternately with each player attempting to improve their chance of winning, while decreasing the opponent's chance. If each player makes the best move available to them from each game state, the path through the tree which represents the best end game state for the initial player may be determined. This relies on picking the best move from each node.

An algorithm that implements this approach is minimax. The leaves are scored and each node in the tree is assigned the maximum score (for nodes representing the player's moves) or the minimum score (for nodes representing the opponent's moves) of the nodes directly under them. In the example below, which is done to a depth of 3, the move to state B is determined to be the best move from state A.

Pseudo-code for the minimax algorithm is as follows:

minimax(node)
    if node is a leaf
        return an evaluated score for the node
    if node is a minimising node
        minscore = +infinity;
        for each child of node
            minscore = min(minscore, minimax(child))
        return minscore
    if node is a maximising node
        maxscore = -infinity;
        for each child of node
            maxscore = max(maxscore, minimax(child))
        return maxscore

Game trees are generally searched depth-first, which allows large trees to be searched as it only requires enough memory corresponding to the depth of the tree (there is never a requirement to have more than the tree-depth number of game states in memory).

Searching a Game Tree with Negamax

Negamax is an extension of the minimax algorithm, where the maximum score is always selected for every node; however scores from child nodes are negated by each node.

Pseudo-code for the negamax algorithm is as follows:

negamax(node)
    if node is a leaf
        return an evaluated score for the node
    maxscore = -infinity;
    for each child of node
        maxscore = max(maxscore, -negamax(child))
    return maxscore


Optimising the Search Process

It is not always necessary to traverse the entire game tree when performing a search. Optimisations may be applied that decrease the number of evaluations that are done. This is advantageous as every evaluation done increases the time it takes for the computer to determine a move to play.

Alpha-Beta Pruning

Alpha-beta pruning involves ignoring parts of the tree that will have no effect on the search process. For example, max(3, min(-2, x)) and min(3, max(8, y)) are both always 3, irrespective of the value of x and y. These two situations can be applied to the nodes for game states B/E and A/C in the minimax game tree below respectively. This implies that the branches to game states L and G (and therefore everything that follows them too) are irrelevant to the outcome and can be pruned. The result on the tree below is that five of the evaluations which would be done by minimax are not necessary.

In order to determine when a branch may be pruned, a search window bound by an upper and lower value (alpha and beta) is maintained. Anything outside of the search window (less than alpha or greater than beta) is pruned. Alpha and beta are changed as the tree is searched, according to the values encountered. Pseudo-code for alpha-beta with minimax is as follows (with initial values of alpha and beta being -infinity and +infinity respectively):

minimax(node, alpha, beta)
    if node is a leaf
        return an evaluated score for the node
    if node is a minimising node
        minscore = beta
        for each child of node
            minscore = min(minscore, minimax(child, alpha, beta))
            beta = minscore
            if alpha >= beta
                return minscore  // cut-off
        return minscore
    if node is a maximising node
        maxscore = alpha
        for each child of node
            maxscore = max(maxscore, minimax(child, alpha, beta))
            alpha = maxscore
            if alpha >= beta
                return maxscore  // cut-off
        return maxscore


Alpha-beta pruning may be applied to negamax too by negating and swapping the alpha and beta values when passing them to a child node. Pseudo-code for alpha-beta with negamax is as follows (again, with initial values of alpha and beta being -infinity and +infinity respectively):

negamax(node, alpha, beta)
    if node is a leaf
        return an evaluated score for the node
    maxscore = alpha
    for each child of node
        maxscore = max(maxscore, -negamax(child, -beta, -alpha))
        alpha = maxscore
        if alpha >= beta
            return alpha  // cut-off
    return alpha


Move Ordering

The efficiency of alpha-beta pruning is affected by the order in which nodes are examined. Adjusting the order so that moves that are more likely to be good moves are examined first increases the probability of alpha-beta cut-offs happening early. A separate heuristic is used to perform the ordering; for example, in a chess game, moves that result in pieces being captured might be examined before moves that don't.

Other Optimisations

Iterative deepening involves starting with a tree depth of 1 and determining the best move, then increasing the tree depth and determining the best move again, and so on, until a particular criteria is met (for example, a predetermined period of time has passed or a maximum number of board evaluations has been done), at which point the best move determined to that point is returned. This allows the amount of time or effort for a tree search to be constrained (although the depth reached will vary depending on the number of nodes in the tree) and can also improve the efficiency of alpha-beta cut-offs if the results of each iteration are used to order the moves for the next iteration. If move ordering is done effectively iterative deepening can even be more efficient than a single pass search. Iterative deepening effectively allows a depth-first search to become a breadth-first search whilst retaining the properties of a depth-first search, such as low memory requirements.

The killer heuristic involves examining the last move that caused a beta cut-off at the same level in the tree search first, as it is likely that this move will result in a cut-off again. Put differently, a move that got a very good score at a particular search depth is likely to get a good score at this depth again. Although this is an assumption and not always true, and bearing in mind that a particular move at a specific depth may be considered many times during a search, it is generally true often enough for this small optimisation to have a big effect; particularly when iterative deepening is being used. Storing more than one killer move per level can further increase the effectiveness of this optimisation.

Refutation tables are a generalisation of the killer heuristic, where sub-tree information is recorded for specific game states. If that particular state is encountered again during a tree search, this information may be reused without having to generate and search this sub-tree, or if the depth was not sufficient, the stored information may be used to order the child nodes.

Searching a Game Tree with Negascout

Negascout is also an extension of the minimax algorithm and can be faster than negamax. Its principle is to narrow the alpha-beta search window to increase the possibility of a cut-off. Negascout uses a narrowed search window to perform an initial search and then a subsequent search with a wide window if values are found to lie outside of the initial window. Negascout is generally only an improvement on alpha-beta pruning if move ordering is applied effectively, and is particularly effective when used in conjunction with iterative deepening and associated move ordering. Conversely, negascout may be less efficient than negamax if move ordering is not applied effectively. Pseudo-code for negascout is as follows (again, with initial values of alpha and beta being -infinity and +infinity respectively):

negascout(node, alpha, beta)
    if node is a leaf
        return an evaluated score for the node
    maxscore = alpha
    b = beta
    for each child of node
        v = -negascout(child, -b, -alpha)
        if alpha < v < beta and not the first child and depth > 1
              v = -negascout(child, -beta, -v)  // re-search
        alpha = max(alpha, v)
        if alpha >= beta
            return alpha  // cut-off
        b = alpha + 1  // set new null window
    return alpha


No-Move Scenarios

Circumstances may arise where a player cannot make a move. Depending on the game, this might represent an end-game state or play might revert to the next player to go (a 'bye'). These scenarios are handled quite differently. The first scenario means that no further branches exist off this node, so the node should be considered to be a leaf and evaluated at this point, as shown in the negamax tree below.

The scenario where a bye is allowed can be handled by creating a single branch from this point, keeping the board state the same and changing the player, as shown in the negamax tree below.