QS code

[cms271828]

I've set up a basic QS,
If this node is in check, then all moves are generated, so if no moves are generated here, a checkmate score is returned.

If this node is not in check, then just captures on the last TO square are considered, if there are non, then I use the score from the static evaluation..

Code: Select all

int QS(int ALPHA, int BETA, int DEPTH, int LAST_TO)
{
    staticEval=getEval();



    if(NOT_IN_CHECK && SIDE_TO_MOVE_HAS_MORE_THAN_2_PIECES)
    {
        if(staticEval >= BETA ) return BETA
    }



    if(IN_CHECK)
    {
          MOVES=generateAllMoves()

          if(MOVES is not empty)
          {
              for(each MOVE in MOVES)
              {
                     MakeMove(MOVE)
                     val = -QS(-BETA,-ALPHA, DEPTH-1, MOVE.TO)
                     UndoMove(MOVE)

                     if(val>=BETA) return BETA;
                     if(val>ALPHA) ALPHA=val;
              }
          }
          else // NO MOVES GENERATED
          {
              return MateScore(DEPTH)
          }
     }



     if(NOT_IN_CHECK)
     {
         MOVES=generateAllCapturesOnLastTO_Square(LAST_TO)

          if(MOVES is not empty)
          {
              for(each MOVE in MOVES)
              {
                     MakeMove(MOVE)
                     val = -QS(-BETA,-ALPHA, DEPTH-1, MOVE.TO)
                     UndoMove(MOVE)

                     if(val>=BETA) return BETA;
                     if(val>ALPHA) ALPHA=val;
              }
          }
          else // NO MOVES GENERATED
          {
              val=staticEval;
        		
              if(val>ALPHA) ALPHA=val;
              if(val>=BETA) return BETA;
          }
     }


    return ALPHA
}

Is this a satisfactory way to do a basic QS?
I realize I'm overlooking many captures, but I'm trying to avoid an explosion in the tree size.

Is it a good idea to handle positions in check with a full move generation, and to return a mate score when no moves are available(when position is in check)?

Thanks for any advice.

[jswaff]

One comment - if I'm reading your code right you're not allowing the static eval to raise alpha unless you are not in check and there are no captures to the last "to" square. It's common to raise alpha if the static eval is > alpha. This is commonly referred to as "standing pat."

--
James

I've set up a basic QS,
If this node is in check, then all moves are generated, so if no moves are generated here, a checkmate score is returned.

If this node is not in check, then just captures on the last TO square are considered, if there are non, then I use the score from the static evaluation..

Code: Select all

int QS(int ALPHA, int BETA, int DEPTH, int LAST_TO)
{
    staticEval=getEval();



    if(NOT_IN_CHECK && SIDE_TO_MOVE_HAS_MORE_THAN_2_PIECES)
    {
        if(staticEval >= BETA ) return BETA
    }



    if(IN_CHECK)
    {
          MOVES=generateAllMoves()

          if(MOVES is not empty)
          {
              for(each MOVE in MOVES)
              {
                     MakeMove(MOVE)
                     val = -QS(-BETA,-ALPHA, DEPTH-1, MOVE.TO)
                     UndoMove(MOVE)

                     if(val>=BETA) return BETA;
                     if(val>ALPHA) ALPHA=val;
              }
          }
          else // NO MOVES GENERATED
          {
              return MateScore(DEPTH)
          }
     }



     if(NOT_IN_CHECK)
     {
         MOVES=generateAllCapturesOnLastTO_Square(LAST_TO)

          if(MOVES is not empty)
          {
              for(each MOVE in MOVES)
              {
                     MakeMove(MOVE)
                     val = -QS(-BETA,-ALPHA, DEPTH-1, MOVE.TO)
                     UndoMove(MOVE)

                     if(val>=BETA) return BETA;
                     if(val>ALPHA) ALPHA=val;
              }
          }
          else // NO MOVES GENERATED
          {
              val=staticEval;
        		
              if(val>ALPHA) ALPHA=val;
              if(val>=BETA) return BETA;
          }
     }


    return ALPHA
}

Is this a satisfactory way to do a basic QS?
I realize I'm overlooking many captures, but I'm trying to avoid an explosion in the tree size.

Is it a good idea to handle positions in check with a full move generation, and to return a mate score when no moves are available(when position is in check)?

Thanks for any advice.

[cms271828]

Thanks, I was actually doing this before..

and for one position I created...
[d]4r1rk/2n4q/2bn1nb1/2np1pN1/1R1RBr1r/2NP1PN1/2NNRNB1/3KQ3 w 0-1

Yes, that is a 21 piece capture sequence on e4

Using

Code: Select all

if(staticEval>ALPHA) ALPHA=staticEval;

The node count upto depth 2, was about 17,000
But without using this, it was 1,300,000.

So, I don't know if I should include this.

I'm not sure what to do, if I use the staticEval, and this is >= BETA, then I get a cutoff straight away, but what if there is a queen that can be captured? Isn't it best to use the staticEval once, the position is quiet (Or at least quiet on the last TO square in my case) ?

Thanks for any help

[Tony]

Thanks, I was actually doing this before..

and for one position I created...
[d]4r1rk/2n4q/2bn1nb1/2np1pN1/1R1RBr1r/2NP1PN1/2NNRNB1/3KQ3 w 0-1

Yes, that is a 21 piece capture sequence on e4

Using

Code: Select all

if(staticEval>ALPHA) ALPHA=staticEval;

The node count upto depth 2, was about 17,000
But without using this, it was 1,300,000.

So, I don't know if I should include this.

I'm not sure what to do, if I use the staticEval, and this is >= BETA, then I get a cutoff straight away, but what if there is a queen that can be captured? Isn't it best to use the staticEval once, the position is quiet (Or at least quiet on the last TO square in my case) ?

Thanks for any help

You might not fully understand alpha-beta yet.

Alpha is "my best score found until now" , beta is "your best score until now". (corrected for stm). Alpha is my guarranteed score, beta is yours.

If current eval>beta then the current score is already better than what I get if you play your best moves. ie you could do better than what you are doing now, we have seen that already before.

If I could also capture your queen, your position is even more worse BUT THIS MAKES NO DIFFERENCE in alpha beta. How much this position sucks is not important, just that it sucks more than when you play your best move.

So, alpha has to be raised to current eval. If it's>beta then cutoff ie don't bother anymore.

Tony

[gladius]

You definitely want to consider captures not just on the "to" square. Pins are a pretty key tactical idea, and just recapturing on the "to" square will miss those motifs. The position can't really be considered quiet while there are still pieces hanging .

Searching checks in q-search is quite valuable, especially if you do more agressive pruning of the main search tree. Some q-searches generate moves that can cause check as well, although I haven't tried this myself yet. It's a tricky balance to how much you want to add in the q-search before it explodes on you.

Generating all moves while in check is fine, but a special check-escape move generator is very useful, and can save some significant make/unmake move time.

[bob]

Just captures to the last <TO> square is not a good idea. Suppose you play NxR and all your opponent can do is recapture the knight. You just won an exchange. But suppose your queen is hanging. Since it is not on the target square, you miss that and get a score of +2.0, rather than -4.0 which will get you into a lot of tactical trouble.

[jwes]

The advantage of this method is that it is much faster than a full qsearch. Since, as you say, qsearch is inherently inaccurate, e.g. in your example, if the static evaluation is above beta, you would stand pat and fail high even if your queen is hanging. We would need to test to see whether the speed would make up for the inaccuracy.

[Uri Blass]

The advantage of this method is that it is much faster than a full qsearch. Since, as you say, qsearch is inherently inaccurate, e.g. in your example, if the static evaluation is above beta, you would stand pat and fail high even if your queen is hanging. We would need to test to see whether the speed would make up for the inaccuracy.

No need to test because normal qsearch of captures ordered by MVV/LVA is also fast enough and no serious program does qsearch that include only captures in one square.

If the programmer want to limit the number of captures then it is more logical to include the first k captures for some small k when captures are ordered based on MVV/LVA
or better order of moves and not captures of the square that the opponent moved to it.

Uri

[cms271828]

I looked at Bruce Morlands site, and he does

Code: Select all

val = Evaluate();
if (val >= beta) return beta;
if (val > alpha) alpha = val;

at the start of the node, instead of what I was doing...(raising alpha if its not in check, and there were no captures made).


So, now I need to decide on something better than captures on last_to square.
Previously I examined all captures, and it was much slower in reaching any good depth. But I didn't have any MVV/LVA ordering on the captures, which is one reason the tree exploded.

I'm not sure if I should generate all captures, and order them, or just some. I feel that if I don't generate all then hanging pieces may be overlooked, but is it worth just generating some of the captures(I don't know which) so that the lack of accuracy gives a greater depth of search, and overall better performance?

Thanks

[Tony]

I looked at Bruce Morlands site, and he does

Code: Select all

val = Evaluate();
if (val >= beta) return beta;
if (val > alpha) alpha = val;

at the start of the node, instead of what I was doing...(raising alpha if its not in check, and there were no captures made).


So, now I need to decide on something better than captures on last_to square.
Previously I examined all captures, and it was much slower in reaching any good depth. But I didn't have any MVV/LVA ordering on the captures, which is one reason the tree exploded.

I'm not sure if I should generate all captures, and order them, or just some. I feel that if I don't generate all then hanging pieces may be overlooked, but is it worth just generating some of the captures(I don't know which) so that the lack of accuracy gives a greater depth of search, and overall better performance?

Thanks

To start, generate all captures, order them MVV/LVA, try them all except where currentEval+Value[capturedPiece]+MARGIN<alpha

That should do it for a while. There is no need to make a part of your programme super sophisticated when it also contains super simple parts. All has to be in balance. Qsearch only has to be reconsidered when you come to the pruning stuff.

First now do nullmove, and extend evaluation ( should keep you busy for a few years )

Tony