Graph Theory37 sections · 1633 units
Open in Course

Distance to Win

(BFS from terminals)

Sometimes you want to know not who wins, but how quickly. The distance to win is the minimum number of moves to force a win. Compute this using BFS at terminal positions. The distance to a terminal position is 00. For other positions, the distance is 11 plus the minimum distance of any losing successor.

This helps when you have multiple winning moves and want to pick the fastest one. When multiple winning moves exist, choosing the path with minimum distance forces the win in fewer steps. This matters in timed games or when you want to minimize opponent options.