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.

Hex - Creating Intelligent Opponents with Minimax AI (Part 1: α-β Pruning)

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…