Author: Uri Blass
Date: 09:08:01 09/02/03
Go up one level in this thread
On September 01, 2003 at 14:16:06, Uri Blass wrote:
>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
1)I wonder if I should include the side to move in the pawn hash.
My evaluation today usually is not dependent on the side to move but
the question if a pawn is unstoppable may be dependent on the side to move and I
may want to include more cases so I think that I should do it.
2)This is the more important point.
I think that I should change my functions to make null move and unmake null move
because they do not update some varaibles that should be updated and my code is
ugly(inspite of the code that my code is clearly productive).
I probably need to change my functions to make null move and unmake null move
and I am not sure at this moment if I think correctly about the exact varaibles
that I need to update in my make nullmove so before I go to change the code I
prefer to read some comments from other people.
Let start with the fact that I have like tscp 2 varaibles ply and hply when ply
is the number of plies from the begining of the search and
hply is the number of plies from the beginning of the game.
The problem starts from the fact that ply includes null moves when hply does not
include null moves.
Today my function to make null moves update only the following varaibles:
a)ply and some arrays that have data about the history of the search and not
about the history of the game(maybe I should have a struct for them)
b)The global varaible zob that is the key for the hash tables.
I consider changing the side to move and the enpassent rule(in my undonullmove I
do not consider it but immediately after undoing it I check if enpassent capture
is possible based on local varaible in the function that called undonull move
and update the global varaible again)
I think that other varaibles that I need to update are:
a)hply(the history ply of the game) and all the varaible in that struct that are
changed.
The struct include the following varaibles
move m;
int capture;
int castle;
int ep[3];
int fifty;
int kingincheck;
int checkingsquare;
Today I do not change the move in the struct but I have no problem to go back
even if the time is over in the middle of the iteration because I have a special
array null[ply] that gets 1 for every ply that I do null move
and I have
if (null[ply]==0)
undomove();
else
undonullmove();
I think that I need to tell my program that there is no capture in null move.
not changing castle rights relative to previous ply is obvious
ep[3] is an array that tell me the capture possibilities(I can tell it
ep[0]=-1 that means no enpassent possible and do not look at ep[1] or ep[2]
I think that I can increase fifty by 1 but I am not sure if it is the right step
to do.
the king was not in check before null move and is not in check after it so I can
tell it that the value is the same as previous ply.
b)zobkey[max_plies_of_game]
Today I simply ignored updating this array during null move
The array is used only for repetition detection
The array should be part of the struct that is described in 1.
c)the global varaible fifty that tells me the number of plies from the last
conversion(today it is not changed during null move and I think that it should
be changed by 1 or changed to 0 and I am not sure which option is correct).
Again I do not know if it is a good idea to have a global varaible.
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.