0-1 breadth-first search
How many more stones does this player need to finish a connection?
A shortest-path search for graphs whose steps cost either 0 or 1, using cost buckets instead of a heap. HEX uses it to count the stones a player still needs.
When every step costs 0 or 1, Dijkstra’s heap is overkill. A double-ended queue does the job: a step that costs 0 goes to the front, because it is as cheap as the cell being left, and a step that costs 1 goes to the back. The queue stays ordered by cost, so cells come out in the right order in time proportional to the board. The version in the demo is the same idea with one list per cost value.
In HEX, a player’s own stones cost 0 to cross, an empty cell costs 1 (a stone still to be placed) and the opponent’s stones are walls. The cheapest path from one of that player’s edges to the other is the number of stones the player still needs.
That number is the evaluation function for the alpha-beta search: the AI prefers positions where its own distance is short and yours is long.
- 01Start from every cell on the player’s first edge: cost 0 if it holds the player’s stone, cost 1 if empty, skipped if it holds the opponent’s.
- 02Take the cheapest cell from the queue.
- 03If it is on the player’s opposite edge, its cost is the answer.
- 04For each neighbour that is not an opponent stone, the step costs 0 if it is the player’s stone and 1 if empty. If that lowers its recorded cost, record it and queue it at the matching end.
- 05If the queue runs out, the player can no longer connect.
function zero_one_bfs(starts, is_target):
dist = {}
deque = []
for s in starts:
dist[s] = step_cost(s) # 0 for my stone, 1 for an empty cell
deque.push_back(s)
while deque is not empty:
cell = deque.pop_front()
if is_target(cell): return dist[cell]
for n in neighbours(cell):
if is_opponent(n): continue
w = step_cost(n) # 0 or 1
if dist[cell] + w < dist.get(n, infinity):
dist[n] = dist[cell] + w
if w == 0: deque.push_front(n)
else: deque.push_back(n)
return infinityLinear in the size of the board, which matters because the evaluation runs on every position the search visits.
- Linear time, no heap.
- Gives an evaluation that has a meaning: stones still to place.
- Works for any graph with 0 and 1 costs.
- Only for costs of 0 and 1.
- Counts stones, not threats, so it cannot see that two routes can protect each other.
- Run once per position, so it has to be fast.
- 01HEXMeasures, for each side, the stones still needed to join its two edges. The AI’s move is the one that leaves your distance long and its own short.