Author: Bas Hamstra
Date: 11:03:26 01/13/03
Go up one level in this thread
On January 13, 2003 at 13:16:33, Bruce Moreland wrote:
>On January 13, 2003 at 08:13:11, Dieter Buerssner wrote:
>
>>On January 12, 2003 at 17:14:18, Bas Hamstra wrote:
>>
>>A few ideas for microoptimization.
>>
>>>Below the 0x88 function used for SquareAttacked, which for the moment is the
>>>fastest I can think of:
>>>
>>>bool TBoard::SquareAttacked(int To, int ByColor)
>>>
>>>{ int n,
>>> D,
>>> From,
>>> Type,
>>> Sq,
>>> Count = PieceCount[ByColor];
>>>
>>> if(ByColor==WHITE && Bord[To-17] == 13) return true;
>>> if(ByColor==WHITE && Bord[To-15] == 13) return true;
>>> if(ByColor==BLACK && Bord[To+17] == 12) return true;
>>> if(ByColor==BLACK && Bord[To+15] == 12) return true;
>>
>>Here you check for pawn attacks. Instead of handling them seperately outside of
>>the loop, you could double the size of PseudoAtt, and handle them there. This
>>will of course give a larger cache foot-print, but less branches in the loop.
>>
>>If not, I would write something like:
>>
>> if (ByColor==WHITE)
>> {
>> if (Bord[To-17] == 13 || Bord[To-15] == 13)
>> return true:
>> }
>> else
>> {
>> ...
>> }
>>
>>Depending on how well the compiler optimizes, this can be faster, and should
>>never be slower.
>>
>>> for(n=0; n<Count; n++)
>>
>>Here a do while loop (Count will allways be at least one)
>>
>>> { From=PieceList[ByColor][n];
>>
>>Depending on the size of the second dimension of the array, the index
>>calculation may be slightly costy. Also depending on how good the compiler
>>optimizes.
>>
>>A new variable at the top
>> int *PieceListp = PieceList[Bycolor]
>>and
>> From = *PieceListp++;
>>
>>migth be faster here. Depending on how you arrange the Pieclist, you could get
>>rid of n and Count alltogether. For example a marker could be at the end of the
>>pieclist, or the K could allways be at the end.
>>
>>> Type=Bord[From]>>1;
>>
>>Would not be needed, with the larger PseudoAtt.
>>
>>> if(Type==PAWN) break;
>>
>>This branch would not be needed.
>>
>>> if(PseudoAtt[127+To-From] & (1<<Type) )
>>> { if(Type==KING || Type==KNIGHT) return true;
>>
>>Two branches. Depending on how exactly KING andKNIGHT are defined, this could be
>>one. Perhaps, you could try, to leave this out alltogether (the logic further
>>down will also work for kings and knights). Perhaps just an array lookup may be
>>faster. Something like
>>
>>int king_knight[]; /* global, initialized at startup */
>>
>>if (king_knight[type]) return true.
>>
>>
>>
>>> D = Dir[127+To-From];
>>> for(Sq=From+D; Sq!=To; Sq+=D)
>>> if(Bord[Sq]) break;
>>> if(Sq==To) return true;
>>> }
>>> }
>>>
>>> return false;
>>>}
>>
>>It might also be worthhile to do the logic the other way around. Start with the
>>To square, and "generate" moves from there in all directions. This should be
>>faster with many pieces on the board, and especially with Board[To] = King (for
>>Incheck), when the K has a good pawn shelter in typical positions.
>>
>>If one really wants to try everything, perhaps two functions - for white and
>>black, a function array (C style here)
>>
>>
>>int (*SqaureAttackedf[2])(int) = {SquareAttackedWhite, SquareAttackedBlack};
>>
>>Also
>>
>>extern int (*SquareAttackedf[2])(int);
>>
>>in some header, and call via a macro:
>>
>>#define SquareAttacked(to, by) SquareAttackedf[by](to)
>>
>>Assumes, white == 0 and black == 1.
>
>This post has some good stuff, but some of it is soul-selling stuff.
>
>I am opposed to making "white" and "black" functions, because it is difficult to
>keep them current. Invariably, something is missed and one of the functions has
>a bug.
>
>If this is going to be done, it should be done by including a file twice, but
>that is also satanic.
>
>Checking specifically for pawns is probably right. Looking at two squares on
>the board is probably faster than spinning through 8 pawns.
>
>I think that the problem here is that he has a loop in the first place, which is
>just an aspect of 0x88.
>
>I don't know how the bitboard "attacked" function works, but if it does less
>work, it's going to be faster.
Hi Bruce,
The BB function works by generating the attack bitboards for all types for the
from square, and ANDing these with the bitboard for the piecelocations, like
this:
inline bool SquareAttacked(int Square, int ByColor)
{ if(ByColor == CLWHITE)
{ if(KnighAttacks[Square] & WKnights) return true;
if(KingAttacks[Square] & WKing) return true;
if(PawnAttacks[Square] & WPawns) return true;
if(GetRookAttacks(Square) & (WRooks | WQueens) ) return true;
if(GetBishopAttacks(Square) & (WBishops | WQueens) ) return true;
}
// else
{ ...
}
return false;
}
For the nonsliding pieces, attacks are read from an array. For the sliders they
are generated on the fly. It is loopless and pretty quick. Capture generation is
also brilliant, because each attackmap typically contains few capture
possibilities. However when you have to pop *many* bits out of a BB you have a
problem.
Bas.
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.