Text & documents
Numbers & maths
Data & formats
Security
Development & DevOps
Artificial Intelligence
Finance
Health & Wellness
Productivity
Games & Entertainment
Multimedia & design
Business
How to use
How to use it

Press Play and watch the algorithm search: light blue is what it has already looked at (expanded), yellow is what it still has pending (the frontier) and, at the end, blue is the path. Paint walls or mud by dragging over the grid, and move the start and the goal.

How they differ

They all do the same thing: take a cell out of the frontier, expand it and add its neighbours. The only difference is WHICH one they take. Breadth-first, the oldest (fewest steps). Depth-first, the newest (finds something, rarely the best). Uniform cost, the cheapest so far (the cheapest path). Greedy, the one that looks closest to the goal (fast, but easily fooled). A*, the one that adds what was spent and what seems to be left: the cheapest path while looking at less.

Sticks and Nim: fully solved games

In the Game tab, sticks and Nim are so small that the machine solves them completely: it knows from the start who wins with perfect play. The tree shows, for each position, who wins from it; and the search ends up finding the same rule a human can learn (the multiples of 4 in sticks, the nim sum in Nim). Note the difference between the nodes of the tree (millions) and the different positions (just a few): remembering what has already been solved, a transposition table, is what makes it instant.

Checkers and chess: how real engines look at less

In checkers, each machine move is measured five times at the same depth: without pruning, with pruning, with move ordering, with a transposition table and with all three. The value is the same; the positions looked at are not. In small chess, the lesson is the horizon effect: if the search stops in the middle of an exchange, the machine thinks it wins what it has just taken. Quiescence search keeps looking at captures until the position is quiet; you can turn it off and compare what it would have played.

Hex and Monte Carlo Tree Search

Hex does not fit in minimax: there are too many positions and a good heuristic is hard to write. MCTS does not need one: to rate a move, it plays many random games from it and counts how many it wins. UCT decides which move gets the next game, balancing the ones that are winning with the ones barely tried. With more games it plays better, and it is the basis of the programs that beat humans at Go (AlphaGo and AlphaZero added a neural network that guides the search).

Portals and one-way cells

A portal takes you to its pair (they are paired in order). With portals, the Manhattan distance is no longer a bound on what remains: there may be a «magic» shortcut. A* no longer guarantees the cheapest path, because its heuristic is no longer admissible, and in the example it returns 19 when there is one of 10. A one-way cell only lets you leave in the direction of its arrow: the map becomes a directed graph, and being able to go from A to B does not mean you can come back.

The weight in A*

With weight 1, A* always gives the cheapest path, because the straight-line (Manhattan) distance never overestimates what is really left. Raising it makes A* trust that estimate more: it looks at fewer cells, but may stop giving the best path. With a very high weight it behaves like greedy.

Search: paths and gamesHow an AI searches: breadth-first, A* and minimax, step by step
Search: paths and gamesHow an AI searches: breadth-first, A* and minimax, step by step

Takes the one with the lowest sum of what was spent and what seems to be left (g + weight·h). With weight 1, the cheapest path while looking at fewer cells.

Going over something already painted with the same brush erases it.

0 expanded · 1 in the frontier

Press Play to watch the search, or «To the end» for the result at once.

All five on this same grid
AlgorithmExpandedStepsCost
10318 18
2120 20
10318 18
3120 20
6218 18