Author: Robert Hyatt
Date: 07:48:29 02/12/04
Go up one level in this thread
On February 12, 2004 at 03:16:27, martin fierz wrote:
>On February 12, 2004 at 00:05:35, Robert Hyatt wrote:
>
>>On February 11, 2004 at 16:43:06, martin fierz wrote:
>>
>>>on my long todo list for my program, the item "pawn hashing" has slowly but
>>>steadily floated upwards. now it's on top. so: how large is your pawn hashtable
>>>(in # of entries)? how large are your entries? i'm using bitboards, and it seems
>>>to me that my entries will be huge, e.g. if i want to save some simple stuff
>>>like
>>>
>>>- passers
>>>- connected passers
>>>- isolated pawns
>>>- doubled pawns
>>>- backward pawns
>>>- blocked pawns
>>
>>You can do all of those with 8 bit values, 1 bit per file, rather than 64 bits,
>>that is what I do... Here is my pawn hash info:
>>
>>typedef struct {
>> BITBOARD key;
>> short p_score;
>> unsigned char allb;
>> unsigned char black_defects_k;
>> unsigned char black_defects_q;
>> unsigned char passed_b;
>> unsigned char candidates_b;
>> unsigned char allw;
>> unsigned char white_defects_k;
>> unsigned char white_defects_q;
>> unsigned char passed_w;
>> unsigned char candidates_w;
>> unsigned char protected;
>> unsigned char outside;
>> unsigned char open_files;
>>} PAWN_HASH_ENTRY;
>>
>>
>>I can explain what each term is, if needed, but note each is a char, which is
>>one bit per file.
>
>nice! no, you don't have to explain, it's rather obvious what they are. what's
>not so obvious to me is how you switch from bitboard to char representation
>efficiently; i imagine you would have to do the following:
>
>-> compute one of the above things (e.g. defects) as bitboard
>-> loop over that bitboard with the usual x&-x trick, peeling off each defect
>one by one
>-> LSB for each defect
>-> LSB_to_file for each defect
>-> sum up to get a file index
I do something simpler. Since I am "behind" the hashing, I don't worry about
speed since most of the time I won't be executing anything since a hash hit will
occur in over 99% of the pawn positions.
I find a pawn, get its square (0-63) using the usual FirstOne()/LastOne() stuff
and then (say) if it is passed, I do something like this:
black_passed |= 1 << (square&7)
square&7 is the file of course. That gives me a 1 bit in the right position for
each possible file. If I have two pawns on the same file, I generally do this
stuff for the most advanced one, since once the bit is set, it will stay set
even if a pawn behind this one is not passed...
Just remember that you can do most anything here you want, without any real
regard to efficiency, because you will _rarely_ execute the code due to the
great pawn hashing efficiency you will see.
>
>the other way round could be a table lookup giving you a bitboard with all
>respective files set, which you & with the pawn bitboard, giving you all
>defects.
>
>it seems that bitboard -> char is slow while char -> bitboard is fast. am i
>missing something in terms of efficiency here? or are you simply saying that you
>have 99% hitrate in your pawn hashtable, and therefore you can spend a lot of
>time stuffing things into it, just as long as you can retrieve them efficiently?
That's the idea although it is not that bad either way since creating the bitmap
chars doesn't happen very often. To use the info, I notice a file has a 1 bit
by using a FirstOne8Bit() function, and I can then AND the pawn 64-bit bitboard
with a mask that just isolates the file in question. An appropriate FirstOne()
(black) or LastOne() (white) gives me the square of the pawn in question...
>
>cheers
> martin
>
>>
>>>
>>>that would be 6x8 = 48 bytes; perhaps times 2 for each side (or i could pop
>>>black and white pawns in the same bitboard, and & it with the black/white
>>>bitboard to save space). still, that's already 48 bytes and i guess i could save
>>>some more stuff if i thought about it a bit longer :-)
>>>is that a reasonable size for a pawn hash entry?
>>>
>>>cheers
>>> martin
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.