Hex - Creating Intelligent Adversaries (Part 2: Heuristics & Dijkstra’s Algorithm)

Demystifying AI Game Opponents

In today’s article, we are going to dive deeper into the creation of an intelligent opponent in the game of Hex. In Part 1 of the Hex series, we’ve covered the α-β Pruned Minimax algorithm, which we have used to find optimal moves. However, in order to make use of the Minimax algorithm, we have to be able to properly evaluate every board state. We are going to do this with heuristic functions that will be the main focus of this article.

If you haven’t seen Part 1 of the Hex series, feel free to check it now.

Heuristics

In computer science, artificial intelligence, and mathematical optimization, a heuristic (from Greek εὑρίσκω “I find, discover”) is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.

tl;dr A heuristic is an approximation of the exact solution.

To get a better understanding of the idea behind the heuristic functions, let’s build an example application.

Our app’s goal would be to find the closest city where we can get to watch a live NBA game.

It would take our location as an input, and yield a city’s name as an output.

Sounds simple, right?

Assuming that you know the coordinates of all cities with the NBA teams, how would you create such a system?

Let’s find the closest NBA city from San Francisco.

Scanning all roads in the country to get the exact paths would be very difficult and time-consuming.

This is a situation where a heuristic function may come in handy. Instead of giving exact solutions, let’s approximate one.

One of the easiest ways to approximate the driving distance between the two places is to use ‘as the crow flies’ distance, which is simply a straight line between the two spots.

Approximation of the distances between San Francisco and Oakland (Golden State Warriors) / Sacramento (Sacramento Kings)

Our heuristic function would yield Oakland (Golden State Warriors) as a San Francisco’s closest NBA city. It would derive it by calculating straight-line distances to the all NBA cities and picking the one with the smallest value.

While it may not work 100% of times, it would probably be sufficient in the vast majority of the cases and what’s most importantly, it will be very easy and fast to compute.

Knowing basic principles behind the heuristic functions, let’s go back to our Hex AI opponent.

Evaluating Board States

Heuristic function

In the previous part of the Hex series, I left you with a question of how to evaluate a board state like the following.

Example board state

In order to come up with a good idea for a heuristic function, let’s ask ourselves a question.

What is the goal of the game?

The goal of the game is to create an unbroken chain of hexes that connect the opposing sides of the board.

Knowing that, let’s take it one step further.

If our goal is to create unbroken chains of hexes, maybe it would be a good idea to calculate the shortest paths of them between the opposing board sides?

Let’s draw them and find out.

Before we come up with a way to compute such paths, let’s check this approach makes sense in the first place and verify if it’s a step towards a good heuristic function.

This is the part where we need to apply some domain/expert knowledge.

In the above example, the Blue player (human) clearly has an advantage and is way closer to winning than the Red player (computer). In order to finish, he needs only 3 hexes, while the Red player needs 6 of them.

Assuming that we are going to compute heuristic functions from the Red player’s maximizing perspective, our heuristic function can look like the following

or simply

heuristic_score = remaining_blue_hexes-remaining_red_hexes

In the above example, the heuristic score for a current board state would be

-3 = 3 - 6

which totally makes sense because Red player is clearly losing.

With an above heuristic function, we are able to evaluate every board state, thus we can leverage Minimax algorithm (computer as a maximizing player) to compute optimal moves.

Okay, our heuristic function looks promising, but how can we compute the necessary shortest paths in the first place?

Dijkstra’s Shortest Path

In order to compute the shortest paths between the hexes on a board, we are going to use the Dijsktra’s algorithm.

But before we proceed with this algorithm, we need to come up with a graph representation of our Hex board.

You may ask now, what’s the purpose of these outer hexes?

Dijkstra’s algorithm works by finding the shortest path between specific nodes (in fact only the starting node needs to be specified, but for the sake of simplicity we’ll specify the end node as well) in a graph and because we have ‘sides’ of hexes instead of the specific ones, we need the outside nodes to represent this.

Blue’s goal is to connect L (left) with R (right) and Red’s goal is to connect T (top) with D (down).

Hexes are represented as follows.

05 15 25 35 45 5504 14 24 34 44 5403 13 23 33 43 5302 12 22 32 42 5201 11 21 31 41 5100 10 20 30 40 50 L R T D

Each Hex has an associated position (x and y coordinates) so we can easily derive its neighbors.

With an above graph representation, we can proceed with the Dijkstra’s algorithm.

To keep things simple, Dijkstra’s algorithm works by visiting all available nodes, checking its neighbors and for each node, storing information about the minimum traveled nodes/distances from start.

We are keeping such information inside each Hex object in pathLengthFromStart and pathVerticesFromStart variables.

Take a look at the following animation that illustrates this mechanism (blue numbers reflect pathLengthFromStart variable).

And finally, take a look at my swift implementation of the Dijkstra’s algorithm.

Line 9

We call getShortestPathFrom function twice for every AI move. In order to compute a heuristic score, we need to check the shortest path for both human and computer player.

Lines 22–26

We clear vertices states that may be cached after previous iterations.

Line 27

For every vertex in a graph.

Lines 29–30

We need to make sure that we check each vertex only once and that we check only unoccupied vertices or ours.

filter { $0.value == .undefined || $0.value == perspective }

Line 31

For every eligible neighbor.

Lines 32–38

We update pathLengthFromStart and corresponding pathVerticesFromStart with new values if pathLengthFromStart is lower than the current one. Connections between same value hexes are weighted as 0 and connections between gray unoccupied hexes and color hexes are weighted as 1.

Lines 40–44

If there are no more vertices to check we return or we select the one with the lowest pathLengthFromStart.

After running the above algorithm, we’ll end up with each Hex updated with the minimum pathLengthFromStart and optimal pathVerticesFromStart.

Finally, we can return our shortest path with the following call.

Besides using above shortest path mechanism for a heuristic function, we can also use it to help human players visualizing the optimal solutions.

What’s next?

Combining Minimax with Dijkstra driven heuristic function proved to be a very powerful way of creating challenging AI opponent. Even though, heuristics usually require some domain knowledge, the underlying principles behind them can be generalized and used in other games or applications. Feel free to leverage concepts presented in the Hex series and apply it to your apps. I am looking forward to seeing your results!

Questions? Comments? Feel free to leave your feedback in the comments section or contact me directly at https://gsurma.github.io.

And don’t forget to 👏 if you enjoyed this article 🙂.