The wrong way

[Henk]

Also after you have extracted a bit of a move you still have to look up the corresponding move in a dictionary.

Look up what?

You have the "from" square where you started to generated moves for, and you have found a bit position which is exactly the "to" square. What else do you need to look up? All moves, except for the few special move types, only need the "from" and "to" squares to be fully defined.

How does your move representation look like?

My engine only generates moves once and moves are pre-calculated so I have to look them up. Also I assigned a unique number to each move for storing it into a database.

Sorry last is not true. I compute that unique number from the move.

So only argument is that I don't want to create a new move each time. Also for testing if moves are equal I only need to compare the references.

[Sven]

Also after you have extracted a bit of a move you still have to look up the corresponding move in a dictionary.

Look up what?

You have the "from" square where you started to generated moves for, and you have found a bit position which is exactly the "to" square. What else do you need to look up? All moves, except for the few special move types, only need the "from" and "to" squares to be fully defined.

How does your move representation look like?

My engine only generates moves once and moves are pre-calculated so I have to look them up. Also I assigned a unique number to each move for storing it into a database.

Sorry last is not true. I compute that unique number from the move.

So only argument is that I don't want to create a new move each time. Also for testing if moves are equal I only need to compare the references.

Well, that is certainly one way to go, albeit a slow one ...

My move representation is 16 bit (6 bit "from", 6 bit "to", 2 bit for one of four move types, and 2 bit for special purpose depending on move type: either the castling type, the promotion piece, or a flag indicating a pawn double step). Plus 16 bit for the move score, for a total of 32 bit. So my move is just an integer, "creating" it is just masking/shifting some bits.

But even a larger move representation does not require "creation" of a move object each time you generate a new move. I would simply preallocate a move list as an array of fixed length, 256 is a safe upper bound for the length.

Put that on your "optimization" to-do list for next year, after having improved your algorithms

[Henk]

Changed pawns and king captures too. Only 1-3 percent faster. Hardly measurable. Pawns spoiled the party. Also because I had to make an exception for En Passant moves. Might be that code for handling pawn captures is slower now.

Code: Select all

            ....
            CPosition.fieldIterator.Reset(curPieces & pawns & (colorSign == ColorSign.White ? ChessBoard.FIFTH_ROW_BITMAP : ChessBoard.FOURTH_ROW_BITMAP) );
            while ((Location = CPosition.fieldIterator.Next(ChessBoard)) != null)
            {
                DirectionMoves allMoves = ((Field)Location).dirMoves[(int)Location.Occupier.PieceSort];
                var epMoves = allMoves[(int)Pawn.Direction.EP_RIGHT];
                if (epMoves.Count > 0)
                {
                    var move = epMoves[0];
                    if (move.CanMove(colorSign, this, Location))
                    {
                        Debug.Assert((move is EPMove));
                        move.Value = ChessPiece.PP_MVVA_VALUE;
                        moves.Add(move);

                    }
                }

                epMoves = allMoves[(int)Pawn.Direction.EP_LEFT];
                if (epMoves.Count > 0)
                {
                    var move = epMoves[0];
                    if (move.CanMove(colorSign, this, Location))
                    {
                        Debug.Assert((move is EPMove));
                        move.Value = ChessPiece.PP_MVVA_VALUE;
                        moves.Add(move);

                    }
                }
            }

            BitBoardIndex bbIndex = BitBoardIndex.Instance;
            UInt64 bits = curPieces;
            while (bits != 0)
            {
                var bit = bits & (~bits + 1);
                bits &= bits - 1;
                Location = ChessBoard.GetField(bbIndex, bit);
                ChessPiece.Sort PieceSort = Location.Occupier.PieceSort;
                var xrayCaptures = Location.XRayMoves(PieceSort) & opponentPieces;

                if (xrayCaptures != 0 )
                {
                    int dir;
                    switch (PieceSort)
                    {
                         case ChessPiece.Sort.whiteKing:
                         case ChessPiece.Sort.blackKing:
                         case ChessPiece.Sort.whiteKnight:
                         case ChessPiece.Sort.blackKnight:                    
                         case ChessPiece.Sort.whitePawn:
                         case ChessPiece.Sort.blackPawn:

                            do
                            {
                                var Move = xrayCaptures & (~xrayCaptures + 1);
                                xrayCaptures &= xrayCaptures - 1;
                                var move = ((Field)Location).AllMovesDict(PieceSort).Get(Move);
                                AddMove(moves, move, Location.Occupier.PieceKind);
                            }
                            while (xrayCaptures != 0);
                            break;

                            ....

Missing part: slow and simpel. Strangely speed of perft did not change.

Code: Select all

                        case ChessPiece.Sort.whiteQueen:
                        case ChessPiece.Sort.blackQueen:
                        case ChessPiece.Sort.whiteRook:
                        case ChessPiece.Sort.blackRook:
                        case ChessPiece.Sort.whiteBishop:
                        case ChessPiece.Sort.blackBishop:

                            for (dir = 0; dir <= pieceOffsets[occupier.PieceKind].Length-1; dir++)
                            {
                                ulong moveBit = ((SlidingPiece)occupier).BitBoardDirMoves(Board, dir, xrayCaptures);
                                if (moveBit != 0)
                                {
                                    var move = ((Field)location).AllMovesDict(PieceSort).Get(moveBit);
                                    AddMove(moves, move, occupier.PieceKind);
                                }
                            }
                            break;

[Sven]

What does your AddMove () do, in addition to inserting something into a set of moves?

[Henk]

Computes/Assigns MVVA value and clears the move list when king capture found.

Code is now significantly slower perhaps 45 percent. Might even be
because of the order that directions are searched has changed.

Perhaps a queen should first search UP directions ??

I don't know.

[Sven]

Computes/Assigns MVVA value and clears the move list when king capture found.

Do you use the same AddMove() function for both capture and non-capture generation? Would not make sense to me for the non-capture part ...

Code is now significantly slower perhaps 45 percent.

Are you talking about perft speed or tree search speed? What are you comparing against: before your last specific change XY vs. now, or before starting this thread vs. now, or ...?

I don't know which of the many suggestions that were given here has caused your program to perform even worse than before. My focus was not on optimizing but on an appropriate use of your data structures. In general this should not lead to a significant slowdown. If it does then I don't know as well - too many possible reasons for that: bugs, sub-optimal data structures, misinterpretation of some suggestions that were made, maybe even sub-optimal suggestions, ...

[Henk]

I think implementation of BitBoardDirMoves is too slow. So I have to look at that first. I can always restore the old code without bitboards. Ugly and fast.
Only last change in QCollectMoves dealing with sliding piece captures made it slow.

Code: Select all

ulong moveBit = ((SlidingPiece)occupier).BitBoardDirMoves(Board, dir, xrayCaptures); 

But strangely speed of kiwipete perft position has not changed.

[Henk]

I think implementation of BitBoardDirMoves is too slow. So I have to look at that first. I can always restore the old code without bitboards. Ugly and fast.
Only last change in QCollectMoves dealing with sliding piece captures made it slow.

Code: Select all

ulong moveBit = ((SlidingPiece)occupier).BitBoardDirMoves(Board, dir, xrayCaptures); 

But strangely speed of kiwipete perft position has not changed.

Last is not correct. Also perft went from 17 to 24 seconds. For now I put old code back.

[Sven]

Check your PM, please.

[Henk]

So looks like this is currently Skippers fastest version.

Code: Select all

     public void CollectNonCaptureMoves(List<MoveBase> moves)
        {
            PieceOffsets pieceOffsets = PieceOffsets.Instance;
            var colSign = (ColorSign)CurPlayer;
            BitBoardIndex bbIndex = BitBoardIndex.Instance;
            UInt64 curPiecesBB = CurPlayer == 1 ? Board.WhitePieces : Board.BlackPieces;
            List<MoveBase> dirMoves = null;
          
            ulong emptySquares = ~Board.Occupiers;
            DirectionMoves allDirMoves = null;
            
 
            while (curPiecesBB != 0)
            {
                var bit = curPiecesBB & (~curPiecesBB + 1);
                curPiecesBB &= curPiecesBB - 1;
                var location = ChessBoard.GetField(bbIndex, bit);
                var occupier = location.Occupier;
                var pieceSort = occupier.PieceSort;
  
                switch (occupier.PieceSort)
                {
                        case ChessPiece.Sort.whiteKing:
                        {
                            allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.whiteKing);
                            for (int dir = 0; dir < 8; dir++)
                            {
                                dirMoves = allDirMoves[dir];
                                if (dirMoves.Count > 0)
                                {
                                    
                                    if (dirMoves[0].End.Occupier == null)
                                    {
                                        MoveBase move = dirMoves[0];
                                        move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                        moves.Add(move);
                                    }

                                }
                            }


                            for (int dir = 8; dir <= 9; dir++)
                            {
                                dirMoves = allDirMoves[dir];
                                int nDirMoves = dirMoves.Count;
                                if (nDirMoves > 0)
                                {
                                    
                                    if (dirMoves[0].CanMove(colSign, this, location))
                                    {
                                        MoveBase move = dirMoves[0];
                                        move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                        moves.Add(move);
                                    }
                                }
                            }

                        }
                        break;
                    case ChessPiece.Sort.blackKing:
                        {
                            allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.blackKing);
                            for (int dir = 0; dir < 8; dir++)
                            {
                                dirMoves = allDirMoves[dir];
                                if (dirMoves.Count > 0)
                                {
                                   
                                    if (dirMoves[0].End.Occupier == null)
                                    {
                                        MoveBase move = dirMoves[0];
                                        move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                        moves.Add(move);
                                    }

                                }
                            }
                           
                           
                            for (int dir = 8; dir <= 9; dir++)
                            {
                                dirMoves = allDirMoves[dir];
                                int nDirMoves = dirMoves.Count;
                                if (nDirMoves > 0)
                                {
                                    
                                    if (dirMoves[0].CanMove(colSign, this, location))
                                    {
                                        MoveBase move = dirMoves[0];
                                        move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                        moves.Add(move);
                                    }
                                }
                            }

                        }
                        break;
                    case ChessPiece.Sort.whitePawn:
                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.whitePawn);
                        dirMoves = allDirMoves[(int)Pawn.Direction.FRONT];
                       
                        for (int j = 0; j < dirMoves.Count; j++)
                        {
                            MoveBase move = dirMoves[j];
                            if (move.End.Occupier == null)
                            {
                                move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                moves.Add(move);
                            }
                            else
                            {
                                break;
                            }
                        }

                        break;
                    case ChessPiece.Sort.blackPawn:

                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.blackPawn);
                        dirMoves = allDirMoves[(int)Pawn.Direction.FRONT];
                       
                        for (int j = 0; j < dirMoves.Count; j++)
                        {
                            MoveBase move = dirMoves[j];
                            if (move.End.Occupier == null)
                            {
                                move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                moves.Add(move);
                            }
                            else
                            {
                                break;
                            }
                        }
                      
                        break;
                    case ChessPiece.Sort.whiteQueen:
                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.whiteQueen);
                        for (int dir = 0; dir < 8; dir++)
                        {
                            dirMoves = allDirMoves[dir];
                            for (int j = 0; j < dirMoves.Count; j++)
                            {
                                MoveBase move = dirMoves[j];
                                if (move.End.Occupier == null)
                                {
                                    move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                    moves.Add(move);
                                }
                                else
                                {
                                    break;
                                }
                            }
                        }
                        break;
                    case ChessPiece.Sort.blackQueen:
                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.blackQueen);
                        for (int dir = 0; dir < 8; dir++)
                        {
                            dirMoves = allDirMoves[dir];
                            for (int j = 0; j < dirMoves.Count; j++)
                            {
                                MoveBase move = dirMoves[j];
                                if (move.End.Occupier == null)
                                {
                                    move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                    moves.Add(move);
                                }
                                else
                                {
                                    break;
                                }
                            }
                        }
                        break;
                    case ChessPiece.Sort.whiteRook:
                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.whiteRook);
                        for (int dir = 0; dir < 4; dir++)
                        {
                            dirMoves = allDirMoves[dir];
                            for (int j = 0; j < dirMoves.Count; j++)
                            {
                                MoveBase move = dirMoves[j];
                                if (move.End.Occupier == null)
                                {
                                    move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                    moves.Add(move);
                                }
                                else
                                {
                                    break;
                                }
                            }
                        }
                        break;
                    case ChessPiece.Sort.blackRook:
                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.blackRook);
                        for (int dir = 0; dir < 4; dir++)
                        {
                            dirMoves = allDirMoves[dir];
                            for (int j = 0; j < dirMoves.Count; j++)
                            {
                                MoveBase move = dirMoves[j];
                                if (move.End.Occupier == null)
                                {
                                    move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                    moves.Add(move);
                                }
                                else
                                {
                                    break;
                                }
                            }
                        }
                        break;
                    case ChessPiece.Sort.whiteBishop:
                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.whiteBishop);

                     
                        for (int dir = 0; dir < 4; dir++)
                        {
                            dirMoves = allDirMoves[dir];
                            for (int j = 0; j < dirMoves.Count; j++)
                            {
                                MoveBase move = dirMoves[j];
                                if (move.End.Occupier == null)
                                {
                                    move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                    moves.Add(move);
                                }
                                else
                                {
                                    break;
                                }
                            }
                        }
                        break;
                    case ChessPiece.Sort.blackBishop:
                  

                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.blackBishop);
                      
                         
                        for (int dir = 0; dir < 4; dir++)
                        {
                            dirMoves = allDirMoves[dir];
                            for (int j = 0; j < dirMoves.Count; j++)
                            {
                                MoveBase move = dirMoves[j];
                                if (move.End.Occupier == null)
                                {
                                    move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                    moves.Add(move);
                                }
                                else
                                {
                                    break;
                                }
                            }
                        }

                        break;
                    case ChessPiece.Sort.whiteKnight:
                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.whiteKnight);
                        for (int dir = 0; dir < 8; dir++)
                        {
                            dirMoves = allDirMoves[dir];
                            if (dirMoves.Count > 0)
                            {
                                MoveBase move = dirMoves[0];
                                if (move.End.Occupier == null)
                                {
                                    move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                    moves.Add(move);
                                }
                            }
                        }
                        break;
                    case ChessPiece.Sort.blackKnight:
                   
                        allDirMoves = location.XRayDirectionMoves(ChessPiece.Sort.blackKnight);
                        for (int dir = 0; dir < 8; dir++)
                        {
                            dirMoves = allDirMoves[dir];
                            if  (dirMoves.Count> 0)
                            {
                                MoveBase move = dirMoves[0];
                                if (move.End.Occupier == null)
                                {
                                    move.Value = (int)(HistoryTable.GetHistoryValue(move));
                                    moves.Add(move);
                                }
                            }
                        }
                        break;
                                         
                }
               
            }
            moves.Sort(OneLevelMoveSelector.descMoveValueComparer);
        }