The History of Noughts and Crosses
(The history of Tic Tac Toe)

Noughts and Crosses is a game that has been played in the United Kingdom for several centuries - even if it’s precise history seems unknown. The game has become known (perhaps more popularly) as Tic Tac Toe in American English but I am going to stick with the original name in the main. It may be that the ancient Roman game of Terni Lapilli was an identical game although the evidence is somewhat mixed. It is certainly true that identical grids to the noughts and crosses grid have been found scratched and etched into surfaces all over the ancient Roman empire. However not a single Nought or Cross has been found to confirm the link. It seems probable that Terni Lapilli was played with simple pieces and may have been played with the same rules but in my mind it’s sheer popularity casts doudbt upon the connection.

Charles Babbage designed a noughts and crosses playing machine and as he was also the designer of a series of mechanical programable computing devices. I do not think that his machine was even completed but given the now proven capacity of his mechanical computing machines it would be interesting to explore the design. Babbage brings me rather nicely to the more modern history of the game.

Modern History of Noughts and Crosses
(the modern history of Tic Tac Toe)

My interest in Noughts and Crosses and Tic Tac Toe is rooted in the use of computer software to play the game. The history of computer based Noughts and Crosses goes back to the very start of modern electronic computers and continues through some very recent research into Artificial Intelligence.

The first software program designed to play Noughts and Crosses was written by A.S. Douglas as part of his Phd disertation on Human-Computer interaction. The computer was the EDSAC machine built at Cambridge University in 1949. The EDSAC machine was the first true programable computer as we would understand it today.

This is what the first computer game in the world looked like and it was noughts and crosses.

You can download an EDSAC simulator and run some of the original programs including this one for yourself. The EDSAC simulator is a fascinating oportunity to experience the birth of computing and to try your hand at programming this early machine. The latest version is available for Windows although an earlier Mac version exists and a Linux/Kylix version is in preparation. You can take a look at the original noughts and crosses program code developed by A.S. Douglas by clicking here - it was written in Assembler.

Where A.S. Douglas led, others followed. Donald Michie reports seeing faultless computer based play at the National Physical Laboratory in 1950 in an interview with Michael Bain covering the early developments of AI research in the UK. Donald Michie is important to this story because of his creation MENACE. In 1959 an Edinborough colleague of Michie’s asserted that learning machines were an impossibility. Michie proved him wrong with a collection of matchboxes and glass beads that became the Matchbox Educable Noughts And Crosses Engine. This relatively simple model demonstrated clearly that a machine could learn.

We built a software simulation of Michie’s MENACE noughts and crosses playing machine. Follow this link to read more about the original machine and our simulation. You can download a working version of the simulator and get your hands on the Visual Basic source code.

The development of the micro-processor and the home computer saw noughts and crosses games for just about any computing device that could be programmed and had a suitable user interface. However nearly all of these (and most found on a wander around the Internet) were based upon simple algorithms or just random play.

The more succesful game playing algorithms and certainly those that are applied to more complex games than noughts and crosses make use of the minimax strategy and alpha-beta pruning. The minimax strategy helps game playing software evaluate alternate playing options and alpha-beta pruning helps minimise the time taken to investigate the alternatives. Read our introduction to the minimax strategy and alpha-beta pruning.

Following on from the success of the MENACE machine we wanted to apply Artificial Neural Networks to the game of noughts and crosses and in particular experimented with the evolution of neural networks. You can follow the story of our experiments in evolving artificial neural networks to play noughts and crosses. You will also find detals on constructing your own neural networks in Visual Basic or in any other programming language.

Where next? I notice that the book “Building Robots with Lego Mindstorms” by Mario Ferrari and Giulio Ferrari (Ralph Hempel as technical editor) includes a noughts and crosses playing robot. Now if my five year old will allow a change from the floor crawling varieties we are building at the moment I might just give that a try.

Noughts and Crosses statistics
(Tic Tac Toe Statistics)

There are 255,168 possible games of noughts and crosses. My work on a MENACE simulator in Visual Basic showed me that the player going first could potentialy be faced by as many as 2201 different non winning board positions in the first four moves. Some of those moves were symetrically similar to others (rotations, reflections and so on) and when I eliminated these I reduced the total count to just 304 totally different board patterns. Applying the same transformations to the 255,168 possible games of noughts and crosses (tic tac toe) reduces the total to 26,830 completely different games - not bad for a three by three grid.

To take a look at the calculations and reasoning behind some of these figures visit Henry Bottomley’s page on the subject.

The very real purpose of game strategies

The serious side of computer gaming is that the techniques developed to solve simple games like noughts and crosses can also be applied to much more complex commercial and research issues. Adit Limited can apply proven strategies to your business challenges to provide you with unexpectedly straightforward software solutions to complex problems. Click here to contact us for more on our software engineering skills.

Other links

[ Home] [About Us] [Systems] [Software Review]