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.


Steven Wolfram’s Computation Knowledge Engine

Posted: March 9th, 2009 | Author: | Filed under: artificial intelligence | Tags: , , , , | 2 Comments »

Ars Technica has no faith.  They are already saying that Wolfram’s knowledge engine will fail based, I’d imagine on the complete and utter disaster that Cuil and other would be google challengers have been.  Here’s why I think that the computation knowledge engine can be a success.

First of all, its Stephen Wolfram, who truly shouldn’t be underestimated.  He is also not trying to say that it can cure cancer, really he isn’t saying what it can do, or what its ultimate goal is.  Except to say that it is going to answer simple questions.  I don’t understand why this is impossible.  Technology is clearly accelerating at a near exponential rate.  The same improvement in technology and science between 1997 and 2000, was probably accomplished by June 2002, and so on.  If that is to be accepted, then you have to believe that at some point soon we should get to an intelligent system that can answer a simple question like what color is the sky.  Not by looking it up in a database, but by actually reasoning out the answer.

I think that Ars isn’t giving these guys enough credit.  I can’t wait to see what they have cooked up.