AlphaBeta and "rule based expert system"

[tms]

Hi folks,

does anyone know if an engine exists which tries to implement some kind of "human logic" for pruning? Some kind of rule-based Shannon-B approach?
Please take a look at these few examples to get an idea what i'm thinking of:

r1bq1rk1/pppnbppp/4pn2/3p2B1/2PP4/2N1PN2/PP3PPP/R2QKB1R w KQ -
A standard queens gambit opening position.
b4, Nxd5 or Ke2, ... no slightly experienced human would even think about them, no reason for a sacrifice. Ke2 in addition not only looses material, it also endangerous the king without any use. Alpha beta will search these moves again and again on every iterating depth. Of course they are always refuted fast, since null move, late move reduction, hashing etc. cut down the tree in a fantastic way. Nevertheless, from a rather human point of view they should be discarded at all (latest after a 2 or 3 ply search), since there are absolutely no hints that some kind of combination might get found.

rq2r1k1/5pp1/p7/4bNP1/1p2P2P/5Q2/PP4K1/5R1R w - -
This is position #1 from BT2430
After Ng7 Kg7 a human will continue with active moves like Qxf7. But not e.g. b3, since the aim of sacrificing on g7 is attacking the king and one can't play that calmly after giving away material.
If this (winning) sacrifice is not found one might think "b2 is attacked, let's safe it". Qa3 should be discarded after a 1-ply search, since it completely fails to achieve the aim "dont loose material".
b3 and Qa3 are valid ideas for a single move, but fail to fit the aim.

r1bqrnk1/pp2bp1p/2p2np1/3p2B1/3P4/2NBPN1P/PPQ2PP1/R4RK1 w - -
A standard middle game position.
I want to point out the possible difference between numerical evaluation and a "usefulness evaluation". A classical evaluation function will score Kh1 and Rb1 roughly equal, but there is a *hugh* difference in usefulness and mid/long term effects.
Kh1 is completely pointless, i can't see any good reason for his move.
Rb1 is preparing the classical minority attack, an usual option in this kind of position. An engine might search 5, 10, 15 plies, Kh1 will stay a bit inferior to Rb1 (and other moves).
If i search through GM games where Kh1 has been played, i see only 3 or 4 distinct reasons why this move is played, and (especially with bitboards) it would be easy to check that the circumstances are not given in the position. Therefore a "rule-based move estimator" should reward 0 points to Kh1 and the move could be discarded (maybe again after a shallow search), especially since there are several moves which would get estimated better AND perform better in terms of search.


So, basically:
have there been attempts to improve alpha-beta with some kind of expert system, fed with rules about position types, knowledge about the flow of the game, the usage of moves and the circumstances when they are used etc.?


Thomas

[ZirconiumX]

Hi folks,

does anyone know if an engine exists which tries to implement some kind of "human logic" for pruning? Some kind of rule-based Shannon-B approach?
Please take a look at these few examples to get an idea what i'm thinking of:

Ed Schröder's program REBEL uses an extremely selective Alpha Beta algorithm. REBEL is closed source (ASM is hard to read anyway) but if you good Ed Schroder's Programming Topics' you should find it and a wealth of other info too.

[D]r1bq1rk1/pppnbppp/4pn2/3p2B1/2PP4/2N1PN2/PP3PPP/R2QKB1R w KQ -
A standard queens gambit opening position.
b4, Nxd5 or Ke2, ... no slightly experienced human would even think about them, no reason for a sacrifice. Ke2 in addition not only looses material, it also endangerous the king without any use. Alpha beta will search these moves again and again on every iterating depth. Of course they are always refuted fast, since null move, late move reduction, hashing etc. cut down the tree in a fantastic way. Nevertheless, from a rather human point of view they should be discarded at all (latest after a 2 or 3 ply search), since there are absolutely no hints that some kind of combination might get found.

On the contrary - there are no hints that Ke2 isn't a useful move. It might go to a winning endgame. This is why Ke2 would only be put to the bottom of the list and reduced. Pruning a move outright is a bad idea at the root - any test position proves this.

[D]rq2r1k1/5pp1/p7/4bNP1/1p2P2P/5Q2/PP4K1/5R1R w - -
This is position #1 from BT2430
After Ng7 Kg7 a human will continue with active moves like Qxf7. But not e.g. b3, since the aim of sacrificing on g7 is attacking the king and one can't play that calmly after giving away material.
If this (winning) sacrifice is not found one might think "b2 is attacked, let's safe it". Qa3 should be discarded after a 1-ply search, since it completely fails to achieve the aim "dont loose material".
b3 and Qa3 are valid ideas for a single move, but fail to fit the aim.

And how is a computer (thick, dumb and stupid) supposed to know what 'the aim' is?

[D]r1bqrnk1/pp2bp1p/2p2np1/3p2B1/3P4/2NBPN1P/PPQ2PP1/R4RK1 w - -
A standard middle game position.
I want to point out the possible difference between numerical evaluation and a "usefulness evaluation". A classical evaluation function will score Kh1 and Rb1 roughly equal, but there is a *hugh* difference in usefulness and mid/long term effects.
Kh1 is completely pointless, i can't see any good reason for his move.
Rb1 is preparing the classical minority attack, an usual option in this kind of position. An engine might search 5, 10, 15 plies, Kh1 will stay a bit inferior to Rb1 (and other moves).
If i search through GM games where Kh1 has been played, i see only 3 or 4 distinct reasons why this move is played, and (especially with bitboards) it would be easy to check that the circumstances are not given in the position. Therefore a "rule-based move estimator" should reward 0 points to Kh1 and the move could be discarded (maybe again after a shallow search), especially since there are several moves which would get estimated better AND perform better in terms of search.

Estimates have been wrong. To prevent these mistakes - lots of computational effort would have to be put in. Lots of computational effort = slowdown. CHESS 4.5 proved that by the time you had decided whether a move was good or not you could have searched it.

So, basically:
have there been attempts to improve alpha-beta with some kind of expert system, fed with rules about position types, knowledge about the flow of the game, the usage of moves and the circumstances when they are used etc.?


Thomas

Yes - but a WGM has his forte in computer chess - EVAL - but search is not what he is used to. As Komodo has shown - it is better to have a programmer do the search and the GM do the eval compared to vice versa.

Matthew:out

[tms]

Hi Matthew,

thanks for answering!

My most basic question left unanswered - are there recent attempts to combine a *real* knowledge based expert system (containing 1000s of rules) into a standard search engine?

Maybe for clarification: i'm not hoping to search 20 plies deep with a tree containing 100 nodes . The idea is rather to get maybe 2 plies deeper by cutting nodes which appear highly unlikely, getting a slight advantage compared to the same engine without expert system.

Thomas

[diep]

hi Thomas,

As for todays search, which is already a reality for a decade or 3,
usually combine Shannon A with Shannon B.

Shannon A in the first part of search and Shannon B the last few plies. Arguably the quiescencesearch also is a typical form of Shannon type B, for example with respect to being in check there.

Note depending upon program, the Shannon type B is of different lengths. Historically Rebel pruned most past few plies. Today it's very different from program to program. 3 plies searchdepth left is what gets used most there, some implementations like Ivanhoe razor up to a ply or 9 searchdepth deep left.

Note there have been huge changes in the shannon A type search. Lots of different forms of methods, chessknowledge, heuristics and algorithms get used to add selectivity to Shannon A.

Todays chessprograms, already for a year or 25, try to combine Shannon type A with selectivity.

One of the best forms of selectivity is nullmove there. In principle nullmove in the form of for example double nullmove (as invented by the writer of this post) is a 100% correct form of search.

The real difference is that for example in your examples after Ke2, most programs give a 2 pawn penalty to the king in center.

So black directly nullmoves and the big savings then is reducing the shannon A parts search depth. So the 'refutation' of Ke2 happens by giving white again the move and reducing search depth significantly.

So this is big selectivity, yet search DOES continue after selectivity was applied. The selectivity means a reduction in search depth.

So that is the big difference with the original Shannon type B definition.

Now the next question: "in how far does chessknowledge get used to define the selectivity in the brute force part of the search (shannon A)?

Around 1999 i implemented reductions in Diep. Most popularly called LMR now, though there is a differences in how every program implements this, so calling it reductions is the best manner.

I used a lot of chessknowledge there to decide which move to reduce and which move not to reduce.

This is not so easy however. Todays reductions in Diep hardly use chessknowledge to decide what to reduce.

A big problem of applying chessknowledge, deciding which move to reduce or not, is that at todays search depths there is possibly another 2 plies of search left to go after this position P occurs.

So just static chessknowledge is of course totally irrelevant compared to the quality of the search and has the big problem of forbidding to reduce more moves than a generic search frame.

This struggle is everywhere in todays chessprograms. It's not impossible you'll find something that works, yet it's not easy.

The most important spot to have massive amounts of knowledge is at the leaves, for the evaluation function.

As for the 'easy to recognize' silly moves, realize how effective nullmove is. So that already gets massively reduced.

Even then using chessknowledge always is an interesting idea. It's quite possible that i'll test again with it, yet its role probaby always will be minor in decisions to reduce or not, as the 'easy cases' what to reduce already get caught by nullmove.

Realize an important difference between todays possibilities in search versus 3 decades ago is the huge amount of positions a second a program can see today.

So in itself it would be possible to invent more interesting algorithms now, especially complex ones, as you simply can afford the overhead.

This where Ed Schroder's selectivity last plies simply is a lot CHEAPER than for example doing a full nullmove. He just didn't have the system time to use clever algorithms and simply had to prune.

I've had algorithmic ideas and inventions in 90s, many of which might work today, but back then just couldn't work as i simply didn't have the system time to use the algorithm, as just the overhead of using up that system time already was too expensive.

Note that you can't make any money with computerchess today, so that explains why only some cheapskate algorithms get invented now - as the genius guys mostly left computerchess - they need to make a living to invent complex algorithms. Also they are not cheap. 1000 dollar here and 1000 dollar there is only interesting to nobodies.

I can confirm that i have on paper some complex algorithms which with hard fulltime work would improve search of *any* todays strong chessprogram, which for sure didn't work in 90s. I can confirm others have those as well, yet most of those genius guys might still read the forum and post now and then and pretend to be active, yet they aren't.

You get what you pay for.

That's the most important reason why Shannon B doesn't get used to more effect than it gets used now - as it requires big effort.

[diep]

hi Thomas,

The only chessprogram on the planet that really manages to use a lot of chessknowledge in the evaluation function is Diep.

That said - there is authors who hardly can play chess who have done efforts to code up everything they could define.

Yet realize this is in the evaluation function.

Maintaining that and tuning it well is fulltime work. A lot of patterns in todays Diep still are from 90s. I fixed a major bug in Diep's evaluation function a few months ago. A chesspattern that was totally wrong, which gave regurarly in GENERIC cases a big bonus for having a passed pawn, easily an error of 0.15 pawn or more.

Something like:

if( i have a passed pawn && my score > 0 ) then bonus;

I traced it down to Diep 1996 and before. Possibly somewhere around 1995 i implemented it - yet i was so stupid to use a control code system in 90s and i can no longer find the program that wrote those - so i can't track down exactly what year i implemented it but it was before januari 1996.

Diep started in januari 1994.

And it's 2012 now, and in 2012 i found out about this chesspattern not working ok.

How it survived all those years?

Easy to explain - a single person wrote it and he never had much testing hardware himself - that changed a bunch of months ago. I've got 8 machines now here. Built for peanuts. 8 core Xeons.

That's another huge difference with the past - only some professionals in 80s and 90s had massive testing hardware - no one else.

I remember Ed posting one day in 90s he had 7 auto232 players active. So that's 14 machines he used to test at.

I'm sure he needed that to fix all the tiny details regarding using chessknowledge to forward prune in Shannon B type, the last X plies of search.

Back to the huge bugs in Diep's evaluation function. It's total trivial chessknowledge is total superior when combined with a decent search.

If you see how the many bugs in Diep's evaluation function still get hidden/made up for by the other chessknowledge - you will realize how strong chessknowledge can play.

Yet here is the important question. If you realize how complex a chessengine is in general, not to mention Diep with its complex parallel search and massive evaluation function. If i spend time at its code,
should i rather be busy fixing the evaluation function or put in massive time in knowledge used to search a tad deeper?

Maybe i can get 1 ply deeper for a year of hard fulltime work. How much elo is that?

Fixing the evaluation function a tad (which is fulltime work don't let the word 'tad' mislead you) is however +500 elo at TODAYS search depths.

I tried to fix big horrors past years, but any horror where a position occured where Diep's evaluation function was off by less than 2 pawns wasn't even worth fixing... ...only now i'm starting to pick up bugs in patterns that give a penalty or bonus worth 0.1 to 0.2 pawns. Such mistakes i hardly noticed years ago! Today such errors really need to get out.

So if you do effort - there is lot of work left to do in chessknowledge in the evaluation function.... ...i can spend my time only a single time in life.

This is why only some very simple heuristics and some well tuned tables get used in general for the Shannon B part of the search, which is the last few plies. The effort to incorporate knowledge there is huge, besides that majority isn't even trying. They are looking exclusively for cheapskate manners to get things done!

Yet i hope to have made clear that todays search algorithms already give a very selective search and that the few who TRY to incorporate chessknowledge, each to his own capability, it's more useful for now to incorporate that into the evaluation function, rather than search.

That said - with todays fast cpu's and many cores - a lot more would be possible than 15 years ago.

p.s. add to the chessknowledge problem the datastructure problem. i always have to laugh if i see a posting on bitboards here where just for 1 pattern someone is busy for a month trying to optimize the implementation of it. If i had done it that way with Diep - its evaluation function would be 10% of its current size. The nerds here simply LOVE complicated datastructures that are impossible to code up knowledge.

The first good example of that is Paradise by if i remember well Wilkins. Functional languages are a disaster there. It's a 100% B* program.

The printout i have here of it of that functional language is a total disaster. Everywhere (( and ))) - pretty complicated. Only bitboards rival that

[tms]

Hi Vincent,
what a long, detailed and insightful answer - many thanks for that! Had to read it twice carefully, so many good points...

Trying to summerize your thoughts very roughly:
* the implementation would need a lot of work and time, which is better used for different tasks.
* the idea deals with a kind of "non-problem", simply not enough to gain here. The weak moves i hope to cut completly are reduced and fast refuted by null moves.

Seeing your experience, you are probably right
I was quite optimistic of the idea, now i'd rather agree that the prospects for improvement are small. It also explains why (as it seems) nobody gave a real shot at it during the last 30 or 40 years.

(The idea appeared also attractive to me because it seems rather easy to implement and check - only calculation time , but no need for fine tuning: let the search engine analyse many positions with and without the "rule advisor" - the results in terms of found move and evaluation must be the same.)

Maybe my idea can be buried completely with a rough estimation?
If the "rule advisor" could reliable point out 25% of the moves as bad (lets simply assume it were the moves which are coming at the end of the move list):
how much smaller would the search tree be?
Since if the last quarter of the moves in an iteration account for in average 5% of the tree - it would be obvious that the effort isn't worth it.


Thanks again,
Thomas

[smrf]

The more moves you can make in a ply, the more intelligence is needed to play well. Thus Arimaa or 10x8 Chess maybe good drosophilas. The latter, when generating some results of intelligence, could flash back and enlighten programming of traditional Chess.

[diep]

Hi Vincent,
what a long, detailed and insightful answer - many thanks for that! Had to read it twice carefully, so many good points...

Trying to summerize your thoughts very roughly:
* the implementation would need a lot of work and time, which is better used for different tasks.


* the idea deals with a kind of "non-problem", simply not enough to gain here. The weak moves i hope to cut completly are reduced and fast refuted by null moves.

What i might not have made clear enough is that chess is a simple game with on average 40 legal moves as i measured in Diep, not counting the 'in check positions', as those get extended anyway.

As a result a pure shannon B engine would 100% lose. It's more effective to search EVERYTHING and use chessknowledge or heuristics or simply an algorithm like nullmove to add selectivity.

That's what everyone is doing. As for the chessknowledge used to add selectivity to shannon A, you correctly wrote down conclusion one: "better to spend time elsewhere", which doesn't say it's impossible. I feel it's very well possible, yet if you decide going the way of adding knowledge, you sure better spend that on the evaluation function, as in the end most engines are single programmers products, if we ignore the illegal things that happens around the clones.

Seeing your experience, you are probably right
I was quite optimistic of the idea, now i'd rather agree that the prospects for improvement are small. It also explains why (as it seems) nobody gave a real shot at it during the last 30 or 40 years.

It's obvious many tried giving it a shot for the last few plies. Yet usually there is system time constraints.

Let me give you a very good example.

If i use Diep's evaluation function to order moves, it reduces around 20% nodes. So the effect isn't exponential as far as i can see, it's seemingly reasonable constant reduction in nodes.

However using evaluation function in all innernodes - that's just TOO EXPENSIVE, in terms of system time. that slows down the engine over factor 2...

So this is something you have to keep in mind as well - how much do you want to slow down?

If you slow down, you MUST win it back somewhere.

A huge evaluation function of Diep will NEVER win any game against any other engine, if it isn't a superior evaluation of course, as i always get outsearched movedepth wise...

Now of course to some extend more modern processors are hiding the problem. Schach 3.0 for example was doing 250k nps at a P5-133Mhz. It's under 600 cycles a node at an old Pentium processor.

Diep was getting at the same hardware something like 2k-4k nps back then. Realize compilers were a lot worse back then not to mention the processor quality let alone my programming skills (i started diep in 1994 on a 386 computer, do the math). Some years later it improved with better processors, especially the pentiumpro was a big step forwards. I got 5k-10k nps on it. Say on average around a 7500k nps. It was exactly 3.0x faster than my P5-100Mhz for Diep.

Back then diep was easily 20x slower than the fast beancounters from back then.

If we look today - Diep is around 5x - 10x slower than most engines. Now to some extend that's because they use nowadays no longer assembler, yet the much slower C++ and most C++ coders here don't know very well how to write for speed as compared to the easiness you can do that in C with (i don't want a 'war' between what is the better choice for todays programmers - yet there is little discussion on speed here). C++ would really slow down Diep, as it already suffers so much from L1i misses. In C++ all those templates and classes, they just increase codesize bigtime. No way to stop that.

Realize there is a BIG speed penalty for chessknowledge. And if you use it to prune, it's most effective if you use a 'complete knowledge set', so one that doesn't ignore a specific important area. Important areas are King Safety, Pawnstructure, passers, material, center control.

If you would leave out kingsafety - your engine is gonna get mated game after game. If you leave out passers, opponents will win by means of a passer.

So it's not so easy to construct knowledge that gives significant search depth win meanwhile also winning significant elo.

sometimes you see people say: "oh i do this and i search 2 ply deeper and it gives elo". Then it appears it gives 10 elopoints to them at most. So the question then is: "would better manner of doing it not only give 2 ply deeper, yet have a much better eloscaling?"

If you get 40 ply like Stockfish does, and an eloscaling that's somewhere close to the dot, the question you should ask yourself: "aren't they doing something wrong?"

Now i'm sure they don't share this feeling, which is why they go the searching path and why i chose already in 1994 for the knowledge path.

Yet knowledge has 5 major drawbacks:

a) it eats lots of time to do it right
b) you slow down because of it, so you HAVE to win back in one or another way a lot more.
c) coding knowledge and coding heuristics is 2 different things
d) more knowledge means more testing
e) tuning gets harder

Some of the above drawbacks are so selfexplaining i won't even discuss them.

the combination of A and B is not easy simply.

Yet it's total trivial to me that knowledge path is the way to go in any complex system where you can AFFORD the programming and especially testing and tuning investment to code knowledge.

Knowledge is total unbeatable if you combine it with a decent search.

Interestingly in the financial world, traders mostly use total braindead stupid simple rules to make money. Around 99% of their logics is total braindead single line single pattern type logics.

Code: Select all

If x > y THEN action

That's not so easy in patterns in computerchess. Most patterns soon become complex.

Point C and especially D is of overwhelming importance why Diep isn't elo 4000 yet.

I simply had no money for testhardware. when i set up testmachine, my entire office got 'cleaned out' by some burglars. Stealing everything, especially harddrives. Also stand alone old broken harddrives got taken.

It was a data burglary. Cash money and new hardware components such as RAM were not taken. A 3000 euro soundsystem in front of the window - not taken. Just everything that could store data including computers.

The time of the burglary and how it was carried out, told me instantly it wasn't the normal type of robbery.

As they also stole my backup harddrives, i lost some months of source code there. This at a critical phase, namely december 2005 when i had worked very hard in diep engine. Interestingly i also lost communication logfiles which prove specific things that happened in december 2005...

You realize how vulnerable knowledge is in this respect?

To expand on point C.

In end 90s if i had a chesspattern in Diep and the other guy didn't, DANG point for Diep. Mate attack somewhere and game over.

Yet what if the pattern is not 100% correct and there is a small bug in it?

Then comes Fruit 2.1 in 2005.

Gets 17 ply search depth and unlike crafty back then it was tactical a lot stronger, so it didn't fall for easy mating attacks.

Basically it appears then that most kingsafety related knowledge is short term knowledge. If you can calculate your way out there - it's worth nothing all those penalties. yet you can lose easily GAMES on overestimating an open file to the opponent king, to give one example.

That's in huge contrast with 90s where even if the pattern sucked ass, to say it really polite, a pattern still WON GAMES.

Stefan Meyer Kahlen world champs 2004: "If your engine knows something someone else doesn't, you win everything"

Where i agree with the statement, there is howeve a lot of constraints to that.

The real important thing is point C. there is a huge difference between a heuristic that's sometimes true and knowledge that's nearly always true.

Material is for example nearly always true. If you get 30 plies and after 30 plies from now you're still that piece up - you probably will win.

So material evaluation we can definitely label as 'knowledge'. It is nearly always true.

We see however that in games of the titled players, how they play into positions where the notion of material is less interesting and where strategic and attacking type motives are important.

So that 1% misevaluated positions, that's defining entirely how strong your engine is.

Yesterday Diep's biggest fan found a position where Diep scores in its evaluation function the positoin as +0.6 for white default and after 1 move it's +0.9.

All the rybka beancounters, including houdini they're with search within 0.2 to 0.4

A single pattern in that position, which i coded in 1994, is causing this in Diep.

So basically it's not a bug, but it's just total not tuned to todays standards.

Tuning is of overwhelming importance now. You need massive hardware for it. Testing your engine very well, that's entirely possible. For tuning the parameters accurate, that's gonna require a lot more cores.

I've got 1000 cores available here for tuning... ...yes that's nvidia Tesla cores

(The idea appeared also attractive to me because it seems rather easy to implement and check - only calculation time , but no need for fine tuning: let the search engine analyse many positions with and without the "rule advisor" - the results in terms of found move and evaluation must be the same.)

Maybe my idea can be buried completely with a rough estimation?
If the "rule advisor" could reliable point out 25% of the moves as bad (lets simply assume it were the moves which are coming at the end of the move list):
how much smaller would the search tree be?
Since if the last quarter of the moves in an iteration account for in average 5% of the tree - it would be obvious that the effort isn't worth it.


Thanks again,
Thomas

-