Introduction
"In a very general way it is clear what kind of models we need, because one basic feature of the organization of social insect colonies is already obvious. Individuals following simple local rules, generate the achievements of colonies."
Deborah Gordon. Ants At Work.
With the Connect Four article, I wrote a piece of software that played a game using random moves and its historical memory in order to play a game. It is true that there is code in the program that verifies the move but the moves are decided by either the memory or on a random basis, which means that to a large extent the moves are made not due to a logical process but by the program's memory of how it has been played before. This program is an expansion on the ideas tried in the Connect Four code and represents a sort of half a step back, half a step forward approach in that although the code never makes a completely random move, it is perfectly capable of playing a game of draughts without referring to the data that it has collected. The historical data collected by the program serves as more of an influence on the way the game is played rather than being the sum and substance that it is in the Connect Four game.
That being said, the essential nature of the program is that it is a draughts game and as such should give a reasonable game of draughts even if the ins and outs of how it gets to play the game are not understood or even known to the player. This is to be achieved within the code not by having a set of overall rules or strategies that the game follows but by making each move as independent as possible from each other move with the exception of the historical influences. The options for the movement of each piece being calculated according to the normal idea of making a move in draughts such as 'will I get taken if I go there' or 'will I be taken if I don't move' are outlined below.
Which brings me to the "learning" in the title and the use of the historical data and the fact that there are any number of definitions for what learning actually is, I'm going to state what the idea of learning is as used by the program. This is not to say that this is the only idea of learning that there is or that I believe it is the only definition of learning that is valid. It is simply the idea of learning that is used by the code for this project.
So, here goes, the idea of learning that is used for this project is that the program experiences certain events or moves within its lifetime/experience. These events are then used to influence the future behaviour of the program, i.e., the program's decision about whether a move to be made is a good move or not is influenced by both the program's understanding of the rules of the game of draughts and by the history of a given move. If a given move has been used in situations in which the program has won the game, then it is more likely to make the same move again than it would if the given move was used in a losing game more often than not.
At the outset of the project, there was the intention that the program would have no concept at all of how to play a perfect game of draughts. The code plays the game one move at a time and determines its best move based on its current position and its past history. There are no decision trees planning x number of moves in advance. There is no grand plan that says if you follow these moves, then the computer will win. There is no rating system that says that if you're not very good at draughts, the computer will take it easier on you. The reason for this is because I wanted to write the program to play the game at its most basic level of understanding simply by considering each move in isolation and giving it a rating. As soon as you start adding things that say if you want to play a good game of draughts, then you have to make sure that you take the edges or you aim for double takes, you go beyond the level of detail that I wanted the code to work at.
The idea being that rather than giving the program a static idea of how to play a game of draughts, its understanding is more fluid in that the code can get better or worse at playing the game. I don't seriously expect that the changes in the program's way of playing the game will go beyond being a subtle improvement or weakening of its general game but then the idea is to mirror the way a real person would get better or worse at the game over time. Although, there is no code to make it forget things over time or to diminish its ability to win if it doesn't play often enough.
Training
One of the original ideas for the program was a training mode in which the computer would achieve a certain level of competence in the way the game is played by playing itself for a specified time. This idea was abandoned due to the reason that it simply wouldn't be of any benefit. The thought behind this was that learning should be an on going process so how do you cap learning? It appears to me that the only way in which you could do this is to say that at a certain point, the program has learned enough. The problem is that there are already some setting rules for good or bad learning, for example if the program learns that a certain move will help it win the game, say moving A3 at move nine and then in practice every time it moves A3 at move nine it loses the game, at precisely which point will you say the program should stop adjusting its responses to the move it makes at move nine? The way the code works at the moment is that it will eventually begin to get the idea that moving A3 at move nine is a really dumb move and start moving other pieces at move nine, whereas if you capped the learning process when it was winning by moving A3 at move nine then the program would continue to do this regardless of the result.
The Rules of the Game
The rules of the game are the standard rules for a draughts or checkers game, that is each colour can move one piece one square at a time per turn, in a diagonal direction unless they are in a position to take an opponent's piece at which point they will jump over the piece to remove it from the board. The game is programmed so that if a player or the computer is able to take a piece then that piece must be taken. This also applies to any piece that can be taken in the same move. The computer will automatically take all the available pieces with a single move but the player must drag and drop the piece taken over each piece in such a way that they are taken until the piece cannot take any more pieces. The program will automatically highlight the pieces that are available to be taken in any given move as long as the option to use the highlights is checked.
The game additionally has an inbuilt rule that says if no pieces are taken for more than twenty moves, then the game is declared a draw. This is done to prevent endless moving backwards and forwards at the end of the game.
The User Interface
The user interface for the program is as basic as it can be without restricting any options available to the player. The computer moves automatically while the player uses drag and drop to move their pieces. The options available to the player are set up on four tab controls, the first of these being the Game Setup Tab.
This tab contains the options for which colour squares the game will be played on, the choices being either the light or the dark squares. It allows you to turn off the highlights option which is used when the player picks up a piece using drag and drop. The highlights option shows the player the available moves for the current piece selected. This tab also includes the Start button that instructs the program to draw the pieces to begin the game according to the options selected. It should be noted that the first move is randomly decided by the computer so there is no option to specify who moves first.
The Player Setup tab simply contains the option for the colour of the pieces that the player chooses to use. It should be noted that the blues always play down the board and the reds always play up the board regardless of which side is moving which colour.
The Board Colours tab sets up the colours for the playing board. As you can see from the images above, these are the colours that I have used on the board above so that you can easily see how it works.
The Optional Colours tab setups up the colours for the items that are optional for the player. There is only the highlights that are optional in this program so it is the only item on the sheet.
The Code
Naturally trying to describe all the code in the project in this article would be a bit too much so I'll concentrate here on a brief outline of the logic for playing the game. For those who are interested in how the other parts work, the fuzzy logic library is fairly comprehensively covered in my articles on Code Project and the BoardControl DLL is a straightforward Windows GUI control which shouldn't be too hard for people to work out for themselves.
Draughts Board
The DraughtsBoard class inherits from the Board class contained in the BoardControl DLL and controls the main setup of the board and keeps the program running smoothly. All the processing for the player's movement is done directly in the DraughtsBoard class which controls the drag and drop controls and the highlighting for the squares as well as displaying of the images for the drag and drop.
The main driving function for any drag and drop operation is the OnDragOver function which in this case is used mainly to figure out which colour piece is being moved. The function then calls either the PlayerLightMove or the PlayerDarkMove functions. These are in effect the same functions that are just written to check different directions. In most circumstances, the functions will execute a version of the following code:
if( bsStartSquare != null
&& GetSquareAboveLeft( bsStartSquare.Identifier ) == square
|| GetSquareAboveRight( bsStartSquare.Identifier ) == square)
{
if( bMustTake == false )
{
square.DragDropImage = bitLightDrop;
bAllowDrop = true;
}
else
{
square.DragDropImage = this.bitLightNoDrop;
bAllowDrop = false;
}
return;
}
This code tells the program which image is to displayed when the mouse is moved around the board. The code to highlight the squares available to the player to move is triggered at the start of the drag and drop operation when the code first calls the OnDragOver function. A standard piece of the highlight function code is:
bool bMultiSquares = true;
while( bMultiSquares == true )
{
bMultiSquares = false;
squareToMoveTo = squareTemp;
BasicSquare squareNext =
GetSquareAboveLeft( squareTemp.Identifier );
if( squareNext != null && squareNext.IsOccupied == true )
{
if( squareNext.OccupyingName == "COMPUTER" )
{
squareTemp = GetSquareAboveLeft( squareNext.Identifier );
if(squareTemp != null && squareTemp.IsOccupied == false)
{
squareTemp.DrawHighlight = true;
bMultiSquares = true;
}
}
}
squareNext = GetSquareAboveRight( squareToMoveTo.Identifier );
if( squareNext != null && squareNext.IsOccupied == true )
{
if( squareNext.OccupyingName == "COMPUTER" )
{
squareTemp = GetSquareAboveRight( squareNext.Identifier );
if(squareTemp != null && squareTemp.IsOccupied == false)
{
squareTemp.DrawHighlight = true;
bMultiSquares = true;
}
}
}
}
This code is typical of the technique used throughout the program in that you begin from a starting square, in this case squareTemp and then search the surrounding squares for the information you require. In the case above, the code is searching the squares above and to the left and right of squareTemp in an effort to ascertain if there is a piece that can be taken and highlights the one that needs drawing.
Draughts Game
The DraughtsGame class is the driving force behind how the game works. This is where the nuts and bolts of the computer's move take place. This is where the main decision process takes place in the MovePiece function, but before the code gets to that, it builds a list of all the available pieces that can be moved in the GetAvailablePieces function, the code for which, looks like this:
DraughtsSquare tempSquare = (DraughtsSquare)board.GetHashTable[
board.GetIdentifierBelowLeft(square.Identifier)];
if( tempSquare.IsOccupied == false )
{
DraughtsPiece piece = new DraughtsPiece( square.Identifier,
"COMPUTER", false, square.IsKing );
if( pattern.IsPieceInPattern( piece.SquareIdentifier,
nMoveNumber ) == false )
{
if( pattern.GamePieces.Count == 0 )
piece.IsStartForPattern = true;
piece.AddMove( tempSquare.Identifier );
pattern.AddGamePiece( piece );
}
else
{
pattern.AddMoveToPiece( piece, tempSquare.Identifier );
}
}
else
{
if( tempSquare.IsOccupied == true
&& square.OccupyingName !=
tempSquare.OccupyingName )
{
DraughtsSquare checkSquare = (DraughtsSquare)board.GetHashTable[
board.GetIdentifierBelowLeft( tempSquare.Identifier )];
if( checkSquare != null && checkSquare.IsOccupied == false )
{
DraughtsPiece piece = new DraughtsPiece( square.Identifier,
"COMPUTER", false, square.IsKing );
if( pattern.IsPieceInPattern(
piece.SquareIdentifier, nMoveNumber ) == false )
{
if( pattern.GamePieces.Count == 0 )
piece.IsStartForPattern = true;
piece.AddMove( checkSquare.Identifier );
pattern.AddGamePiece( piece );
}
else
{
pattern.AddMoveToPiece( piece, tempSquare.Identifier );
}
}
}
}
The code starts by finding a square on the board and then checking to see if it is occupied or not. By the time we enter the code above, we know that the square contains a piece that is not the player's piece and that the player is playing with light pieces which means that the player is playing down the board and the computer is playing up. The code above then checks to see if the square below and to the left of the square that we are checking is null or not, (omitted from the code above) if the square is valid, we proceed by checking if the square below left contains another piece. If it doesn't, it is considered a valid move. The else clause of the if/else above checks to see if the piece blocking a move is different from the occupier of the square that we are moving from. In this case, it can only be a player's piece; if it is different, it means we could have a valid take move.
Once a move has been validated, the process is the same in both cases in that a new computer piece is created and is added to the movement pattern for this square. If the piece has already been added by a check in a previous direction say Below Right then a move is added to that pattern, if not the piece is added to the pattern.
Once we have the available patterns for all the pieces available on the board, we can begin to consider how to move them in the MovePiece function. The main decision processes of the MovePiece function are pictured below with each part of the process being assigned a value by the following variables declared in the DraughtsGame class:
private const int nMustTake = 3;
private const int nNormalMove = 1;
private const int nHistoricalMove = 1;
private const int nTakenMove = 2;
private const int nSacrificeMove = 1;
private const int nSupportMove = 1;
private const int nKingMove = 1;
private const int nLeavingOpenMove = 2;
private const int nOutOfWayMove = 1;
private const int nMustTakeTakenReduction = 1;
private const int nKingInfluenceMove = 1;
As there is no concept of tactics within the game, the values have been arrived at by playing the game and seeing which way it plays best. There was originally an idea to allow this part of the process to be user configurable but this was abandoned due to the fact that with it being open to all, it would only be a matter of time before someone changed it so that it was completely rubbish at playing and then started complaining that it didn't work.
A simple example of how these values are used within the code is shown in the following snippet from the code that checks normal, i.e., single diagonal moves:
for( int i=0; i<collection.Count; i++ )
{
bDecisionIncremented = false;
bDecisionDecremented = false;
pattern = (DraughtsPattern)availablePatterns.GetPattern(i);
if( pattern.MoveNumber != nMoveNumber )
continue;
decisionSet = ( FuzzyDecisionSet )collection[ i ];
piece = ( DraughtsPiece )pattern.GetStartsWithPiece();
if( piece.LightPiece == true && piece.IsKing == false )
{
if( processMoves.IsAboveLeftClear(board,
piece.SquareIdentifier) == true)
{
decisionSet.AddByName( "MoveAboveLeft", nNormalMove );
bDecisionIncremented = true;
}
else
{
if( processMoves.IsEnemyAboveLeft( board,
piece.SquareIdentifier, piece.Player ) == true
&& processMoves.CanTakeAboveLeft( board,
piece.SquareIdentifier, piece.Player ) == false )
{
decisionSet.SetIsValidByName( "MoveAboveLeft", false );
}
}
}
if( processMoves.IsAboveRightClear( board,
piece.SquareIdentifier ) == true )
{
decisionSet.AddByName( "MoveAboveRight", nNormalMove );
bDecisionIncremented = true;
}
else
{
if( processMoves.IsEnemyAboveRight( board,
piece.SquareIdentifier, piece.Player ) == true
&& processMoves.CanTakeAboveRight( board,
piece.SquareIdentifier, piece.Player ) == false )
{
decisionSet.SetIsValidByName( "MoveAboveRight", false );
}
}
The code cycles through the available pieces and gets the pattern of moves available for each piece, before deciding what action is required for each move.
Below is the diagram used for the decision process used in the MovePiece function, each movement option is stored in the FuzzyDecisionSetCollection class that holds an array of FuzzyDecisionSets which are set up in the function as:
for( int i=0; i<availablePatterns.Count; i++ )
{
FuzzyDecisionSet fuzzyDecisionSet = new
FuzzyDecisionSet( availablePatterns.GetPattern( i ).GetStartsWith() );
fuzzyDecisionSet.Decision.IsValid = true;
fuzzyDecisionSet.Decision.IncrementDecision();
fuzzyDecisionSet.IsValid = true;
fuzzyDecisionSet.AddDecision( new FuzzyDecision( "MustTake", true ) );
fuzzyDecisionSet.AddDecision( new FuzzyDecision( "MoveAboveLeft", true ) );
fuzzyDecisionSet.IncrementByName( "MoveAboveLeft" );
fuzzyDecisionSet.AddDecision( new FuzzyDecision( "MoveAboveRight", true ) );
fuzzyDecisionSet.IncrementByName( "MoveAboveRight" );
fuzzyDecisionSet.AddDecision( new FuzzyDecision( "MoveBelowLeft", true ) );
fuzzyDecisionSet.IncrementByName( "MoveBelowLeft" );
fuzzyDecisionSet.AddDecision( new FuzzyDecision( "MoveBelowRight", true ) );
fuzzyDecisionSet.IncrementByName( "MoveBelowRight" );
collection.Insert( i, fuzzyDecisionSet );
}
Any changes to the code values are then made throughout the process using the named tags of “MoveAboveLeft”, “MoveBelowRight”, etc.
Draughts Process Moves
The DraughtsProcessMoves class is the glue that binds the functionality between the player and the computer. The class in concept is a simple checking class in that both the player and the computer parts of the program use it when they are deciding the availability of their respective moves, though of course for the player this information is used to calculate which moves are going to be available for the highlights option.
The Data
The image below shows a picture of the XML data that is saved by the program to record its historical progress. It is displayed in Microsoft's XML Notepad links which can be found at the bottom of the page.
The data shown above is the information stored for the square GC when it is the first move and the computer is playing with the blue pieces which means that the two places available to move to are the squares FD and HD. The details for each draughts move are stored in the BasicMove class that the DraughtsMove class inherits from and these are contained in the DraughtsPiece class that inherits from the BasicGamePiece class, although thinking about it, the details stored in the DraughtsPiece class will probably be moved to the BasicGamePiece class for the next program in the series.
Conclusion
The aim of this project was to develop a program that works in a more natural way than the standard idea of how a draughts game should work. This was done by aiming more for a system of calculating the moves on a basis that relied not on a total omniscient idea of controlling everything that occurs on the board and having a fixed response or series of responses preprogrammed into the code but for the code to consider each move in isolation from every other move and to make its judgments based on the best move in the given situation. This is coupled with the concept of a program having its own history which is able to influence but not necessarily dominate the individual decisions that are made about each move. This in theory at least will mean that each version of the code should display subtle differences when played as each version of the game will have its own history that is determined largely by the moves made by each individual player of the game.
The effectiveness of this method and the validity of the techniques used in the coding of this program is left to the reader.
A Note on the References
The books listed below are the books that I have read since I started research on artificial intelligence. All of them have influenced my thinking to a greater or lesser degree, and where I knowingly use something from a book I will make it clear in the article that it uses it. The fact that a specific book or books are not mentioned in the text does not mean it has not had an influence as they are all part of the core research.
References
- Tom Archer (2001) Inside C#, Microsoft Press
- Jeffery Richter (2002) Applied Microsoft .NET Framework Programming, Microsoft Press
- Charles Peltzold (2002) Programming Microsoft Windows With C#, Microsoft Press
- Robinson et al (2001) Professional C#, Wrox
- William R. Staneck (1997) Web Publishing Unleashed Professional Reference Edition, Sams.NET
- Robert Callan, (1999) The Essence Of Neural Networks, Prentice Hall
- Timothy Masters (1993) Practical Neural Network Recipes In C++, Morgan Kaufmann (Academic Press)
- Melanie Mitchell (1999) An Introduction To Genetic Algorithms, MIT Press
- Joey Rogers (1997) Object-Orientated Neural Networks in C++, Academic Press
- Simon Haykin (1999) Neural Networks A Comprehensive Foundation, Prentice Hall
- Bernd Oestereich (2002) Developing Software With UML Object-Orientated Analysis And Design In Practice Addison Wesley
- R Beale & T Jackson (1990) Neural Computing An Introduction, Institute Of Physics Publishing
- Bart Kosko (1994) Fuzzy Thinking, Flamingo
- Buckley & Eslami (2002) An Introduction To Fuzzy Logic And Fuzzy Sets, Physica-Verlag
- Steven Johnson (2001) Emergence, The Penguin Press
- John H. Holland (1998) Emergence From Chaos To Order, Oxford University Press
- Earl Cox (1999) The Fuzzy Systems Handbook, AP Professional
- Mark Ward (1999) Virtual Organisms, Pan
- Bonabeau, Dorigo, Theraulaz (1999) Swarm Intelligence From Natural To Artificial Systems, Oxford University Press
- Masao Mukaidono, Fuzzy Logic For Beginners (2002) World Scientific Publishing
- Deborah Gordon, Ants At Work (1999), W W Norton
- Gigerenzer, Todd & ABC Research Group (1999) Simple Heuristics That Make Us Smart, Oxford University Press
- Rodney A. Brooks (1999) Cambrian Intelligence
Helpful Links
License
This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below.
A list of licenses authors might use can be found here.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
