Regarding Transposition Tables

Discussion of chess software programming and technical issues.

Moderator: Ras

R. Tomasi
Posts: 307
Joined: Wed Sep 01, 2021 4:08 pm
Location: Germany
Full name: Roland Tomasi

Re: Regarding Transposition Tables

Post by R. Tomasi »

Sven wrote: Sat Jan 01, 2022 2:52 pm
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.
You're right :oops: if you want to do anything at all with the hash move, you'll have to ensure that it's pseudo legal, elsewise all kind of silly stuff will happen (I'm pretty sure my engine would just crash in such cases).

Actually, when I profile my engine, a significant amount of time is spent on pseudo-legality verification of hash moves, because more or less any position it looks at is of course checked against the TT at some point. Now before the usual suspects jump at me to tell me that I should use a fully legal move generator: the hash move isn't generated, so this does not help in a straight-forward way. I wonder what the fastest way to check for pseudo-legality is in a bitboard based framework.
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Regarding Transposition Tables

Post by Sven »

R. Tomasi wrote: Sat Jan 01, 2022 3:17 pm I wonder what the fastest way to check for pseudo-legality is in a bitboard based framework.
It certainly depends on the concrete engine which checks are really necessary to ensure that making the hash move does not crash the engine. Certainly the minimum is that the "from" square should be occupied by a friendly piece and the "to" square should either be empty or occupied by an enemy piece. En passant captures are slightly different here ("to" must be empty, and the corresponding square next to "from" must be occupied by an enemy pawn). If the information stored in the TT helps to recognize that the hash move was a castling move (and not just a move of any piece from e1 to g1) you would usually perform some more validation steps, e.g. for white short castling there should be a white king on e1, a white rook on h1, and all intermediate squares should be empty.

I don't think it matters much whether you do these validation steps in a bitboard or mailbox engine.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)