Author: Uri Blass
Date: 03:46:07 03/24/04
Go up one level in this thread
On March 24, 2004 at 05:57:02, Heiner Marxen wrote:
>On March 23, 2004 at 14:48:32, Dann Corbit wrote:
>
>>On March 23, 2004 at 09:21:21, Heiner Marxen wrote:
>>
>>>On March 23, 2004 at 04:51:18, Uri Blass wrote:
>>>
>>>>On March 23, 2004 at 02:24:38, Tony Werten wrote:
>>>>
>>>>>On March 22, 2004 at 19:21:42, Dann Corbit wrote:
>>>>>
>>>>>>On March 22, 2004 at 18:57:52, Uri Blass wrote:
>>>>>>
>>>>>>>On March 22, 2004 at 18:50:15, Dieter Buerssner wrote:
>>>>>>>
>>>>>>>>On March 22, 2004 at 18:16:37, martin fierz wrote:
>>>>>>>>
>>>>>>>>>of course i would also like to make an incremental update of that table, but i
>>>>>>>>>decided against such an attempt because i couldn't figure out how to do it - or
>>>>>>>>>rather, i devised a scheme for incremental updating which was so horribly
>>>>>>>>>complicated that i decided not to use it - i'd rather have a slow engine with
>>>>>>>>>little bugs and good maintainability than a fast engine with many bugs and low
>>>>>>>>>maintainability :-)
>>>>>>>>
>>>>>>>>Reminds me of:
>>>>>>>>
>>>>>>>>"Debugging is twice as hard as writing the code in the first place. Therefore,
>>>>>>>>if you write the code as cleverly as possible, you are, by definition, not smart
>>>>>>>>enough to debug it." Brian W. Kernighan
>>>>>>>>
>>>>>>>>At the moment, I don't use attack tables at all. But I want them again. And I
>>>>>>>>also only have a "build-from-scratch" routine. I also thought about incremental
>>>>>>>>updates, and it seems like a very hard job. And the bad thing is, they seem to
>>>>>>>>be especially useful at the leafs or close to the leafs. Perhaps I will start
>>>>>>>>again with using them only closer to the root, for pruning/extension decisions.
>>>>>>>>
>>>>>>>>Regards,
>>>>>>>>Dieter
>>>>>>>
>>>>>>>I update them incrementally.
>>>>>>>I can only give a hint that I simply have a function to update incrementally
>>>>>>>when I add a piece or delete a piece.
>>>>>>>
>>>>>>>I got this idea when I got the conclusion that having a function to update them
>>>>>>>based on a move is a very hard task.
>>>>>>
>>>>>>I think I have the same idea:
>>>>>
>>>>>You left out the interesting part:
>>>>>
>>>>>>
>>>>>>1. Lift the piece off the board, and remove all of its influence
>>>>>
>>>>>1b for every slider attacking the fromsquare, extend its influence
>>>>
>>>>You miss the idea
>>>>
>>>>All the idea is that I consider no from square and no to square in updating the
>>>>attack table.
>>>>
>>>>I look at a move as a sequence of add piece to square and remove the piece from
>>>>square and I have function to update the attack table when I add piece or remove
>>>>piece.
>>>
>>>That is exactly the way I do it in Chest all the time.
>>>Still, extending through a removed piece is necessary, as well as restricting
>>>sliders at a newly placed piece. But you knew that already :-))
>>>
>>>But e.p. and castling are just some more calls of these basic operations.
>>>I have 3 basic operations: put, delete and replace.
>>>
>>>>Uri
>>
>>Here is something I sent to someone else in an email to explain my ideas about
>>it:
>>
>>I have an idea that I like. When you generate the moves, also generate an
>>attack bitmap that is attacked and a shadow bitmap that shows the pins. The
>>attack bitmap is very helpful to know where to step. It is used to update an
>>array or 0x88 board that holds the counts of attacks for each piece type for
>>each square. So you can get a SEE almost for free. (But of course you have the
>>cost of redoing the bitmaps). The reason I bring it up is that it really only
>>useful if you have incremental move generation.
>>
>>I carry a bitmap of the attacks for each piece (even for pawns). I also carry a
>>bitmap of the shadows (pins up to pinned pieces). YOu could use arrays or lists
>>or any other sort of structure that you like. It does not need to be a bitmap.
>>Of course, you can use any mix you like as well. I like an array the shape of a
>>chessboard that contains the following for each square on the board:
>>
>>(Attacks by white pawns) - (Attacks by black pawns)
>>
>>(Attacks by white knights) - (Attacks by black knights)
>>
>>(Attacks by white bishops) - (Attacks by black bishops)
>>
>>(Attacks by white rooks) - (Attacks by black rooks)
>>
>>(Attacks by white queens) - (Attacks by black queens)
>>
>>(Attacks by white kings) - (Attacks by black kings)
>>
>>That is because the pawn attack is the strongest and the king attack is the
>>weakest. Since we can stop whenever we want, ordering them in this way is
>>beneficial. It could be easy enough to sum the knight and bishop attacks
>>together, because they have the same weight. These attacks are for occupied and
>>empty squares. I also keep track of: (Shadow attacks by white bishops) - (Shadow
>>attacks by black bishops) (Shadow attacks by white rooks) - (Shadow attacks by
>>black rooks) (Shadow attacks by white queens) - (Shadow attacks by black queens)
>>These are only valid for sliders. A shadow attack is a square that would be
>>attacked if you move the first piece on the ray out of the way. By keeping this
>>data, you can not only calculate pins but also battery force. SLIDER ONLY STUFF:
>>For each of the 128 [max] possible bit combinations along a rank or file {or
>>diagonal}, I precompute both the attacks and shadow attacks for any of the 128
>>distinct bit combinations (the bit the piece is sitting on is ignored as it is
>>not needed in the array). Hence, the attacks and shadows are simply a lookup for
>>each row/column or diagonal. E.g. {showing row processing only}:
>>+-+-+-+-+-+-+-+-+
>>| |*|R| | |*| | |
>>+-+-+-+-+-+-+-+-+
>> S A d A A A S S
>>S= shadow
>>A=attack
>>d = don't care, it is where I am sitting. {index shifts this bit out for 7 bit
>>index, but 8 bits are returned. Space occupied by piece is always 0}
>>* = any piece/white or black. If my color, I defend it. If opponent color, I
>>attack it.
>>+-+-+-+-+-+-+-+-+
>>| |*|R| | |*|*| |
>>+-+-+-+-+-+-+-+-+
>> S A d A A A S
>>S= shadow
>>A=attack
>>d = don't care, it is where I am sitting.
>>* = any piece/white or black. If my color, I defend it. If opponent color, I
>>attack it. What is returned are two 8-bit bitmaps. E.g. rook on file 3 for the
>>second picture above returns: S = 10000010 A = 01011100 The bitmaps are fed to
>>an accumulator (along with the rank/col/diag) to update the scores. A union of 8
>>unsigned characters and a 64 bit integer also allows direct manipulations of the
>>attack bitboard (handy for calculations like king move legality and 'should I
>>put my queen here...' that sort of thing). By using the attack arrays described
>>above, I can tell without any SEE if I can win or lose a combination
>>(approximately) by looking at the values in the arrays. We have to remember one
>>simple thing: When I move any piece to the target square, his attack vanishes.
>>This will tell me what the biggest piece I should consider to attack with. Of
>>course, a real alpha-beta search might find something better, but for static
>>evaluation, it's pretty neat. This study has also shown me that the A and H
>>pawns are weaklings. They are not worth as much as a B or G pawn because they
>>have less influence.
>
>How neat! That is nearly exactly what I do in Chest, although for different
>reasons (I don't do SEE).
>
>Your attack (A) == direct attack (DATT) in Chest
>Your shadow (S) == indirect attack (IATT) in Chest
>
>Such attack information is e.g. very helpful to estimate mate nets or their
>absence, and similar things. And for generation of legal moves, of course.
>
>Cheers,
>Heiner
I admit that I did not understand Dann's post and some example of diagram with
the content of the attack table may be more productive for me to understand but
I think that I will try your replace function.
hopefully it is only few hours of work because I only need to copy and paste the
right part from other functions and to use the new function correctly and I
guess that it may do the program at least 5% faster.
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.