Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: To bitboard or not to bitboard?

Author: Peter McKenzie

Date: 19:46:36 08/31/03

Go up one level in this thread


On August 31, 2003 at 15:12:25, Uri Blass wrote:

>On August 31, 2003 at 05:30:38, Peter McKenzie wrote:
>
>>On August 31, 2003 at 01:03:46, Uri Blass wrote:
>>
>>>On August 30, 2003 at 22:29:56, Sune Fischer wrote:
>>>
>>>>On August 30, 2003 at 14:37:44, Tord Romstad wrote:
>>>>
>>>>I think you have found some good arguments against bitboards,
>>>>but all representations have some disadvantages.
>>>
>>>I do not think that you have to choose only one.
>>>It may be better to have both so you can choose which one to use based on your
>>>needs.
>>>
>>>You pay by some static speed reduction but the advantage is that you increase
>>>your opportunities for future developement.
>>>
>>>>Ie. in other schemes you must struggle to keep order on a piecelist, getting
>>>>things reproducable seems pretty difficult to me with this.
>>>>
>>>>But looking at different source codes, I think the big difference
>>>>is that bitboards use large tables and in return have relative few branches.
>>>>Processors and compilers get better in branch pridiction and they get more and
>>>>more cache.
>>>>Which factor eventually will dominate I can't say, but I believe the cache size
>>>>will only grow and it doesn't even seem to be a problem nowadays, so the table
>>>>sizes I don't personally worry about too much.
>>>>
>>>>What I like about bitboards is that you can work on the entire board with just
>>>>a few masks.
>>>>
>>>>As an example, say you have in your move generator a stage where you would like
>>>>to generate non-captures to squares not attacked by opponent pawns.
>>>>
>>>>This would require you only to AND the attack board for the given piece with:
>>>>~(occupied | opponent->PawnAttacks())
>>>>
>>>>Something which is of course a constant and can be pulled out of the piece loop.
>>>>
>>>>For move generation, the advantage of bitboards lies not in the speed of which
>>>>it can add dumb pseudo legal moves to a list (who does this anyway?)
>>>
>>>I think that you do it even in the search.
>>>
>>>In case that you expect all the moves to fail low it is not logical to spend
>>>time on incremental move generator and it is better to generate all moves.
>>>
>>>, but in the
>>>>way it enables you to generate classes of moves with minimal overhead.
>>>>
>>>>A second classic example, is if you want to know if there is a pawn on the 7th
>>>>rank.
>>>>With non-bitboards you can do a loop with branches, or if you enumerate your
>>>>pieces in power of two's, you could do something like:
>>>>if (Pawn & (pc[a7]|pc[b7]|pc[c7]|pc[d7]|pc[e7]|pc[f7]|pc[g7]|pc[h7]))
>>>
>>>For that purpose you can also keep a 8 bit varaible that tell you
>>>the pawns in the 7th rank when you update after every move that change it.
>>
>>Better to get that sort of information out of the pawn hash table.
>

At the risk of reducing my 'relative advantage', I will attempt to answer your
questions...

>I do not understand what is wrong with a varaible that is updated incrementally.

Nothing is wrong with them, it just seems to me that it is simpler (and at least
as efficient) to get such things from the pawn hash table if possible.

>
>Note also that I do not have a pawn hash tables because I am not sure exactly
>what information to store there and I also did not like this subject and
>prefered to look at other things.

You can store any information that depends only on pawn position.  For example,
I stored a bitmap of open files.  You might even like to store your pawn
bitboard(s), or some more specific information.

>
>I believe that the time that I use for updating bitboards in my make and unmake
>moves is relatively small and I have other updated information but I do not like
>to see my program become slower because of generating more information so
>maybe it is time to .

The nice thing about a pawn hash table is that you can add more pawn structure
knowledge and it costs very little.

>
>I do not like to store evaluation inspite of the fact that today most of my pawn
>evaluation is dependent only on the pawn structure because I will probably
>change it later and I do not like to store information only to delete it later.
>
>My evaluation is also relatively fast and I spend more time on incremental
>update of bitboards that are used by the evaluation.
>
>I have bitboard for pawns so practically I check if white has a pawn in the 7th
>by
>
>if (pawnBB[LIGHT]&RANK7)
>
>How should I define pawn hash tables and use it to save time?
>
>I guess that unlike normal hash tables 32 bits are enough for the key of pawn
>hash tables.

Probably, although I just use a 64bit key.

>
>Suppose that I want only to store the information about pawns in the 7th and
>about squares of passed pawns in order to save updating the bitboard of passed
>pawns every time that I make moves.
>
>Should I start with something like
>
>typedef struct tagPAWNHASHE
>{
>	unsigned int key;
>        unsigned int white_pawns_in_the_7th:8;
>        unsigned int black_pawn_in_the_2th:8;
>        BitBoard passedpawns[2];
>}
>PAWNHASHE;

something like this, yes

>
>Should I have some global varaible
>int zobpawns for the key of the position in the board or maybe an array that
>tell me the zobrist key for every ply and local varaible is enough.
>
>I have a global varaible with the hash key of the position of the board and also
>an array that tell me the hash key of every position.
>
>If I remember correctly
>I remember a claim of Bob Hyatt that using local varaible and array is better
>but I did not understand exactly how to do it in a productive way.
>
>I do not like the idea to call an array every time that I record a position or
>probe a position in the hash tables and this is the reason that I kept one
>global varaible and not only an array.
>I understand that there is probably something that I do that is not optimal
>there but I did not understand exactly what I do wrong and I left this subject.

I can't follow this.

>
>Now when every time people suggest to have a pawn hash tables I prefer not to do
>the same mistake with pawn hash tables so I want to know exactly what to do
>with pawn hash tables.

Just implement it in a similar way to your main hash table.

Peter

>
>
>
>Uri



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.