Author: Uri Blass
Date: 11:16:06 09/01/03
Go up one level in this thread
On September 01, 2003 at 13:17:08, Peter McKenzie wrote:
>On September 01, 2003 at 05:14:17, Uri Blass wrote:
>
>>On August 31, 2003 at 22:46:36, Peter McKenzie wrote:
>>
>>>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.
>>
>>The point is that I think that I do somethings that are not optimal in my main
>>hash tables and it is better if I understand it before implementing pawn hash
>>tables and maybe do the same mistake,
>
>Ah, having read what you wrote below I understand what you are saying now. I
>think these details that you are worrying about are extremely small and would
>have very little impact upon overall performance.
>
>Its nice to get this sort of stuff right, although I personally don't lose too
>much sleep over it and prefer to emphasize algorithmic efficiency over code
>efficiency.
I agree but the last changes that I do are about collecting more information
per node and not about improving the algorithm.
I decided not to think about the near future and
I believe that collecting more information increase my possibilities for future
developement but I also do not like to see movei become slower in nodes per
seconds(movei already is not a fast searcher and search at similiat speed to
shredder) and this is the reason that I think how to compensate for the fact
that it becomes slower by doing it faster in other areas.
It is only a psychological explanation and of course the fact that it became
slower is not a reason to make it faster in other areas(the opposite and I could
earn more speed for making it faster before I made it slower).
I calculate the information incrementally so it is not simple to implement it
correctly without bugs so it takes time to do it.
I already see how the information can help me in my search but I still did not
implement it.
>>
>>I will explain the data that I have today for my hash tables
>>
>>I have the following global varaibles when hash_table is a struct.
>>
>>__int64 zobrist[6][2][64];
>>__int64 zob;
>>__int64 zobkey[max_plies_of_game];
>>HASHE *hash_table;
>
>that looks reasonable, I do something similar although it is entirely possible
>that my approach isn't optimal
>
>I find it a bit weird you have a separate array though, don't you have a generic
>data structure thats tracks information for each ply of the game?
In order to get information for each ply of the game I have arrays.
I also have a struct that I copied from tscp but I did not think to add
information to that struct later when I added hash tables.
I see also that I have the constant
max_plies_of_game in another name because I forgot about the struct that I
copied from tscp when I decided to add more information.
>
>I have a pointer called 'Stack' (terrible name, I think most people might call
>it 'Tree') which is incremented/decremented when traversing the tree. It points
>into an array of structures that contain information about each ply, including
>the zobrist key of course.
I have only
typedef struct
{
move m;
int capture;
int castle;
int ep[3];
int fifty;
int kingincheck;
int checkingsquare;
}
hist_t;
This was basically struct from tscp1.73 when I added information about direction
that the king is in check and about the checking square when
kingincheck=-1 when the king is not in check and checkingsquare=-1 when the
check is a double check.
Later when I added information I forgot about this struct.
I think that tree is not good name because it contain only one line.
I will probably use a name like game_info because it includes information about
a single game that ends in the position that the program considers.
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.