Author: Vincent Diepeveen
Date: 05:51:17 01/30/02
Go up one level in this thread
On January 29, 2002 at 21:22:19, Dann Corbit wrote:
>On January 29, 2002 at 16:37:19, Andrew Dados wrote:
>>On January 29, 2002 at 14:37:27, Les Fernandez wrote:
>>>On January 29, 2002 at 14:03:24, Robert Hyatt wrote:
>>>>On January 29, 2002 at 10:47:40, Les Fernandez wrote:
>>>>>On January 29, 2002 at 09:57:30, Robert Hyatt wrote:
>>>>>>On January 28, 2002 at 17:48:48, Les Fernandez wrote:
>>>>>>>Just curious to know what is the best being done now for storing a chess
>>>>>>>position. In the worse case scenario (castling right exists) it takes me 162
>>>>>>>bits to store 32 pieces, color, location, side to move, castling, enpassant,
>>>>>>>promotion, ce and pv. Now if castling rights do not exist then the worse case
>>>>>>>scenario for the above is 81 bits. Much further reduction in bits/position is
>>>>>>>possible but at the moment I am interested in the above.
>>>>>>>
>>>>>>>Thanks in advance,
>>>>>>>
>>>>>>>Les
>>>>>>
>>>>>>
>>>>>>How can you store a complete chess position without castling rights in 81
>>>>>>bits? castling rights are certainly not 81 bits of information to get you
>>>>>>up to 162.
>>>>>>
>>>>>>Something is wrong.
>>>>>
>>>>>Hi Bob,
>>>>>
>>>>>The point is that in cases where castling is not available there exists a
>>>>>minimum of 4 rotations that can be applied to a board, top-bot and left-right.
>>>>>The method I discuss to store a position requires 9 bits to store piece, color
>>>>>and x and y location. 32x9=288 and then 36 bits are needed to store the other
>>>>>pertinent things about the position. (288+36)/4=81 bits/position on avg. just
>>>>>as Uri explained here (thx Uri sorry Bob if I was not clear). I thought the
>>>>>scheme I used to store a piece using only 9 bits was different and would
>>>>>appreciate feedback here.
>>>>>
>>>>>Thanks,
>>>>>
>>>>>Les
>>>>
>>>>
>>>>I think your math is wrong. If you need 288+36 bits to store one position, you
>>>>need 288+36-2 bits to store 1/4 of that number of positions. This is log math
>>>>and you _subtract_ exponents, not divide.
>>>>
>>>>ie 2^32 / 4 == 2^30, _not_ 2^8
>>>>
>>>>That is where I am getting lost in your description...
>>>
>>>Hi Bob,
>>>
>>>First let me say my intention is not to play with semantics as the other
>>>responder eludes too, I am not here to play. Basically I went on the basis of
>>>the following. Lets say I have a Key position (3 pieces) and that I need 63
>>>bits to store "all" the information about this position. Now if from this
>>>Binary key I can extract say 44 other positions of equivalent nature then I only
>>>need to use 63 bits of space to store the key position but I actully have access
>>>to 44 positions that require no storage at all and yet have the same solution.
>>>
>>>I hope I am saying it right <s>,
>>>
>>>Thanks Bob for the input
>>
>>Than for any database application you'll need to do a 'search' for position,
>>killing your performance. You may need to compare hundreds of entries, or use
>>huge space for indexing.
>
>Chess search is a database application. It's an "in-core" application. EGTB
>files and opening books are database tables. The bet is that the lookup will
>save more time than recalculation from scratch.
all assumptions are of course wrong:
- EGTB ==> O(1) lookup, whereas in databases no such thing happens soon,
i miss a managed binary tree concept in your writings so you need O(n)
for every lookup AFAIK.
- you waste bits. If you store a position you can better store the
hash like i do in my hashtable and then add a score to it. So you
would need 64 bits + 8 bits score at most. Side to move of course
doesn't need to get stored, nor bounds or whatever, nor best move,
waste of bits it is.
Most important is however that you do it all for nothing because:
- it will never save time putting your stuff in hashtable, but it will
instead waste memory as the the search space is just too big to store
in a few terabyte of memory, especially if you use 250 bits a position.
>If the files can be made compact enough, they can sit in memory and be looked up
>via perfect hash or some such instant locator.
>
>If the files cannot be made compact enough, then they can be stored on disk. In
>this case, only use them for the search at the root. If you can search in 1
>second (an eon of computer time) then it is not a problem unless someone stoops
>to playing game in 30 seconds or something bletcherous like that.
>
>If someone plays an ultra-fast game, just turn it off.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.