alphabeta issue

[flok]

Hi,

I implemented alphabeta in my chess-engine.
That seems to work until it encounters a checkmate happening before it reaches the end of the search-tree: it then tries to continue the search without a king.
My move generator then aborts (throws an exception) as it cannot do its thing without a king.
So to solve that, I either need to hack the movegenerator to just continue without the king but I don't like that as it is hackery.
So my question is: what is the regular way of aborting the search?

thanks

[hgm]

The search ends naturally: if you have no moves in a certain position, and you search them all, you search nothing.

The question is only which score to return. Without any special treatment, you would return some very low value, to which you normally initialize bestScore before you start seaching moves in that node, (let's call that -INF), because it was never increased by a better move. That is OK, because you could make that score represent mate. But in Chess you could also be stalemated, and then you would like to return a score close to 0, and not the same as for being checkmated. So if after searching all moves (which could be none) your score is still at -INF, you would have to test if you are currently in check. If not, you can correct the score to DRAWSCORE (=~ 0).

[rbarreira]

When a search finds a checkmate it should return a mate score immediately.

If your search strategy is to let the king be captured, at the beginning of your search function you should detect the absence of the king and return a negative mate score regardless of the depth. I think this would be called a "terminal node".

[hgm]

Better to return a +INF score when you generate a move that captures the King. That is easier to test than if a King is on the board.

[flok]

Hi,

Thanks for the replies.

I think the problem is different: I think I implemented a bug.

Here the processing starts:

Code: Select all

List<Move> moves = scene.getMoveList(myColor);
for(Move currentMove : moves) {
        Scene positionAfterMove = scene.Move(currentMove);
        positionAfterMove.validateMoves(hisColor);

        score = alphaBeta(afterMove, myColor, myColor, 3, -Double.MAX_VALUE, Double.MAX_VALUE);

        // etc.
}       

The definition of the alphaBeta is in my case:

Code: Select all

double alphaBeta(Scene position, int side, int rootSide, int depth, etc.);

As I'm executing first a move 'myColor' can do, the alphaBeta must start with 'hisColor'.

Code: Select all

score = alphaBeta(afterMove, hisColor, myColor, 3, -Double.MAX_VALUE, Double.MAX_VALUE);

Do you agree with my logic here?


Thanks[/code]

[Sven]

Hi,

I implemented alphabeta in my chess-engine.
That seems to work until it encounters a checkmate happening before it reaches the end of the search-tree: it then tries to continue the search without a king.
My move generator then aborts (throws an exception) as it cannot do its thing without a king.
So to solve that, I either need to hack the movegenerator to just continue without the king but I don't like that as it is hackery.
So my question is: what is the regular way of aborting the search?

thanks

The problem you reported should not happen with a correct legality checking. Be sure to fix that first.

If you never search an illegal move (or, when choosing the "king capture" strategy - see below - always refute an illegal move by detecting that the king can be taken) then your move generator will also never encounter a position with a missing king. The fact that your search "continues" beyond an illegal move directly implies that you do not detect all illegal moves. Even if you don't have some kind of checkmate scoring (resp. stalemate!) your search algorithm must return some score in case there is no (legal) move in the move list.

Implementing the mate/stalemate handling correctly depends on your overall legality checking strategy. If your move loop will try legal moves only, e.g. by checking move legality right after move generation but prior to starting the move loop, then you can also detect and handle both checkmate and stalemate prior to the loop, too:

Code: Select all

// move generation ...
// legality checking ...
if (moveList.size == 0) {
    if (inCheck) {
        return checkmatedScore(distanceToRoot());
    } else {
        return 0; // stalemate
    }
}
// move loop ...

If, however, you do the legality check move by move then you can only detect and handle checkmate or stalemate below the move loop:

Code: Select all

// move generation ...
int nLegalMovesPlayed = 0;
for (all moves) {
    makeMove(...);
    if (lastMoveWasIllegal()) {
        unmakeLastMove();
    } else {
        ++nLegalMovesPlayed;
        // recursive search ...
        // unmake move ...
        // back up value ...
    }
}
if (nLegalMovesPlayed == 0) {
    if (inCheck) {
        return checkmatedScore(distanceToRoot());
    } else {
        return 0; // stalemate
    }
} else {
    return bestScore;
}

The third way, as mentioned by HGM, is the "king capture" implementation. If the moving side has a move that captures the enemy king then stop processing the current node immediately, returning a high positive score (+INF). From the opponent's viewpoint at the parent node to which you return control this looks like having made just some bad move, so for a correct mate/stalemate detection you also need to detect, after the move loop, whether the "bestScore" is still "-INF", meaning that all moves were refuted by capturing the king.

If you are not sure which way to go, in your current stage I would choose the first one. You can always go for optimization later.

Sven

[Sven]

Hi,

Thanks for the replies.

I think the problem is different: I think I implemented a bug.

Here the processing starts:

Code: Select all

List<Move> moves = scene.getMoveList(myColor);
for(Move currentMove : moves) {
        Scene positionAfterMove = scene.Move(currentMove);
        positionAfterMove.validateMoves(hisColor);

        score = alphaBeta(afterMove, myColor, myColor, 3, -Double.MAX_VALUE, Double.MAX_VALUE);

        // etc.
}

The definition of the alphaBeta is in my case:

Code: Select all

double alphaBeta(Scene position, int side, int rootSide, int depth, etc.);

As I'm executing first a move 'myColor' can do, the alphaBeta must start with 'hisColor'.

Code: Select all

score = alphaBeta(afterMove, hisColor, myColor, 3, -Double.MAX_VALUE, Double.MAX_VALUE);

Do you agree with my logic here?

Are you still using a minimax framework? The name of the formal parameter "rootSide" seems to indicate this. In that case, why do you pass "myColor" for that parameter when calling alphaBeta()? It seems you'll always have to pass the same color at that point, i.e. the moving side at the root node, to know whether you are at a "maximizer" (myColor == rootSide) or "minimizer" node.

To be honest, I sincerely hope you don't continue using minimax Now that you have started with alphaBeta I would abandon minimax and continue with a normal recursive alphaBeta algorithm based on a negamax framework. Everything else is clearly inferior, at least in the current stage of your engine. Also, with negamax there is no need any longer to extensively deal with "myColor", "hisColor", "rootSide" and so on, at least for the basic parts of the search you are looking at right now.


One more point: what exactly is the purpose of your "validateMoves()" method? In the snippet above you use it right after making a move. Does it validate (I guess: check legality of) ONE move, or ALL moves?

a) In the former case I wonder about the name, should better be "-Move" instead of "-Moves".

b) In the latter case it would have to include move generation, so I wonder why you do it there and not in the beginning of alphaBeta(), and I also wonder why no legality checking occurs prior to the move loop starting few lines above.


"alphaBeta" should already be applied at the root node. You seem to search all subtrees of moves at the root node with the same full alpha-beta window of (-MAX_VALUE, +MAX_VALUE) which wastes a big portion of the benefit of the alpha-beta algorithm, by missing a lot of opportunities of applying a cutoff.


The typical structure of a very simple recursive alphaBeta search using negamax is as follows (omitting mate detection for simplicity here):

- starting perspective: a node has been entered (by making a move, that was done one level of recursion above).

- return "appropriate score" (e.g. static evaluation) if current node is a leaf node (e.g. draw by rule => return 0, technical limits reached, max depth reached [if no quiescence search], timeout, other external interrupt)

- generate moves

- loop over all moves, trying captures first based on the MVV/LVA principle, and search all legal successor nodes of the current node recursively like this:

Code: Select all

int score = -alphaBeta(successorNode, -beta, -alpha, ...);
if (score >= beta) {
    return alpha; // cut off all other subtrees, current move already refutes opponent's previous move
}
if (score > alpha) {
    alpha = score; // raise alpha
}

- finally, return "alpha" which is the best score found for the moving side at the current node.


At least for the root node (but you might want to do it for all nodes for simplicity in the beginning) the search needs to determine also the best move at a node, in addition to its score. You can easily figure out how to do that.

Sven

[flok]

Are you still using a minimax framework? The name of the formal parameter "rootSide" seems to indicate this.

No this is the alphabeta code. My evaluator (getShannonValue) needs the color for which it evaluates. Or course I could always say white to it and then negate it when applicable, but in this stage of the project I keep it like this.

One more point: what exactly is the purpose of your "validateMoves()" method? In the snippet above you use it right after making a move. Does it validate (I guess: check legality of) ONE move, or ALL moves?

It validates all of them. So I do a move, then automatically all possible moves are calculated and then that validate command sees which are determined.

"alphaBeta" should already be applied at the root node. You seem to search all subtrees of moves at the root node with the same full alpha-beta window of (-MAX_VALUE, +MAX_VALUE) which wastes a big portion of the benefit of the alpha-beta algorithm, by missing a lot of opportunities of applying a cutoff.

Hmmm I see.
(cut for brevity)

At least for the root node (but you might want to do it for all nodes for simplicity in the beginning) the search needs to determine also the best move at a node, in addition to its score. You can easily figure out how to do that.

Yes, I'll give it a try!

[Sven]

Are you still using a minimax framework? The name of the formal parameter "rootSide" seems to indicate this.

No this is the alphabeta code. My evaluator (getShannonValue) needs the color for which it evaluates. Or course I could always say white to it and then negate it when applicable, but in this stage of the project I keep it like this.

If I have understood you correctly then the name of the formal parameter "rootSide" of the "alphaBeta()" method can lead to misunderstandings. This was the code you posted, only put in different order:

Code: Select all

double alphaBeta(Scene position, int side, int rootSide, int depth, etc.);
...
List<Move> moves = scene.getMoveList(myColor);
for(Move currentMove : moves) {
        Scene positionAfterMove = scene.Move(currentMove);
        positionAfterMove.validateMoves(hisColor);

        score = alphaBeta(afterMove, myColor, myColor, 3, -Double.MAX_VALUE, Double.MAX_VALUE);

        // etc.
}

When not using minimax any longer you also don't need to know the color of the moving side at the root node at arbitrary nodes in the tree. You should choose a name that reflects the semantics, also to avoid introducing new bugs.

One more point: what exactly is the purpose of your "validateMoves()" method? In the snippet above you use it right after making a move. Does it validate (I guess: check legality of) ONE move, or ALL moves?

It validates all of them. So I do a move, then automatically all possible moves are calculated and then that validate command sees which are determined.

Could you please explain the meaning of "moves are calculated" and of "sees which are determined"? A second question: why does that "validateMoves()" call appear at that point in the search instead of appearing above the move loop (possibly implying few other changes)?

Sven

[flok]

When not using minimax any longer you also don't need to know the color of the moving side at the root node at arbitrary nodes in the tree. You should choose a name that reflects the semantics, also to avoid introducing new bugs.

Well, it can be a matter of convenience. E.g. to be able to do a simple compare so that I can either use the "regular shannon" (for the opponent moves) and my own "enhanced shannon" (for the moves my engine performs).

One more point: what exactly is the purpose of your "validateMoves()" method? In the snippet above you use it right after making a move. Does it validate (I guess: check legality of) ONE move, or ALL moves?

It validates all of them. So I do a move, then automatically all possible moves are calculated and then that validate command sees which are determined.

Could you please explain the meaning of "moves are calculated" and of "sees which are determined"?[/quote]

Code: Select all

Scene::Move(Move move) {
     return new Scene(move);
}

// constructor
Scene::Scene(Move move) {
     // execute move
     // calculate moves that white and black can do
}

Scene::validateMoves(PlayerColor color) {
     // validate the moves for player 'color'
}

A second question: why does that "validateMoves()" call appear at that point in the search instead of appearing above the move loop (possibly implying few other changes)?

Oh that is an historical thing. I could move it in to the top of alphabeta but it would not give a direct gain. Maybe easier to read for outsiders but the program is not ready for opensourcing anyway.