Analysis of Game Playing Heuristics for Isolation

Kory Becker - April 3, 2020

Synopsis

Isolation is a game in which two players take turns making moves on a grid in an attempt to block the other player from being able to make a move. Each player can choose to move to a particular cell, provided the cell path is clear according to the rules of the game. As the game board in Isolation is fully viewable by both players at all times, the game is fully observable, adversarial, and deterministic. This allows the development of an AI-based game playing agent using suitable algorithms and heuristics, including Minimax.

This report includes an analysis of several advanced search techniques and heuristics for building a game playing agent for Isolation. The performance of each heuristic is detailed, including the resulting win ratio and performance metrics. Finally, we summarize the most effective heuristic algorithm for an AI game playing agent in Isolation from the selected algorithms.

Figure 1. Baseline win percentages for an AI agent using the Minimax algorithm at varying levels of search depth, playing against an opponent using Minimax at a fixed search depth of 3. The depth of search directly corresponds to the win percentage.

Agent Heuristic Effectiveness
Heuristic	Wins vs Minimax (%)
random	5.2
baseline	50.0
simple	49.8
defensive	49.5
offensive	51.0
defensive_to_offensive	46.0
offensive_to_defensive	52.2
walls	46.8

Table 1. A comparison of AI agent heuristic win percentages from the Minimax algorithm at a search depth of 3, against an opponent using the baseline heuristic. The random heuristic provides the lowest win percentage, while a combined strategy of changing between offensive and defensive mode results in the highest.

Results

In order to establish a baseline of win percentages, we first compare the same baseline heuristic against both players iterating from a Minimax search depth of 2 through 6. The opponent is fixed at a Minimax search depth of 3. As shown in the first plot, the win percentage for the AI agent steadily increases with direct correlation to the Minimax search depth. As the agent is able to utilize a deeper look-ahead on the game board, the percentage of wins increases for the player. Note, as expected, at a search depth of 3 the AI agent wins exactly 50% of the time against the opponent (that is also using a search depth of 3).

We next compare a series of advanced heuristics against the opponent at the same Minimax search depth of 3. Details of each heuristic applied are listed below.

What features of the game does your heuristic incorporate, and why do you think those features matter in evaluating states during search?

The most effective heuristic is offensive_to_defensive with a win percentage of 52.2% over Minimax using a baseline heuristic. To confirm the effectiveness of this heuristic, the agent is given a search depth of 6 and, as expected, results in a higher win percentage over the baseline of 58% (see output below).

The effectiveness of this heuristic likely stems from the dynamic capability that allows the agent to switch between two different strategies depending on the state of the game. Different strategies may be more effective according to early versus late game techniques. In the offensive_to_defensive heuristic, the agent is able to play an aggressive style of game-play at the beginning of the game, attempting to force the opponent into a weaker position. The agent can then switch to a defensive style of game player as available spaces become limited, thus maximizing the time the agent can continue playing with available moves, while the opponent (in a weaker position) has a higher likelihood of running out of moves.

Analyze the search depth your agent achieves using your custom heuristic. Does search speed matter more or less than accuracy to the performance of your heuristic?

As the results demonstrate, the search depth appears to have the most impact on the win percentage for the Minimax heuristic, even for the baseline heuristic type. Search speed also plays a factor, in the fact that utilizing a search depth beyond 6 resulted in agents that were unable to complete their game-play. For this reason, it’s important to consider optimizing heuristic techniques, such as using alpha-beta pruning with the Minimax algorithm and iterative deepening to limit the lag time between moves and optimize the agent’s decision process.

Advanced Heuristics

Each heuristic used in this analysis is described below. The most effective advanced heuristic was able to achieve a maximum win percentage of 58% at a Minimax search depth of 6, against the baseline opponent. The heuristic utilized several unique features of the game as described in the following section.

Baseline

A baseline heuristic was used by both the player and the opponent. This heuristic relied on a simple formula to maximize the number of available player moves minus the number of opponent moves. This effectively maximizes moves that the player can make, while minimizing the opponent’s.

len(player_moves) - len(opponent_moves)

Simple

The simple heuristic is similar to the baseline, with the exception that it only considers the player’s available moves.

len(player_moves)

Defensive

The defensive heuristic favors maximizing the player’s available moves at a weighted cost against those available to the opponent. This has the effect of strongly preferring to keep the player’s moves larger at all costs against the opponent.

(len(player_moves) * 2) - len(opponent_moves)

Offensive

By contrast to the defensive strategy, the offensive heuristic favors minimizing the opponent’s available moves at a weighted cost against those available to the player. This achieves an aggressive style of game play, attempting to force or limit the opponent into a weaker game position.

len(player_moves) - (len(opponent_moves) * 2)

Defensive to Offensive

The defensive to offensive heuristic applies an early-game defensive strategy, where the player tries to initially maximize the number of available moves. After a period half-way through the game, the heuristic switches to offensive, attempting to limit and block the opponent.

This is achieved by taking into account a ratio value, computed from the current round divided by the game board size. When the number of rounds in the game is less than half-way through, the heuristic employs a defensive strategy. Afterwards, an offensive strategy is utilized.

ratio = state.ply_count / (_WIDTH * _HEIGHT);
self.defensive(state) if ratio <= 0.5 else self.offensive(state)

Offensive to Defensive

The most effective heuristic is the offensive to defensive strategy. By contrast to the defense to offensive strategy, this heuristic applies an aggressive game-play early, and later switches to a defensive strategy.

ratio = state.ply_count / (_WIDTH * _HEIGHT);
self.offensive(state) if ratio <= 0.5 else self.defensive(state)

Walls

The walls heuristic takes into account the distance that the player is from each side of the game board, attempting to favor being placed in the center of the board, in the goal of allowing more available moves to be present without being blocked by a wall.

dis = self.distance(state)
if dis >= 2:
  return self.defensive(state)
else:
  # Favor the center of the board.
  return len(player_moves) - len(opponent_moves)

Output

Options: Rounds=100, Fair-Game

python3 run_match.py -r 100 -f

depth=3

random

Running 200 games:
----------------------------------------------------+----------------------------------------------------------------+--------+--------------------------------------------------------------+++---+------------------+
Running 200 games:
-----------------------+---------+--------------------+----------------------------------------++-------+----+-----------+-------------------------------------+----+-----------+---------+-------------------+-+----+--
Your agent won 5.2% of matches against Minimax Agent

baseline

Running 200 games:
+-++++-++-+++-+++----+++--+++++-+-+-++-++-+--++---++-+-+--+-++++--++++++++++---+-++--++-++--++++--++++++++++---+-----+--++---+--+-+--+++++++++++++--+--++++---++--++--++-++-+-++--+++-+++-++++++++-+---+++++--+++-+--
Running 200 games:
-+--+---+-------+++++---+-+--+-+-+-+--++--++---+++--+---++++-----++---------+++-+-+--+---+--+--+---------+++-++++++++---++-+++-+-+-+----+--------+-+-+---+++-+-+----+-++--++--+-+--+---+--++----+-++++---+-+-+---++-
Your agent won 50.0% of matches against Minimax Agent

simple

Running 200 games:
--+++++--+++---++++-+--++++---++++--++++------++++++++-------+++------++++---+--+-+--+++----+++-+-+-+-+-+--+-+--++---++--++--+---+--++-+++---++-+++-+---+-+++-+--+---+++---++++---++-+--+++++-++++-----+-+-++-+---++--+--+-+
Running 200 games:
++-+++--+--+--+-+++----+++-----+++++---++-+---+++-+----++-++---+++----++--+-+--++---+++++-+-+-++-+-+---+-++-++-++-+-+++--+-++++--+-++-+--++----++------+--+------++++-+---+--+-++++--++++--+-++----+-+-+++-+-++-----
Your agent won 49.8% of matches against Minimax Agent

defensive

Running 200 games:
-+-----++-++-+----+---+-+-++----+-++--++----+++-+++-++-+++++----------+++-++++----++-+-++++----++---+++-++++-++++++-+++++---++-+-+---+-++-+--+-----++++---+-++++----+++--+-+-+-++-+-+----+++---+-++++-++-+--+-+---
Running 200 games:
-----+----+-++-+----++++-++-+----+-+-----++-+---------+--++++--+++++------+-+--++-++--+-+++---+++++++---++--+-+------+++++++----++---++++--+--+++-++----+-++-+-++-+++++--++++++++--+++-+--++---+--+++--+-+-+++----++-+
Your agent won 49.5% of matches against Minimax Agent

offensive

Running 200 games:
+++++-+++--+++---+-+++++---+-+----+++-+--+++--++++--+----++--++----++++++-+-+--+----+-+++-+-+-+++++-----+-+----+-++++++-+-+----+-++--+++++++++--++----+++++++-++--+++--++--+-++++-+--+-+---+-+---+--++++++-++--+--+++-
Running 200 games:
-+++-++++--------+--+++-+-++-+---+-++----+-+-+-++-++-+-++++--++++-+-----+++---++-++++--++-++-----+++++------+----+-+-+--++-+--++-+--+--++++---+-----++-------+-++-----+++--++-++-++-++-+++++-+-++-+--+--++---+--++---+-+-+
Your agent won 51.0% of matches against Minimax Agent

defensive_to_offensive

Running 200 games:
---+-----++-+--+--+-+--+-+--+++----+-+-+-------+-+-----++-+-+----+--++----++--+++----+-+-+--+++++---+++-+--+-+--++++-++++--+-+-+--+----+-+++++-+--++-+--++++-+++++++-------+++--++--+-+++++++-+-+------+--+---+++-++++
Running 200 games:
+-+--+--++++-+---+--+--+++-+------++-+----+----++-++----+--++--++-+++------+--+-+-++---++++------+----+++-+++--+--++++++-+-+-+-+++-+-----+-++-++++++++++-+--+----+-----+--++----+-+--++----+-----+-++--+----+--++-+-++
Your agent won 46.0% of matches against Minimax Agent

offensive_to_defensive

Running 200 games:
+++-+--+-+++-+++++-+--+++++-++---+-++--++++-+-+---++++--++-++-+---+-++-++++-+++++--++-++++-+---++-+-+-----+++-++---++++------+++-+++++---++++-++---+-++-+-++-+--+++----++++--+++---+++++---+++--+++++--++-+++++--+++-+++----
Running 200 games:
-------+-++----+-+---+-++--+-++++-+-++---+---+++---+++-++----++++++-+-++-+---+---+--+-++-+-++---+++-++-++-------++++----++++---+--+-+-+-+++++---------++---+-+++----+++++-+---++---++++-++---++++++-++++---++---+++++---+--
Your agent won 52.2% of matches against Minimax Agent

walls

Running 200 games:
+++--++++--++---+-+--++-+-+-+++-++-++---+++-+---+--+-+-------++---+-++--+--+++-+--++-++++--+-----+++--+++--++--++----+++---++++---++--++--+-+----+-+-+-+-+--+++-++-++-----+---+-----+----+-+---++++-+-+-+-++--+---++--
Running 200 games:
+-++-++++++++-+---+--+--+-----+++-++++-----++-+-+---+-------+-+++----+-+++--+-------++-++--+++-++-+++---+---+---+---+--+-+++-++-----++-+-+++++-+-----+--++++--+--+---+-+++--++---++++--++-++----+-+++-++-+----+---++-+++
Your agent won 46.8% of matches against Minimax Agent

depth=2

baseline

Running 200 games:
-+-+----++-+++-+---+----+--+-------+-+----+++++-+-+-++---+---+------++-++----+-+-+++--++----++---+-+--+------++---+-+--+-++-++----++---+--+-++--++++----+------+--++---+------+-+-+-+-++-++--++-++++--++-+++--+++++
Running 200 games:
--+--+--+-++--+-+----+--+-----+--+----------+-++-+---+-++--+-+-------+--+-++-++-+-+-+---+------++------+-+-++---+-----+-+-+-+-+---+-+--+---+++-+-+++------+----+----+++-----------++++-+----+---------+-++-++++-+--
Your agent won 37.8% of matches against Minimax Agent

depth=3

baseline

Running 200 games:
+-++-+----++++++++--++---++++-----+++-++++---+++++++-+---+--+-----+-++-++-+-+++++++++++--++++-+++-+-++--+---+---++++++---+--++++-++++-++--+++--++-+----++--+++---+-+++-----+--+--+-++---+++++-+---+--++-+--+-++++-+++--++
Running 200 games:
-+-+-+++--------++-+++---++--+++++++-+----+++---------+++-++-++++---+--+-+-++----------+-++------+---++-+-++----++-+-++++----+----+---+++----+--+-++++-+---+++--++---+++-++-++-+-+++---+-+++++--+++-++----+----++----
Your agent won 50.0% of matches against Minimax Agent

depth=4

baseline

Running 200 games:
--+---++---+++---+---+++----++-++++--+--+-+++++-++--+--+++-++-++-++--+-+++---+---+++-----+---+-+++-----+------++--++--++---+-++++----+--+++++-+++---+-----++++---++--+---++---+++++++++-++-+-+++++-+++++-----+-+-+--
Running 200 games:
+++++++-++++-+----+++++-+++--++++++-+---+++----++-++--+-----+++++-+-----+++-----+-++++--++++-+---+-+-++-++-+--+-+-+++++-+++-++--+----+--++--+++-++++---+--+++--+--++---+-++--+--++++-++-+-+-+-+-+++++++-+----++----+-
Your agent won 52.0% of matches against Minimax Agent

depth=5

baseline

Running 200 games:
--+-+---++---+-----++-++++++---+--++-+++-+-++-+++--+++++++++-++---++----+++----+++++-------++-+----+++--++++--++-++--+++-+-+++-+-++--+++-+---+-++++--+-++++-+++-+-++-++++-+----++-+++-+-----++++-++---++++--+--+-+++-++
Running 200 games:
-----+++-++-++-++++--+-+--------+-+-+-++-+-++-+++-++++++++--+-+++--+-+----+--+-+---+--++-++-+--++--+--+++-+----+---+++++-+--++--+--+-+++++-++++++-+++----+-+-+---+++-++++++-++-----+---+-++--++++--+-+--+--++--++-+---
Your agent won 52.5% of matches against Minimax Agent

depth=6

baseline

Running 160 games:
+-+--+-++++++++++--+++-+-++++-++---+--+--++++++++++-+----+--++----++++-++-++++--++--++-++-+++++-+----++--++++----++++--++-+-++++--+-+---++-++-++----+-+-++-+++++--+++-+---
Running 160 games:
+++--++-++-+++-----+----+-+---+-+++--+-+++++--+----++++++-+-++++-++++++++++++++----+-----+----++-++-++++-+-++-+--++-+++++---+-+++--+++-+-+-++++---+---+-+---+++--+--------+
Your agent won 55.6% of matches against Minimax Agent

offensive_to_defensive

Running 150 games:
-+---++++--+-++-+-++++-+++-+++++-+++----++----++-+++-++----++-++-+-+++-++-+--+-+-++--+-+--+-++++--++--++++--+-++--+--+-+-++-+++--++-+-++-++++-+++---++++-
Running 150 games:
-+--+--++---+++-++-++-+----++++-+---+-++-+++++-+----+------+++-+++-++-++--+---+++++++++++----+--+-+-+---+-++++-+++-++++++++-+++++-++++--+++++++++++--+--+-+-
Your agent won 58.0% of matches against Minimax Agent