KPK bitbase

[AlvaroBegue]

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.

[Don]

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.

[bob]

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.

[Don]

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.

[wgarvin]

In the mid 90's, the DarkThought engine had bitbases in RAM for all 3- and 4-man endings. They used the bitbases plus a heuristic scoring function, and because they were in RAM it could consult them everywhere in the search tree whenever it saw a position with <5 men.

Nowadays you could do the same thing for 5-man endings, especially if the bitbases could be compressed in a form that is easy to randomly access (e.g. a decision-tree plus a bitbase of exceptional positions, or something). You need the heuristic scoring function to drive the engine towards the win in a won position (so it doesn't lose by 50-move rule).

Assuming you had some W/L/D function (bitbase, decision-tree, whatever) + heuristic scoring function, for a particular ending. You could generate a "proof database" for that ending using retrograde analysis. Just like generating a tablebase, except one side would always use your custom strategy to choose 1 successor move (the same one the engine chooses with it). The other side would look at all successors and choose minimum DTZ, so it will play optimally against this custom strategy and automatically exploit any weaknesses in it. Then you can compare the "proof database" to an ordinary tablebase or bitbase, to find any positions your custom strategy classifies with the wrong W/L/D result, and any positions that are supposed to be won, but which your custom strategy can't win within the limits of the 50-move rule (i.e. its heuristic scoring function doesn't steer it strongly enough to the right moves, so it ends up taking more moves than necessary and gets a draw).

This "proof database" could be used to prove that the custom strategy was just as good as playing the ending using a full tablebase (i.e. it could win every won position, and draw every non-lost position). Or if that turns out to be false, maybe the info from the "proof database" would be useful to help figure out what needs to be modified or augmented in the custom strategy. (e.g. you could make a sparse database of specific positions where the scoring heuristic causes it to pick lousy moves, and put just enough data into this sparse database so that it can win every should-be-won position within 50 moves).

There seems to be more interest in endgame recognizers and bitbases now than even 5 years ago, which is nice. I got the "proof database" idea around 14 years ago and I'm pretty sure I've written babbling posts here about it before, maybe not for several years though!

[bob]

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...

[Maarten]

Thank you all for your comments.
So there are (at least) 2 ways to implement the KPK bitbase:
1. Generate the KPK bitbase at startup of the program (like Stockfish)
2. Precompute a lookup table, and load the table at startup (like OpenCritter, Komodo)

I should have stated my objectives for my KPK bitbase unit:
1. Generate a 100% correct KPK bitbase.
2. Fast lookup for the mailbox engine can probe the KPK bitbase efficient during eval.
3. Non-bitboard, for the lazy programmer
4. Low system footprint. The 24 kb memory footprint is sufficient; reducing it to 12 Kb is to me an academic problem.
5. No/minimal dependency on other software components, like as in Delfi 5.1 using a zlib compression library; in Stockfish bitboard attack tables are required, in OpenCritter a decompression routine is called on the data, so there must be somewhere a compression routine. The only dependency I have is on a max() function, and some type definitions.

At first my idea was to compute a lookup table once an store the bitbase as a constant array in the program, along the line as in OpenCritter, however when I got the generation time reduced from 13 seconds to 55 milliseconds I opted for the “Generate” approach, which is to me a more elegant solution: I have to maintain only one 1 object (the engine) and not 3: the KPK bitbase computation program, the engine and the interface between the two, probably me doing cut and paste and some editing. Somewhere in the past I already lost my book generation program (moving house/computer/HD crash/you_name_it), it is still on my todo list.
At least I've shown that implementing more rules in the static eval of KPK positions improves generation time, as an average programmer doing something faster than Stockfish is not an every day event.

Do you have exact Win/Draw statistics for your KPK bitbase? Otherwise I would appreciate receiving a copy!

@Gerd, thanks for your kind words and CPW!

Regards, Maarten

[Don]

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!

[bob]

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.

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.

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.

[Don]

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.

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.

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.

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.

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 clear.

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.