I figure I’d start revisiting some work I did a couple quarters ago at UCI in an AI project course. We set out to experiment with some different Checker strategies and see how they would fair against each other, against us, and (most importantly) against another team developing another Checkers AI system. I’ve created a simple game from my own ideas, but I haven’t created a game from a preexisting set of rules before or have the game play against the human. The game system is pretty self-explanatory; moves are hi-lighted, jumps are mandatory, a piece becomes a king on the other end of the board, and you win when you lose all your pieces or when you can’t make a move.  I really wanted to build this in something other than a Java applet, since they aren’t used much these days, but UCI programming courses heavily use java and their game courses heavily use a custom library called UCIGame (you-see-ga-me).  The AI depth search uses a min/max and alpha/beta pruning strategy to allow the massive move set to be shortened so a move decision can be made in reasonable time, but a search of depth 10 still makes a noticeable pause.

The most interesting part of this project is the AI strategies we implemented.

• Random
  • The AI selects a move at random.  Hardly a challenge
• Basic
  • The AI examines all possible moves within the search depth value.  It then selects the move that allows the AI to be in the position were losses and gains will be the most beneficial.  Ideally, the more pieces it can take and least amount of pieces it can lose will increase the probability to win the entire game.  This strategy is easily countered by tricking the AI with bait, and then trapping and taking its piece.  The best choice is based on an average score derived from a couple of heuristics.
    • Taking pieces(+ for regular; ++ for kings)
    • Loosing computer pieces(- for regular; — for kings)
    • Getting ‘Kinged'(+)
    • Moving a piece from a ‘King Me’ square(–)
• Piece Table
  • In addition to the heuristics above for the basic strategy, a piece table is also incorporated into the score for a move. The piece table gives each square a value and it is added into the average score for each move. This is the piece table used for our AI.  Each number denotes a square worth value. The higher the value, the higher the worth of keeping a piece on that square. Notice that all ‘King Me’ squares hold the highest value of 4, these spots are very important, and a player would only want to move a piece from this location as a last resort. Squares close to the sides of the board also have the value 4, and closer inside is 3, are the least vulnerable from attacks. On the other hand, the squares in the very middle of the board hold a value of 1. These squares get vacated as fast as possible since they are most susceptible from attacks. The numbers make a sort of spiral from the outside, decreasing in value as they come closer to the middle. This strategy is very strong since it combines the heuristics from the Basic strategy to minimize losses and maximize gains as well as achieve optimal piece placement on the board to further minimize more losses and maximize more gains. I have not been able to beat this strategy with a high depth.

Overall, it was a very enlightening project to work on.  I learned a lot working with massive decision trees, different strategies, implementing given rules, and classifying data sets using a range of scores. I was quite happy with the outcome of an AI that can easily beat its creator, and with the fact that we smoked the other Checkers project team. Checkers is a solved problem after all, so if we were evenly matched it should tie or win ~50% of the time.

EDIT// before java was more or less shuttered from browser support, we had a working embedded applet you could play but not anymore.

I have a couple of planned changes for this application’s future:

• Simplify the button options
  • The three buttons on the GUI made sense at the time I created them, but many users have reported that they have trouble knowing which one to click when.  Combining the Resign and New Game button into a single one will free space for an AI vs AI option.  Another problem is that when the Make AI Move button is pressed the player switches sides.  They have to click it again to resume play as the original red color.
• Allow  the player to select his color at start of game
  • Just a nice option for the player to choose.