[math-fun] tic-tac-toe & qubic
I recall seeing both 3^3 and 4^3 TicTacToe c. 1955. The 4^3 game was played with circular tokens - skinny checkers - on a board with 4 transparent plastic levels, separated by spindly legs. It was called Qubic. The 3^3 game was played on a foldable wire frame, using colored wooden beads with holes, as for making a necklace. The 3^3 game had more complicated rules -- maybe you had to make two connected lines (?) -- probably you couldn't start in the center. There were three colors of beads for a three-person game. Of course plain 3^3 TTT is an easy first player win. For 4^3, around 1980, Oren Patashnik showed a first player win. It was based on a table of 2900 key positions, where he specified the winning move. Non-table positions have a forcing sequence to complete the win. He took a job as a PDP10 night shift operator, and used a year of background computer time to do the necessary searches. When his program got stuck, he would figure out a winning move and add the position to the table. His result wasn't widely known; as late as 1985, Qubic was one of the games played in a British computer games tournament, where programs competed against each other. In contrast to most computer games (which tend to be acquired tastes), Qubic is fun to play. It might even be appropriate for bright seven year olds. I've done some work on TicTacToe, exhibiting drawing strategies for various sizes of game (or proving existence). I've shown N^3 TicTacToe is drawn for N >= 7; N^4 is drawn for N >= 11; N^5 is drawn for N >= 14; ... N^D is drawn for N >= 3 D - (D mod 2) (and D>=3). Most of these are based on fancy weighting & counting arguments to show the existence of a simple pairing strategy draw: each possible winning line contains two paired cells, and if X plays in one cell, O takes the other. The 7^3 has too many lines (193) for this to work. Instead, I have an explicit ad hoc blocking strategy. The game group is special when either D=1 or N<=2. In the non-special case, the groups are the same for (2N)^D and (2N+1)^D. Proving the group is hard: Exhibiting and checking the generators is easy enough, but showing no other elements is tricky. Rich rcs@cs.arizona.edu
participants (2)
-
Jud McCranie -
Richard Schroeppel