When the world fights back
Route finding is search in a world that holds still. In a game, an opponent moves too, and wants the opposite of what you want. In 1997 IBM's Deep Blue beat world chess champion Garry Kasparov using the ideas in this lesson, searching over 100 million positions a second. In 2016 AlphaGo beat Lee Sedol at Go by adding learned evaluation to search.
Tic-tac-toe is small enough to search completely: there are 255,168 possible games. You'll write a player that searches all of them — it never loses — and then make it about thirty times faster without changing a single decision.
Minimax
Give finished games a value from X's point of view: +1 if X won, −1 if O won, 0 for a draw. For an unfinished board, X will choose the move with the highest value and O the move with the lowest. Apply that rule recursively from every leaf back up to the current board and you get its minimax value — the result if both sides play perfectly.
if (toMove(board) === "X") {
let value = -Infinity;
for (const i of moves(board))
value = Math.max(value, minimax(play(board, i)));
return value;
}
// O does the same with Math.min and +InfinityThe empty board's value is 0: tic-tac-toe is a draw with perfect play. That's why children stop playing it once they've worked out the strategy.