A 100 by 100 tic-tac-toe: why you check only four lines

transcript

A hundred by a hundred board. Five in a row wins. Someone just moved. Did they win? Do you scan all ten thousand cells, after every single move? There is a far smaller question to ask.

Scan the whole board: ten thousand reads. Every single move. A game of fifty moves is half a million reads. For tic-tac-toe. Check only the lines through the move: thirty-two reads.

Why is that safe? The game wasn't won before this move. So any new win must contain the new mark. Through one cell pass four lines. Row, column, two diagonals.

Walk out from the move on each line. Stop at a gap or the edge. At most four steps each way, for five in a row. Four lines, two ways, four steps. Thirty-two reads. Make the board a thousand wide. Still thirty-two. Size stops mattering.

Don't scan the board. Check the lines through the move. Say that sentence in the interview, and you have the whole insight.

Full breakdown in the lecture.