nim
the oldest solved game. the computer knows how to win it. by the end, so will you.
already know the trick? open every step
piles of stones. on your turn, pick one pile and take as many stones from it as you like, at least one. then the computer does the same. whoever takes the last stone wins.
click a stone to take it and every stone to its right. the computer never makes a mistake. you move first, and every game here starts from a position you can win.
two piles
start small. two piles, 3 and 5. you move first. find a way to beat it.
you made the piles equal, then copied: whatever it took from one pile, you took from the other. you always had a reply, so the computer was the one who ran out. equal piles are a lost position for whoever has to move next.
no two alike
three piles: 1, 2 and 3. no two are equal. this time the computer moves first.
the computer moved first from 1, 2, 3 and lost, so 1, 2, 3 is a lost position too, like equal piles. but no two piles were equal. what do they share?
write them in binary. binary writes a number as a sum of 4, 2 and 1, each used at most once: 3 = 2 + 1, so 3 is 011. now count the 1s in each column:
every column has an even number of 1s. equal piles have identical digits, so their columns are even too. that's the whole pattern. call a position even when every column has an even number of 1s. whoever has to move from an even position is losing.
the rule
the binary is showing now. the bottom row counts the 1s in each column: green when even, yellow when odd. your goal: after every move you make, the whole row is green.
why it works
charles bouton proved this in 1901. here is his argument, in the words of this page. the notes under each step are moves you made.
the part that surprised me
nim isn't one game. in the 1930s roland sprague and patrick grundy proved that every game like it, where both players have the same moves available and the game has to end, plays exactly like a single nim pile of some size.
here's one you can use tonight. if each turn you may take only 1, 2 or 3 stones from a pile, a pile of n stones plays like a nim pile of n mod 4, the remainder when you divide by 4. with one pile that means: leave your opponent a multiple of 4, and they can never win. with several piles, turn each into its remainder and use the column rule you just learned.
every game in the family has a number like that. finding it is the only hard part.