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..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 StatesHeuristic functionIn 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 stateIn 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 followingor simplyheuristic_score = remaining_blue_hexes-remaining_red_hexesIn the above example, the heuristic score for a current board state would be-3 = 3 – 6which 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 PathIn 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 DEach 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 9We call getShortestPathFrom function twice for every AI move.. More details