Proving Always Wins

• One adversarial game is four across (connect 4).
• It's a 7 row 6 column game, like tic tac toe, but you need to get 4 in a row.
• How many options do you have at each ply?
• How many states are there?
• Can you use these techniques to prove that some games are always winnable?
• Yes, they've used these techniques to prove that connect four is always winnable.
• If the first person starts in the middle, he can always win.
• Just expand the minimax tree fully, and it comes to 1 middle, 0 (draw) 3 or 5, -1 (loss) 1,2,6,7.
• You can't do that at run time, but you can do it over a few days.
• The UCI benchmark has connect 4 boards classified as win, lose or draw.
• Now, can you write a game that always wins?