Transposition table problem

[marion]

Hello, chess programmers!

In my chess program, I'm trying to implement for storing values of positions, which were already determined. I'm pretty frustrated with that, because maybe two weeks I can't find the mistake in my source code, but the program behaves strange: The moves are different when the transposition heuristic is used and when it is not used. The moves are not bad in both cases, but I think, that they should be the same, shouldn't they? My source code:

Code: Select all

    int alfabeta(Board board, int depth, int alpha, int beta, int color) {
        TranspositionItem transpoItem;
        TranspositionTable transpoTable = board.transpositionTable;
        if ((transpoItem = transpoTable.getContent()) != null ) {
            if (transpoItem.getStep() >= depth ) {
                if (transpoItem.getValueFlag() == TranspositionItem.EXACT_FLAG) {
                    return transpoItem.getValue();
                }
                if ((transpoItem.getValueFlag() == TranspositionItem.ALPHA_FLAG) &&(transpoItem.getValue() <= alpha))  {
                    return alpha;
                }
                if ((transpoItem.getValueFlag() == TranspositionItem.BETA_FLAG) &&(transpoItem.getValue() >= beta)) {
                    return beta;
                }
            }
        }
        MoveList moves = new MoveList();
        moves.generate(board, color, false);
        int value;
        if ((timeExpired == true) || depth <= 0) { 
            MoveList opponentMoves = new MoveList();
            opponentMoves.generate(board, -color, false);
            return evaluation.value(board, moves, opponentMoves, color);
        }
        int flag = TranspositionItem.ALPHA_FLAG;
        for (OneMove move: moves) {
             board.playMove(move, false);
             transpoTable.move(board, move);
             if (!board.isCheck(color)) {
                value = -alfabeta(board, depth - 1, -beta, -alpha, -color);
                if (value > alpha) {
                    alpha=value;
                    flag = TranspositionItem.EXACT_FLAG;
                    if(value >= beta) {
                        transpoTable.move(board, move);
                        board.revertMove(move);
                        transpoTable.putRealPosition(beta, depth, TranspositionItem.BETA_FLAG);
                        return beta;
                    }
                }
             }
            transpoTable.move(board, move);
            board.revertMove(move);
        }
        transpoTable.putRealPosition(alpha, depth, flag);
        return alpha;
    }

I really don't know where is the problem. Does anybody see something there?
Thanks a lot, Marika.

[Sven]

Hi Marika,

welcome at TalkChess!

[...] but the program behaves strange: The moves are different when the transposition heuristic is used and when it is not used. The moves are not bad in both cases, but I think, that they should be the same, shouldn't they?

It depends on what you compare. Do you compare
a) fixed-depth search with and without TT,
b) fixed-time search with and without TT, or
c) something else?

In case a) there might be some bug around, but it could also be in other parts than search (e.g. zobrist key management). I have not found a bug in your code fragment so far, after looking on it only for a few minutes.

Have you checked, for instance, that your hash key generated incrementally after each move is 100% identical to the hash key calculated from scratch? And, since you seem to have some "unmake" operation for the hash key, that the hash key after makeMove+revertMove is always identical to the hash key before makeMove? Promotions, castling, ep capture are typical pitfalls. Your two weeks of frustration sound so familiar when I think of these problems ...

In case b) I would say that you should expect the search to go slightly deeper with TT, and possibly (sometimes) find a different move than without TT, so nothing unexpected there. I have to add, though, that you are using the TT for transpositions only but (as far as I could see) not for move ordering yet, so the difference in move decisions may be small. So even in case b) the same kind of bugs as in a) might be responsible.

Regarding your source code, I have one question: what is the purpose of this part?

Code: Select all

        if ((timeExpired == true) || depth <= 0) {
            MoveList opponentMoves = new MoveList();
            opponentMoves.generate(board, -color, false);
            return evaluation.value(board, moves, opponentMoves, color);
        }

Most people simply return without further action in case of a timeout, and ignore the whole subtree at the root node since it was searched incompletely and must not influence the move decision. In case of reaching the horizon (depth <= 0), why do you generate moves there? Is it to test for mate? Probably you will add quiescence search at that point later on but for the moment I could imagine that generating all moves of the opponent at leaf nodes slows down a lot.

Sven

[Desperado]

Hello Marika,

Sven already has given some good advices. But anyway here are
some "little" other ideas which can cause strange behaviour.

a: your source
==========

Like Sven i wasnt able to see sth obious wrong in your source, maybe
it is a good idea to post your storage methods too (move,putRealPosition)

only one little thing which may cause "strange" behaviour. you store
a bestmove to trans even if it is below alpha right ?!, and if so and you also use it for move ordering already (dont know what your movegenerator does...), well that can easily cause strange behaviour because it not necessaraly the best move (at least you can proove that point).

b: ideas
========

- how are the values stored (check signs,mate scores)
- check things like mixing up , positionKey, lockingKey (like hibits,lobits)when storeing+retrieving from slot.
- in general check if the things you want to store,retrieve _are_ like you
put them to the functions and arent changed because using wrong types for example.

c: hint
=======

recently i changed my replacement scheme and refreshed my functions.
Of course i introduced a very stupid bug which was:
i stored replacement score , instead of position score to the table.
These kind of bugs may be very hard to find, because for your own programm, you read what you are thinking of, instead what is
really written.

good luck.

maybe we can help more if you send your methods from transtable.

regards Michael

[Sven]

maybe it is a good idea to post your storage methods too (move,putRealPosition)

Method TranspositionTable::move() is probably no storage method, it appears to maintain the hash key of the current board. All methods called on the "transpoTable" object implicitly seem to know the hash key. Apart from that I fully agree to you.

@Marika: are you sure that one method move() is sufficient for all possible cases of reverting the effect of a move on the hash key? This might require to store the captured piece, perhaps also the moving piece, within the move object, beneath the usual from/to/promotionPiece and possibly flags for castling and ep.

only one little thing which may cause "strange" behaviour. you store a bestmove to trans even if it is below alpha right ?!, and if so and you also use it for move ordering already (dont know what your movegenerator does...), well that can easily cause strange behaviour because it not necessaraly the best move (at least you can proove that point).

The code does not look like using TT for move ordering since I see no piece of code where the best move is even being tracked, let alone passed to the TT. From what I see, all that is stored is the value along with draft and flags.

Sven

[marion]

Thanks for your response.

I compare the fixed depth.

Have you checked, for instance, that your hash key generated incrementally after each move is 100% identical to the hash key calculated from scratch?

Perhaps I don't understand here. Do you mean that the hash codes should be identical when I play a sequence of moves with or without searching?

And, since you seem to have some "unmake" operation for the hash key, that the hash key after makeMove+revertMove is always identical to the hash key before makeMove? Promotions, castling, ep capture are typical pitfalls. Your two weeks of frustration sound so familiar when I think of these problems ...

Yes, this should be alright. It was the first thing I checked. Actually there was this problem with wrong promotion reverting, but the program was "falling down", so when I found this bug and fixed It, the program now doesn't fall, but there's still something.

Regarding your source code, I have one question: what is the purpose of this part?

Code: Select all

        if ((timeExpired == true) || depth <= 0) {
            MoveList opponentMoves = new MoveList();
            opponentMoves.generate(board, -color, false);
            return evaluation.value(board, moves, opponentMoves, color);
        }

The possible moves from the leaves are a part of the evaluation function. Positions with more possible moves I consider as better. But you're right, it's counted really often:). So I'll re-make it.

[marion]

Thanks for your response too.

only one little thing which may cause "strange" behaviour. you store
a bestmove to trans even if it is below alpha right ?!, and if so and you also use it for move ordering already (dont know what your movegenerator does...), well that can easily cause strange behaviour because it not necessaraly the best move (at least you can proove that point).

I don't use move ordering yet, but I thought, that even if the value is below alfa, I can store it with alfa-flag and when the position occurs again, I can use the alfa value, or...?

b: ideas
========
- how are the values stored (check signs,mate scores)
- check things like mixing up , positionKey, lockingKey (like hibits,lobits)when storeing+retrieving from slot.
- in general check if the things you want to store,retrieve _are_ like you
put them to the functions and arent changed because using wrong types for example.

I don't see any problem with this points, but I will try to test more cases. Maybe I should say, that the moves are different when the searching is deeper (>4), but of course, It doesn't automatically mean, that there is no problem with smaller depths.

[Onno Garms]

The moves are different when the transposition heuristic is used and when it is not used. The moves are not bad in both cases, but I think, that they should be the same, shouldn't they?

No.

If you want your search to return the same moves with and without the TT, you are very restricted in what you can do in your search. For example you must not:

- use a TT score from a larger depth
- use TT for move ordering
- use killer heuristic (the move in the TT might have been computed with different killers; having cutoffs by TT also fills the killers with different values)
- use history tables (same reasons)
- use PV scores (with more extensions) when you probe on non-PV positions
- and much more

Over all: Any reasonable search has results that differ when you use the TT or not.

When I started my engine, I had a search that in deed did not depend on TT or not. But it was not worth the effort to maintain that, even for testing purposes.

[marion]

@Marika: are you sure that one method move() is sufficient for all possible cases of reverting the effect of a move on the hash key? This might require to store the captured piece, perhaps also the moving piece, within the move object, beneath the usual from/to/promotionPiece and possibly flags for castling and ep.

Yes, this bug was there with castling, but the program didn't work almost at all, now all special moves are correctly moved and retrieved, I hope

[Desperado]

maybe it is a good idea to post your storage methods too (move,putRealPosition)

Method TranspositionTable::move() is probably no storage method, it appears to maintain the hash key of the current board. All methods called on the "transpoTable" object implicitly seem to know the hash key. Apart from that I fully agree to you.

@Marika: are you sure that one method move() is sufficient for all possible cases of reverting the effect of a move on the hash key? This might require to store the captured piece, perhaps also the moving piece, within the move object, beneath the usual from/to/promotionPiece and possibly flags for castling and ep.

only one little thing which may cause "strange" behaviour. you store a bestmove to trans even if it is below alpha right ?!, and if so and you also use it for move ordering already (dont know what your movegenerator does...), well that can easily cause strange behaviour because it not necessaraly the best move (at least you can proove that point).

The code does not look like using TT for move ordering since I see no piece of code where the best move is even being tracked, let alone passed to the TT. From what I see, all that is stored is the value along with draft and flags.

Sven

@Sven

Think you are right...

@Marika

well, i reread your post and i wonder if we are searching a _bug_ or
we are searching for a reason that your expectations arent met, in the
sense that your engine is not blowing away the version without TT-usage.

i mean, depending on the development stage your engine has (i assume it is an early stage),
you should know that the TT-Pruning is the "small" advantage.
The "big(ger)" advantage comes from a better move ordering which
also requires to store the bestmove found with the other stuff.
Next time visiting that node and if no TT-cut occurs
because of insuffcient draft, you will try the bestMove as first and speed up the search drastically.

lets assume there is no bug. So moves (at the root, and elsewhere) can change of course
because the whole tree is full of different decisions. The optimal case is that by virtual depth the quality of the search result
for a node gets better, but a transposition table _can_ and _will_ also remember nonsense, which can lead to bad play.

So, what do you think ? wrong expectations or bug hunting ?

Michael

[sje]

It might be helpful to use the almost-standard position for transposition table testing:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
This is from Reuben Fine's Basic Chess Endings, position #70. The winning move is 1 Kb1 and a program with a working transpostion subsystem should find the move in under a second.