Tic-Tac-Toe, also known as “Noughts and Crosses” or “Xs and Os” is a simple[1] strategy game that has repeatedly appeared in computer history. The System Source Computer Museum has a new exhibit highlighting a few Tic Tac Toe machines.
- There are dozens of web pages devoted to analyzing the complexity of Tic-Tac-Toe. Here is a summary: Upper bound is 9!=362,880 9 possibilities for the first move, 8 for the second and so on. Removing games that ended because of a win (3 in a row) (http://www.se16.info/hgb/tictactoe.htm) takes us to 255,168 possible games. Further reflection (and rotation) vastly reduces the number of games. To get the “right” answer we need to answer 3 well formulated questions: (http://www.mathrec.org/old/2002jan/solutions.html retrieved from https://web.archive.org/web/20071026011151/http://www.mathrec.org/old/2002jan/solutions.html)
- What is a unique move?
- Choice of first player is distinct and every board position is distinct
- Choice of first player is arbitrary and every board position is distinct
- Choice of first player is arbitrary and board orientation is arbitrary, but once the board is oriented every position is distinct
- Choice of first player is arbitrary and only distinct player choices are distinct moves
- What moves are allowed?
- Any open square
- Players must make three in a row if possible
- Players must make three in a row if possible, otherwise must make a blocking move if possible
- When is a game over?
- When either player makes three in a row or the board is full
- When the outcome of the game is fully determined
- Depending on how you answer these questions, you can justify 26,830, 23129, or even 1145 possible games!
1848
Charles Babbage originated the concept of a digital programmable computer. He spent years trying to finance the construction of his designs for the “Difference Engine” and the later “Analytic Engine” which, had they actually worked would have been the first programable computers. (Modern reconstructions from his notes do work!)
Babbage tried to design a chess playing computer, but determined the problem too complex so beginning in 1848 “I commenced an examination of a game called ‘tit-tat-to.’” He fully figured out the winning algorithm in 1860, and continued notes on the project until 1868.
He hoped that he could build a tic-tac-toe machine, sell ticket to use it to raise funds for the more general computers he was constructing. More details at http://www.digra.org/wp-content/uploads/digital-library/paper_436.pdf
We have Charles Babbage and his Calculating Engines: Selected Writings by Charles Babbage and Others on display.
1949
A century later (1949), Noel Elliot, then a high school student, constructed a working machine to play “Tick-Tack-Toe” Noel and his family have lent the machine to the System Source Computer Museum (https://ca.mdtechnology.museum) where you may use the machine, and see his careful notes used to document the theory and the construction of the machine. The machine is a beast weighing in at over 52 lbs.
LOOK Magazine ran a feature article on Noel and his invention.
Noel’s computer never loses, but sometimes passes up an easy win.
1950
“Bertie the Brain” was built by Josef Kates for the 1950 Canadian National Exhibition. Bertie had controls to adjust how well the machine played. While Kates later built early general purpose computers, Bertie could only play Tic-Tac-Toe.
Roger’s Magestic, the sponsor is a distant predecessor of Rogers Communications, a major cable, internet and wireless company in Canada.
1950 Bernie the Brain – Bing video
1952
EDSAC was 2nd stored program computer (after ENIAC) completed in 1949. As part of his doctoral thesis on human-computer interaction, Sandy Douglass programmed the machine to play “noughts and crosses” in 1952. Input was via a telephone dial!
Around the same time, Christopher Stachey ported the game to a Ferranti Mark 1
https://en.wikipedia.org/wiki/OXO
