Learn A* (A-star) Algorithm in Python — Code An AI to Play a Game

In this article, we are going to discuss a planning algorithm that’s still used widely in the industry (eg in robotics), has great theoretical guarantees, and can be used as a baseline for many other more complex algorithms (ie reinforcement learning). Say hello to A* :)

(Pss — My video version of this article is now available on youtube)

Simply put, A* is an algorithm for finding the shortest path between some start node and end node.

A* Application Examples

A node can represent states, like states in a game, with the end-state being the winning state. The edges between the nodes represent the moves between the nodes (game states). Together, the nodes and edges make a graph. In this case, A* applied to this graph would find the quickest way to win in the least amount of moves.

A node could also be an intersection in Manhatten (like a 2d Cartesian grid). And the edges could be the roads between each intersection. Our house might be located at point (0,0) and the grocery store at node/coordinate (10,10). In this case, A* would be like google maps and find the min distance route for us to get to the grocery store. Nice!

What A* Does

A* can find the min cost path fast because it has the help of a little thing called a heuristic. A heuristic *is not* the thing we are trying to minimize but rather it gives us a hint of which where…