endgame databases
Robert Hyatt
We are getting close to be ready to distribute some "new" databases that
can initially only be used in Crafty, but I assume that other freeware programs
will use them once they grab the "probe" code I am going to do for Crafty.
First, why a new tablebase format? There are several answers. (1) the
new format handles en passant correctly, which means we can do things like
kpp vs kp now without having to exclude probes when en passant is ever
going to be possible. So this will be "clean." (2) Eugene has done a
cute indexing scheme that reduces the size of the file significantly from
the original "tablebase" format. His sample "probe" code will supposedly
probe the new (and old) formats if compiled properly, although I obviously
haven't checked this out yet. But he writes good code so I wouldn't expect
any problems. In fact, his sample probe code is really nice in the area of
caching, and lets you specify the amount of memory to reserve for TB
caching (under unix this is probably not important but it will save a
little even there.) (3) his code allows the tb files to reside in
multiple directories, a common request from you "operating system
challenged folks" (aka windows users. :) ) Now you can put em all over
your multiple 2 gig partitions with no problems, where us unix folks have
been using symbolic links for this from day one.
Second, why the notice now? I am going to (shortly) replace the original
SJE tablebases with the new format. And the demand for them is going to be
high. I'd like to find a couple of places around the world that have good
transfer times from my ftp machine, and for a while, perhaps mirror the
tablebases there to ease the downloading crunch and speed it up for
everyone, hopefully. How much space? Good question. What I currently have
on my ftp (all 3/4 piece files, plus KRP and derivatives) take about 400Mb.
Eugene's will be smaller, but we are going to make more available at the
same time. I consider what I have now to be the "starter" set that is
probably the most important ones available (KRP vs KR is pretty common in
crafty's play).
If you have a quick link to me, and have disk space (permanent or temp for
a month or two) let me know and we can get this to going. Be nice to do
EP captures finally, plus smaller files as well...
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Ernst A. Heinz
> We are getting close to be ready to distribute some "new" databases that
> can initially only be used in Crafty, but I assume that other freeware programs
> will use them once they grab the "probe" code I am going to do for Crafty.
>
> [...]
I like to add due credits to ***** Eugene Nalimov ***** for this because
the new tablebases are his creation and deserve to be named after him.
Please let nobody forget what they owe to Eugene in this respect!
Eugene wrote a cute new tablebase generator and according indexing/probe
code that produce much smaller databases than Edwards' originals and also
handle en-passant correctly. I was so lucky as to being involved in the
design of the index scheme as well and was a beta-tester of his generator
under Digital Unix. All I can say about the new endgame databases is that
they are absolutely great.
Thank you very much for this fine piece of work and for making it publicly
available, Eugene!
=Ernst=
+----------------------------------------------------------------------------+
| Ernst A. Heinz, School of CS (IPD), Univ. of Karlsruhe, P.O. Box 6980, |
| D-76128 Karlsruhe, F.R. Germany. WWW: <http://wwwipd.ira.uka.de/~heinze> |
| E-Mail: <hei...@ira.uka.de> Tel. / Fax: +49-(0)721-6084386 / 6087343 |
+----------------------------------------------------------------------------+
"It has recently been found out that research causes cancer in rats!"
Ren Wu
wrote:
>
>We are getting close to be ready to distribute some "new" databases that
>can initially only be used in Crafty, but I assume that other freeware programs
>will use them once they grab the "probe" code I am going to do for Crafty.
>
>First, why a new tablebase format? There are several answers. (1) the
>new format handles en passant correctly, which means we can do things like
>kpp vs kp now without having to exclude probes when en passant is ever
>going to be possible. So this will be "clean."
Hi, Bob
Can you outline how he manage to solve en passant problem? Thanks.
Ren.
- delete one iname if you reply by email
Robert Hyatt
: Bob Hyatt wrote:
:> We are getting close to be ready to distribute some "new" databases that
:> can initially only be used in Crafty, but I assume that other freeware programs
:> will use them once they grab the "probe" code I am going to do for Crafty.
:>
:> [...]
: I like to add due credits to ***** Eugene Nalimov ***** for this because
: the new tablebases are his creation and deserve to be named after him.
I hope I didn't slight him. Most have seen the name here several times,
and I've mentioned it several times, including in the text below. Hope it
was clear that *I* didn't write this and wasn't trying to imply that I did.
I hope...
Robert Hyatt
: On 13 Oct 1998 19:08:28 GMT, Robert Hyatt <hy...@crafty.cis.uab.edu>
: wrote:
:>
:>We are getting close to be ready to distribute some "new" databases that
:>can initially only be used in Crafty, but I assume that other freeware programs
:>will use them once they grab the "probe" code I am going to do for Crafty.
:>
:>First, why a new tablebase format? There are several answers. (1) the
:>new format handles en passant correctly, which means we can do things like
:>kpp vs kp now without having to exclude probes when en passant is ever
:>going to be possible. So this will be "clean."
: Hi, Bob
: Can you outline how he manage to solve en passant problem? Thanks.
No. I know how I did it a long time ago when I played with these things
on the Cray, late 80's, in that I used the impossible squares (first rank
for example) for a pawn that can be captured enpassant. There was some
ugly fakery that went along with this, but it worked for kpkp. I have not
yet looked carefully at Eugene's code, as I just got the thing to compile
using gcc, and am trying to work on the probe mechanism.
I'm sure he'll explain it if asked here, however...
Chris Whittington
Robert Hyatt wrote in message <700kff$m1t$6...@juniper.cis.uab.edu>...
>Ren Wu <re...@iname.iname.com> wrote:
>: On 13 Oct 1998 19:08:28 GMT, Robert Hyatt <hy...@crafty.cis.uab.edu>
>: wrote:
>
>:>
>:>We are getting close to be ready to distribute some "new" databases that
>:>can initially only be used in Crafty, but I assume that other freeware
programs
>:>will use them once they grab the "probe" code I am going to do for
Crafty.
>:>
>:>First, why a new tablebase format? There are several answers. (1) the
>:>new format handles en passant correctly, which means we can do things
like
>:>kpp vs kp now without having to exclude probes when en passant is ever
>:>going to be possible. So this will be "clean."
>
>: Hi, Bob
>
>: Can you outline how he manage to solve en passant problem? Thanks.
>
>No. I know how I did it a long time ago when I played with these things
>on the Cray, late 80's, in that I used the impossible squares (first rank
>for example) for a pawn that can be captured enpassant. There was some
>ugly fakery that went along with this, but it worked for kpkp. I have not
>yet looked carefully at Eugene's code, as I just got the thing to compile
>using gcc, and am trying to work on the probe mechanism.
>
>I'm sure he'll explain it if asked here, however...
>
Based on a relatively cursory look ...
If the previous move was a double pawn push to a specific square, then this
info is passed to the egtb lookup device. Basically it means that two-pawn
endings (there need to be at least one pawn per side) require more space to
cover these extra eventualities. In the grand scheme of things, such
tablebases are rare in 4-man, kpkp being the only one, and relatively rare
in 5-man (I don't mean rare as chess positions, but rare as tablebases) - so
the extra space required is only specific to kxpkp and kpkp.
And, it seems to me, that en passent table bases are not needed within the
tree, only at the root. eg only when the root position is down to 5 or fewer
men.
For reasons that should be obvious, it is only necessary to make a tablebase
lookup in the tree after there has been a *capture* down to 5 or 4 men (ie a
reduction from a non-tablebase situation into a tablebase situation).
Since a *capture* can never give rise to an immediately subsequent en
passent, an en passent situation with tablebases can never arise within the
tree. And since they can only arise at the root; I don't actually see the
purpose of expending space (albeit not huge) on coding en passent into the
tablebase format. Just search any potential en passent root position one
move deep and use the info from the non-en passent situations that will
arise one move on. Maybe this would create a requirement to search another
10 nodes or so every now and again. Hardly very problematic.
So why bother to do the en passent at all ? Or am I missing something ?
Notwithstanding, also hearty contratulations to Eugene as well. Obviously
this tablebase data should be called the Eugene Nalimov tablebases. Or en
egtb. As in en passent :)))
Chris Whittington
Robert Hyatt
: Based on a relatively cursory look ...
: If the previous move was a double pawn push to a specific square, then this
: info is passed to the egtb lookup device. Basically it means that two-pawn
: endings (there need to be at least one pawn per side) require more space to
: cover these extra eventualities. In the grand scheme of things, such
: tablebases are rare in 4-man, kpkp being the only one, and relatively rare
: in 5-man (I don't mean rare as chess positions, but rare as tablebases) - so
: the extra space required is only specific to kxpkp and kpkp.
: And, it seems to me, that en passent table bases are not needed within the
: tree, only at the root. eg only when the root position is down to 5 or fewer
: men.
: For reasons that should be obvious, it is only necessary to make a tablebase
: lookup in the tree after there has been a *capture* down to 5 or 4 men (ie a
: reduction from a non-tablebase situation into a tablebase situation).
: Since a *capture* can never give rise to an immediately subsequent en
: passent, an en passent situation with tablebases can never arise within the
: tree. And since they can only arise at the root; I don't actually see the
: purpose of expending space (albeit not huge) on coding en passent into the
: tablebase format. Just search any potential en passent root position one
: move deep and use the info from the non-en passent situations that will
: arise one move on. Maybe this would create a requirement to search another
: 10 nodes or so every now and again. Hardly very problematic.
: So why bother to do the en passent at all ? Or am I missing something ?
You miss one case: I have a pawn on g2, you have a pawn on f7. I can't
look this one up in the database if it didn't include enpassant when it
was built (I have this problem not in KPKP from Steven's generator) because
at some point, one side can play g2-g4 or f7-f5, and the database will
produce the wrong result *on that move*. Which means that the original
position I described may appear to be won for one side after (say)
g2-g4, king move, f4-f5, f7-f5 and the database concludes white (or
black) wins here..
In crafty, I have to (currently) specifically *not* probe, even at the
root, if the position can *ever* produce an enpassant capture (for KPKP
pawns can't be on adjacent files, or if they are, they must have already
"passed and ep can not be possible on current move, before I can probe.
: Notwithstanding, also hearty contratulations to Eugene as well. Obviously
: this tablebase data should be called the Eugene Nalimov tablebases. Or en
: egtb. As in en passent :)))
If you look at search.c in Crafty, you will spot the kludge to avoid
getting stung by the ep bug. That gets tossed out, finally...
: Chris Whittington
Chris Whittington
Robert Hyatt wrote in message <7024mn$427$2...@juniper.cis.uab.edu>...
Yup. Ok. You need to know about the position when it's doing a database
build. But then, after the build, the ep positions can be junked
(effectively if the indexing for ep is such as to put the ep positions all
at the end of the data).
Then space gets saved, at the cost of having to search *root* positions that
are ep possible to a depth of one ply. As I pointed out this costs about 10
nodes for maybe 2 or 3 game positions out of an entire game. Eg a cost of
0.0000000000000000000000000001 % in search time at a saving of how much hard
drive space and/or cache ?
>
>In crafty, I have to (currently) specifically *not* probe, even at the
>root, if the position can *ever* produce an enpassant capture (for KPKP
>pawns can't be on adjacent files, or if they are, they must have already
>"passed and ep can not be possible on current move, before I can probe.
Understood. The new format gets around that. But the new format with ep
entries junked for the distribution data would be even better, no ?
Eugene ? Is it worth considering, or is the saving inconsequential ?
>
>: Notwithstanding, also hearty contratulations to Eugene as well. Obviously
>: this tablebase data should be called the Eugene Nalimov tablebases. Or en
>: egtb. As in en passent :)))
>
>If you look at search.c in Crafty, you will spot the kludge to avoid
>getting stung by the ep bug. That gets tossed out, finally...
>
Understood. Any more bugs nobody thought of ? :))
Chris Whittington
Robert Hyatt
: Yup. Ok. You need to know about the position when it's doing a database
: build. But then, after the build, the ep positions can be junked
: (effectively if the indexing for ep is such as to put the ep positions all
: at the end of the data).
: Then space gets saved, at the cost of having to search *root* positions that
: are ep possible to a depth of one ply. As I pointed out this costs about 10
: nodes for maybe 2 or 3 game positions out of an entire game. Eg a cost of
: 0.0000000000000000000000000001 % in search time at a saving of how much hard
: drive space and/or cache ?
I think Eugene said something like 1% overhead in space for this. But it
still has to be stored in the database unless you want to ensure that when
you do a probe no EP is possible in that position.
In my case, I would *never* probe with an EP possible, because I only
probe *after* captures that take me to 5-4-3 piece endings. And there,
this overhead is wasted. But then there are database programs what probe
these things as well, and they might not have search capability.
I'm neutral on storing EP results since it doesn't help/hurt me at all,
normally, while near the root I'd have to be sure no EP is possible before
probing. Easy enough...
:>
:>In crafty, I have to (currently) specifically *not* probe, even at the
:>root, if the position can *ever* produce an enpassant capture (for KPKP
:>pawns can't be on adjacent files, or if they are, they must have already
:>"passed and ep can not be possible on current move, before I can probe.
: Understood. The new format gets around that. But the new format with ep
: entries junked for the distribution data would be even better, no ?
: Eugene ? Is it worth considering, or is the saving inconsequential ?
Ernst A. Heinz
> [...]
>
> Understood. The new format gets around that. But the new format with ep
> entries junked for the distribution data would be even better, no ?
>
> Eugene ? Is it worth considering, or is the saving inconsequential ?
Chris,
I can answer this as well because the whole en-passant stuff springs from
an article that I submitted to the ICCA Journal in August 1998.
The basic idea of the scheme to handle en-passant is to enumerate all
possible en-passant constellations of 2 opposing Pawns (even if there are
more Pawns on the board, two of them suffice to uniquely define the
pending en-passant capture). By confining one of these 2 Pawns to either
the King- or the Queen-side flank, you end up with exactly 14 different
en-passant constellations.
If your index space still features illegal positions, you can stuff the
14 en-passant constellations in there without increasing the space
consumption of your database at all. In case of an already tight index
space you must add the 14 en-passant constellations to it which results
in an increase of the space consumption by roughly 1.2%. Actually not
much to worry about ...
Chris Whittington
Ernst A. Heinz wrote in message <702a4p$cgb$1...@nz12.rz.uni-karlsruhe.de>...
>Chris Whittington wrote:
>
>> [...]
>>
>> Understood. The new format gets around that. But the new format with ep
>> entries junked for the distribution data would be even better, no ?
>>
>> Eugene ? Is it worth considering, or is the saving inconsequential ?
>
>Chris,
>
>I can answer this as well because the whole en-passant stuff springs from
>an article that I submitted to the ICCA Journal in August 1998.
>
>The basic idea of the scheme to handle en-passant is to enumerate all
>possible en-passant constellations of 2 opposing Pawns (even if there are
>more Pawns on the board, two of them suffice to uniquely define the
>pending en-passant capture). By confining one of these 2 Pawns to either
>the King- or the Queen-side flank, you end up with exactly 14 different
>en-passant constellations.
>
>If your index space still features illegal positions, you can stuff the
>14 en-passant constellations in there without increasing the space
>consumption of your database at all. In case of an already tight index
>space you must add the 14 en-passant constellations to it which results
>in an increase of the space consumption by roughly 1.2%. Actually not
>much to worry about ...
Thanks for the maths :)
Agreed, not much to worry about.
Does the 1.2% space requirement still hold for 6 and 7 men builds ? Or does
it start expanding ? Because, if it starts expanding (in A.D. 2005 or
whenever) it might be an idea to design a mapping out of the ep positions
now. Kind of future-prooofing the data ... ?
Isn't this fun :)
Chris Whittington
>
>=Ernst=
>
>+--------------------------------------------------------------------------
Ernst A. Heinz
> [...]
>
> Does the 1.2% space requirement still hold for 6 and 7 men builds ? Or does
> it start expanding ?
It does not expand percentage-wise because you only need to add the 14
en-passant constellations *once* (i.e., to one pair of opposing Pawns).
But the absolute space consumption grows with larger databases, of course.
BTW, the exact increase in size is given by (24*47 + 14)/(24*47) = 1.01%
which is even less than I quoted from my head before.
=Ernst=
Komputer Korner
--
--
Komputer Korner
The inkompetent komputer
To send email take the 1 out of my address. My email address is
kor...@netcom.ca but take the 1 out before sending the email.
Robert Hyatt wrote in message <7008fc$e0k$1...@juniper.cis.uab.edu>...
>
>We are getting close to be ready to distribute some "new" databases
that
>can initially only be used in Crafty, but I assume that other
freeware programs
>will use them once they grab the "probe" code I am going to do for
Crafty.
How much space? Good question. What I currently have
>on my ftp (all 3/4 piece files, plus KRP and derivatives) take about
400Mb.
>Eugene's will be smaller, but we are going to make more available at
the
>same time. I consider what I have now to be the "starter" set that
is
>probably the most important ones available (KRP vs KR is pretty
common in
>crafty's play).
>
>If you have a quick link to me, and have disk space (permanent or
temp for
>a month or two) let me know and we can get this to going. Be nice to
do
>EP captures finally, plus smaller files as well...
>
>
>
Robert Hyatt
: What about the 5 men other than KRP vs KR?
We can build whatever we want now. Eugene has (I believe) built all the
K*PK* endings that are interesting... The only problem is making them
available since they get quite large even when zipped.
Here's what I hope to make available before long:
k*k k**k k*k* (all 3-4 piece files as always (*=pnbrq)
krpkr, kqpkq, knpkn, kbpkb, knpkb, kbpkn
After those, I am not sure. Do note, of course, that knpkn means kn*kn
since the pawn can promote to anything... Someone has suggested things
like KRB KQ and so forth. I'll have to see how space on my ftp box goes
first...
Quenton Fyfe
tablebases themselves ?
Regards
Quenton Fyfe
Robert Hyatt wrote in message <702t71$iet$1...@juniper.cis.uab.edu>...
Robert Hyatt
: Will the program to build the tablebases be made available - or just the
: tablebases themselves ?
: Regards
Both... we are doing testing on the stuff right now...
Bob
jw...@oro.net
wrote:
>Quenton Fyfe <que...@excelsiordirect.com> wrote:
>: Will the program to build the tablebases be made available - or just the
>: tablebases themselves ?
>
>: Regards
>
>Both... we are doing testing on the stuff right now...
>
You might consider making executables available for various systems.
It could be quicker to build them than to download them (especially if
your ISP tends to crash), and it would surely reduce bandwith.
Eugene Nalimov
thread, so I saw it only today.
Currently I calculated all forty 3+2 pawnless endings, KRPKR, KQPKQ,
K(B/N)PK(B/N/R). I calculated KBNKP, but verification failed - don't know
why, and had not enough time to look at it yet (I hope that's hardware
problem, not bug in the program). In any case, right now I have ~2.3Gb
of gzipped tablebases that passed verification and I'm sure they are
correct. I started calculations of more tablebases at idle machines during
weekend - lopsided ones, but necessary for K(B/N)PKP. But don't wait
this ones soon - several weeks in the best case.
I doubt average user can build 5-man ending (him/her)self - it can take
several days at a very fast machine with *A LOT OF* RAM. Generator
is RAM-hungry, because it keeps entire tablebase pair in RAM during
construction; also, compactness of the tablebases slows down generator
a lot - it spends ~40% of CPU time doing index calculation. So, for next
2-3 years it's better to download tablebases from the net.
About en passant: Chris is right - if you probe only after the capture, it's
not necessary to store positions with en passant - it's enough for generator
to know about en passant and correctly handle it during construction.
I included those positions because of
(1) It could be easily done,
(2) It can be convinient for some database programs,
(3) Theoretically it's possible to have only one tablebase of the pair (if
TB caching works good - experiments needed); indexing schema was
designed with that possibility in mind. If so, positions with possible
en
passant capture can happen OTB. Once again, chess program can
handle that position itself - you always can make en passant capture,
seek resulting position in the TB, and promote result to the original
position, but it's again not-convinient.
For positions with one pawn per side tablebase size grow by ~0.7%; for
KPPKP - by ~1.4%.
Eugene
Robert Hyatt wrote in message <702t71$iet$1...@juniper.cis.uab.edu>...
>Komputer Korner <kor...@netcom.ca> wrote:
>: What about the 5 men other than KRP vs KR?
>
>We can build whatever we want now. Eugene has (I believe) built all the
>K*PK* endings that are interesting... The only problem is making them
>available since they get quite large even when zipped.
>
>Here's what I hope to make available before long:
>
>k*k k**k k*k* (all 3-4 piece files as always (*=pnbrq)
>
>krpkr, kqpkq, knpkn, kbpkb, knpkb, kbpkn
>
>After those, I am not sure. Do note, of course, that knpkn means kn*kn
>since the pawn can promote to anything... Someone has suggested things
>like KRB KQ and so forth. I'll have to see how space on my ftp box goes
>first...
>
>
>
>
Chris Whittington
Eugene Nalimov wrote in message ...
>Sorry for delay, but newsserver at office somehow lost that entire
>thread, so I saw it only today.
>
>Currently I calculated all forty 3+2 pawnless endings, KRPKR, KQPKQ,
>K(B/N)PK(B/N/R). I calculated KBNKP, but verification failed - don't know
>why, and had not enough time to look at it yet (I hope that's hardware
>problem, not bug in the program). In any case, right now I have ~2.3Gb
>of gzipped tablebases that passed verification and I'm sure they are
>correct. I started calculations of more tablebases at idle machines during
>weekend - lopsided ones, but necessary for K(B/N)PKP. But don't wait
>this ones soon - several weeks in the best case.
>
>I doubt average user can build 5-man ending (him/her)self - it can take
>several days at a very fast machine with *A LOT OF* RAM. Generator
>is RAM-hungry, because it keeps entire tablebase pair in RAM during
>construction; also, compactness of the tablebases slows down generator
>a lot - it spends ~40% of CPU time doing index calculation. So, for next
>2-3 years it's better to download tablebases from the net.
For those of us with modems that's going to be next to impossible (time).
2.3 Gbytes of zip could go onto 5 CDs, no ?
Can anybody get distributing these ?
Or, can anybody with a very fast download direct net connection make a
download and then write some gold CDs ?
Since I rather suspect (and hope) that Eugene's egtbs will become standard,
availability is a problem that needs to be adressed.
Chris Whittington
mclane
>For those of us with modems that's going to be next to impossible (time).
>2.3 Gbytes of zip could go onto 5 CDs, no ?
>Can anybody get distributing these ?
>Or, can anybody with a very fast download direct net connection make a
>download and then write some gold CDs ?
Why not use DVD-rom ?
You could put the files on ONE DVD ...
>Since I rather suspect (and hope) that Eugene's egtbs will become standard,
>availability is a problem that needs to be adressed.
>Chris Whittington
best wishes
mclane
Har...@t-online.de
quoting a mail from mcl...@prima.ruhr.de concerning Re: endgame databases
> >For those of us with modems that's going to be next to impossible (time).
> >2.3 Gbytes of zip could go onto 5 CDs, no ?
> >Can anybody get distributing these ?
>
> >Or, can anybody with a very fast download direct net connection make a
> >download and then write some gold CDs ?
>
> Why not use DVD-rom ?
> You could put the files on ONE DVD ...
Later on will probably be better. At the moment there are not so many
users with DVD-Rom/Ram-drive.
Harald Faber