One day, my father, an amateur programmer, sent me a sample of his code for the logic of a simple Tic-Tac-Toe application. I'm sorry to say, it befit an amateur; it had different local variable for every board position, haphazard logic for a computer player thrown together as a series of if statements, a single main function, and so on. I tried to point out some of these problems, and suggested he use something like the minimax algorithm for his computer opponent. His response was
Eight variables are not many if one wants to make a game that can not be won. It is easy to use a "for" loop if you just want a game. I want a game that people like you have to sweat over. I challenge you $100 to make a Tic-Tac-Toe game that can not be won with only one variable and a "for" loop.
This was, of course, a challenge I couldn't refuse.
After thinking about this for a while, I decided I could do even better: I could write a Tic-Tac-Toe game that always wins without any loops, variables, or function calls, other than I/O, by simply using a huge series of nested switch statements representing the game tree, anticipating all possible moves beforehand, effectively encoding the game state in the program counter. Tic-Tac-Toe has a small enough game tree that this seemed feasible. However, writing it by hand was not.
Because of this I wrote another C++ program (which you can see here) which used the minimax algorithm and some auxiliary code, not to play Tic-Tac-Toe itself, but to emit this loopless C++ program that plays Tic-Tac-Toe. Because it used minimax, and could generate the whole game tree, it was infallible; the computer must always win.
The generated source file (which you can see here) is 8,587 lines long, has only one function
(main()), uses no variables or indention, and contains
switches nested up to 5 levels, the maximum number of turns the player
can take in Tic-Tac-Toe. Each of the switches follows a different
code path depending on a number input by the player giving their move,
and error checking is done on the input (note that the game must exit
given bad input, since it can't loop back). Every board position is
hardcoded. If you don't believe the generator's minimax algorithm
always wins, you'll believe it when you attempt to search this source
file for "You win", the message shown when a player wins. It simply
isn't there.
I compiled it with gcc, optimizing for size, and
produced a 150k binary. When I ran it, it seemed to work great.
Although occasionally it would do something odd, like give up an
immediate win in favor of forcing a win a few turns away, it was quite
effective at slaughtering whoever was put against it.
Unfortunately, when I sent the code to my dad, and he attempted to compile it in Visual C++ 6.0 on Windows, the compiler crashed with a mysterious message about running out of internal stack space. Eventually, we figured out that adding certain flags would fix this, but then the linker crashed, giving only an unexplained internal error. My dad, who thought my ISO standard C++ code wasn't portable because of this, refused to concede that I had won the bet. Oh well.