Search algorithmsCTRL K
Play tic-tac-toe against minimax
· the engine's search tree drawn while it thinks/signatures/tic-tac-toebuilt on Alpha-beta pruningNODES SEARCHED
—
for the engine's last moveCUTOFFS
—
branches alpha-beta skippedCANDIDATES
—
moves scoredPLIES LEFT
9
empty cellsFORECAST
—
with best play from herebeing scoredchosen · best replyXcandidate—
step 0 / 0
Your turn (X)you are X
MOVES—
CURRENT STEP
Your turn (X)
Play tic-tac-toe against minimax
Tic-tac-toe is small enough to search to the end: from the empty board there are 255,168 possible games. Minimax assumes you will answer every move with your best reply and picks the move whose worst case is best; alpha-beta reaches the same answer while skipping branches that cannot change it.
The tree on the stage is the top of that search: the engine's candidate moves with their exact values (a win in fewer moves scores higher), then, under the move it picked, your possible replies and what each one leads to. The engine cannot lose; the best you can do is draw.
What to notice
The first move searches over a hundred thousand nodes, every candidate and every reply to it played to the end; by the fourth move it is a few hundred: the tree shrinks with every ply.
Cutoffs count the branches alpha-beta never expanded; without pruning the node count would be several times larger.
All nine opening moves score 0, so the tie-break decides: the engine counts traps, the replies that would lose for you, and opens in a corner because seven of your eight answers lose there; the centre leaves only four.