Introduction

Artificial Intelligence can be developed to play games using premade strategies. For deterministic games, this can be implemented using basic search trees. The problem becomes even more trivial if the game is a turn based game. Using strategies like minimax, one could in theory evaluate every possible game-state and determine if they can win the game or not. This can allow the player to force certain outcomes that can help them win the game in nearly all cases.

Isolation is a game in which there are two players, each with their own game piece, and a 7-by-7 grid of squares. At the beginning of the game, the first player places their piece on any square. The second player follows suit, and places their piece on any one of the available squares. From that point on, the players alternate turns moving their piece like a queen in chess (any number of open squares vertically, horizontally, or diagonally). When the piece is moved, the square that was previously occupied is blocked, and cannot be used for the remainder of the game. The first player who is unable to move their queen loses.

Live Demo Github repository

Goals

In a variant called the Skid Isolation, each player leaves behind traces when they move their queen. We say the piece/queen "skids", and as a result the skid places a permanent block in the previously occupied block and the block "just before" the player's current position and the block "just after" the player's previous position. The opponent cannot move on or through squares blocked by this skid.

The goal of the project is to successfully make an AI agent that can perform optimal moves that guarantee a winning strategy in as less time as possible.

Work Done

In deterministic turn-based games like Skid-Isolation, achieving optimal AI gameplay involves conducting a graph tree search to explore potential future paths. This process entails examining all feasible moves for both the player and the opponent, aiming to identify the winning strategy. However, due to the exponential growth of the decision tree—particularly considering an average of 10 moves per player and a game duration of around 30 moves—it becomes computationally intensive to explore all possibilities within a limited timeframe.

To address this computational challenge, an AI agent typically searches only to a predetermined depth within the decision tree. As many games may not reach an end state within this depth, a heuristic function is crucial for evaluating leaf nodes. This function, ranging from complex considerations of game state to simpler metrics like available tiles, assists in making informed decisions based on relevant information.

To further refine the decision-making process, scoring is applied to leaf nodes, prioritizing paths that lead to confirmed wins or losses. The minimax strategy is employed, maximizing scores during the agent's turn and minimizing scores during the opponent's turn. To optimize computing resources, alpha-beta pruning is implemented, allowing the agent to skip unnecessary exploration of certain nodes when a decisive outcome is confirmed.

To enhance efficiency, additional techniques, such as iterative deepening, are employed. Iterative deepening incrementally increases the depth of the tree exploration until the time limit is reached, allowing the AI to utilize available time effectively and derive the best possible move by thoroughly exploring various leaf node combinations.

Results

The agent was developed to use an iterative deepening minimax algorithm with alpha-beta pruning. Heuristic function used was (number of moves available for the player - number of moves available for the opponent). It was tested against other agents with different levels of strategies.

The agent was able to complete its moves within 2 seconds of time and it was able to defeat other agents which searched the game tree till a depth of 8 moves more than 70% of the time. This could have been improved further using a special dictionary for end game states and start game sets. But the goal of this project was to make an agent without storing game states in memory. For which, the agent seemed to perform pretty well.

Introduction

Goals

Work Done

Results

Contact me!

Linkedin

Github