KPK bitbase

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20636
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: KPK bitbase

Post by bob » Fri Jan 18, 2013 5:55 pm

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.

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.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: KPK bitbase

Post by Don » Fri Jan 18, 2013 7:37 pm

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.

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.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: KPK bitbase

Post by Gerd Isenberg » Fri Jan 18, 2013 7:58 pm

bob wrote: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. :)
Thanks for the hint, it was November 1991 ...
[pgn]
[Event "ACM 1991"]
[Site "Albuquerque USA"]
[Date "1991.11.12"]
[Round "2"]
[White "Mephisto"]
[Black "Lachex"]
[Result "1-0"]

1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.O-O Nxe4 6.d4 b5 7.Bb3 d5 8.dxe5 Be6 9.Nbd2 Nc5 10.c3 d4 11.Bxe6 Nxe6 12.cxd4 Ncxd4 13.Ne4 Be7 14.Be3 Nf5 15.Qc2 O-O 16.Nf6+ Bxf6 17.Qxf5 Be7 18.Rfd1 Qc8 19.Rd2 c5 20.Rad1 Qc6 21.b3 Rad8 22.h3 c4 23.bxc4 bxc4 24.Nd4 Nxd4 25.Rxd4 c3 26.Rc1 Ba3 27.Rc2 Bb2 28.Qe4 Qe6 29.Ra4 Rd1+ 30.Kh2 Rfd8 31.Rc4 Rc8 32.Rxc8+ Qxc8 33.a4 Ra1 34.Bb6 Qe8 35.a5 Ra4 36.Qd5 Rb4 37.Qd6 Rc4 38.Kg1 h6 39.Qd3 Ra4 40.Qd6 Re4 41.Bc7 Re1+ 42.Kh2 Qc8 43.Qb6 Qf5 44.Qb8+ Kh7 45.e6 Qxc2 46.exf7 Ba3 47.Qg8+ Kg6 48.Qe8 Qe4 49.f8=N+ Kf6 50.Nd7+ Kg5 1-0
[/pgn]

bob
Posts: 20636
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: KPK bitbase

Post by bob » Fri Jan 18, 2013 8:29 pm

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

bob
Posts: 20636
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: KPK bitbase

Post by bob » Fri Jan 18, 2013 8:31 pm

Gerd Isenberg wrote:
bob wrote: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. :)
Thanks for the hint, it was November 1991 ...
[pgn]
[Event "ACM 1991"]
[Site "Albuquerque USA"]
[Date "1991.11.12"]
[Round "2"]
[White "Mephisto"]
[Black "Lachex"]
[Result "1-0"]

1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.O-O Nxe4 6.d4 b5 7.Bb3 d5 8.dxe5 Be6 9.Nbd2 Nc5 10.c3 d4 11.Bxe6 Nxe6 12.cxd4 Ncxd4 13.Ne4 Be7 14.Be3 Nf5 15.Qc2 O-O 16.Nf6+ Bxf6 17.Qxf5 Be7 18.Rfd1 Qc8 19.Rd2 c5 20.Rad1 Qc6 21.b3 Rad8 22.h3 c4 23.bxc4 bxc4 24.Nd4 Nxd4 25.Rxd4 c3 26.Rc1 Ba3 27.Rc2 Bb2 28.Qe4 Qe6 29.Ra4 Rd1+ 30.Kh2 Rfd8 31.Rc4 Rc8 32.Rxc8+ Qxc8 33.a4 Ra1 34.Bb6 Qe8 35.a5 Ra4 36.Qd5 Rb4 37.Qd6 Rc4 38.Kg1 h6 39.Qd3 Ra4 40.Qd6 Re4 41.Bc7 Re1+ 42.Kh2 Qc8 43.Qb6 Qf5 44.Qb8+ Kh7 45.e6 Qxc2 46.exf7 Ba3 47.Qg8+ Kg6 48.Qe8 Qe4 49.f8=N+ Kf6 50.Nd7+ Kg5 1-0
[/pgn]
Not so good. I thought it was 92. :) But in 20 years, that is only a 5% tolerance. :)

Bob

It was funny to watch, and we made a collective conference call to burt at home to tell him.. :)

Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: KPK bitbase

Post by Gerd Isenberg » Fri Jan 18, 2013 8:44 pm

bob wrote: Not so good. I thought it was 92. :) But in 20 years, that is only a 5% tolerance. :)

Bob
Even less for November 1991. Somehow ACM switched the cycle to February 1993.
bob wrote: It was funny to watch, and we made a collective conference call to burt at home to tell him.. :)
hehehe ...

bob
Posts: 20636
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: KPK bitbase

Post by bob » Fri Jan 18, 2013 9:06 pm

Gerd Isenberg wrote:
bob wrote: Not so good. I thought it was 92. :) But in 20 years, that is only a 5% tolerance. :)

Bob
Even less for November 1991. Somehow ACM switched the cycle to February 1993.
bob wrote: It was funny to watch, and we made a collective conference call to burt at home to tell him.. :)
hehehe ...
Burt had gone nutso with efficiency in Lachex. All in asm. All very fast. And he intentionally left out underpromotions as unnecessary. Others have also done that (Rybka being one well-known example, among others). It is OK to ignore it, until it bites you. :)

I remember Tony's words on that phone call. "you remember that underpromotion discussion/argument we were having when you left, and you said 'when it bites me I will consider fixing it?' Well it just bit us." :)

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: KPK bitbase

Post by Don » Fri Jan 18, 2013 10:04 pm

bob wrote:
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?
I concluded later that you must have. There is no question in my mind about whether you understood the concept - in fact that is what made the whole experience so bizarre.

I regret bringing this up because it was wrong for me to do so if you do not remember. You are not in a position to defend yourself because you don't even remember the situation. I get mad as a hornet when someone tasks me with defending something they say I said but I cannot remember saying and do not believe I said.


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.
I think their primary value is in playing out the game once you are IN a particular ending and for people who like to use computers to analyze positions that have a real chance of moving into these.

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 evaluation is quite slow so this is much faster, but it's something that is called so rarely that being much faster is not a big deal.


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...
My memory of the whole event is razor sharp because my interest in computer chess at the time was super high and I had won that event.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

From my old program Spector in 1994

Post by sje » Tue Jan 22, 2013 1:41 am

Code: Select all

Summary for TB/KPK.tbw (WTM):

Score        Sp        Sp/unfold Tp        Tp/unfold Ap        Ap/unfold
------------ --------- --------- --------- --------- --------- ---------
Even             19184     38368      1338      2676     20522     41044
MateIn28             3         6         0         0         3         6
MateIn27             7        14         0         0         7        14
MateIn26            19        38         0         0        19        38
MateIn25            64       128         0         0        64       128
MateIn24           144       288         0         0       144       288
MateIn23           343       686         0         0       343       686
MateIn22           562      1124         0         0       562      1124
MateIn21           606      1212         0         0       606      1212
MateIn20           558      1116         0         0       558      1116
MateIn19           658      1316         0         0       658      1316
MateIn18           871      1742         0         0       871      1742
MateIn17          1066      2132         0         0      1066      2132
MateIn16          1154      2308         0         0      1154      2308
MateIn15          1065      2130         0         0      1065      2130
MateIn14          3829      7658         0         0      3829      7658
MateIn13          6719     13438         0         0      6719     13438
MateIn12          8178     16356         0         0      8178     16356
MateIn11          8601     17202         0         0      8601     17202
MateIn10          8395     16790         0         0      8395     16790
MateIn9           7541     15082         0         0      7541     15082
MateIn8           5647     11294         0         0      5647     11294
MateIn7           3121      6242         0         0      3121      6242
MateIn6           1636      3272         0         0      1636      3272
MateIn5            915      1830         0         0       915      1830
MateIn4            422       844         0         0       422       844
MateIn3            219       438         0         0       219       438
MateIn2             97       194         0         0        97       194
MateIn1             40        80         0         0        40        80
Bust             27704     55408     20366     40732     48070     96140

Entry count: 131072
Entry count (unfolded): 262144

Longest mate score (WTM): MateIn28
Sample WTM longest mating position: 8/8/8/6k1/8/8/1P4K1/8 w - - 0 1

Optimal move sequence from the above WTM longest mating position:

1. Kg3 Kf5 2. Kf3 Ke5 3. Ke3 Kd5 4. Kd3 Kc5 5. Kc3 Kb5 6. Kb3 Ka5 {Ka6 Kc5 Kc6}
7. Kc4 Kb6 8. Kb4 Ka6 {Ka7 Kc6 Kc7} 9. Kc5 Kb7 10. Kb5 Ka7 11. Kc6 Ka8 12. Kb6
{b4} Kb8 13. b3 {b4} Ka8 {Kc8} 14. b4 Kb8 15. b5 Kc8 16. Ka7 Kc7 {Kd7 Kd8} 17.
b6+ Kc6 {Kd6 Kd7} 18. b7 Kd5 19. Kb6 {b8=Q} Kd4 {Ke4 Ke5 Ke6} 20. Kc6 {b8=Q}
Kc3 {Kc4 Kd3 Ke3 Ke4 Ke5} 21. Kd5 {b8=Q} Kb4 {Kd2 Kd3} 22. Kd4 {b8=Q+} Kb5 23.
b8=Q+ Kc6 24. Qd8 Kb5 25. Qc7 {Qd6 Qd7+ Qf6} Ka4 {Ka6 Kb4} 26. Kc4 {Qb6 Qb7
Qb8} Ka3 27. Qh2 Ka4 28. Qa2#

No WTM non-transition lose positions exist.

Summary for TB/KPK.tbb (BTM):

Score        Sp        Sp/unfold Tp        Tp/unfold Ap        Ap/unfold
------------ --------- --------- --------- --------- --------- ---------
Even             47876     95752       996      1992     48872     97744
Bust             12690     25380      7724     15448     20414     40828
Checkmated           0         0        42        84        42        84
LoseIn1              9        18        55       110        64       128
LoseIn2             23        46       140       280       163       326
LoseIn3             64       128       342       684       406       812
LoseIn4            153       306       668      1336       821      1642
LoseIn5            332       664      1366      2732      1698      3396
LoseIn6            812      1624      2312      4624      3124      6248
LoseIn7           2089      4178      3752      7504      5841     11682
LoseIn8           4226      8452      3377      6754      7603     15206
LoseIn9           7180     14360       930      1860      8110     16220
LoseIn10          7857     15714         0         0      7857     15714
LoseIn11          7215     14430         0         0      7215     14430
LoseIn12          5843     11686         0         0      5843     11686
LoseIn13          4185      8370         0         0      4185      8370
LoseIn14          2501      5002         0         0      2501      5002
LoseIn15          1026      2052         0         0      1026      2052
LoseIn16          1194      2388         0         0      1194      2388
LoseIn17           902      1804         0         0       902      1804
LoseIn18           711      1422         0         0       711      1422
LoseIn19           597      1194         0         0       597      1194
LoseIn20           436       872         0         0       436       872
LoseIn21           565      1130         0         0       565      1130
LoseIn22           430       860         0         0       430       860
LoseIn23           292       584         0         0       292       584
LoseIn24           109       218         0         0       109       218
LoseIn25            31        62         0         0        31        62
LoseIn26            14        28         0         0        14        28
LoseIn27             4         8         0         0         4         8
LoseIn28             2         4         0         0         2         4

Entry count: 131072
Entry count (unfolded): 262144

No BTM non-transition mate positions exist.

Longest lose score (BTM): LoseIn28
Sample BTM longest losing position: 8/8/8/7k/8/7K/1P6/8 b - - 0 1

Optimal move sequence from the above BTM longest losing position:

1... Kg5 2. Kg3 Kf5 3. Kf3 Ke5 4. Ke3 Kd5 5. Kd3 Kc5 6. Kc3 Kb5 7. Kb3 Ka5 {Ka6
Kc5 Kc6} 8. Kc4 Kb6 9. Kb4 Ka6 {Ka7 Kc6 Kc7} 10. Kc5 Kb7 11. Kb5 Ka7 12. Kc6
Ka8 13. Kb6 {b4} Kb8 14. b3 {b4} Ka8 {Kc8} 15. b4 Kb8 16. b5 Kc8 17. Ka7 Kc7
{Kd7 Kd8} 18. b6+ Kc6 {Kd6 Kd7} 19. b7 Kd5 20. Kb6 {b8=Q} Kd4 {Ke4 Ke5 Ke6} 21.
Kc6 {b8=Q} Kc3 {Kc4 Kd3 Ke3 Ke4 Ke5} 22. Kd5 {b8=Q} Kb4 {Kd2 Kd3} 23. Kd4
{b8=Q+} Kb5 24. b8=Q+ Kc6 25. Qd8 Kb5 26. Qc7 {Qd6 Qd7+ Qf6} Ka4 {Ka6 Kb4} 27.
Kc4 {Qb6 Qb7 Qb8} Ka3 28. Qh2 Ka4 29. Qa2#

Post Reply