Today is a good day to code

Adding Machine Learning to Nc3 Bb4 Chess

Posted: September 29th, 2011 | Author: | Filed under: artificial intelligence, chess, JavaScript, nc3bb4, Programming | Tags: , , , , | No Comments »

While the garbochess engine is plenty strong used in the Nc3 Bb4 Chromebook chess game, I thought it would be interesting to look at adjusting the weighting mechanism by sucessful and unsuccessful outcomes.

The first thing I had to look at was how garbochess weights potential moves.  This took me into the super interesting world of bitboards.  A quick aside,  I have been working on mapreduce for the past few weeks, so looking at early methods of dealing with big data ( chess has an estimated ~ 10120 ) legal moves, in order to successfully evaluate all of the possible moves for a given position, plus all of the possible counters, weight them and choose the best possible move given criteria certainly qualifies as big data.

Interestingly, the approach wasn’t the hadoop approach, the hardware to use such brute force methods wasn’t available, instead early chess programmers tried to filter out undesirable moves, or obvious bad moves, moves that had no clear advantage, etc… What they ended up with was a pretty manageable set of moves for a circa 2011 computer.

The way garbochess considers moves, it looks at mobility for a given piece, control of the center, if a capture is possible, what the point differential for a trade would be, etc… and assigns a score for each possible legal move, it then runs through it repeatedly re-scoring the set relative to the available moves, removing the lowest scored moves, etc… eventually coming up with the best possible move.  What I wanted it to consider, was given that and the specific weights, mobility vs actual point value for a given piece, to use a markov chain for reinforcement learning to describe the entire process of a game and then rate each move with a weight enhancement upon endgame moves as being more important.  Every time the machine takes an action that leads to a success, the heavier the bias on the scoring for a given action.  Failure doesn’t automatically nullify the learning, but it definitely has an effect.

Where I got was a rudimentary implementation of this, as a bunch of housekeeping chores popped up, for example, as this is JavaScript, and all I really have is HTML5 storage, how do I store all of the moves while keeping the system responsive, no O(nn) or O(n2) lookups, what I wanted was to keep it O(n). Obviously that called for a HashMap of a sort, but the serialization / deserialization plus the key system were a challenge.  I didn’t want for it to cause too much overhead for the map / scoring system, as the bit twiddling is already pretty efficient, so I did the best that I could using the FEN + PGN.  The FEN is the state for the markov chain, since one could have a given PGN in many situations, and the weighting system could never be applied against the gravity of the situation.

I need to do more work on weighting changes based on how in trouble the machine is, whether they have an advantage or not, etc… But for a start with machine learning in chess, I think it works.