Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old February 2nd 04, 07:33 AM
Mikko Nummelin
 
Posts: n/a
Default On 6-men tablebases

Frequently it is noted that having 6-men Nalimov tablebases is
problematic, both because it takes an enormous time to create them and
also because they are huge, some of them even multiple gigabytes each. I
think I have a proposed solution to the second problem, i.e. the size but
not to the first (enormous time to create): "Leapbases" or "skipbases".
As far as I know, Nalimov tablebases do store all positions of a special
kind in one tablebase file, where there is forced mate in N for either
side. My suggestion is, that as powerful chess engines are able to "patch"
missing portions of table by calculating independently 6-8 plies, even
more forward, what if only those positions were taken into tablebase
where there are, say 3*x full moves to mate where x is an integer.
Generating these would be the same as with usual Nalimov tbs, but after
listing all positions where there is mate in 3, it deliberately throws
away mate-in-1:s and mate-in-2:s, likewise when all positions with mate in
6 are found, all mate-in-4:s and mate-in-5:s are thrown out etc. Wouldn't
that provide a chess engine enough to play those endings perfectly with
lesser space requirements?


Mikko Nummelin
  #2   Report Post  
Old February 2nd 04, 10:03 AM
Anders Thulin
 
Posts: n/a
Default On 6-men tablebases

Mikko Nummelin wrote:

Generating these would be the same as with usual Nalimov tbs, but after
listing all positions where there is mate in 3, it deliberately throws
away mate-in-1:s and mate-in-2:s, likewise when all positions with mate in
6 are found, all mate-in-4:s and mate-in-5:s are thrown out etc. Wouldn't
that provide a chess engine enough to play those endings perfectly with
lesser space requirements?


You've thrown out two of three score values from the database, and so
far, you've made the database smaller.

But you have not explained the tricky part. You need some kind of
mapping function (position - file offset) to get at the position
score. And you also need to be able to detect the positions that are not
stored in the database, but for which you need to search for the score.

Creating the mapping function is going to be quite difficult, I suspect,
but until you've said exactly how it is done, it's not going to be possible
to decide if you really use less data storage in toto.

--
Anders Thulin http://www.algonet.se/~ath

  #3   Report Post  
Old February 2nd 04, 10:38 AM
Mikko Nummelin
 
Posts: n/a
Default On 6-men tablebases

On Mon, 2 Feb 2004, Anders Thulin wrote:

Mikko Nummelin wrote:


Generating these would be the same as with usual Nalimov tbs, but after
listing all positions where there is mate in 3, it deliberately throws
away mate-in-1:s and mate-in-2:s, likewise when all positions with mate in
6 are found, all mate-in-4:s and mate-in-5:s are thrown out etc. Wouldn't
that provide a chess engine enough to play those endings perfectly with
lesser space requirements?


You've thrown out two of three score values from the database, and so
far, you've made the database smaller.


But you have not explained the tricky part. You need some kind of
mapping function (position - file offset) to get at the position
score.


When the engine notices that it the material on board is such that a
tablebase value might exist, it generates a hash value by ORing its
bitboards (of course taking into count that in endings without pawns the
position should first be rotated to get white king confined in a1-d1-d4
triangle). The positions in the tablebase should be ordered the same way.
Then it just requires a binary search to see whether the position is in
the tablebase or not.

And you also need to be able to detect the positions that are not
stored in the database, but for which you need to search for the score.


When binary search fails, then we'll do this.

Creating the mapping function is going to be quite difficult, I suspect,
but until you've said exactly how it is done, it's not going to be possible
to decide if you really use less data storage in toto.


Well, I think it depends how much positions are actually thrown out (of
course making it more and more difficult for the computer to patch the
gaps).


Mikko Nummelin
  #4   Report Post  
Old February 2nd 04, 03:21 PM
Pham Hong Nguyen
 
Posts: n/a
Default On 6-men tablebases

Hi,
Your idea about reducing mate value to save space is quite good!!!

However, I think you would be luckier if you was born earlier.
Otherwise, you are reinventing the wheel

Let me explain few recent ways to store a position for a table.
1) Using 1 byte (8 bit) for one position. With the range from -128 to
128, in general that value is enough for all generated tables to store
information about win/loss in N moves (but it may be not sufficient in
the future).
2) Using 1 bit for one position. One bit allows to save only 2 values.
Thus, it is just enough for win and no-win. Obviously, you can reduce
the size of a table to 8 times. One other advantage is that table can
be generated much faster (because the table doesn't need information
about distance to mate). After knowing the status of a position, your
chess engine should do a search to know: if win, how many moves to
mate; if no-win, that is a draw or loss, and how many moves to lose.
3) Using 2 bits for one position. With 4 values, it is enough to
sto win, draw, loss. You can save 4 times of size of table. The
advantage compares with 1 bit method is that you don't need to search
any more if it is a draw.

I don't hear about anyone who uses 3-7 bits/position. But you can try


Regards,
+Pham



Mikko Nummelin wrote in message . fi...
Frequently it is noted that having 6-men Nalimov tablebases is
problematic, both because it takes an enormous time to create them and
also because they are huge, some of them even multiple gigabytes each. I
think I have a proposed solution to the second problem, i.e. the size but
not to the first (enormous time to create): "Leapbases" or "skipbases".
As far as I know, Nalimov tablebases do store all positions of a special
kind in one tablebase file, where there is forced mate in N for either
side. My suggestion is, that as powerful chess engines are able to "patch"
missing portions of table by calculating independently 6-8 plies, even
more forward, what if only those positions were taken into tablebase
where there are, say 3*x full moves to mate where x is an integer.
Generating these would be the same as with usual Nalimov tbs, but after
listing all positions where there is mate in 3, it deliberately throws
away mate-in-1:s and mate-in-2:s, likewise when all positions with mate in
6 are found, all mate-in-4:s and mate-in-5:s are thrown out etc. Wouldn't
that provide a chess engine enough to play those endings perfectly with
lesser space requirements?


Mikko Nummelin

  #5   Report Post  
Old February 2nd 04, 03:31 PM
Anders Thulin
 
Posts: n/a
Default On 6-men tablebases

Mikko Nummelin wrote:

On Mon, 2 Feb 2004, Anders Thulin wrote:


But you have not explained the tricky part. You need some kind of
mapping function (position - file offset) to get at the position
score.


When the engine notices that it the material on board is such that a
tablebase value might exist, it generates a hash value by ORing its
bitboards (of course taking into count that in endings without pawns the
position should first be rotated to get white king confined in a1-d1-d4
triangle). The positions in the tablebase should be ordered the same way.
Then it just requires a binary search to see whether the position is in
the tablebase or not.


Aha -- you assume the database file contain information about positions.
They don't: if the Nalimov files did that, they would be much much larger
than they are now. From *that* perspective your proposal might work.

However, from *that* perspective, the Nalimov files (as well as the other
endgame database files I know of) do much better: they have thrown away
*all* positions, which is far better.

A mapping function is used, which takes a position, and maps it
onto a integer (0, 1, 2, 3, ..., N-1), and at that file offset, the
score corresponding to the position is stored. (modify as required,
if scores need two or three bytes for storage.)

A very stupid mapping function for any 3-piece endgame would be:

((square_1 * 64) + square_2) * 64 + square_3

and number the squares from 0 to 63 in any way you like. As I said, this
is a very stupid function, and it's quite easy to improve it, but it
illustrates the basic design of the endgame databases.

If you know the mapping function, it's easy to go from the position, to the
place where the corresponding position score has been stored. In this
particular case, it's even possible to reverse the process: given a score
position, you can caclulate the corresponding position.

But ... given this design, *all* positions must be mapped, and some
illegal positions (say, all with square 1 = square 2, -- i.e. two pieces on
the same square) must be flagged as illegal by using a reserved score value
that must not be possible to confuse with a real score.

Your design assumes that it's possible to remove 2/3 of the positions,
but bases that on the assumption that positions are stored in the file. As they
aren't stored there, it's not clear that this method can be used to shrink
storage space further.

--
Anders Thulin http://www.algonet.se/~ath



  #6   Report Post  
Old February 2nd 04, 03:32 PM
Alexander Belov
 
Posts: n/a
Default On 6-men tablebases

This is usual memory vs. performance tradeoff. You suggest to keep
less "ready" results and calculate the rest. But the time of 0.5-2.5 move
solution tree generation and probation of all its leafs in tablebase can be
unacceptable.

"Mikko Nummelin" wrote in message
i...
Frequently it is noted that having 6-men Nalimov tablebases is
problematic, both because it takes an enormous time to create them and
also because they are huge, some of them even multiple gigabytes each. I
think I have a proposed solution to the second problem, i.e. the size but
not to the first (enormous time to create): "Leapbases" or "skipbases".
As far as I know, Nalimov tablebases do store all positions of a special
kind in one tablebase file, where there is forced mate in N for either
side. My suggestion is, that as powerful chess engines are able to "patch"
missing portions of table by calculating independently 6-8 plies, even
more forward, what if only those positions were taken into tablebase
where there are, say 3*x full moves to mate where x is an integer.
Generating these would be the same as with usual Nalimov tbs, but after
listing all positions where there is mate in 3, it deliberately throws
away mate-in-1:s and mate-in-2:s, likewise when all positions with mate in
6 are found, all mate-in-4:s and mate-in-5:s are thrown out etc. Wouldn't
that provide a chess engine enough to play those endings perfectly with
lesser space requirements?


Mikko Nummelin



Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Using 6-man tablebases Brigitte Schipol rec.games.chess.computer (Computer Chess) 4 November 4th 03 09:14 PM
Nalimov Tablebases Frederick Smith rec.games.chess.computer (Computer Chess) 5 September 16th 03 07:25 PM
Castling bug in Chessmaster 9000 tablebases? Peter Bereolos rec.games.chess.computer (Computer Chess) 6 August 30th 03 04:15 AM
tablebases hang Shredder7.04 with XP CeeBee rec.games.chess.computer (Computer Chess) 7 August 26th 03 04:15 PM
tablebases Leonardo Ljubicic rec.games.chess.computer (Computer Chess) 10 August 23rd 03 04:46 PM


All times are GMT +1. The time now is 12:08 PM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017