Artificial Intelligence Nanodegree: Game Playing Agent

The purpose of this project is to design and implement a game playing agent to play a game using adversarial search methods. The goal is to create a game playing agent that defeats our opponent at a game of isolation consistently. For this project I’ve designed three heuristics to create an effective edge for the game playing agent. Don’t know what Isolation is? Check out out this page: isolation.secdevops.ai and compete against my agent.

Minimax

In the case of the game isolation, there are two players competing against each other. We are under the assumption that the AI player and human player are both playing two win. While back-propagating through the search tree, our algorithm must maximize the outcome (choose the optimal move) for when it’s the AI’s turn and minimize the outcome (choose the least optimal move for us) when it’s the human player’s turn.

Image from http://cs.lmu.edu/~ray/images/minimax.png

Observe the bottom-left portion of the search tree — the bottom nodes are maximizing nodes. Maximizing nodes select the highest value (most optimal outcome). As you may guess, minimizing nodes select the lowest value (least optimal outcome). Imagine that you are playing a game of chess, each move you make is a maximizing node (your intention is to win) — and every move your opponent makes is a minimizing node (move that messes up your game 😞).

Iterative Deepening

Thus far in the Nanodegree we’ve been exploring search algorithms that enable us to brute force winning outcomes based on a specific game state. Some games have a very large game-state space (same is true for isolation game) — which would make traditional depth-first search an inefficient solution to find a winning outcome. In some cases, we may want to search each possible outcome of a game move while returning an optimal next move in a reasonable time. That’s where iterative deepening comes into play. With iterative deepening, you define the minimum search depth; if time persists, another depth will be explored.

The above image is an example of depth-first search iteratively checking each depth until goal state is reached.

Evaluation Functions

Once the minimum search depth is reached, we must evaluate each node and provide a score. For example, an evaluation function could be the number of moves a player has available — The below figure shows an example search tree with the number of moves available in each game state.

For this project I’ve designed and implemented three evaluation functions.

Evaluation Function 1 (Good)

num_of_my_moves - 2 * num_of_opponent_moves

Evaluation Function 2 (Worst)

num_of_blank_spaces / 2 + 2 * num_of_my_moves

Evaluation Function 3 (Best)

(num_of_my_moves - 2 * num_of_opponent_moves) + (num_of_blank_spaces / 2 + 2 * num_of_my_moves) / 13

AlphaBeta Pruning

AlphaBeta Pruning is an amazing AI technique I was introduced to during this project. This pruning technique allows us to ignore entire sections of a search tree while reaching the same outcome as minimax. For the sake of accuracy, I’m pasting in the video that helped me with this concept the most:

Conclusion

This project was an excellent introduction into creating game playing agents. At the conclusion of this project, I created a React web application that allows a player to compete against my game playing agent — Check it out here isolation.secdevops.ai or checkout my code on Github.