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.

What is Nc3 Bb4

Posted: September 16th, 2011 | Author: | Filed under: chess, nc3bb4 | Tags: , , , , , | 2 Comments »

Other than being Knight to c3, Bishop to b4, and a move from a variation of the French Defense, it is now my hobby HTML5 chess project.  Based on the engine of garbochess, it uses web workers to factor and rank the moves in a map/reduce way.  I used to play chess for an hour and a half every day when I was a kid, and I hadn’t realized how much I missed it until I started playing with my 4 year old recently.  Then when I got onto my Chromebook, there didn’t seem to be any local storage using, HTML5 based apps just for Chrome.  Incidentally, an awesome resource for getting started with chess programming is the chessprogramming wiki.  Check it out if you have an interest as well.

Being a programmer, and starting out looking at map/reduce, I was seduced by the chess bug.  Boy chess programming is fun!  For now, the project is in an MVP state.  I intend to modify garbochess such that the machine will learn how to play better against you by weighting the ranking of moves for successes and failures during the evaluation.  It is going to be tricky to modify it in such a way so as the machine learning algorithm doesn’t get stupid with a simple mod, and that I use a markov chain to make sure to consider the state as a basis for each move down the line.  My current thought is to weight endgame moves logarithmically higher or worse depending on the outcome of the game, however my thinking is likely to change as I learn more.

I do intend to create an online component to this, but I am torn between connecting to, and building my own service to facilitate games using XMPP and / or node.js.  I am leaning toward building my own, because freechess’ api is non-existent, however the community over there is awesome.  I guess that since it is a hobby, having a bit of NIH syndrome is probably O.K.  If you like it, please drop me a comment, likewise if you don’t like it, please drop me a comment.