As part of our simple demonstration of the application of machine learning techniques to the game of Noughts and Crosses (or Tic Tac Toe) we needed to develop a program capable of playing the game at more than one level of competance. We also needed to be able to test our creations using a player that could be relied upon to provide a suitable challenge. We therefore followed in the footsteps of many others and developed a version of the game based upon an algorithm to decide upon the playing strategy.

Our algorithm was tested against human subjects to ensure that it could give a good range of games right up to the standard of a competant adult. Not forgetting that a draw is a respectable result for two experiened players.

The game was initially developed as an interactive process ready to play against humans and was then restructured as two Visual Basic classes. One class manages the game play and the other acts as a simple referee. This separation gave us the spread of functionality we would need for further experimentation.

The algorithm used makes no attempt to develop a strategy, it simply analyses each board position presented to it and decides upon the best move at that moment in time.

How the algorithm works

To start off with the algorithms used were pretty proscriptive. This proved a problem when they were used in some of the experimental trials. The algorithms were then revisited to encourage a wider range of playing strategies by introducing random choices wherever possible. This succeeded in producing a range of playing styles that were reasonably interesting to play against. Even in expert mode it is possible to beat the software but a lapse of concentration will see you losing in return.

When analysing a given position the game always looks to see if it can win with it’s next move. If it can’t win then the move may be decided by the “level” it is playing at.

There is a random mode that simply makes a random selection from the available playing positions.

In beginner mode the program first checks to see if a defensive move is required to stop the oponent completing a line of three noughts or crosses. If a defensive move is not immediatly required then chance plays a hand. If a random value is above a constant value then a random move is made but if it is below that constant then the program uses the same algorithm as the intermediate mode.

In the intermediate mode the game first checks to see if a defensive move is required. If not, then the board is checked to locate lines that contain just one of the program’s markers. If one or more such lines are located then the program plays a randomly selected position for the available positions within those lines. If more than one such line exists then it is possible that a given cell is part of more than one of them. the random selection process is passivley biased towards such cells. If no such lines are located then the program looks for any empty lines and randomly selects a cell within any such lines found. As a last resort, a random play may be made.

In the expert mode then following a check for a win and a check to see if a defensive move is required then the playing position is analysed for a good attacking move..

The attack algorithm analyses the board to try and identify an unplayed position that is included in the greatest number of potential winning lines - that is, those without an oponent’s nought or cross. If that does not produce a clear result then the analysis changes to try and locate the playing position that is in the most empty lines of play. If that does not produce a good choice then the algorithm shifts to the same as is used in intermediate play.

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