Building An Evaluation Functon Using A Binary Classifier

[towforce]

Binary classifiers are steadily improving - it seems to be fair to assume that one day they'll be good enough to automatically build an evaluation function that can accurately classify a chess position in a single ply:



I suppose the first problem is that positions have 3 classifications (win, draw, lose) - not two - but that's OK - you just need two classifiers instead of one.

[rbarreira]

Is there any reason to believe that binary classifiers would be able to accurately evaluate a chess position compared to other models?

[melajara]

The problem with chess is the strong non linearity between input (positions) and output (evals).

Unless you are encoding other parameters than the raw position (and FEN flags),
I don't see ANY way for a binary classifier to correctly partition a set of positions.

[towforce]

Is there any reason to believe that binary classifiers would be able to accurately evaluate a chess position compared to other models?

The word "believe" might be a bit strong - but can there be any serious doubt that that a good binary classifier would find relationships that the human neural network trained to think about chess in a particular way has missed?

The problem with chess is the strong non linearity between input (positions) and output (evals). Unless you are encoding other parameters than the raw position (and FEN flags), I don't see ANY way for a binary classifier to correctly partition a set of positions.

Imagine a program had been written to generate random legal chess positions. I suspect that you'd agree with me that the overwhelming majority of them would actually be very easy to classify. The difficulty would start to arise in positions from high-quality games. The question would be whether the improvement in static evaluations would grind to a halt - or even suffer from the old AI issue that when you improve skill in one aspect of the game, it might weaken in others.

Regarding linearity: this is not obviously a show-stopper for me:

1. "linear" is not synonymous with "simple". A good deal of complexity can be modelled with linear algorithms (hence why LINPACK and LAPACK have traditionally been used as supercomputer speed tests)

2. not all binary classifiers will be blocked by non-linearity anyway (though I concede that it would raise the difficulty of making good classifications)

It is my opinion that if complex enough, a single, static evaluation function could classify positions with near 100% accuracy - and thus play near-perfect chess instantaneously in terms of human perception.

[zullil]

It is my opinion that if complex enough, a single, static evaluation function could classify positions with near 100% accuracy - and thus play near-perfect chess instantaneously in terms of human perception.

For some reason, this made me think of mathematical knot theory, my area of research. It's like saying: If complex enough, a single invariant could classify knots with perfect accuracy.

To which I'd likely respond: Well sure, we could just use the isotopy class of the knot as our invariant!

(In other words, without a limit on complexity, lots of things are possible.)

[rbarreira]

It is my opinion that if complex enough, a single, static evaluation function could classify positions with near 100% accuracy - and thus play near-perfect chess instantaneously in terms of human perception.

For some reason, this made me think of mathematical knot theory, my area of research. It's like saying: If complex enough, a single invariant could classify knots with perfect accuracy.

To which I'd likely respond: Well sure, we could just use the isotopy class of the knot as our invariant!

(In other words, without a limit on complexity, lots of things are possible.)

Indeed... Just make a 32-man EGTB and there's your perfect static evaluation stored on a lookup table.

To compress it to a manageable size (if it's even possible) would require/imply having a very intelligent data compressor. There are strong reasons to believe that better and better data compression approaches strong, general AI, which would be useful for much more than evaluating chess positions.

[towforce]

Indeed... Just make a 32-man EGTB and there's your perfect static evaluation stored on a lookup table.

If two patzers were playing, it seems to me that it is very likely that a master would be able to look at the board and know, almost at a glance, which side was winning.

If you accept this, then you must also accept that static evaluation is possible to some degree of accuracy without a full table base.

You might even accept that a a well-written specialist static evaluation function would be able to accurately classify most of the positions in that game as win/draw/lose.

I suspect that you would further accept that if the programmer worked on it, he could improve that static evaluation function - and to continue to improve it for quite a long while.

Going further still, if shown a good study from a reliable source, you might accept that binary classification is better done by machine than by hand programming.

From there, it wouldn't be too much of a stretch to believe that a binary classifier that was specifically written to classify chess positions could outperform even a good hand-written evaluation function.

Hopefully, you're still with me here. The next steps are not fully clear in my own head - but maybe writing them down will resolve this, and others will understand my thinking:

* if you play a simple game (or puzzle), you will soon have patterns and heuristics that will enable you to resolve it without having to have a table base equivalent

* we know that heuristics exist in chess, because we know that masters can make a good assessment of a position in a short space of time

* I would guess that good heuristics (or equivalent) exist that are not known to humans - and that a specialist chess binary classifier could find them

* if that is accepted, then it would not be unreasonable to guess that a specialist chess binary classifier might be able to find good heuristics in good permutations for a static evaluation without using anything remotely like the storage requirements of a 32-man table base

[towforce]

Just thinking out loud about my last post: whether it could be made to work seems to depend mainly on two things:

1. whether the complexity of heuristics required to classify positions, as those positions become more difficult to classify, grows exponentially (and if so, whether the limit that would have to be reached is practically achievable).

Sometimes, when things appear to be getting more complex, they actually "self simplify" - something that appears to add complexity actually reduces the complexity of things that are are already there (or they enable a new permutation of heuristics to be discovered more easily).

2. whether the binary classifier would converge towards a solution. If the solution space of available heuristics is highly symmetrical, then convergence towards a good solution might prove to be very big obstacle

[Mike S.]

Is this related to quantum computing, somehow? After a decade in the 21st century, I still don't see any working quantum computer. It seems to remain a myth.

[towforce]

Is this related to quantum computing, somehow? After a decade in the 21st century, I still don't see any working quantum computer. It seems to remain a myth.

1. what I am talking about has nothing whatsoever to do with quantum computing

2. if they are a myth, then the Advertising Standards Authority should tell D-Wave to stop calling the device they sell for $10 million a "quantum computer".