Don wrote:bob wrote:Don wrote:bob wrote:Don wrote:bob wrote:Don wrote:AlvaroBegue wrote:The Kolmogorov complexity of all tablebases is at most the length of a naive minimax searcher that gives the right answer for each position. But that's not a very practical representation of the knowledge.
Of course, that is a good point.
So obviously what one would need for a given ending is something that specialized in that ending and scored it correctly with minimal CPU and memory overhead.
When I started to work on KRPvsKR I noticed that simple rules were almost always right UNLESS there was some immediate tactical issue involved. In some cases you would have a "winning" pattern except that the opponent could check your king and win your rook! When I tried to code this up with rules I kept finding more an more exceptions due mostly to tactics that wee very shallow. I gave up without trying to hard - but the general process was to make up a rule and have the database show me the first exception, then try to cover that, etc ..... The code took the form of a hand coded decision tree.
I believe it might be easier to build a specialized search that might do the trick however. The question is whether it would beat a real database, trading cache and some disk access for computation time. It would still be appealing for people to have a program that does not require gig's of database to have the equivalent.
What I took away from this is that you could probably write a specialized evaluation function for KRP vs KR that would not be perfect, but would probably still outperform a bit-base in the tree. You can always use a real database when the position occurs at the root. I don't know about other endings - some of them are more profound.
I don't think KRP vs KR is very hard. One CAN depend on the search to expose the tactical issues, and if you reach a KRP vs KR after a deep search, I think you can safely assume nothing is hanging. My eval for KRPKR is pretty simple, yet it does work well enough in testing. Might be interesting to give it some hard positions and have it play against an EGTB version to see if it can draw when it should, and win when it should. I"ve done this with classic KRBK and KQKR type positions and have found zero failures for those rather easy endings.
I think all modern engines of Crafty's calibre will play this ending correctly
once you get into them, but that is not the real power of these databases. The real power is when they are incorporated into the tree search.
You probably don't remember this, but you, I and John Stanback had this same discussion 20 years ago, 1993 in Indianapolis with respect to the king and pawn vs king database. We both had this tiny database built into our programs but you were critical of the idea, saying that this ending could be trivially handled with a king opposition rule and bonus for keeping the king in front of the pawn and therefore no database was needed.
KPK is trivial to do with bitbases, and trivial to do with an eval term. KRPKR is not so trivial for bit bases, and is still pretty easy to code as a special case.
I'm not sure I would lump them into the same discussion...
The principle is no different so it's completely relevant. You were basically claiming in 1993 that if you have enough evaluation in the program that it can manage to play some ending correctly, then no database is needed to know if it's a win, loss or draw.
When this incident happened in 1993 the discussion was short but John and I just couldn't believe that you didn't see a distinction. The main reason it stands out so clearly to me was how bizarre it seemed to me that you are a giant in computer chess and couldn't understand that.
After thinking about more I had to conclude that it was silly for you not to understand that you probably were too focused on what you wanted to say to listen to us in this case (just as I do sometimes.) But this discussion does give me a very strong sense of Déjà vu over this, some 20 years later!
Two issues here.
1. Does this improve your program? No. Elo gain = 0. Measured with > 100000 games, in fact.
There is no improvement to Komodo that I could measure for having this database.
I don't see what that has to do with this discussion though. This is a totally unrelated point. The point is that end node evaluation is not the same as root node searching and you would not acknowledge that.
Here I don't follow, because we were using Ken's tables back then. I don't know if I specifically used them in that game or tournament, as it was not always easy to get them copied to the specific machine I was using, since the machines were getting reformatted many times during their testing cycles.
I understood the idea of having exact scores deep in the tree. Because even without Ken's databases, we had the KPK evaluation code in Cray Blitz, and that was certainly done out at the tips, and not inside the tree.
So perhaps I misunderstand exactly what you are talking about?
2. Then why do it at all (either with bitbase or eval term)? So that you don't look stupid when that VERY rare KPK game comes up. In all the games I have watched over 40+ years of doing this, I have NEVER seen my program reach a KPK ending. Since most of those are won positions, not evaluating it correctly is not critical, the side with the pawn generally wins, when you think of all the possible squares the kings and pawn can occupy. But for me, the answer was "to avoid looking stupid SHOULD it come up." Sort of like bishop under-promotions. Or knight underpromotions. We had a long discussion about this at Supercomputing 92, where the ACM event was held. Burt Wendroff didn't do under-promotions and we were talking about it with him and Tony (Warnock, other Lachex author). I forget who they were playing (event was in Albuquerque, maybe 100 miles from Los Alamos where Burt lived / worked) but Burt left early right after having this discussion where his ultimate defense was "it has never happened". Before he got home, Lachex lost in a won position, because it didn't notice the knight underpromotion that was a check that killed.
In any case, having or not having this knowledge, whether it be bit base format or just static evaluation, really doesn't matter. If you are measuring Elo.
A lot of people believe that databases don't improve the program strength anyway, or least if it does it is very hard to measure. But that has nothing to do with discussions about how to integrate database knowledge into the search. One could argue about whether you SHOULD but that is a whole different discussion.
I am one of those. I've tested extensively (only using 3-4-5 however) and found exactly zero improvement, and a few of the tests even show slight harm being done, if you start off in endgame positions to begin with, because of the slow-down.
It's still interesting because it is easy to construct positions where this knowledge is crucial to making the right decision and people want their program to be able to see that.
In the case of the king and pawn database, even though this is not relevant to this discussion I would like to say it does improve the strength of the program, you just cannot measure it because it turns out the benefit is just too small to easily measure. In Komodo's case I completely avoid calling the evaluation in favor of a much faster routine that looks up the answer in a tiny table.
"much faster" might be a bit of a stretch since the code is quite small and simple...
My point about bitbases back then was memory. Memory was not exactly "plentiful". 45kb or so was not insignificant. Our main campus computer had 512kb of RAM. Our Vax had 4mb. The static eval code is FAR smaller than the bit base representation. It's also a bit slower, but the rules are so simple it is likely impossible to measure the speed difference. Today, who really cares about 45kb? But in 1992 it was not something to toss out without due consideration.
You never once raised the issue of performance trade-offs. But I have a very difficult time swallowing this one unless the Cray machine you used in 1993 was less powerful than the PC I was using. In fact I think every program there was using hash tables. If you tell me Cray Blitz didn't have enough memory for hash table I guess I have no choice but to believe you. But even in 1993 a 24k table was not that big a deal.
I do not remember the machine. But remember, MOST of my development and testing was not on the Cray. It was on our campus machines. And Harry's bitboard attack stuff (with a REALLY large array) made us count bytes everywhere else to get the machine to fit on the Vax or Xerox box. If it couldn't run there, we never even tried as that was always the first stop.
Still, it's not even relevant because John and I explained carefully how it could be used to evaluate positions at END NODES as to whether they were WINS or DRAWS and you just kept repeating that you evaluation all position including king and pawn. You never made an argument about whether it was good tradeoff and I would think being a professor you would be able to make yourself clea
Anyway, let's consider this closed. I KNOW that you understand the difference and that is all that matters. We both agree that the value for this particular ending is limited to cosmetics and debating about what you meant 20 years ago is silly.
I don't remember the discussion, and really don't remember John being there at that event at all... much less discussing endgame databases vs w/l/d databases...