Understanding AlphaBetaMinMax

[msarchet]

I'm trying to implement AlphaBetaMinMax (negascout) following the algorithm that is posted on the CPW.

https://github.com/msarchet/panzer/blob ... search.cpp you can see my code here.

Ignore the bits for the transposition table as they are not used, and currently not implemented correctly.

What happens is I end up with these kind of scores when searching from the startpos for white

go depth 3
info depth 1 score 1662 g1f3
info depth 2 score 1837 g1f3
info depth 3 score 32767 g1f3 <--- This is INT16_MAX
bestmove g1f3

I'm doing a full window search right now.

This worked for me fine when I was using separate Min and Max function so I'm not sure what I implemented incorrectly.

My code works by calling an iterative deepening function to check all of the depths, and to help with bestmove ordering. In my iterative search I call

Code: Select all

makeMove(move)
if (!InCheck)
{
    score = -AlphaBetaMinMax(board, -beta, -alpha, depth);
}
unmakeMove(move)
if (score > alpha) { 
    score = alpha;
    bestMove = move;
 }

In AlphaBetaMinMax I do the following

Code: Select all

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

for (moves)
{
     makemove(move);
     if (!inCheck)
     {
          score = -AlphaBetaMinMax(board, -beta, -alpha, depth - 1);
          if (score > alpha)
          {
             if (score >= beta)
             {
                 unmakeMove(move);
                 return beta;
             }
             
             alpha = score;
         }
     }
}

return alpha;

In QSearch I return early if the stand pat is >= beta, and after each recursive search I return if the result of the recursive call is > beta, otherwise I return the bestScore at the end.

Clearly I am not understanding something correctly, and would appreciate some guidance, as I feel like I'm floundering around trying to understand what I am doing incorrectly.

[odomobo]

The issue might be due to negating min int. I think negating min int can return itself.

[R. Tomasi]

The issue might be due to negating min int. I think negating min int can return itself.

Indeed. It results in undefined behaviour, so not only could it return itself, but it could return anything really. Just use -INT_MAX as negative infinity score and you're quarding against that. (In C/C++ that is - not sure how other standards handle the fact that there is always a non-zero number that maps to itself).

The reason for this, is that the cardinality of all ints is a power of two, thus an even number. But there already is one element that maps to itself - zero. So one additional odd element without a counterpart will always be present.

[msarchet]

Thanks. I will try this out and see if that improves things.

[Bo Persson]

Another option is to NOT use a 16-bit value for the score.

Using a short value can save space (if you store a huge number of them), but it doesn't save execution time as they will be promoted to an int in all arithmetic operations anyway. The code could just as well use an int.

[R. Tomasi]

Another option is to NOT use a 16-bit value for the score.

Using a short value can save space (if you store a huge number of them), but it doesn't save execution time as they will be promoted to an int in all arithmetic operations anyway. The code could just as well use an int.

That doesn't resolve the problem with -INT_MIN being ill-defined. It's independend from the number of bits representing the signed integer.

[msarchet]

Switching from INT16_MAX/MIN to using a defined INF as 10000 appears to have resolved the issue.

Now to work out my other issues.

Another option is to NOT use a 16-bit value for the score.

Using a short value can save space (if you store a huge number of them), but it doesn't save execution time as they will be promoted to an int in all arithmetic operations anyway. The code could just as well use an int.

Aren't int16_t and short the same number of bytes?

[Ras]

Switching from INT16_MAX/MIN to using a defined INF as 10000 appears to have resolved the issue.

I'd go for a bit more such as maybe 16000 because there are some pathological positions where 10000 can lead to an overlap between mate scores and material difference.

Aren't int16_t and short the same number of bytes?

No. int16_t is 16 bits while short is at least 16 bits, but can be more, depending on the compiler and platform.

[R. Tomasi]

Switching from INT16_MAX/MIN to using a defined INF as 10000 appears to have resolved the issue.

I'd go for a bit more such as maybe 16000 because there are some pathological positions where 10000 can lead to an overlap between mate scores and material difference.

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.

[msarchet]

Switching from INT16_MAX/MIN to using a defined INF as 10000 appears to have resolved the issue.

I'd go for a bit more such as maybe 16000 because there are some pathological positions where 10000 can lead to an overlap between mate scores and material difference.

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?