Search and Game AI: A* and Minimax in Python

The concept in plain words

Classical AI solves problems by searching through possible states. A* finds the cheapest path by adding the cost so far to a guess of the cost left, and minimax chooses moves in two-player games by assuming the opponent plays well.

Find the shortest path on a grid with A* search and pick the best move in a game with minimax.

Key ideas

A* finds the best path when the guess (heuristic) never overestimates the real cost.
Minimax explores the game tree to a fixed depth or to the end of the game.
Alpha-beta pruning skips branches that cannot change the decision.
Genetic algorithms search differently: they evolve a population of candidate solutions.

When should you use it?

Understand what happens inside neural networks and AI libraries.
Learn the idea before you implement it in the matching challenges.
Prepare for machine learning courses, interviews and projects.

See it in action

Press Play to watch A* explore the grid; click cells to add or remove walls. In the game tree, click a leaf to change its score.

Example code

Run code →

main.py

import heapq

# A* finds the cheapest path using cost so far + a guess of the cost left.
grid = ["S..#",
        ".#..",
        "...G"]
start, goal = (0, 0), (2, 3)
guess = lambda r, c: abs(r - goal[0]) + abs(c - goal[1])   # Manhattan distance

frontier = [(guess(*start), 0, start, [start])]
seen = set()
while frontier:
    _, cost, (r, c), path = heapq.heappop(frontier)
    if (r, c) == goal:
        print("path:", path, "cost:", cost)
        break
    if (r, c) in seen:
        continue
    seen.add((r, c))
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 4 and grid[nr][nc] != "#":
            heapq.heappush(frontier, (cost + 1 + guess(nr, nc), cost + 1, (nr, nc), path + [(nr, nc)]))

# Minimax: the maximizer assumes the opponent always picks the worst for it.
def minimax(node, maximizing):
    if isinstance(node, int):
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)

tree = [[3, 5], [2, 9], [0, 7]]   # our move, then the opponent's reply
print("best guaranteed score:", minimax(tree, True))

Expected output

path: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] cost: 5
best guaranteed score: 3

How it works

The priority queue always expands the cell with the smallest cost + guess, where the guess is the Manhattan distance to the goal, so A* reaches G in 5 steps around the walls. minimax() takes the maximum on our turn and the minimum on the opponent's turn; the first move guarantees 3, the best of the three worst cases.

Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.

Practice exercises

Modify the runnable example with the exercises below to build understanding beyond copying the result.

Change the inputs or weights and predict the output before running.
Print the intermediate values to follow each step of the calculation.
Solve the linked challenges below to implement the idea yourself.

Run in Python IDE →

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges