Need help: End Game Table Base and BitBase.

[Josué Forte]

Geschrieben von:/Posted by: Josué Forte at 24 April 2004 21:01:30:

Hi All,
Despite my little time for chess programming, my chess engine (Matheus) is still alive.
For the last two years, I have made several improvements to make it stable, reliable and pleasant(I hope). But many things have to be done yet.
Now I will work on two modifications.
First step: I plan to implement Nalimov End Game Table Base, and another technic called BitBase.
If some of you can help me by telling me where can I find informations about these two subjects (in English or Portuguese), specially BitBase, I would be grateful.
Second step: I plan to make the source code publicly available in the future.(by the end of this year) But before that, I have to comment the code, make it more readable and translate it into English for better understanding. I still want to rewrite the move generation routines, as well as the search and evaluation ones. Hope it will be usefull to other.
Regards,
Josué.

[Dieter Bürßner]

Geschrieben von:/Posted by: Dieter Bürßner at 25 April 2004 01:24:10:
Als Antwort auf:/In reply to: Need help: End Game Table Base and BitBase. geschrieben von:/posted by: Josué Forte at 24 April 2004 21:01:30:

First step: I plan to implement Nalimov End Game Table Base, and another technic called BitBase.
If some of you can help me by telling me where can I find informations about these two subjects (in English or Portuguese), specially BitBase, I would be grateful.

For Nalimov TB access, it might be easiest to read the code of an engine that it implements it, besides the documentation of Nalimov himself (in probe.txt - not sure, if this is available anymore - but he will probably send it to you, if you ask). Also have a look at http://f11.parsimony.net/forum16635/messages/20833.htm
For "bitbases" you have to do everything yourself - indexing, etc. Three articles by Ernst Heinz might help.
E.A. Heinz.
Knowledgeable encoding and querying of endgame databases.
In ICCA Journal, Vol. 22, No. 2, pages 81-97, June 1999.
(published by the ICCA; preprint available from http://supertech.lcs.mit.edu/~heinz/ps/know_edb.ps.gz)
E.A. Heinz.
Endgame databases and efficient index schemes.
In ICCA Journal, Vol. 22, No. 1, pages 22-32, March 1999.
(published by the ICCA; preprint available from http://supertech.lcs.mit.edu/~heinz/ps/edb_index.ps.gz)
E.A. Heinz.
Efficient interior-node recognition.
In ICCA Journal, Vol. 21, No. 3, pages 156-167, September 1998.
(published by the ICCA; preprint available http://supertech.lcs.mit.edu/~heinz/ps/node_rcg.ps.gz)
But perhaps it is more fun, to do it without this knowledge (when I implemented bitbases, I did not know about those articles yet). I think it is rather straight forward. You can think of your own index scheme (you will probably come up with something similar to the ones used already - perhaps not that tight) and how to organize the data. To create the bitbases, I took the easy road, and just asked the Nalimov TBs for the result of each position.
Good luck,
Dieter

[Josué Forte]

Geschrieben von:/Posted by: Josué Forte at 25 April 2004 03:28:31:
Als Antwort auf:/In reply to: Re: Need help: End Game Table Base and BitBase. geschrieben von:/posted by: Dieter Bürßner at 25 April 2004 01:24:10:

First step: I plan to implement Nalimov End Game Table Base, and another technic called BitBase.
If some of you can help me by telling me where can I find informations about these two subjects (in English or Portuguese), specially BitBase, I would be grateful.

For Nalimov TB access, it might be easiest to read the code of an engine that it implements it, besides the documentation of Nalimov himself (in probe.txt - not sure, if this is available anymore - but he will probably send it to you, if you ask). Also have a look at http://f11.parsimony.net/forum16635/messages/20833.htm
For "bitbases" you have to do everything yourself - indexing, etc. Three articles by Ernst Heinz might help.
E.A. Heinz.
Knowledgeable encoding and querying of endgame databases.
In ICCA Journal, Vol. 22, No. 2, pages 81-97, June 1999.
(published by the ICCA; preprint available from http://supertech.lcs.mit.edu/~heinz/ps/know_edb.ps.gz)
E.A. Heinz.
Endgame databases and efficient index schemes.
In ICCA Journal, Vol. 22, No. 1, pages 22-32, March 1999.
(published by the ICCA; preprint available from http://supertech.lcs.mit.edu/~heinz/ps/edb_index.ps.gz)
E.A. Heinz.
Efficient interior-node recognition.
In ICCA Journal, Vol. 21, No. 3, pages 156-167, September 1998.
(published by the ICCA; preprint available http://supertech.lcs.mit.edu/~heinz/ps/node_rcg.ps.gz)
But perhaps it is more fun, to do it without this knowledge (when I implemented bitbases, I did not know about those articles yet). I think it is rather straight forward. You can think of your own index scheme (you will probably come up with something similar to the ones used already - perhaps not that tight) and how to organize the data. To create the bitbases, I took the easy road, and just asked the Nalimov TBs for the result of each position.
Good luck,
Dieter

Hi Dieter,
You are fast like Yace.
Thanks for the informations.
I am downloading the papers.
Now I have a long road...
Best,
Josué.

[Alex Morozov]

Geschrieben von:/Posted by: Alex Morozov at 25 April 2004 21:01:58:
Als Antwort auf:/In reply to: Re: Need help: End Game Table Base and BitBase. geschrieben von:/posted by: Dieter Bürßner at 25 April 2004 01:24:10:

Dieter. Are Bitbases useful? I think they can ask on question "Is that endgame wining or not", but can't show the winning way.

[Dieter Bürßner]

Geschrieben von:/Posted by: Dieter Bürßner at 25 April 2004 22:07:40:
Als Antwort auf:/In reply to: Re: Need help: End Game Table Base and BitBase. geschrieben von:/posted by: Alex Morozov at 25 April 2004 21:01:58:

Dieter. Are Bitbases useful? I think they can ask on question "Is that endgame wining or not", but can't show the winning way.

I think, they are useful. Perhaps not (or not so much) for typical games, but rather for some analysis. Indeed, alone they primarily do not show the way to a win (but they will be enough, to defend a really tough to defend drawn endgame alone. At least when we leave out complications by the 50 moves rule - which Nalimov TBs ignore, too).
In most situations, they will be enough, to also show how to win a game (when they cooperate with the search of the engine and some eval code. See the paper of Heinz: Instead of reporting just "pos is won", they can also report a score by static eval. For example a pos in KRPKR with a more advanced pawn will then result in a higher score, and lead the engine in the right direction).
But even, when you do not consider all this: bitbases are about speed. You can use Nalimov TBs at the same time. Bitbases deep inside the search tree will tell you, this pos is won. When the pos is on the board, you can consult the "classical" TB, which will show you the concrete way to win. At that time, performance is no issue anymore, because you don't have to lookup many positions from the TBs.
Regards,
Dieter

[Dann Corbit]

Geschrieben von:/Posted by: Dann Corbit at 26 April 2004 20:44:13:
Als Antwort auf:/In reply to: Re: Need help: End Game Table Base and BitBase. geschrieben von:/posted by: Alex Morozov at 25 April 2004 21:01:58:

Dieter. Are Bitbases useful? I think they can ask on question "Is that endgame wining or not", but can't show the winning way.

From the experiments I have seen, bitbases clearly make an engine stronger. This is in sharp contrast to EGTB, which do not increase playing strength according to every experiment I have seen.



my ftp site {remove http:// unless you like error messages}

[Josué Forte]

Geschrieben von:/Posted by: Josué Forte at 28 April 2004 02:28:20:
Als Antwort auf:/In reply to: Re: Need help: End Game Table Base and BitBase. geschrieben von:/posted by: Dieter Bürßner at 26 April 2004 00:08:49:

I get the following error
E:\_CHESS~2>gzip -d know_edb.ps.gz
gzip: know_edb.ps.gz: not in gzip format

I can confirm this. I get the same error with a new gzip.exe just downloaded from the URL noted by Peter. I have many versions of gzip on my computer, and all the ones I tried seemed to fail on the freshly downloaded know_edb.ps.gz.
Still Gsview was able to open the compressed file. Also, on my HD I have the ps-file uncompressed. This means, that I was able to decompress it once (and I am very certain, that I really had downloaded it at ps.gz file at that time). Very strange.
Regards,
Dieter

Hi Dieter,
I have the same problem with gzip.
So, I downloaded Gsview as sugested by you. This way I got to open all ps.gz files.
But something very strange happened with my computer the day after when I tried to boot it.
I have 3 OS in my computer (Linux, Windows 98 and Windows 2000). When I boot the computer I can select the OS I want with the arrow keys.
But in the day after may keyboard could not recognize many keys, including the arrow keys, when the screen to select the OS showed up.
Then, after many tries in different ways, I got to run Windows 98.
Then I decided to uninstall Gsview and my computer worked fine again.
Perhaps this is a coincidence...
Regards,
Josué