Regarding Transposition Tables

[StackFish5]

<r>I have been working on a chess engine recently in Python. And after implementing some basic searching algorithms, I decided to try to implement transposition tables which only stores the score of the position it's analyzing. Unfortunately, when I attempted to test its speed, all it did was choose some very very questionable moves. And I don't know how to fix this issue even though I have looked into it countless times.<br/>
<br/>
Negamax code:
<CODE><s>

Code: Select all

</s>def selectmove(depth):
    try:
        move = chess.polyglot.MemoryMappedReader("Perfect2021.bin").weighted_choice(board).move
        return move #book moves
    except:
     bestMove = chess.Move.null()
     bestValue = -99999
     alpha = -1000000
     beta = 1000000
     global ttable
     ttable={} #transposition table
     for move in board.legal_moves:
        board.push(move)
        boardValue = -alphabeta(-beta, -alpha, depth - 1)
        if boardValue > bestValue:
            bestValue = boardValue
            bestMove = move
        if (boardValue > alpha):
            alpha = boardValue
        board.pop()
     return bestMove<e>

</e></CODE>
Modified alpha beta pruning for transposition tables (not working):
<CODE><s>

Code: Select all

</s>def alphabeta(alpha, beta, depthleft):
 global ttable
 if (depthleft == 0):
   position=chess.Board.fen(chess.Board()) #having problems with this section
   if position in ttable.keys():
     return ttable.get(position)
   else:
      value=quiesce(alpha, beta)
      ttable[chess.Board.fen(chess.Board())]=value
      return value
 else:
   for move in board.legal_moves:
     board.push(move)
     score = -alphabeta(-beta, -alpha, depthleft - 1)
     board.pop()
     if (score >= beta):
      return score
     if (score > alpha):
       alpha = score
 return alpha<e>

</e></CODE></r>

Side note: I am using the python-chess library I found on Github.

[Ras]

only stores the score of the position it's analyzing.

It also needs to store the depth draft that the score refers to, the node type, and if available, the best move: https://www.chessprogramming.org/Transp ... _is_Stored

[StackFish5]

only stores the score of the position it's analyzing.

It also needs to store the depth draft that the score refers to, the node type, and if available, the best move: https://www.chessprogramming.org/Transp ... _is_Stored

Thanks! I'll definitely try those methods. Hopefully all works out as I intended.

[Sven]

You only need to store the best move if you use the hash table for move ordering, of course. The code above does not appear to do that but usually it is a significant strength improvement to try the hash table move first.

What I observe in your code example is also:
- You only store data in the TT at horizon nodes (depthLeft = 0). Storing also at inner nodes at depthLeft > 0 would help a lot. As already mentioned here, storing and using depth information is essential.
- Unrelated to TT: you have no mate/stalemate detection and no other draw detection yet (or you omitted it for simplicity).

[Henk]

TT is a problem for history is not the same.
Even after a capture. For instance when using history heuristic for move ordering.
So I deleted TT for why store outdated information. But I think it plays worse now at longer time controls.

[R. Tomasi]

You only need to store the best move if you use the hash table for move ordering, of course. The code above does not appear to do that but usually it is a significant strength improvement to try the hash table move first.

What I observe in your code example is also:
- You only store data in the TT at horizon nodes (depthLeft = 0). Storing also at inner nodes at depthLeft > 0 would help a lot. As already mentioned here, storing and using depth information is essential.
- Unrelated to TT: you have no mate/stalemate detection and no other draw detection yet (or you omitted it for simplicity).

Another reason to store the best move may be to defend against hash collisions (the best move may be illegal in such a case), but doing so can be time consuming.

[Ras]

Another reason to store the best move may be to defend against hash collisions (the best move may be illegal in such a case), but doing so can be time consuming.

I always validate a hash move for pseudo legality because I'll most likely need that move for a beta-cutoff anyway, and then without even generating a move list so that it better be a possible move. The test for full legality comes when trying it, just like all other moves.

[R. Tomasi]

Code: Select all

position=chess.Board.fen(chess.Board()) #having problems with this section
if position in ttable.keys():
     return ttable.get(position)

This line just caught my eye: are you using the FEN string of the position as TT key? If that's the case it's probably not a good idea, since generating the FEN is rather expensive. The typical way to generate the TT keys is to use incremental Zobrist hashing: the key of the position is a 64bit (for some engines 32bit) integer that can be incrementally updated during making/unmaking of moves. Index of a position in the TT is then obtained by simply clipping the hash value to the lower n bits. That's quite efficient but of course it's not a unique mapping, i.e. there will be hash collisions. That's why one usually stores the complete hash key within the TT entry (test against full hash == less collisions) and verifies that the best move is legal. That way chances of hash collisions are really neglegible and in the rare event of a collision the engine will not loose the game by playing an illegal move.

https://www.chessprogramming.org/Zobrist_Hashing

[Sven]

Another reason to store the best move may be to defend against hash collisions (the best move may be illegal in such a case), but doing so can be time consuming.

I always validate a hash move for pseudo legality because I'll most likely need that move for a beta-cutoff anyway, and then without even generating a move list so that it better be a possible move. The test for full legality comes when trying it, just like all other moves.

My point was that an engine in an early development stage that does not use the TT for move ordering yet (i.e., does not try the hash move first) also has no need yet to store a best move in the TT. Measuring the improvement you get from using TT also for move ordering should include storing/retrieving the hash move vs. not doing so.

When not using the TT for move ordering, I think that storing a hash move in order to reduce hash collisions by testing the hash move for pseudo-legality is much too expensive to be worth the effort. Hash collisions are very rare, so the benefit would be quite small. And in the past it has been proven that hash collisions usually have a very small impact on the final search result at the root node. Testing the hash move for pseudo-legality is crucial when trying it as the first move before even doing any move generation, to avoid crashing the engine. But I would refrain from doing so just to reduce hash collisions.

[Sven]

Code: Select all

position=chess.Board.fen(chess.Board()) #having problems with this section
if position in ttable.keys():
     return ttable.get(position)

This line just caught my eye: are you using the FEN string of the position as TT key? If that's the case it's probably not a good idea, since generating the FEN is rather expensive. The typical way to generate the TT keys is to use incremental Zobrist hashing: the key of the position is a 64bit (for some engines 32bit) integer that can be incrementally updated during making/unmaking of moves. Index of a position in the TT is then obtained by simply clipping the hash value to the lower n bits. That's quite efficient but of course it's not a unique mapping, i.e. there will be hash collisions. That's why one usually stores the complete hash key within the TT entry (test against full hash == less collisions)

Fully agreed so far, except that it is not necessary to store the full hash key since also storing its index part (the lower N bits which you use for TT lookup) would be redundant.

and verifies that the best move is legal. That way chances of hash collisions are really neglegible and in the rare event of a collision the engine will not loose the game by playing an illegal move.

I disagree. You never perform a TT cutoff at the root node, and you never play an illegal root move in the game. Missing to detect a hash collision somewhere down the tree can, in the worst case, lead to a wrong score obtained by accidentally detecting (or missing) a transposition. And as I wrote in another post (and as it is well-known), using the TT also for move ordering definitely requires to test the hash move for pseudo-legality but the latter does not primarily follow the goal to reduce hash collisions.