12,893,816 members (46,925 online)
alternative version

#### Stats

29.3K views
22 bookmarked
Posted 31 Oct 2007

# Matchbox Educable Noughts And Crosses Engine (MENACE) in C++

, 31 Oct 2007 GPL3
 Rate this:

## Introduction

Recently I came across M. Gardner's 'New mathematical diversions from scientific American' (NY, Simon and Schuster, 1966) and read the article on self-learning tic-tac-toe machine made from matchboxes. I found it interesting and worth implementing in C++.

One of the first self-learning machines was IBM 704. Designed by A. Samuel in 1959, the program allowed a machine to play draughts, improve game strategy using experience from previous games it played. At first Samuel easily won the games, but as the machine learned how to play, it started beating him at every game played.

## Background

You should be familiar with the tic-tac-toe game.

## Using the Code

To save you from matchbox hurdles, I've written the same program in C++. To start playing with the computer, I supplied with it the player1.dat file which is a trained player playing first always. Run play.bat to play with it. To make your move, type y and x coordinates of the empty square. To make a move to [0, 0] type 00 and enter, to make a move to [1, 0] type 10 and enter and so on. Just type a string containing the y coordinate as the first letter and x coordinate as the second letter.

The tic-tac-toe play could look like this:

012

0  ---
1  ---
2  ---

0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000

012

0  ---
1  -x-
2  ---

human move o enter (y,x) coord or '--' to quit: 20

012

0  ---
1  -x-
2  -o-

0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000

012

0  ---
1  -x-
2  xo-

human move o enter (y,x) coord or '--' to quit: 00

012

0  o--
1  -x-
2  xo-

0.000000 1.000000 0.000000 0.000000 0.000000

012

0  o-X
1  -X-
2  Xo-

player No 1 won
wins: 5868
loses: 214
draws: 10934

finished.

The string of numbers 0.0 and 1.0 are for debugging purposes and are the probabilities of making a particular move for a computer. As you can see, it learned to always make the first move to the central square, which is a win strategy.

The help for the command line arguments is shown below:

argv[1] = 'uc', 'cu', 'cc', 'uu'
'uc' - user vs. computer
'cu' - computer vs. user
'cc' - computer vs. computer
'uu' - user vs. user
argv[2] = number of plays
argv[3] = 'player1.dat'
argv[4] = 'player2.dat'

You may play either as the computer goes first cu or uc to make a first move yourself. In cc regime, the computer plays with itself. That helps you to save time training it yourself to play the game. Just run it this way:

>ccross.exe cc 1000 player1_name player2_name

It will play 1000s of times with itself, creating player1_name and player2_name if they do not exist, otherwise reading them from the files. To increase performance, try to redirect console output to the file.

As the computer player encounters novel board configuration, it denotes equal probabilities for performing a move to empty squares. In case it loses the game, it decreases the probabilities of the moves for the board configurations it played, otherwise it increases the probability. In the case of a draw, the probabilities do not change. It keeps every played board configuration and probablities for making a move in a file along with its wins, loses and draw counts.

## Share

 Engineer Russian Federation
Highly skilled Engineer with 14 years of experience in academia, R&D and commercial product development supporting full software life-cycle from idea to implementation and further support. During my academic career I was able to succeed in MIT Computers in Cardiology 2006 international challenge, as a R&D and SW engineer gain CodeProject MVP, find algorithmic solutions to quickly resolve tough customer problems to pass product requirements in tight deadlines. My key areas of expertise involve Object-Oriented
Analysis and Design OOAD, OOP, machine learning, natural language processing, face recognition, computer vision and image processing, wavelet analysis, digital signal processing in cardiology.

## You may also be interested in...

 First Prev Next
 Brings back memories... Don Clugston1-Nov-07 4:15 Don Clugston 1-Nov-07 4:15
 Re: Brings back memories... Chesnokov Yuriy1-Nov-07 5:09 Chesnokov Yuriy 1-Nov-07 5:09
 I like the introduction in the article citing A. Bierce short story Moxon's Master. As Moxon built a robot to play chess, after Moxon won him one game, the machine strangled his creator. I believe Michie started with matchboxes to avoid the same fate
chesnokov
 Last Visit: 31-Dec-99 18:00     Last Update: 28-Apr-17 3:00 Refresh 1