Penney's game [as described in Knuth's Croncrete Math]

It's not as symmetric as it looks at first. Proving the optimality of the advertised strategy can be done with finite automata.