Henk, what you have here is not a bitboard engine. It is a mailbox engine using bitboards. You're not going to get any speed improvement if you don't harness the full power of bitboards.
Rewrite your generator to use the bitboard serialization idiom, and you'll be significantly faster.
Alternatively, use a mailbox board representation.
Matthew:out
The wrong way
Moderator: Ras
-
ZirconiumX
- Posts: 1359
- Joined: Sun Jul 17, 2011 11:14 am
- Full name: Hannah Ravensloft
Re: The wrong way
tu ne cede malis, sed contra audentior ito
-
Henk
- Posts: 7251
- Joined: Mon May 27, 2013 10:31 am
Re: The wrong way
I have already tried that. Does not work. Makes it much slower. But I used
these definitions: http://www.mayothi.com/nagaskakichess6.html
So you get something like this.
these definitions: http://www.mayothi.com/nagaskakichess6.html
So you get something like this.
Code: Select all
public static UInt64 Moves(IChessPosition pos, UInt64 andMask, IShiftOperator shift, int multiplier, UInt64 locationDirMoves)
{
UInt64 occupiedDirMoves = pos.Board.Occupiers & locationDirMoves;
return
(locationDirMoves ^ (
(
shift.Shift(occupiedDirMoves, multiplier)
| shift.Shift(occupiedDirMoves, 2 * multiplier)
| shift.Shift(occupiedDirMoves, 3 * multiplier)
| shift.Shift(occupiedDirMoves, 4 * multiplier)
| shift.Shift(occupiedDirMoves, 5 * multiplier)
| shift.Shift(occupiedDirMoves, 6 * multiplier)
) & locationDirMoves
)
) & andMask;
}
-
ZirconiumX
- Posts: 1359
- Joined: Sun Jul 17, 2011 11:14 am
- Full name: Hannah Ravensloft
Re: The wrong way
That website uses a fairly inefficient attack getter. Try an implementation of Magic Bitboards.Henk wrote:I have already tried that. Does not work. Makes it much slower. But I used
these definitions: http://www.mayothi.com/nagaskakichess6.html
So you get something like this.Code: Select all
public static UInt64 Moves(IChessPosition pos, UInt64 andMask, IShiftOperator shift, int multiplier, UInt64 locationDirMoves) { UInt64 occupiedDirMoves = pos.Board.Occupiers & locationDirMoves; return (locationDirMoves ^ ( ( shift.Shift(occupiedDirMoves, multiplier) | shift.Shift(occupiedDirMoves, 2 * multiplier) | shift.Shift(occupiedDirMoves, 3 * multiplier) | shift.Shift(occupiedDirMoves, 4 * multiplier) | shift.Shift(occupiedDirMoves, 5 * multiplier) | shift.Shift(occupiedDirMoves, 6 * multiplier) ) & locationDirMoves ) ) & andMask; }
As for your code, is your code so high level you have to overload the shift operator to achieve OOP?
By the way, is this C#?
Matthew:out
tu ne cede malis, sed contra audentior ito
-
Henk
- Posts: 7251
- Joined: Mon May 27, 2013 10:31 am
Re: The wrong way
Yes C#. I only used these definitions on that website for it was relatively easy to understand. (Clear explanation and examples).
For bishop you get:
For bishop you get:
Code: Select all
public UInt64 RightUpMoves(IChessPosition pos, UInt64 andMask)
{
return Moves(pos, andMask, leftShift, 9, Location.RightUpMoves);
}
public UInt64 LeftUpMoves(IChessPosition pos, UInt64 andMask)
{
return Moves(pos, andMask, leftShift, 7, Location.LeftUpMoves);
}
public UInt64 LeftDownMoves(IChessPosition pos, UInt64 andMask)
{
return Moves(pos, andMask, rightShift, 9, Location.LeftDownMoves);
}
public UInt64 RightDownMoves(IChessPosition pos, UInt64 andMask)
{
return Moves(pos, andMask, rightShift, 7, Location.RightDownMoves);
}
-
Henk
- Posts: 7251
- Joined: Mon May 27, 2013 10:31 am
Re: The wrong way
Can't post the whole method. For it is too long. Speed is comparable.
Code: Select all
...
case ChessPiece.Sort.whiteQueen:
var dirMovesWQ = location.DirMoves(ChessPiece.Sort.whiteQueen);
var moveDictWQ = ((Field)location).WhiteQueenMovesDict;
if ((dirMovesWQ[0] & opponentPieces) != 0)
{
var locationDirMoves = location.LeftMoves;
var occupiedDirMoves = occupiers & locationDirMoves;
moveBit =
(locationDirMoves ^ (
(
occupiedDirMoves >> 1
| occupiedDirMoves >> 2
| occupiedDirMoves >> 3
| occupiedDirMoves >> 4
| occupiedDirMoves >> 5
| occupiedDirMoves >> 6
) & locationDirMoves
)
) & xrayCaptures;
if (moveBit != 0)
{
var move = moveDictWQ.Get(moveBit);
switch (move.End.Occupier.PieceKind)
{
case ChessPiece.Kind.King:
moves.Clear();
moves.Add(move);
return;
case ChessPiece.Kind.Pawn:
move.Value = ChessPiece.PQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Knight:
move.Value = ChessPiece.NQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Bishop:
move.Value = ChessPiece.BQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Rook:
move.Value = ChessPiece.RQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Queen:
move.Value = ChessPiece.QQ_MVVA_VALUE;
break;
}
moves.Add(move);
}
}
if ((dirMovesWQ[1] & opponentPieces) != 0)
{
var locationDirMoves = location.RightMoves;
var occupiedDirMoves = occupiers & locationDirMoves;
moveBit =
(locationDirMoves ^ (
(
occupiedDirMoves << 1
| occupiedDirMoves << 2
| occupiedDirMoves << 3
| occupiedDirMoves << 4
| occupiedDirMoves << 5
| occupiedDirMoves << 6
) & locationDirMoves
)
) & xrayCaptures;
if (moveBit != 0)
{
var move = moveDictWQ.Get(moveBit);
switch (move.End.Occupier.PieceKind)
{
case ChessPiece.Kind.King:
moves.Clear();
moves.Add(move);
return;
case ChessPiece.Kind.Pawn:
move.Value = ChessPiece.PQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Knight:
move.Value = ChessPiece.NQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Bishop:
move.Value = ChessPiece.BQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Rook:
move.Value = ChessPiece.RQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Queen:
move.Value = ChessPiece.QQ_MVVA_VALUE;
break;
}
moves.Add(move);
}
}
if ((dirMovesWQ[2] & opponentPieces) != 0)
{
var locationDirMoves = location.DownMoves;
var occupiedDirMoves = occupiers & locationDirMoves;
moveBit =
(locationDirMoves ^ (
(
occupiedDirMoves >> 8
| occupiedDirMoves >> 16
| occupiedDirMoves >> 24
| occupiedDirMoves >> 32
| occupiedDirMoves >> 40
| occupiedDirMoves >> 48
) & locationDirMoves
)
) & xrayCaptures;
if (moveBit != 0)
{
var move = moveDictWQ.Get(moveBit);
switch (move.End.Occupier.PieceKind)
{
case ChessPiece.Kind.King:
moves.Clear();
moves.Add(move);
return;
case ChessPiece.Kind.Pawn:
move.Value = ChessPiece.PQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Knight:
move.Value = ChessPiece.NQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Bishop:
move.Value = ChessPiece.BQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Rook:
move.Value = ChessPiece.RQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Queen:
move.Value = ChessPiece.QQ_MVVA_VALUE;
break;
}
moves.Add(move);
}
}
if ((dirMovesWQ[3] & opponentPieces) != 0)
{
var locationDirMoves = location.UpMoves;
var occupiedDirMoves = occupiers & locationDirMoves;
moveBit =
(locationDirMoves ^ (
(
occupiedDirMoves << 8
| occupiedDirMoves << 16
| occupiedDirMoves << 24
| occupiedDirMoves << 32
| occupiedDirMoves << 40
| occupiedDirMoves << 48
) & locationDirMoves
)
) & xrayCaptures;
if (moveBit != 0)
{
var move = moveDictWQ.Get(moveBit);
switch (move.End.Occupier.PieceKind)
{
case ChessPiece.Kind.King:
moves.Clear();
moves.Add(move);
return;
case ChessPiece.Kind.Pawn:
move.Value = ChessPiece.PQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Knight:
move.Value = ChessPiece.NQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Bishop:
move.Value = ChessPiece.BQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Rook:
move.Value = ChessPiece.RQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Queen:
move.Value = ChessPiece.QQ_MVVA_VALUE;
break;
}
moves.Add(move);
}
}
if ((dirMovesWQ[4] & opponentPieces) != 0)
{
var locationDirMoves = location.RightDownMoves;
var occupiedDirMoves = occupiers & locationDirMoves;
moveBit =
(locationDirMoves ^ (
(
occupiedDirMoves >> 7
| occupiedDirMoves >> 14
| occupiedDirMoves >> 21
| occupiedDirMoves >> 28
| occupiedDirMoves >> 35
| occupiedDirMoves >> 42
) & locationDirMoves
)
) & xrayCaptures;
if (moveBit != 0)
{
var move = moveDictWQ.Get(moveBit);
switch (move.End.Occupier.PieceKind)
{
case ChessPiece.Kind.King:
moves.Clear();
moves.Add(move);
return;
case ChessPiece.Kind.Pawn:
move.Value = ChessPiece.PQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Knight:
move.Value = ChessPiece.NQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Bishop:
move.Value = ChessPiece.BQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Rook:
move.Value = ChessPiece.RQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Queen:
move.Value = ChessPiece.QQ_MVVA_VALUE;
break;
}
moves.Add(move);
}
}
if ((dirMovesWQ[5] & opponentPieces) != 0)
{
var locationDirMoves = location.LeftUpMoves;
var occupiedDirMoves = occupiers & locationDirMoves;
moveBit =
(locationDirMoves ^ (
(
occupiedDirMoves << 7
| occupiedDirMoves << 14
| occupiedDirMoves << 21
| occupiedDirMoves << 28
| occupiedDirMoves << 35
| occupiedDirMoves << 42
) & locationDirMoves
)
) & xrayCaptures;
if (moveBit != 0)
{
var move = moveDictWQ.Get(moveBit);
switch (move.End.Occupier.PieceKind)
{
case ChessPiece.Kind.King:
moves.Clear();
moves.Add(move);
return;
case ChessPiece.Kind.Pawn:
move.Value = ChessPiece.PQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Knight:
move.Value = ChessPiece.NQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Bishop:
move.Value = ChessPiece.BQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Rook:
move.Value = ChessPiece.RQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Queen:
move.Value = ChessPiece.QQ_MVVA_VALUE;
break;
}
moves.Add(move);
}
}
if ((dirMovesWQ[6] & opponentPieces) != 0)
{
var locationDirMoves = location.LeftDownMoves;
var occupiedDirMoves = occupiers & locationDirMoves;
moveBit =
(locationDirMoves ^ (
(
occupiedDirMoves >> 9
| occupiedDirMoves >> 18
| occupiedDirMoves >> 27
| occupiedDirMoves >> 36
| occupiedDirMoves >> 45
| occupiedDirMoves >> 54
) & locationDirMoves
)
) & xrayCaptures;
if (moveBit != 0)
{
var move = moveDictWQ.Get(moveBit);
switch (move.End.Occupier.PieceKind)
{
case ChessPiece.Kind.King:
moves.Clear();
moves.Add(move);
return;
case ChessPiece.Kind.Pawn:
move.Value = ChessPiece.PQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Knight:
move.Value = ChessPiece.NQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Bishop:
move.Value = ChessPiece.BQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Rook:
move.Value = ChessPiece.RQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Queen:
move.Value = ChessPiece.QQ_MVVA_VALUE;
break;
}
moves.Add(move);
}
}
if ((dirMovesWQ[7] & opponentPieces) != 0)
{
var locationDirMoves = location.RightUpMoves;
var occupiedDirMoves = occupiers & locationDirMoves;
moveBit =
(locationDirMoves ^ (
(
occupiedDirMoves << 9
| occupiedDirMoves << 18
| occupiedDirMoves << 27
| occupiedDirMoves << 36
| occupiedDirMoves << 45
| occupiedDirMoves << 54
) & locationDirMoves
)
) & xrayCaptures;
if (moveBit != 0)
{
var move = moveDictWQ.Get(moveBit);
switch (move.End.Occupier.PieceKind)
{
case ChessPiece.Kind.King:
moves.Clear();
moves.Add(move);
return;
case ChessPiece.Kind.Pawn:
move.Value = ChessPiece.PQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Knight:
move.Value = ChessPiece.NQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Bishop:
move.Value = ChessPiece.BQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Rook:
move.Value = ChessPiece.RQ_MVVA_VALUE;
break;
case ChessPiece.Kind.Queen:
move.Value = ChessPiece.QQ_MVVA_VALUE;
break;
}
moves.Add(move);
}
}
break;
...
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: The wrong way
The whole method for *what* ? Bitboards capture move generator? Still no substantial use of bitboards so far ...Henk wrote:Can't post the whole method. For it is too long. Speed is comparable.
Once more: get rid of thinking in "directions" in a bitboard program. Simply forget it. Get all sliding attacks in one function call (diagonal for bishops, orthogonal for rooks, both for queens) which returns *one* bitboard. Then, depending on capture or non-capture generation (or other purposes like in-check detection), AND either with bitboard of all enemy pieces or with bitboard of all empty squares. The result is *one* bitboard showing all your target squares. Now loop over this bitboard, unfolding it into moves which you put into your move list.
And again: don't measure speed for the next months, please. Measure code quality. Your whole engine infrastructure would need a lot of changes to allow for substantial speed improvements but you will never get there with unmanageable low-quality code. Appropriate data structures and algorithms are important, and a bug-free implementation, not optimization. You can optimize the performance of the functions that return the bitboard of all diagonal resp. orthogonal slider attacks at once in a later step (e.g. by switching from an ad-hoc "manual" approach to magic bitboards or another fast implementation), but you can already use it in the move generator (and in-check detection and mobility evaluation and ...) before having done so. You can also optimize your data structures later (e.g. get rid of looking up moves in a move database) but if you carefully hide implementation details then this will turn out to be much easier. Why else would you use an OO language like C# if you are not willing to use abstraction and encapsulation?
Don't write huge monolithic code. Use smaller functions to break down the problem into smaller sub-problems.
Don't clear the move list on detecting a king capture, just assign a high MVV/LVA score to it. (I would even drop the king capture stuff at all but that's another story.)
Don't repeat the MVV/LVA calculation switch statement 1000 times, please. That's utter bullshit! Please, put it into a function. By following my advice regarding king capture detection above, such a function would become trivial since it would not have to bother with the special case where you want your whole move generator function to return immediately (but your current approach makes that a bit harder).
And please, don't unfold a loop manually for i=1..8 with a loop body of considerable size, that's a compiler's job ... simply use a loop for it and, if really necessary, put data that depends on the value of "i" into an array[1..8] or similar.
I would also avoid to loop over all friendly pieces, checking each one for its type and then doing the corresponding action (your outermost loop of the move generator). That is a from-scratch mailbox approach (and even that can be done better with a piece list). But you have a bitboard representation of the board. You have a pawns bitboard, so generate pawn moves by just using these bits (no need to lookup their piece type, they are all pawns). Then you have a knights bitboard, so generate knight moves. Then king moves. Then sliding moves. Each part in a separate function. Done.
A considerable part of the program's performance will come automatically with good algorithms and data structures.
Try to get rid of "unusual" stuff as much as possible.
Look how strong bitboard programs do it. No need to copy them, just look and learn.
The biggest part of my move generation code in my (not very strong) bitboard programs is usually for pawn moves and castling, due to the many special cases. The smallest part is for everything else, like in this C++ example (note the reuse of the "generate...MovesTo()" functions):
Code: Select all
template <Color self, Color opp>
static void generateKnightMovesTo(uint64_t bbTargets, Board const & b, MoveList & moveList)
{
uint64_t bbMyKnights(b.bbPieces(Knight, self));
while (bbMyKnights != 0) {
SqrId from(BitUtil::popAndGetPositionOfLSB(bbMyKnights));
uint64_t bbMoves(Attacks::allKnightAttacksFrom(from) & bbTargets);
while (bbMoves != 0) {
generateOneMove(Move(from, BitUtil::popAndGetPositionOfLSB(bbMoves)), b, moveList);
}
}
}
template <Color self, Color opp>
static void generateKingMovesTo(uint64_t bbTargets, Board const & b, MoveList & moveList)
{
uint64_t bbMyKing(b.bbPieces(King, self));
ASSERT(BitUtil::popCount64Sparse(bbMyKing) == 1);
SqrId from(BitUtil::positionOfLSB(bbMyKing));
uint64_t bbMoves(Attacks::allKingAttacksFrom(from) & bbTargets);
while (bbMoves != 0) {
generateOneMove(Move(from, BitUtil::popAndGetPositionOfLSB(bbMoves)), b, moveList);
}
}
template <Color self, Color opp>
static void generateSlidingMovesTo(uint64_t bbTargets, Board const & b, MoveList & moveList)
{
{
uint64_t bbMyDiagonalPieces(b.bbPieces(Queen, self) | b.bbPieces(Bishop, self));
while (bbMyDiagonalPieces != 0) {
SqrId from(BitUtil::popAndGetPositionOfLSB(bbMyDiagonalPieces));
uint64_t bbMoves(Attacks::bishopAttacksFrom(from, b.bbOccupied()) & bbTargets);
while (bbMoves != 0) {
generateOneMove(Move(from, BitUtil::popAndGetPositionOfLSB(bbMoves)), b, moveList);
}
}
uint64_t bbMyStraightPieces(b.bbPieces(Queen, self) | b.bbPieces(Rook, self));
while (bbMyStraightPieces != 0) {
SqrId from(BitUtil::popAndGetPositionOfLSB(bbMyStraightPieces));
uint64_t bbMoves(Attacks::rookAttacksFrom(from, b.bbOccupied()) & bbTargets);
while (bbMoves != 0) {
generateOneMove(Move(from, BitUtil::popAndGetPositionOfLSB(bbMoves)), b, moveList);
}
}
}
}
template <Color self, Color opp, bool QS>
static void generateTacticalMoves(Board const & b, MoveList & moveList)
{
generateAllPromotions<self, opp, QS>(b.bbOccupied(opp), b, moveList);
// TODO: ep captures
generatePawnCaptures <self, opp> (b.bbOccupied(opp), b, moveList);
generateKnightMovesTo <self, opp> (b.bbOccupied(opp), b, moveList);
generateKingMovesTo <self, opp> (b.bbOccupied(opp), b, moveList);
generateSlidingMovesTo <self, opp> (b.bbOccupied(opp), b, moveList);
}
// public interface methods
template <Color self, Color opp>
static void generateQuietMoves(Board const & b, MoveList & moveList)
{
// TODO: castling moves
generatePawnMoves <self, opp> ( b, moveList);
generateKnightMovesTo <self, opp> (b.bbEmpty(), b, moveList);
generateKingMovesTo <self, opp> (b.bbEmpty(), b, moveList);
generateSlidingMovesTo <self, opp> (b.bbEmpty(), b, moveList);
}
// static
template <Color self, Color opp>
void MoveGenerator::generateAllMoves(Board const & b, MoveList & moveList)
{
generateTacticalMoves<self, opp, false> (b, moveList);
generateQuietMoves <self, opp> (b, moveList);
}
// static
template <Color self, Color opp>
void MoveGenerator::generateQSMoves(Board const & b, MoveList & moveList)
{
generateTacticalMoves<self, opp, true> (b, moveList);
}-
Henk
- Posts: 7251
- Joined: Mon May 27, 2013 10:31 am
Re: The wrong way
I think looping (iterating) again over the bitboard moves is too slow. Also function calls are too slow on this level. By the way I found another simple optimization so I have to rewrite it anyhow. It is all about speed now. Every instruction counts.Sven Schüle wrote:The whole method for *what* ? Bitboards capture move generator? Still no substantial use of bitboards so far ...Henk wrote:Can't post the whole method. For it is too long. Speed is comparable.
Once more: get rid of thinking in "directions" in a bitboard program. Simply forget it. Get all sliding attacks in one function call (diagonal for bishops, orthogonal for rooks, both for queens) which returns *one* bitboard. Then, depending on capture or non-capture generation (or other purposes like in-check detection), AND either with bitboard of all enemy pieces or with bitboard of all empty squares. The result is *one* bitboard showing all your target squares. Now loop over this bitboard, unfolding it into moves which you put into your move list.
And again: don't measure speed for the next months, please. Measure code quality. Your whole engine infrastructure would need a lot of changes to allow for substantial speed improvements but you will never get there with unmanageable low-quality code. Appropriate data structures and algorithms are important, and a bug-free implementation, not optimization. You can optimize the performance of the functions that return the bitboard of all diagonal resp. orthogonal slider attacks at once in a later step (e.g. by switching from an ad-hoc "manual" approach to magic bitboards or another fast implementation), but you can already use it in the move generator (and in-check detection and mobility evaluation and ...) before having done so. You can also optimize your data structures later (e.g. get rid of looking up moves in a move database) but if you carefully hide implementation details then this will turn out to be much easier. Why else would you use an OO language like C# if you are not willing to use abstraction and encapsulation?
Don't write huge monolithic code. Use smaller functions to break down the problem into smaller sub-problems.
Don't clear the move list on detecting a king capture, just assign a high MVV/LVA score to it. (I would even drop the king capture stuff at all but that's another story.)
Don't repeat the MVV/LVA calculation switch statement 1000 times, please. That's utter bullshit! Please, put it into a function. By following my advice regarding king capture detection above, such a function would become trivial since it would not have to bother with the special case where you want your whole move generator function to return immediately (but your current approach makes that a bit harder).
And please, don't unfold a loop manually for i=1..8 with a loop body of considerable size, that's a compiler's job ... simply use a loop for it and, if really necessary, put data that depends on the value of "i" into an array[1..8] or similar.
I would also avoid to loop over all friendly pieces, checking each one for its type and then doing the corresponding action (your outermost loop of the move generator). That is a from-scratch mailbox approach (and even that can be done better with a piece list). But you have a bitboard representation of the board. You have a pawns bitboard, so generate pawn moves by just using these bits (no need to lookup their piece type, they are all pawns). Then you have a knights bitboard, so generate knight moves. Then king moves. Then sliding moves. Each part in a separate function. Done.
A considerable part of the program's performance will come automatically with good algorithms and data structures.
Try to get rid of "unusual" stuff as much as possible.
Look how strong bitboard programs do it. No need to copy them, just look and learn.
The biggest part of my move generation code in my (not very strong) bitboard programs is usually for pawn moves and castling, due to the many special cases. The smallest part is for everything else, like in this C++ example (note the reuse of the "generate...MovesTo()" functions):Code: Select all
template <Color self, Color opp> static void generateKnightMovesTo(uint64_t bbTargets, Board const & b, MoveList & moveList) { uint64_t bbMyKnights(b.bbPieces(Knight, self)); while (bbMyKnights != 0) { SqrId from(BitUtil::popAndGetPositionOfLSB(bbMyKnights)); uint64_t bbMoves(Attacks::allKnightAttacksFrom(from) & bbTargets); while (bbMoves != 0) { generateOneMove(Move(from, BitUtil::popAndGetPositionOfLSB(bbMoves)), b, moveList); } } } template <Color self, Color opp> static void generateKingMovesTo(uint64_t bbTargets, Board const & b, MoveList & moveList) { uint64_t bbMyKing(b.bbPieces(King, self)); ASSERT(BitUtil::popCount64Sparse(bbMyKing) == 1); SqrId from(BitUtil::positionOfLSB(bbMyKing)); uint64_t bbMoves(Attacks::allKingAttacksFrom(from) & bbTargets); while (bbMoves != 0) { generateOneMove(Move(from, BitUtil::popAndGetPositionOfLSB(bbMoves)), b, moveList); } } template <Color self, Color opp> static void generateSlidingMovesTo(uint64_t bbTargets, Board const & b, MoveList & moveList) { { uint64_t bbMyDiagonalPieces(b.bbPieces(Queen, self) | b.bbPieces(Bishop, self)); while (bbMyDiagonalPieces != 0) { SqrId from(BitUtil::popAndGetPositionOfLSB(bbMyDiagonalPieces)); uint64_t bbMoves(Attacks::bishopAttacksFrom(from, b.bbOccupied()) & bbTargets); while (bbMoves != 0) { generateOneMove(Move(from, BitUtil::popAndGetPositionOfLSB(bbMoves)), b, moveList); } } uint64_t bbMyStraightPieces(b.bbPieces(Queen, self) | b.bbPieces(Rook, self)); while (bbMyStraightPieces != 0) { SqrId from(BitUtil::popAndGetPositionOfLSB(bbMyStraightPieces)); uint64_t bbMoves(Attacks::rookAttacksFrom(from, b.bbOccupied()) & bbTargets); while (bbMoves != 0) { generateOneMove(Move(from, BitUtil::popAndGetPositionOfLSB(bbMoves)), b, moveList); } } } } template <Color self, Color opp, bool QS> static void generateTacticalMoves(Board const & b, MoveList & moveList) { generateAllPromotions<self, opp, QS>(b.bbOccupied(opp), b, moveList); // TODO: ep captures generatePawnCaptures <self, opp> (b.bbOccupied(opp), b, moveList); generateKnightMovesTo <self, opp> (b.bbOccupied(opp), b, moveList); generateKingMovesTo <self, opp> (b.bbOccupied(opp), b, moveList); generateSlidingMovesTo <self, opp> (b.bbOccupied(opp), b, moveList); } // public interface methods template <Color self, Color opp> static void generateQuietMoves(Board const & b, MoveList & moveList) { // TODO: castling moves generatePawnMoves <self, opp> ( b, moveList); generateKnightMovesTo <self, opp> (b.bbEmpty(), b, moveList); generateKingMovesTo <self, opp> (b.bbEmpty(), b, moveList); generateSlidingMovesTo <self, opp> (b.bbEmpty(), b, moveList); } // static template <Color self, Color opp> void MoveGenerator::generateAllMoves(Board const & b, MoveList & moveList) { generateTacticalMoves<self, opp, false> (b, moveList); generateQuietMoves <self, opp> (b, moveList); } // static template <Color self, Color opp> void MoveGenerator::generateQSMoves(Board const & b, MoveList & moveList) { generateTacticalMoves<self, opp, true> (b, moveList); }
I agree writing out loops makes no sense for compiler does that better.
Also iterating the bits per piece type is extra work and therefor too slow. I already tried something like that before.
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: The wrong way
Henk, unfortunately you haven't understood anything of what I wrote. For now I give up.Henk wrote:I think looping (iterating) again over the bitboard moves is too slow. Also function calls are too slow on this level. By the way I found another simple optimization so I have to rewrite it anyhow. It is all about speed now. Every instruction counts.
I agree writing out loops makes no sense for compiler does that better.
Also iterating the bits per piece type is extra work and therefor too slow. I already tried something like that before.
-
Henk
- Posts: 7251
- Joined: Mon May 27, 2013 10:31 am
Re: The wrong way
ok, last optimization did not work. So I will copy (if I have time) the code given with the straight and diagonal pieces. I assume it is allowed.
See if that makes it faster.
See if that makes it faster.
-
ZirconiumX
- Posts: 1359
- Joined: Sun Jul 17, 2011 11:14 am
- Full name: Hannah Ravensloft
Re: The wrong way
I hate to pull a Lucas Braesch on you, Henk, but I think you're missing something obvious.Henk wrote:ok, last optimization did not work. So I will copy (if I have time) the code given with the straight and diagonal pieces. I assume it is allowed.
See if that makes it faster.
Your code is written in C#. This is the fundamental reason why your code is slow.
If you want to continue writing your slow program in C#, fine, but remember than C# is the bottleneck here.
Matthew:out
tu ne cede malis, sed contra audentior ito