Algorithms and games
Pathfinding
Five grid search algorithms side by side on walls you draw. The search […]
Tic-tac-toe
A tic-tac-toe opponent that cannot be beaten, built on minimax with alpha-beta pruning.
Live demo
Loading the demo…
Algorithms
- 01Minimax with alpha-beta pruning →The opponent explores every continuation and drops branches that cannot change the best move.
Algorithm pages
Each of these has a page of its own, with the steps, the cost and the other places it is used.
How it works
- 01The AI explores every possible continuation of the game, scoring a win, a draw or a loss at the end of each, and picks the move that leads to the best result against a perfect opponent. That is minimax.
- 02Alpha-beta pruning drops branches that cannot change the best move, so it plays the same move after looking at far fewer positions. Turn on the scores to see what the AI sees, and switch between plain minimax and alpha-beta to compare.