Understanding AlphaBetaMinMax

[mvanthoor]

Also, you should do make(), "continue" when the make() turned out to be illegal, if legal then search, then unmake().

If I'm reading this correctly, you're now only unmaking moves when they give you a bèta cutoff.

So:

Code: Select all

if (depth == 0)
{
    auto eval = QSearch(board, alpha, beta);
    return eval;
}

for (moves)
{
     makemove(move);
     
     // Skip illegal moves (and the rest of the loop)
     if (inCheck) {
     	continue;
     }
     
	score = -AlphaBetaMinMax(board, -beta, -alpha, depth - 1);

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

return alpha;

[Ras]

For +/- INF I'd actually go for the maximum/minimum safe value (i.e. +INT16_MAX for positive infinity and -INT16_MAX for negative infinity), since those are supposed to be larger/smaller than any mating score.

Doesn't this run me into the same problem with -(-INF) being -INT16_MIN?

No. INT16_MAX is +32767, and int16_t can represent -32767. It's just that int16_t can represent -32768 (i.e. INT16_MIN), but not +32768.

[Desperado]

Code: Select all

for (moves)
{
     makemove(move);
     
     // Skip illegal moves (and the rest of the loop)
     if (inCheck) {
     	continue;
     }
     
	score = -AlphaBetaMinMax(board, -beta, -alpha, depth - 1);

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

Well, it is only a short look at you code snippet (maybe i am overlooking sth. trivial), but you call unmakeMove(move) twice if you have a beta cut.
Do i miss something? If that is a bug, the board will be shuffeld somehow and the result will be unpredictable.

Another point, might be the checkmate detection. It is not obvious to me how your report a mate score. (no legal moves available).
When people handle mate scores, sometimes the initial score at a node will be set to sth. like "NO_SCORE" or "MIN_SCORE".
If this isn't done you might get an undefined score from nowhere.

Regards

[dangi12012]

I want to add that having a legal movegenerator would remove all that Incheck() checking - and would improve speed by 2x at least. Probably more since that is an expensive check to do for each position.

[mvanthoor]

Well, it is only a short look at you code snippet (maybe i am overlooking sth. trivial), but you call unmakeMove(move) twice if you have a beta cut. Do i miss something?

Argh. No. The unmake move does not belong in the beta cut. I forgot to delete it

Another point, might be the checkmate detection. It is not obvious to me how your report a mate score.

In my snippet, I don't cover that.

In my engine, -CHECKMATE is returned if the king is in check and there are no legal moves. STALEMATE is returned if the king is not in check and there are no legal moves. This is right after the move loop.

I want to add that having a legal movegenerator would remove all that Incheck() checking - and would improve speed by 2x at least. Probably more since that is an expensive check to do for each position.

True, but a pseudo-legal move generator is easier to write, so most people start there (myself included). Staged move generation is an even better optimization than a fully legal move generator: not generating any moves is faster than the fastest move generator.

[R. Tomasi]

True, but a pseudo-legal move generator is easier to write, so most people start there (myself included). Staged move generation is an even better optimization than a fully legal move generator: not generating any moves is faster than the fastest move generator.

That, and it's then also possible to sort the stages (instead of only the moves). Generating potentially winning captures first in QS, for example. I have a kind of history heuristics which sorts the stages in Pygmalion. Only if not in QS I will then also sort the generated moves. Not sorting the individual moves, and only generating potentially winning stages first proved to be better for me.

Edit: Btw, it seems debatable to me whether a pure legal-movegen will in the end be faster. It will have to do the legality check in some form or another during generation, which make the generation slower than pseudo-legal. And with a pseudo-legal movegen you will skip all this checking for moves that come behind a beta cut-off. To me the best option (I'm not doing this currently, though, and haven't tried), seems to be to do pure legal move-gen in expected all-nodes and staged pseudo-legal in expected cut-nodes.

[msarchet]

Also, you should do make(), "continue" when the make() turned out to be illegal, if legal then search, then unmake().

If I'm reading this correctly, you're now only unmaking moves when they give you a bèta cutoff.

So:

Code: Select all

if (depth == 0)
{
    auto eval = QSearch(board, alpha, beta);
    return eval;
}

for (moves)
{
     makemove(move);
     
     // Skip illegal moves (and the rest of the loop)
     if (inCheck) {
     	continue;
     }
     
	score = -AlphaBetaMinMax(board, -beta, -alpha, depth - 1);

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

return alpha;

This isn't my actual code I do handle the unmake move properly.

True, but a pseudo-legal move generator is easier to write, so most people start there (myself included). Staged move generation is an even better optimization than a fully legal move generator: not generating any moves is faster than the fastest move generator.

That, and it's then also possible to sort the stages (instead of only the moves). Generating potentially winning captures first in QS, for example. I have a kind of history heuristics which sorts the stages in Pygmalion. Only if not in QS I will then also sort the generated moves. Not sorting the individual moves, and only generating potentially winning stages first proved to be better for me.

Edit: Btw, it seems debatable to me whether a pure legal-movegen will in the end be faster. It will have to do the legality check in some form or another during generation, which make the generation slower than pseudo-legal. And with a pseudo-legal movegen you will skip all this checking for moves that come behind a beta cut-off. To me the best option (I'm not doing this currently, though, and haven't tried), seems to be to do pure legal move-gen in expected all-nodes and staged pseudo-legal in expected cut-nodes.

This is something that I plan to look into. My move generation from profiling is only about 1-2% of the cost of executing a search, so I haven't been worrying about it at this point. For QSearch I do only generate captures.

[msarchet]

This is something that I plan to look into. My move generation from profiling is only about 1-2% of the cost of executing a search, so I haven't been worrying about it at this point. For QSearch I do only generate captures.

Actually looking again it's about 5%

[R. Tomasi]

That, and it's then also possible to sort the stages (instead of only the moves). Generating potentially winning captures first in QS, for example. I have a kind of history heuristics which sorts the stages in Pygmalion. Only if not in QS I will then also sort the generated moves. Not sorting the individual moves, and only generating potentially winning stages first proved to be better for me.

Edit: Btw, it seems debatable to me whether a pure legal-movegen will in the end be faster. It will have to do the legality check in some form or another during generation, which make the generation slower than pseudo-legal. And with a pseudo-legal movegen you will skip all this checking for moves that come behind a beta cut-off. To me the best option (I'm not doing this currently, though, and haven't tried), seems to be to do pure legal move-gen in expected all-nodes and staged pseudo-legal in expected cut-nodes.

This is something that I plan to look into. My move generation from profiling is only about 1-2% of the cost of executing a search, so I haven't been worrying about it at this point. For QSearch I do only generate captures.

I plan so, too. It's however not very high on the to-do list currently.

What I do/meant is not to generate only captures in QS (I think almost everybody does that). The idea is to generate captures in stages, and only generate the potentially winning stages first. For example when generating captures for the queen: capturing a pawn is with very high probability not a winning capture (but there probably are lot's of "queen captures pawn" cases, because of the high queen mobility). I generate (probably) winning captures in a first stage, then (probably) equal captures, and finally the (probably) loosing captures in QS. Within the individual stages I have passes (for example winning queen captures, winning rook captures, etc.). Those get sorted by a history score.

A typical approach in QS would then be to sort the generated captures by SEE. That I do not do. It may be because my SEE implementation is poor/slow, but the cost of that last sort outweighs any benefits in my engine. And it's not like the moves in QS aren't ordered - I just don't sort the moves within individual passes.

Edit: well, the (probably) winning queen captures is a BS example They don't exist, becuase the queen can at best capture a queen, which would be a (probably) equal capture. But you get the idea...