Moving instantly based on the transposition table.

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
konsolas
Posts: 166
Joined: Sun Jun 12, 2016 3:44 pm
Location: London
Full name: Vincent
Contact:

Moving instantly based on the transposition table.

Post by konsolas » Tue May 14, 2019 8:09 pm

So in my last release of Topple, I added an interesting feature called "move from hash", where Topple probes the transposition table at the root position of a search, and if there is an entry with an exact bound, returns that as the bestmove instantly without any further searching, subject to some conditions:
  • The depth of the entry must be at least the root depth of the last search
  • The last search must have taken more than the "average" time taken for a search
Here is my implementation of the idea: https://github.com/konsolas/ToppleChess ... #L241-L264

As far as I can tell, this isn't present in any of the top open source engines, but, based on testing, it seems to significantly improve playing strength at short time controls, as it leaves time for other moves to be searched more deeply.

Has anyone else considered/tried this? Are there any caveats I should be aware of?

User avatar
xr_a_y
Posts: 539
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Moving instantly based on the transposition table.

Post by xr_a_y » Tue May 14, 2019 8:21 pm

I have tested it (more or less) already in Minic a few weeks ago without success. Code is commented around line 3428. I took the idea seing another engine starting search at a deep depth and guessing this is due to tt usage...

PK
Posts: 790
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Moving instantly based on the transposition table.

Post by PK » Wed May 15, 2019 8:54 am

Success of this technique probably depends on whether lower iterations help in move ordering by setting history values etc. If they help, then iteration right after one that returned hash score can actually take longer than all the skipped iterations together.

User avatar
xr_a_y
Posts: 539
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Moving instantly based on the transposition table.

Post by xr_a_y » Wed May 15, 2019 9:58 am

PK wrote:
Wed May 15, 2019 8:54 am
Success of this technique probably depends on whether lower iterations help in move ordering by setting history values etc. If they help, then iteration right after one that returned hash score can actually take longer than all the skipped iterations together.
That's what I though ...

voffka
Posts: 34
Joined: Sat Jun 30, 2018 8:58 pm
Location: Ukraine
Full name: Volodymyr Shcherbyna

Re: Moving instantly based on the transposition table.

Post by voffka » Wed May 15, 2019 10:58 am

I've run ~ 1000 CCRL 40/4 games and I don't see any significant improvement in Igel:

Score of Igel 1.6.0 64 POPCNT vs Igel 1.5.1 64 POPCNT: 207 - 195 - 423 [0.507] 825
Elo difference: 5.05 +/- 16.54

I think the elo gain will wear off if I do more games (5-10k), so I am not sure it is helping at least in Igel's case.

konsolas
Posts: 166
Joined: Sun Jun 12, 2016 3:44 pm
Location: London
Full name: Vincent
Contact:

Re: Moving instantly based on the transposition table.

Post by konsolas » Wed May 15, 2019 3:00 pm

Maybe this is specific to certain time controls: at a repeating time control like 40/4, engines rarely get under time pressure that this change would help to avoid.

User avatar
hgm
Posts: 23221
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Moving instantly based on the transposition table.

Post by hgm » Wed May 15, 2019 5:42 pm

This is something that is supposed to never happen, right? The depth you need in the root is the largest depth of the entire search, so only positions that have been searched at the root before should satisfy the requirement (but then you are already repeating positions, and mindlessly sticking to the loop is probably the last thing you want to do in such a case).

konsolas
Posts: 166
Joined: Sun Jun 12, 2016 3:44 pm
Location: London
Full name: Vincent
Contact:

Re: Moving instantly based on the transposition table.

Post by konsolas » Wed May 15, 2019 5:48 pm

hgm wrote:
Wed May 15, 2019 5:42 pm
This is something that is supposed to never happen, right? The depth you need in the root is the largest depth of the entire search, so only positions that have been searched at the root before should satisfy the requirement (but then you are already repeating positions, and mindlessly sticking to the loop is probably the last thing you want to do in such a case).
It happens quite frequently in fast games, because the root depth usually isn't representative of the actual search depth.

Most frequently, it happens for recaptures and checks, due to singular extensions and check extensions. So the hash move will only apply if the new position was extended to have the same depth as the root node.

Post Reply