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

Demystifying AI Game Opponents

Greg Surma

--

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.

--

--