#StackBounty: #algorithm #search #tree Principal variation search: how to keep track of the best move

Bounty: 150

I have a Java implementation of the Principal Variation Search algorithm. That algorithm is used for searching a game tree starting from the root node and proceeding downwards until a particular depth reached or a terminal state is reached.
It looks like this:

public final class PrincipalVariationSearchGameEngine 
        <S extends AbstractState<S, P>,
         P extends Enum<P>> 
           extends AbstractGameEngine<S, P> {

    public PrincipalVariationSearchGameEngine(
            EvaluatorFunction<S> evaluatorFunction,
            int depth) {
        super(evaluatorFunction, depth, Integer.MAX_VALUE);
    }

    @Override
    public S makePly(S state, 
                     P minimizingPlayer, 
                     P maximizingPlayer, 
                     P initialPlayer) {
        state.setDepth(depth);

        return makePlyImplTopmost(state,
                                  depth,
                                  Double.NEGATIVE_INFINITY,
                                  Double.POSITIVE_INFINITY,
                                  initialPlayer == minimizingPlayer ? -1 : 1);
    }

    /**
     * Performs the search directly under the root node denoted by 
     * {@code state].
     * 
     * @param state the root state of the game tree to search.
     * @param depth the total depth of the search.
     * @param alpha the alpha cutoff value.
     * @param beta  the beta cutoff value.
     * @param color the color. -1 for minimizing player, +1 for maximizing
     *              player.
     * @return the game board after optimal move from {@code state}.
     */
    private S makePlyImplTopmost(S state,
                                 int depth,
                                 double alpha,
                                 double beta,
                                 int color) {
        boolean firstChild = true;
        S bestState = null;
        double tentativeScore = color == -1 ?
                                Double.POSITIVE_INFINITY :
                                Double.NEGATIVE_INFINITY;

        for (S child : state.children()) {
            double score;

            if (firstChild) {
                firstChild = false;
                score = -makePlyImpl(child, 
                                     depth - 1, 
                                     -beta, 
                                     -alpha,
                                     -color);
                bestState = child;
                tentativeScore = score;
            } else {
                score = -makePlyImpl(child, 
                                     depth - 1, 
                                     -alpha - 1.0, 
                                     -alpha,
                                     -color);

                if (color == -1) {
                    if (tentativeScore > score) {
                        tentativeScore = score;
                        bestState = child;
                    }
                } else {
                    if (tentativeScore < score) {
                        tentativeScore = score;
                        bestState = child;
                    }
                }

                if (alpha < score && score < beta) {
                    score = -makePlyImpl(child, 
                                         depth - 1,
                                         -beta,
                                         -score,
                                         -color);

                    if (color == -1) {
                        if (tentativeScore > score) {
                            tentativeScore = score;
                            bestState = child;
                        }
                    } else {
                        if (tentativeScore < score) {
                            tentativeScore = score;
                            bestState = child;
                        }
                    }
                }
            }

            if (alpha < score) {
                alpha = score;
            }

            if (alpha >= beta) {
                break;
            }
        }

        return bestState;
    }

    private double makePlyImpl(S state,
                               int depth,
                               double alpha,
                               double beta,
                               int color) {
        if (state.getDepth() == 0 
                || state.checkVictory() != null
                || state.isTerminal()) {
            return color * evaluatorFunction.evaluate(state);
        }

        boolean firstChild = true;

        for (S child : state.children()) {
            double score;

            if (firstChild) {
                firstChild = false;
                score = -makePlyImpl(child, 
                                     depth - 1, 
                                     -beta, 
                                     -alpha,
                                     -color);
            } else {
                score = -makePlyImpl(child, 
                                     depth - 1, 
                                     -alpha - 1.0, 
                                     -alpha,
                                     -color);

                if (alpha < score && score < beta) {
                    score = -makePlyImpl(child, 
                                         depth - 1,
                                         -beta,
                                         -score,
                                         -color);
                }
            }

            alpha = Math.max(alpha, score);

            if (alpha >= beta) {
                break;
            }
        }

        return alpha;
    }
}

This, however, does not work since it returns suboptimal (next) moves. I believe that the culprit is this if statement:

if (color == -1) {
    if (tentativeScore > score) {
        tentativeScore = score;
        bestState = child;
    }
} else {
    if (tentativeScore < score) {
        tentativeScore = score;
        bestState = child;
    }
}


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.