I need help, performance wall!

[nevatre]

You could place your stand pat test before your move generation and sorting, if you haven't already done it in the second version.

[hgm]

I am not using Principle Variation or Iterative Deepening, Just vanilla Alpha Beta.

You can still use vanilla Alpha Beta and search the PV first. Doing depth-first without having any idea what the PV is is quite suicidal, and probably fully explains all your problems.

Even micro-Max 1.6 determines through iterative deepening what the best move is, to search that first at higher depth. In every node, actually. With just 1433 characters of source code it hardly can do anything more...

But it sounds like micro-Max 1.6 would blast your engine out of the water...

[aberent]

I am not using Principle Variation or Iterative Deepening, Just vanilla Alpha Beta.

You can still use vanilla Alpha Beta and search the PV first. Doing depth-first without having any idea what the PV is is quite suicidal, and probably fully explains all your problems.

Ok this sounds promising but I am not sure what you mean. What do you mean by "search the PV first"

[aberent]

You could place your stand pat test before your move generation and sorting, if you haven't already done it in the second version.

Good catch, already done in my version at home

[hgm]

Ok this sounds promising but I am not sure what you mean. What do you mean by "search the PV first"

If at the 3-ply iteration you find the PV = e2e4 - e7e5 - g1f3, search for the 4-ply iteration first the branch that starts with e2e4 - e7e5 - g1f3. I.e. at ply=0 (root) search e2e4 first, then, in the ply=1 node after e2e4 search e7e5 first, etc. At ply=3 you are beyond the end of your old PV, so you try the best capture first, or the moves in random order. (There is only one more ply to go, and the window is still fully open, so this is good enough.)

[aberent]

In case someone has the time, here is my AlphaBeta. This is the second version that makes one move at a time, maybe you guys can see a bug?

Code: Select all

internal static int AlphaBetaFast(Board examineBoard, byte depth, int alpha, int beta, ChessPieceColor movingSide, ref int nodesSearched, bool quiescence, bool extended)
        {
            nodesSearched++;

            if (depth == 0)
            {
                //If last move was a capture
                if (examineBoard.LastMove.TakenPiece.PieceType != ChessPieceType.None && quiescence == false)
                {
                    //Perform a Quiessence Search
                    return AlphaBetaFast(examineBoard, 6, alpha, beta, movingSide, ref nodesSearched, true, true);
                }
                if (extended == false)
                {
                    if ((examineBoard.BlackCheck || examineBoard.WhiteCheck) && examineBoard.EndGamePhase)
                    {
                        return AlphaBetaFast(examineBoard, 3, alpha, beta, movingSide, ref nodesSearched, false, true);
                    }
                }

                //Evaluate Score
                Evaluation.EvaluateBoardScore(examineBoard);
                //Invert Score to support Negamax
                examineBoard.Score = AbsoluteScore(examineBoard.Score, GetOppositeColor(movingSide));

                return examineBoard.Score;
            }

            if (examineBoard.FiftyMove >= 50 || examineBoard.RepeatedMove >= 3 || examineBoard.StaleMate)
                return 0;

            //Stand Pad
            if (quiescence)
            {
                //Evaluate Score
                Evaluation.EvaluateBoardScore(examineBoard);
                //Invert Score to support Negamax
                examineBoard.Score = AbsoluteScore(examineBoard.Score, GetOppositeColor(movingSide));

                if (examineBoard.Score >= beta)
                    return beta;

                if (alpha > examineBoard.Score)
                    alpha = examineBoard.Score;
            }

            List<Position> positions = EvaluateMoves&#40;movingSide, examineBoard, quiescence&#41;;

            if &#40;positions.Count == 0&#41;
            &#123;
                //Evaluate Score
                Evaluation.EvaluateBoardScore&#40;examineBoard&#41;;
                //Invert Score to support Negamax
                examineBoard.Score = AbsoluteScore&#40;examineBoard.Score, GetOppositeColor&#40;movingSide&#41;);

                return examineBoard.Score;
            &#125;

            positions.Sort&#40;Sort&#41;;

            depth--;

            foreach &#40;Position move in positions&#41;
            &#123;
                //Make a copy
                Board board = examineBoard.FastCopy&#40;);

                //Move Piece
                Board.MovePiece&#40;board, move.SrcPosition, move.DstPosition&#41;;

                //We Generate Valid Moves for Board
                PieceValidMoves.GenerateValidMoves&#40;board&#41;;

                
                int value = -AlphaBetaFast&#40;board, depth, -beta, -alpha, GetOppositeColor&#40;movingSide&#41;, ref nodesSearched,
                                       quiescence, extended&#41;;
               
                if &#40;value >= beta&#41;
                &#123;
                    return beta;
                &#125;
                if &#40;value > alpha&#41;
                    alpha = value;
            &#125;
            return alpha;
        &#125;

[nevatre]

Adam, this doesn't look correct
"if (alpha > examineBoard.Score)
alpha = examineBoard.Score; "

[Dann Corbit]

I see that you do a full width search for all the moves in the list.

Using an aspiration window for pv nodes (it is possible that you have an aspiration window from the root using previous search data, I can't tell from what you posted here) and a zero window for non-pv nodes will speed things up quite a bit if your move ordering is even decent.

You might consider fail-soft alpha-beta, which adds a small benefit.

Action items:
Null move search and a hash table would be my next additions, if I were king of the forest.

I did not see the code you posted in what I downloaded from your site. What is the correct link?

[Harald]

I don't know C# and your ode looks like some ideas shuffled and written down
but I will make some notes. May be I don't see your main problems. However.

In case someone has the time, here is my AlphaBeta. This is the second version that makes one move at a time, maybe you guys can see a bug?

Code: Select all

internal static int AlphaBetaFast(Board examineBoard, byte depth, int alpha, int beta, ChessPieceColor movingSide, ref int nodesSearched, bool quiescence, bool extended)
//// May be you copy too much boards. Try to use only one copy per call
//// or use a reference to ONE updated board. make_move()/undo_move()
        {
            nodesSearched++;

            if (depth == 0)
//// Use a second function for quiescence. Don't mix it with your main alpha-beta search.
            {
                //If last move was a capture
                if (examineBoard.LastMove.TakenPiece.PieceType != ChessPieceType.None && quiescence == false)
                {
                    //Perform a Quiessence Search
//// I don't understand the connection between last-move-capture and qsearch.
                    return AlphaBetaFast(examineBoard, 6, alpha, beta, movingSide, ref nodesSearched, true, true);
//// Why is depth 6? Normally depth <= 0 is qsearch indicator and we use
//// depth = 0 or depth - 1 in the calls inside qsearch.
//// Again&#58; dont mix search and qsearch&#58; for better understanding.
                &#125;
                if &#40;extended == false&#41;
//// What is this extension?
                &#123;
                    if (&#40;examineBoard.BlackCheck || examineBoard.WhiteCheck&#41; && examineBoard.EndGamePhase&#41;
//// If you want to extend checks then only if you are in check
//// &#40;or only when you are giving check&#41; but not both
                    &#123;
                        return AlphaBetaFast&#40;examineBoard, 3, alpha, beta, movingSide, ref nodesSearched, false, true&#41;;
//// A typical extension would use depth + 1 and not 3.
                    &#125;
                &#125;

                //Evaluate Score
                Evaluation.EvaluateBoardScore&#40;examineBoard&#41;;
                //Invert Score to support Negamax
                examineBoard.Score = AbsoluteScore&#40;examineBoard.Score, GetOppositeColor&#40;movingSide&#41;);
//// AbsoluteScore is misleading. It sounds like abs&#40;). Perhaps you mean
//// sideToMoveDependentScore when your evaluate function always 
//// sees score > 0 as good for white?

                return examineBoard.Score;
            &#125;

            if &#40;examineBoard.FiftyMove >= 50 || examineBoard.RepeatedMove >= 3 || examineBoard.StaleMate&#41;
                return 0;
//// Perhaps move50 and repetition should be done first in every node.
//// How do you know about stalemate without building a move list?
//// Where do you find out that you are mated and where is the mating score?

            //Stand Pad
//// Stand pat.
            if &#40;quiescence&#41;
            &#123;
//// Again why quiescence flag instead of depth <= 0?
                //Evaluate Score
                Evaluation.EvaluateBoardScore&#40;examineBoard&#41;;
                //Invert Score to support Negamax
                examineBoard.Score = AbsoluteScore&#40;examineBoard.Score, GetOppositeColor&#40;movingSide&#41;);

                if &#40;examineBoard.Score >= beta&#41;
                    return beta;

                if &#40;alpha > examineBoard.Score&#41;
                    alpha = examineBoard.Score;
//// Where do you collect the best move so far?
            &#125;

            List<Position> positions = EvaluateMoves&#40;movingSide, examineBoard, quiescence&#41;;
//// Assuming this is the move generator.
//// Why a list of positions instead a list of moves?
            if &#40;positions.Count == 0&#41;
            &#123;
                //Evaluate Score
                Evaluation.EvaluateBoardScore&#40;examineBoard&#41;;
                //Invert Score to support Negamax
                examineBoard.Score = AbsoluteScore&#40;examineBoard.Score, GetOppositeColor&#40;movingSide&#41;);
//// See above.
                return examineBoard.Score;
//// Is this your place to recognise mates or stalemates?
            &#125;

            positions.Sort&#40;Sort&#41;;

            depth--;
//// The usual approach is not to change depth here but in the call below.

            foreach &#40;Position move in positions&#41;
            &#123;
                //Make a copy
                Board board = examineBoard.FastCopy&#40;);
//// Is this the only board copy or just another one?
//// See comment above.

                //Move Piece
                Board.MovePiece&#40;board, move.SrcPosition, move.DstPosition&#41;;
//// Once you do promotion you will need a promotion piece also.

                //We Generate Valid Moves for Board
                PieceValidMoves.GenerateValidMoves&#40;board&#41;;
//// Ups! Why? This is not the typical place for move generation.
//// See comment on move generator above.
                
                int value = -AlphaBetaFast&#40;board, depth, -beta, -alpha, GetOppositeColor&#40;movingSide&#41;, ref nodesSearched,
                                       quiescence, extended&#41;;
//// I would expect depth-1 in the call.

                if &#40;value >= beta&#41;
                &#123;
                    return beta;
                &#125;
                if &#40;value > alpha&#41;
                    alpha = value;
//// Keep track on the best move.
            &#125;
//// Here would be a good place to recognise mate.
//// &#40;No best move found and in check&#41;.
//// Here you can store something in a hash table when you implement one later.
            return alpha;
        &#125;

I am sure I found only some obvious problems. When I guessed wrong
that is an indication for a strange way to do something in your code.
Please try to react to some of my comments and in an improved version
we may find more and more serious errors. Have fun.

Harald

[Gerd Isenberg]

In case someone has the time, here is my AlphaBeta. This is the second version that makes one move at a time, maybe you guys can see a bug?

At depth <= 0 you are already in quiescence. You should then call eval first, to return score if >= beta (standing pat). You should not do depth 3 or 6 searches from the horizon!? Better write a separate qsearch routine to uncouple things, to generate only captures if not in chess. As mentioned by Neil, don't lower alpha if your stand pat score is below, but higher if above.