transposition table details

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 23795
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: transposition table details

Post by hgm » Wed May 27, 2009 10:52 am

mcostalba wrote:I have played with an idea that I called "Iterative deepening shortcut"
In Joker this is automatic. You start a search at iteration 1, and all moves from the root return score (or bound) with depth 13 (because they are hash hits on entries with this draft). Then the next iteration will be a 14-py search.

jdart
Posts: 3843
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: transposition table details

Post by jdart » Wed May 27, 2009 3:58 pm

That's an interesting idea.

I haven't experimented with this much lately, but the last time I did the difference in algorithms was not huge.

Arasan currently uses a dual table scheme like Crafty/Belle, but the replace and depth-based tables are equal in size.

--Jon

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: transposition table details

Post by diep » Wed May 27, 2009 7:13 pm

mcostalba wrote:
Don wrote:
You will notice that the first "go depth 15" command takes 29.3 seconds in this case.

The second time I run this it takes 0.002 seconds!

This makes me think that Vas has a rule not to ever overwrite PV nodes, it's probably as simple as that or something similar.
I have played with an idea that I called "Iterative deepening shortcut"

This is how it works.

- At the end of a search say at depth 13 we return the best move and store the ponder move and also the PV

- If the next opponent move is the ponder move we will detect this (because we remember previous ponder move) and so we know that the PV we have stored is the best one until depth 13 - 2 = 11

- So we try the PV and do not change it until we don't reach at least depth 11. This avoids false fail highs at lower depth that we know in advance will be reverted by a next search at deeper depths. This also avoids spikes and instability at very thight times when you have to return the best move before to reach the previous depth -2.

I have still not managed to make it work right, but I would think it has some potential. Another possibility is to skip completely the Iterative Loop and jump directly to Iteration 11 because we know the PV that we have stored is the best until that depth.

Have someone tested this idea before ?

Thanks
Marco
Hi Marco,

If you scroll up and see how little nodes it costs diep:

You want to save out those 344 nodes meanwhile getting a million a second or so?

What i understood from Don is that he doesn't get to depth 15 instantly.

What diep's doing is 8 probes (used to be 4, probably 4 is better for you, as diep searches pretty slow) and create an overwrite value x
x = depthleft+numberofsearchesdoneingame;

Smallest x always gets overwritten.

Vincent

Post Reply