1
$\begingroup$

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 >= beta )
            return beta;
        if( score > 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. horizon effect
  • Please note that MIN is actually MAX, because I use negamax and not minimax.
$\endgroup$
1
  • $\begingroup$ Quiescence search relies on a definition of quiescent. In chess, a quiescent state is apparently one where no capture is possible. Perhaps for Connect-4, it could be defined as one where each player can't make a longer line than their current longest. $\endgroup$ Jul 11, 2022 at 15:13

0

You must log in to answer this question.

Browse other questions tagged .