Algorithms and games
Pathfinding
Five grid search algorithms side by side on walls you draw. The search […]
HEX
The connection game with no draws, against an AI whose search you can watch. First written in C as a command line game, rebuilt for this page in TypeScript.
Live demo
Loading the demo…
Algorithms
- 01Alpha-beta search →Minimax with pruning: a branch is dropped as soon as it cannot change the best move, so the AI looks deeper for the same effort.
- 02Shortest connection (0-1 BFS) →The evaluation. For each side, the number of stones still needed to join its two edges, where own stones cost 0 and empty cells cost 1.
- 03Move ordering and candidate pruningOnly cells near existing stones are tried, best first by the evaluation, so alpha-beta cuts earlier.
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
- 01HEX is a game with no draws: on a board of hexagons, one player links the top and bottom edges, the other links left and right, and exactly one of them will manage it.
- 02To judge a position the AI measures, for each side, the cheapest chain still missing to connect its edges. Your own stones are free, empty cells cost one and enemy stones block, so this is a shortest-path problem. It prefers moves that lengthen your path and shorten its own.
- 03Raise the depth to make it think further ahead, and watch how many positions it examines. Alpha-beta pruning is why that number stays small.
More in this category
Algorithms and games
Tic-tac-toe
A tic-tac-toe opponent that cannot be beaten, built on minimax with […]
Algorithms and games
Othello
Outflank and flip your opponent’s discs, against an AI you can switch […]