Question about QSearch

[okidoki]

I have a routine which calls QSearch at depth of 0.
Right now I am not checking if the player is in check before calling QSearch and will do it once I am able to understand this behaviour.

I have a very simple search routine with alpha-beta search and a simple evaluation, I count material and have 5cp assigned for Knight on c3 and Bishop on d3. My evaluation returns turn based score.

In move generation, I generate captures and non-captures, but captures are getting tried first.

When I try the code with start pos, it is giving the following PV at depth of 8. (similar lines could be seen, where only additional ply would make the engine realize loss of material)

e2e3 c7c6 b1c3 d8a5 b1c4 b7b5 c4d3 a5a2??

What I observed that during the depth 0, QSearch is being called and standpat is equal to beta and hence by the code I return beta.
Thus even if black loses his queen, the eval return -90cp as score (from eval it is correct white is -100 (down a pawn) but bishop and knight psqt adds 10 points hence equal to -90), what I don't understand is why my q-search is not taking care of horizon effect.

Here is the pvs which is returned to me by engine from depth 1-8.

info depth 1 score cp 5 time 11 nodes 21 nps 1000 pv b1c3
info depth 2 score cp 0 time 17 nodes 368 nps 20000 pv b1c3 b8c6
info depth 3 score cp 35 time 19 nodes 3797 nps 189000 pv b1c3 b8c6 c3d5
info depth 4 score cp -20 time 62 nodes 88839 nps 1410000 pv b1a3 b8c6 a3c4 c6d4
info depth 5 score cp 90 time 153 nodes 162076 nps 1052000 pv e2e3 b8a6 d1h5 a6b4 h5f7
info depth 6 score cp -70 time 1455 nodes 2542536 nps 1746000 pv h2h4 c7c6 b1c3 d8a5 c3e4 a5a2
info depth 7 score cp 95 time 7816 nodes 11557412 nps 1478000 pv c2c3 a7a5 d1c2 c7c5 c2b3 b8c6 b3b7
info depth 8 score cp -90 time 67797 nodes 106143455 nps 1565000 pv e2e3 c7c6 g1f3 d8a5 f1c4 b7b5 c4d3 a5a2

Here is my implementation for alpha-beta search

Code: Select all

 
 public static int NegaMax(int alpha, int beta, int depth, bool turn)
        {
            long bestMoveSoFar = 0;
            int oldAlpha = alpha;
            int legalMovesMade = 0;
            PVLength[ply] = ply;
           
            if (depth == 0) return QSearch(alpha, beta, turn);



            nodes++;


            bool isCheck = LegalMoveManager.IsKingInCheck(turn);
            MoveGeneration.GenerateMoves(ply, turn);
            //SortMoves(ply);
            var mCount = MoveGeneration.MOVES_AT_PLY.AsSpan();
            var mList = MoveGeneration.moveList.AsSpan();

            for (int i = 0; i < mCount[ply]; i++)
            {

                Move m = mList[ply][i];
                MoveGeneration.MakeMove(m.move, ply);
                ply++;
                if (LegalMoveManager.IsKingInCheck(turn))
                {
                    ply--;

                    MoveGeneration.UndoMove(m.move, ply);
                    
                    continue;
                }

                legalMovesMade++;



                int score = -NegaMax(-beta, -alpha, depth - 1, !turn);

                ply--;
                MoveGeneration.UndoMove(m.move, ply);
  
                if (score > alpha)
                {
                    // This move is better than previous move and a new best move.
                    // We consider this as a PV node.
                    alpha = score;

                   
                    if (ply == enginePly)
                    {
                        bestMoveSoFar = m.move;
                    }
                    
                }
                // This is fail-hard implementation of alpha-beta cut-off.
                if (score >= beta)
                {
                    // move which has failed high.
                    break;
                }

            }
            if (legalMovesMade == 0)
            {

                if (isCheck) return mateValue + ply;
                return 0;
            }
            if (oldAlpha != alpha)
            {
                bestMove = (ulong)bestMoveSoFar;
            }

            return alpha;

        }
        

Implementation for QSearch

Code: Select all

public static int QSearch(int alpha, int beta, bool turn)
        {
            nodes++;

            int stand_pat = Evaluation.Eval(turn);

            if (alpha < stand_pat)
                alpha = stand_pat;

            if (stand_pat >= beta)
                return beta;
            

            var mCount = MoveGeneration.MOVES_AT_PLY.AsSpan();
            var mList = MoveGeneration.moveList.AsSpan();

            for (int i = 0; i < mCount[ply]; i++)
            {

                Move m = mList[ply][i];
                MoveGeneration.MakeMove(m.move, ply);
                ply++;
                if (LegalMoveManager.IsKingInCheck(turn))
                {
                    ply--;
                    MoveGeneration.UndoMove(m.move, ply);
                    continue;
                }
                int score = -QSearch(-beta, -alpha, !turn);
                ply--;
                MoveGeneration.UndoMove(m.move, ply);


                if (score > alpha)
                {
                    alpha = score;
                   
                }
                if (score >= beta)
                    return beta;

            }

            return alpha;
        }
        

Please let me know if my understanding is wrong.
Adding some more information, the engine is able to figure out mate in 3,2,1 and also scored very about 204 out of 300 in WAC.

[hgm]

There must be something wrong with your alpha-beta implementation. Moves that return beta (or alpha) should never become part of the PV. That is what beta means: that the side on move already had a move with this score closer to the root. So at best you can get an equal score for the line you search now, and that should not be enough to replace it.

So it doesn't have to see you lose a Queen; scoring the line as -90 should already be enough to disqualify it.

[okidoki]

@hgm, thanks for the reply.
I understood what you said and replaced call to QSearch with Eval and observed that it is giving the same result.
Not sure where the bug is in my alpha-beta implementation, will try to figure out and update here once I do.
Thank you.

[okidoki]

Hi, I have fixed this bug. It seems that it was an issue in QSearch while returning alpha and beta.

Now my program has the following features.
1. Negamax with alpha-beta pruning. (No internal iterative, no null move, no LMR, no TT).
2. QSearch expanding captures only.
3. Move ordering via MVV/LVA.
4. Evaluation using material values and PSQT. (This is taken from Rofchade version of TSCP)
5. Evaluation uses tapered eval.

Few more details, it on an average gets to 1.5 Mnps+ nodes for processing and reaches depth of 6 in less than 1 sec and 7 in about 3secs.

I will add rest of the information in another thread, since it has nothing to do with QSearch question asked above.