Dann Corbit wrote:Don wrote:Has anyone experimented with naive bayes classifiers for computer chess?
I was thinking in the context of endgame databases, specifically the win/loss/draw databases.
One could combine a set of basic observations about the position and get the classifiers opinion on the "probability" that a position is a win, loss or draw.
Such a thing might form a pretty good evaluation function for a specific ending, even if it's not perfect.
In recent years there has been a resurgence of interest in these classifiers, as they are really simple to code up, do not use as much memory as neural networks and many other classifiers, are very fast and are surprisingly powerful.
What appeals to me about them is that for chess endings you can probably make it as good as you want by helping it out with hand-crafted attributes. For instance in KPvsK, if one were building a classifier, you might code up as an attribute whether the white king has the opposition - surely this attribute would contribute to the accuracy of the classifier.
I am thinking about grabbing the KRPKR database and experimenting and was wondering what if anything has already been tried.
For something like KPK, you only need one bit per position if you store the absolute answer. After all, it is impossible to lose if you are the KP side, so a 1 will say 'win' and a 0 means draw.
So I think it won't have any utility with a very simple problem like KPK (which is small enough even in a full tablebase anyway).
I only used the KPK database as a simple to understand example - I would not consider it for this in actual practice. As a matter of fact I built my own KPK database over 20 years ago and have been using it ever since then - it's 24k with no compression of any kind and fit's neatly into memory. (I have since discovered that other programs use a database of the same exact size, but it's not my database as the bits are layed out in different patterns.)
The more complicated systems like KRPKR might have more utility, but with RAM dropping to $10/GB or so, it seems to me that a bitbase would give certain results. We already know that 'KRP' is usually better than KR, so how much value would the Bayesian results be? Will we be happy with 80% certainty?
I was thinking that we would need much higher certainty, something above 95% or it would not be worth considering to me. Unless it turns out that it works as an excellent evaluation function. We don't fully understand how mini-max works but I wonder if a bayes calculation might be an excellent evaluation function. If you know about bayes classifiers they return a "percentage" of membership to a certain class. That could be translated to a score trivially. Used this way, it never really returns a win/loss or draw score, just how likely it is a win,loss,draw.
My thinking is that it would be a very good evaluation function if it was rarely "way off." For instance it might think a draw is slightly more likely to be a win when in fact it's just a draw. This may be enough to make it a huge win in the absence of a real database.
But there are other considerations too. You mentioned that we might as well just use a real database for this interesting ending with RAM sizes constantly going up. But I'm think of this as a problem that will ALWAYS be with us. At some point cache and ram may be a non-issue for this particular database, but what about the next one that comes along that is a couple of orders of magnitude larger?
So what I'm trying to do is to find a lossy compression algorithm that will be able to super-compress perfect knowledge. Think of this is trying to store images on a tiny storage device using a lossy compression format such as jpeg.
I do think that a Bayes classifier would be very useful in the following sort of circumstances:
A quick check to see if you win the pawn race. If a precalculated race shows 'won' then there is less need to consult the tablebase. I suspect that such a precalculated race could be formed in terms of simple geometry and might fit in 10K. So you would only need to consult the bitbase or tablebase if it were unclear whether the race was won or lost.
It could also be a hint to try the tablebase:
Bayes says that pawn race looks won --> check tablebase to be sure.
Yes, I agree there may be many opportunities to exploit this. But if you can precalculate a pawn race, it should just become an attribute for your bayes net, no doubt drastically increases it's predictive ability.
The real appeal when you talk about using it as a substitute for a bitbase is that you KNOW in advance exactly how good or bad it is. You know from offline testing exactly which positions are right and wrong. So you can accurately evaluate and tune it.
If you can get the accuracy really high, you can use a bloom filter or some other data structure to note the exceptions - and you might end up with a loss-less procedure that is far more memory efficient than a real database.
I don't pretend that won't be challenging! There are some endings where it's probably very difficult to classify accurately.
It seems to me that Bayesian logic might prove valuable in evaluation.
I think so too. I was even going to present a separate post on how it might be used to build an evaluation function.
For instance, suppose that some features combine in a non-linear fashion. It could be worthwhile to see if {for example} having a particular sort of material imbalance together with a mobility advantage leads to a particular probability of winning. It might be possible to engineer a set of rules that combine things in a non-linear way to arrive at better decisions than by simple additions.
Yes, this might be possible. There are tons of papers on naive bayes and hybrid approaches that combine this with something else which are pretty interesting.