Negamax: how should you avoid the horizon effect in the connect four game?

Question

I'm trying to implement a quiescence search in the negamax algorithm, for a connect four game.

The algorithm is as follow for a chess game:

int Quiesce( int alpha, int beta ) {
    int stand_pat = Evaluate();
    if( stand_pat >= beta )
        return beta;
    if( alpha < stand_pat )
        alpha = stand_pat;
until( every_capture_has_been_examined )  {
    MakeCapture();
    score = -Quiesce( -beta, -alpha );
    TakeBackMove();

    if( score &gt;= beta )
        return beta;
    if( score &gt; alpha )
       alpha = score;
}
return alpha;

}

I get the idea, but unfortunately there is not much more details in the article. I don't get how the sentence "until( every_capture_has_been_examined )" could be transposed to the connect four game. How would one evaluate silent move in such a game?

Also, there is no depth parameter, does that mean that quiescent search only applies to a single depth? As far as I understand, it seems so.

Here is an example output of my connect four AI game, where the horizon effect occurs (if I understand correctly):

AI player is YELLOW
Depth is 1 (obviously)
AI player wrongly chose to play c5 in the -300 cell, considering letters a,b,c, ... for the y axis. Thus, AI adds a third connected chess men and improves his is score (c3 to c5)
However, AI doesn't see that by doing so, it gives a winning move to the RED player. Indeed, RED now sets a connect-four in the line just below (d3-d6, playing d6) and wins the game.

Please note that MIN is actually MAX, because I use negamax and not minimax.

Negamax: how should you avoid the horizon effect in the connect four game?

0 Answers0