Paul Shields W4701 – Artificial Intelligence

Assignment 3

Introduction

This assignment created an intelligent Italian Checker playing agent called Saltare.   Italian Checkers is played on the black squares of an 8 by 8 checkerboard. The board oriented so a black square is in the bottom right hand corner.  It is similar to American Checkers with the addition of a complicated hierarchy of capture precedence.  The assignment was to create an agent which correctly interpreted and played to the rules.  It was also to play in a way that would try and win.  In this regard Saltare was successful, playing at about a ‘B’ level based on the Chungkuo site evaluation (http://www.chungkuo.org/checkerprograms.html), ahead of many commercial programs.  Given the relatively short amount of time for the assignment there are many optimizations not implemented and I focused on ‘time to implement’ verses playing strength for the optimizations included.

This write-up is divided into 5 main sections as follows

• User Interface and Source Code
• Move Generation
• Dynamic Evaluation
• Static Evaluation
• Playing Strength

Saltare is written using Delphi 7 which is based on the Pascal programming language.  Pascal already has high readability but this is enhanced by using indentation, long variable names and the frequent use of comments.  All source code is included in the attached files.   

The Checkerboard (www.fierz.ch/checkers.htm) interface was chosen as a front-end for Sattare.  This has the dual advantage of having an easy to use test-bed and the ability to test the software against other programs and people.  I also implemented another test-bed for testing a variety of the features rather than just playing a game.  

Email address for contact:  paul.shields@sportscoach.com.au

User Interface and Source Code

The Checkerboard interface was chosen as the main interaction with Saltare.  Checkerboard, written by Martin Fierz, is described by him as follows

 “CheckerBoard is an interface to a checkers engine. CheckerBoard allows you to load and save games in the standard PDN format, to set up and search for positions in a PDN database, and to replay games. You can also save games as HTML to publish your favorite games on the internet. CheckerBoard itself cannot play checkers; for this it uses a so-called checkers engine. CheckerBoard communicates with the engine and tells it to think about a move.”

 The communication is via functions exported from a Dll’s.  These are defined (in C) as follows

• int WINAPI getmove(int board[8][8], int color, double maxtime, char str[1024], int *playnow, int info, int unused, struct CBmove *move);
• gets a move from the engine
• int WINAPI enginecommand(char command[256], char reply[1024]);
• controls engine setup and options
• int WINAPI gametype(void);
• sets the game type eg American checkers = 21 Italian = 22
• int WINAPI islegal(int board[8][8], int color, int from, int to, struct CBmove *move);
• called when checking the legality of an opponents move

Partial documentation can be found on Martin’s site (www.fierz.ch/checkers.htm).  The initial part of the assignment focused on interfacing the Delphi code to the C API ’s defined by checkerboard.  This is more than was required by the assignment (which only required outputting a move) however it enabled easy testing and increased the versatility of the finished program.

It also allowed automated testing of the program as Checkerboard includes an Italian Checkers game playing agent called ‘Dama’.   Dama is based on SimpleTech which is rated at ‘B’ level on the Chungkuo Site.  Saltare and Dama played many matches together with Dama having the most wins but Saltare also won many times.

The source code can be found in attached 5 files

• Engine.pas – 650 lines of code
• Deals with the interface with Checkerboard, controls the flow of the program, and defines the major data structures used in the program.
• Moves.pas – 730 lines of code
• These are the move generation functions.  They are separated into jumps and normal moves.  If no jumps are found the other moves are looked for.
• Search.pas – 240 lines of code
• The dynamic evaluation is performed using the NegMax variant of the MiniMax search algorithm with alpha/beta cut-offs.
• Eval.pas – 550 lines of code
• The static evaluation is performed in this unit.  This is done using a weighted sum of both piece and positional information.

Total lines of code is just over 2200 is about the same as SimpleTech which is written in C.  My move generation routines are coded more compactly than SimpleTech but the other aspects are slightly larger.

Move Generation

Generation of legal moves is a critical and complex part of a checkers program.  This section needs to be fast as it will be performed extensively in the dynamic search and also has to be correct.  This is made more difficult by the precedence hierarchy required of Italian Checkers.  Significant time was spent in this part of the assignment both optimizing the code and making sure the moves generated were both complete and correct.  

A set of four 32 bit integers was used as the board representation.  This enabled relatively fast shifting and logical comparison operators to be used in move generation rather than additions and multiplications for an array based approach.  The structure was defined in Delphi as follows:

  BoardBits = record

      whitemen : cardinal;           {bit array of 32 values 8x4 board  }

      blackmen : cardinal;           {bit array of 32 values 8x4 board  }

      whitekings : cardinal;

      blackkings : cardinal;

  end;  {Boardbits}

Within each of the integers a 1 indicated the presence of the piece.  The numbering scheme was the standard Italian checkers scheme with the least significant bit representing the 1 square in the bottom right hand corner of the black side as follows.

                           (White)

             32      31      30      29

                  28      27      26       25

             24      23      22      21

                  20      19      18       17

             16      15      14      13

                  12      11      10        9

             8         7        6        5

                   4        3        2         1

                           (Black)

It is possible to use more compact bit mapped representations.  For example a 3 integer representation could be as follows.  There would be an integer for black, an integer for white and an integer to represent the kings.  Access could be achieved using

     Empty := not (Black or White);

     Whiteman := White and not Kings

     Blackman := Black and not Kings

     Whiteking := White and Kings

     Blackking := Black and Kings

I elected to use the 4 integer representation as storage was less of an issue than speed and the piece access functions added some overhead.

A move was stored in a simple structure that was flexible enough to handle jump sequences and simple moves.  It was defined as follows:

//    Details for a jump

  jump = record

       two: Integer;               //  intermediate path coordinates of the moving piece

       delpiece : Integer;      //  what is deleted

       delpos : integer;         // squares whose pieces are deleted after the move

  end; {jump}

//      The Move record

  move = record

      two : integer;               //  where we move to

      from : integer;             //  where we come from

      jumplist : array[1..12] of jump;

      parts : integer;             // how many jumps are there in this move?  

      oldpiece : integer;       // what disappears on from

      newpiece : integer;     //what type of piece appears on to

  end;  {move }

Move Generation was divided into simple moves and jump moves.  Jump moves were checked first and if there were none then simple move checking continued.  Both simple moves and jumps had two main sections.  Firstly possible moves where created by shifting and bit matching operations and then these possible moves were expanded to create the full move if viable.  The full code is out lined in the Moves.pas file however here are brief descriptions of each process

Moves

The possible move section operated by checking to see if squares in front of a piece were free, and in the case of a king behind it as well.  Here is some sample code for white to give a flavour for this.

PotentialMoves4 := (not Occupied) and (OccupiedWhite shr 4);

PotentialMoves3 := (not Occupied) and ((OddRows and OccupiedWhite and not Edges) shr 3);

PotentialMoves5 := (not Occupied) and ((EvenRows and OccupiedWhite and not Edges) shr 5);

Here the potential moves for a piece that can move 3, 4, or 5 places ahead are checked. 

Once potential moves are developed each of these is expanded to full move and the move structure is filled in.

Jumps

This were created in a similar way to moves although the possible jumps were +-7 or +-9 away from a current piece.  The square in front was checked to ensure a piece of the opposite colour was present and the next square was vacant.  Example code (partial) for this is as follows:

InFront4 := (OccupiedWhite and (OccupiedBlack shl 4)) shr 4;

if InFront4 <> 0 then

InFront4AK := InFront4 and not ((Posn.whitekings and (TheBlackMen shl 4)) shr 4)

else InFront4AK := 0;

……..

PotentialMoves7 := (not Occupied) and (((InFront3AK or (InFront4AK and OddRows)) and not RightEdge) shl 7);

This code looks to see if the squares immediately in front have a piece of the opposite colour, then checks to make sure it is not a king (AK) if you are a man and finally looks to see if the next square out is vacant.

Once a jump is confirmed a move structure is created for it and a depth first search is initiated to see how long the jump sequence lasts.  If there are choices of pieces to jump then a duplicate move structure is created and both branches are explored until there are no more jumps.

Although all pieces on the board are passed to the search only the jump to expand is passed to the possible move generator.  This limits the time spent exploring non valid sequences. Also any man jump which lands on the far edge of the board is terminated and a king replaces the man.

Finally if there are multiple jumps the jump list is passed to the Italian Checkers jump validation routine.  This routine checks the following conditions in order of precedence.

1. Check for the move with the most captures

2. Capture with a king in preference

3. Capture the most kings

4. Capture any kings first

Jumps are quite a complex part of the Italian Checkers game so some time was spent making sure this was correct using an external test-bed.

The move generation routines are split and called only if required.  The ‘AnyMoves’ and ‘AnyJumps’ functions are used in quiescence checking and testing for a loss as well as in move generation.  Simple moves are only checked for if there are no jumps.

Saltare maintains a copy of the progress of the game internally via an array of board positions.  Checkerboard does this as well, however it is needed to test for a draw.  If a position is repeated three times then a draw is signaled.  A loss is signaled if no moves are available or there are no pieces of the playing colour.  Checkerboard has some problems with the handling of the win/loss and draw conditions so although these are detected and signaled correctly by Saltare checkerboard often keeps playing.

Dynamic Evaluation

This is where possible moves and counter moves are explored as far into the future as possible.  The NegMax (Knuth) variant of the alpha-beta MiniMax search algorithm is used for dynamic evaluation.  The code is based on the corrected version of the partial code provided in class.  The NegMax algorithm reverses the sign of the evaluation at each alternate depth.  It does this by multiplying it by -1.  It is sensitive to the initial start depth and the evaluation function is inverted for each odd start depth.

The NegMax variant provides quite compact fast code and so was chosen in preference the standard and/or minimization and maximization approach which must have separate code for each ply. It can be a little tricky to get the signs correct and on occasions, during testing, it was interesting to see Saltare choose the worst possible move!

Alpha Beta cutoffs are used to decrease the number of nodes searched.  This adaptation is sensitive to the order of node expansion but can potentially cutoff large sections of the search space. 

Optimizations can be divided into two broad classes.  Firstly ideas to increase the performance of the alpha-beta cutoffs and secondly to optimize the depth of the dynamic searching.  Looking at each of these groups in turn

Alpha-Beta Cutoff Performance

Ordering of the moves and initial setting of the of the alpha-beta window were the areas considered.  Three optimizations regarding move ordering were included

·       Ordering of move generation –Where it caused no degradation in speed moves were ordered to increase the likelihood of a selected move. In practice this meant that possible king moves were placed ahead of men.

·       Sorting of moves based on 1 ply evaluation – This operation is fairly costly in terms of time as board positions needs to be developed for each move and an evaluation made of the position.  This needs to be traded off against improvement in the alpha-beta cutoffs.  This optimization provide the most pruning of the search space but the cost of doing this meant that the total time was worse than no sorting (see data below). Based on test cases run it was found that using this where there were no Killer moves available was the best approach.

·       Killer moves – Moves are that have been shown to provide alpha-beta cutoffs in one part of the tree can be used first elsewhere.  It was decided to store only a single killer to speed its inclusion at the front of the move list.  Also full sorting was available so both ends of the spectrum were available.  Details of testing various combinations of 1-ply sorting and killers are as follows.  Each run was a full width 7 ply search.

• Speedup from opening position (both to depth 7)

• With killer                   2,533,922 nodes searched in 4 seconds

• Without killer              5,635,997 nodes searched in 12 seconds

• Sorting only                 2,386,658 nodes searched in 20 seconds

·       Optimizations not used – Several optimizations were considered and not implemented primarily due to time constraints.  These included

• History heuristics – keep a history of good moves and sort based on this

• Transposition Cutoff – Storing and searching in a transposition table(see static evaluation section for the hash table) for cutoff moves to eliminate large sections of search evaluation

• Aspiration Search – varying the initial alpha-beta cutoffs (small gain for potentially large loss)

• Opening move database – Two approaches were canvassed to achieve this.  Firstly, using the extensive series of expert games and opening literature create a table of opening positions and good responses.  Secondly compute good moves offline with lengthy searches to pre-compute a good move.  These can then be used during play.

• Endgame database – The Chinook team has created a 6-move Italian Checkers database and I obtained this from Jonathan Schaeffer the author of Chinook and am in the process of converting this for use.  The endgame is the poorest aspect of Saltare’s playing ability and would improve significantly from the use of this database

Depth of Dynamic Searching

There are two components to this.  Firstly how deep will you broadly search everywhere and secondly are there any areas where you might search deeper.

·       Iterative Deepening – This provided several advantages.  It enabled a good move to be available when time was up at any stage of the search and in conjunction with the hash table, was not too costly in terms of duplicate node evaluation.  It also enabled cutoffs developed in early iterations to prune the search in deeper iterations.  The trick here was to store the cutoffs in reverse depth order so they are available at the beginning of each new iteration.

·       Quiescence Depth Extension – It is inappropriate sometimes to perform a static evaluation as there may be a situation which is volatile.  An example of this is when there are jumps available.  Another situation is when a king has been just crowned. The dynamic evaluation will increase the depth by 2-ply anytime it finds a volatile position (jumps and new king) and test for quiescence again. I also tested using a 1 ply increment which looked for simple combinations but 2-ply gave the best outcome.

·       Optimizations not used – Interesting move depth extension was one area I almost implemented.  This is where the search depth is extended if an interesting line of play is being followed.  I though this would be most useful in a won end-game to help avoid the horizon effect when chasing down opposition pieces.

Dynamic search performance is critical to the success of the program.  The optimizations implemented combined with the static evaluation approach resulted in nodes being searched at a rate of up to 1 million per second and depths of up to 30 ply(quiescence extensions) reached most times in a game with my 3gHz laptop.

Static Evaluation

Static evaluation is performed at the leaf nodes of the dynamic search.  It provides an indication of how good the position is.  This valuation is what is optimized by the search process.  The evaluation here is based on the sum of weighted position and piece features.  It is based around  Martin Fierz's Simple Tech evaluation function and has been enhanced to improve performance.  A hash table has also been added to improve evaluation performance.  The evaluation is mostly performed using bit operations to improve speed.  Even the bit counting routine avoids the use of loops and just uses five bit comparisons.  A discussion of the various components is as follows

Feature Vector

The feature vector is calculated by taking into account of the following items

·       Any Action – A quick check to see if there are any moves.  If there are none then it is a loss for the side.

·       Piece Calculation – Each of the men is weighted by 100 whilst each of the kings is weighted by 170.  Kings are doubled in value if they are around in the opening and mid-game.  If the program is ahead in pieces it will also aggressively seek exchanges adding a score if the material is weighted in its favour.

Ø     300*(WhiteScore-BlackScore)/(BlackScore+WhiteScore)

·       Positional Calculations

The actual weights for these were adjusted by hand to optimize performance.  The final values can be seen in the source code file (Eval.pas). See the learning section for learning optimizations considered.

Ø     Tempo Addition for your move – a couple of evaluation points are added if it is your turn to move

Ø     Back Rank Guard – Guarding the back rank squares is relatively important and a calculation is made to keep the men on key squares for as long as possible.  Holding on to squares 4 and 29 (one inside from the left edge) are the most important and so these men will come off last.

Ø     Intact Double Corner – Keeping your double corner (4 and 7 for white) intact is useful as it avoids an easy path for a king.  There is an addition for keeping pieces in these squares

Ø     Centre Control – Control of the centre gives you more flexibility and mobility. Men in the centre adds value but kings add more.

Ø     Edge Avoidance – Just as the centre is important, keeping your pieces off the edges is critical as well

Ø     Cramp – Cramps also limit a pieces movement. Cramps on squares 17 and 16 are tested for and the evaluation adjusted.

Ø     Tempo – This is a measure of how far forward your men are.  There is an adjustment for the opening, middle game and end game.  The near end game is not adjusted.  The game type is determined by the total number of pieces on the board

§       16 Opening

§       >=12 and <=15 Mid-Game

§       >=9 and <15 Near end-game

§       < 9 End-game

Ø     Safe Edges – Some edges are safer than others.  If you are outnumbered and only have a couple of kings or less then seek sanctuary on a safe edge.

·       The Move

Some thought was given to weighting actual move as well as positional and piece information.  Not enough time was available to fully explore this concept but it would try and put value on the move being considered as well.

Hash Table

A hash table is used to quickly evaluate previously seen positions.  This table must be able to locate the move quickly and if not available spend little time searching for it.  Several different hashing algorithms were considered and a couple of hash table access mechanisms were trialed.  The results of these trials were as follows:

·       Hashing Algorithm – Seven algorithms were tested.  The test looked at a sequence of typical board positions and determined average number of probes and the length of the longest probe.  The algorithms tested came from Arash Patow’s site ((http://www.partow.net) and were as follws

Ø     RS Hash Function - A simple hash function from Robert Sedgwicks Algorithms in C book.

Ø     JS Hash Function – A bitwise hash function written by Justin Sobel

Ø     PJW Hash Function - This hash algorithm is based on work by Peter J. Weinberger of AT&T Bell Labs.

Ø     ELF Hash Function - Similar to the PJW Hash function, but tweaked for 32-bit processors.

Ø     BKDR Hash Function -  This hash function comes from Brian Kernighan and Dennis Ritchie's book "The C Programming Language".

Ø     SDBM Hash Function – This is the algorithm of choice which is used in the open source SDBM project.

Ø     DJB Hash Function – An algorithm produced by Daniel J. Bernstein and shown first to the world on the comp.lang.c newsgroup.

Ø     AP Hash Function – An algorithm produced by Arash Partow. It is a hybrid rotative and additive hash function algorithm based around four primes 3,5,7 and 11.

·       Hash Table Access – Two techniques were trialed.  Firstly a pseudo random number generator was used to drive the position in the hash table after the hash function.  The random sequence was then followed for any additional probes.  Also a simple linear probe using the modulus of the hash table size as the entry point followed by single location incremental probes.  The linear probe ended up the fastest in practice and so ended up in the final implementation.

Learning and Future Steps

At the start of the project I planned to use a back propagation neural net to learn a set of optimum features from a set of board positions from a series of expert game players.  There was not enough time to implement this so the fallback position was to tune the feature vector weights based on games played against itself and others.  There was also not enough time for this.  As a final method I hand crafted the weights based on playing various implementations of the program against itself.  Although not the best approach it did produce credible performance in the time available for the project.

Saltare plays well enough to be released to the public.   The key next steps to improve the performance would be as follows

1.     Transposition Table – Now the hashing works optimally it would be a short step to add a transposition table to the dynamic search routine.  This would store hashed moves and depth as well as the board position and playing side.  If the search routine encountered a transposed position from its current depth or higher up it would stop descending further and return with the previously evaluated score and move.  This is said to cut the nodes required to be searched by about a factor of four.

2.     Opening Book – An opening book would also be relatively simple to implement as all you need is a series of expert games and processing time.  Both of these are available and so a book could be cheaply added

3.     Endgame Database – The endgame is where Saltare needs most help and implementing a database would be useful.  I would either need to develop one or decode the Chinook one I have obtained.

Overall the assignment was great deal of fun, but I severely underestimated the amount of time that it would take to debug the program.  The algorithm implementations were mostly simple, but the debugging hard and subtle in some cases.

Playing Strength

The program plays quite good Italian Checkers and has had some wins against the Simple Tech Italian Checkers program developed by Martin Fierz.  I cannot beat the program and none of my family, but we are not particularly good checkers players.  Several of its games are provided in appendix one.  Two items seemed to significantly improve it’s playing strength.  The first was the inclusion of killer moves at the front of a node expansion.  This reduced the by about 60% the number of nodes explored for a given depth.  The second was the extension of the quiescence search out from 1-ply to 2-ply.  It would seem that this extension although reducing the overall depth of search increased it significantly down interesting lines of play.  

paul.shields@sportscoach.com.au

Appendix 1 – Sample Games

This appendix provides two example games between Dama (SimpleTech version that plays Italian Checkers) and Saltare.  In both of these games Saltare won and they provide an example of the strengths of the dynamic evaluation.  In other games that Saltare lost or were drawn it was mainly due to the greater depth full width search achieved by Dama.

1) A 1-second (not exact) per move game where although down on pieces the program found a winning combination from its selective deepening search.  I have included two analyses of the game.  The first is by Dama and the second by Saltare and shows that Dama searched deeper on average but less deep selectively than Saltare.

Dama (SimpleTech) – Saltare (P Shields)

1 Second Game
Result: Saltare won

Analysis by dama italiana 1.03 at 1s/move on Mobile Intel(R) Pentium(R) 4 CPU 3.06GHz generated with CheckerBoard 1.6

Dama (SimpleTech) – Saltare (P Shields)

1 Second Game
Result: Saltare won

Analysis by Saltare 1.00 (P Shields - Italian Checkers Project) at 1s/move on Mobile Intel(R) Pentium(R) 4 CPU 3.06GHz generated with CheckerBoard 1.6

2) A 30-second (not exact) per move game where Saltare gradually improved its postion to dominate in the end game.  Again I have included two analyses of the game.  The first is by Dama and the second by Saltare and shows that Dama’s deeper but broader search was not as effective as the selective deepening of Saltare

Saltare (P Shields) - Dama (SimpleTech)

30 Second per Move Test Game
Result:  Saltare won

Analysis by dama italiana 1.03 at 30s/move on Mobile Intel(R) Pentium(R) 4 CPU 3.06GHz generated with CheckerBoard 1.6

 
Saltare (P Shields) – Dama (SimpleTech)

30 Second per Move Test Game
Result: Saltare won

Analysis by Saltare 1.00 (P Shields - Italian Checkers Project) at 30s/move on Mobile Intel(R) Pentium(R) 4 CPU 3.06GHz generated with CheckerBoard 1.6