Author: Heiner Marxen
Date: 02:57:02 03/24/04
Go up one level in this thread
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
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.