TT question?

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

TT question?

Post by Kempelen » Sat May 19, 2012 10:54 am

What is the reason for not using transposition table in quiesce search? most programs don't use it, but I have seen very few that use it.

thanks.
Fermin
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

syzygy
Posts: 4809
Joined: Tue Feb 28, 2012 10:56 pm

Re: TT question?

Post by syzygy » Sat May 19, 2012 11:10 am

Kempelen wrote:What is the reason for not using transposition table in quiesce search? most programs don't use it, but I have seen very few that use it.
Probing the transposition table in the quiesce search will hurt nps, but should lower total node count. So it's a trade-off. For engines that don't do it, the effective gain was likely found to be negative.

Another reason could be that storing results in the transposition table during the quiesce search will more quickly fill the table thereby preventing more valuable information from being stored. However, that can be remedied by a proper replacement strategy.

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

Re: TT question?

Post by hgm » Sat May 19, 2012 11:20 am

I probe TT in QS because it speeds up all my engines (time-to-depth-wise). I guess it would be the same for others that do it, as it is easy enough to not do it.

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

Re: TT question?

Post by diep » Sat May 19, 2012 1:05 pm

syzygy wrote:
Kempelen wrote:What is the reason for not using transposition table in quiesce search? most programs don't use it, but I have seen very few that use it.
Probing the transposition table in the quiesce search will hurt nps, but should lower total node count. So it's a trade-off. For engines that don't do it, the effective gain was likely found to be negative.

Another reason could be that storing results in the transposition table during the quiesce search will more quickly fill the table thereby preventing more valuable information from being stored. However, that can be remedied by a proper replacement strategy.
Oh dear. 'lowering the total node count' is never the goal. Lowering time is the goal. Especially near the qsearch this is a crucial difference.

Let me give a simple example with Diep. Note Diep is using transpositiontables everywhere of course.

Some years ago i did do next statistics. If in Diep i do not use nullmove at depthleft == 1, then total node count decreases nearly 20%.

If in Diep i do use nullmove at depthleft == 1, total nodecount increases nearly 20%, but time to ply reduces by exactly 20%.

So time to ply always is the superior measure here.

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

Re: TT question?

Post by diep » Sat May 19, 2012 1:07 pm

Kempelen wrote:What is the reason for not using transposition table in quiesce search? most programs don't use it, but I have seen very few that use it.

thanks.
Fermin
10-20% decrease in time by using transpositiontables in qsearch for Diep.

syzygy
Posts: 4809
Joined: Tue Feb 28, 2012 10:56 pm

Re: TT question?

Post by syzygy » Sat May 19, 2012 1:23 pm

diep wrote:Oh dear. 'lowering the total node count' is never the goal. Lowering time is the goal. Especially near the qsearch this is a crucial difference.
This is why I mentioned the word trade-off. It's a trade-off between lower nps and lower total number of nodes for the same depth. So I was already talking about time-to-ply.
So time to ply always is the superior measure here.
Here it is. In general, it is not. Tweaking null-move parameters and other reductions will also affect the quality of a fixed-depth search. In that case, time-to-ply isn't telling you the whole story anymore.

User avatar
lucasart
Posts: 3141
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: TT question?

Post by lucasart » Sun May 20, 2012 4:29 am

syzygy wrote:
Kempelen wrote:What is the reason for not using transposition table in quiesce search? most programs don't use it, but I have seen very few that use it.
Probing the transposition table in the quiesce search will hurt nps, but should lower total node count. So it's a trade-off. For engines that don't do it, the effective gain was likely found to be negative.

Another reason could be that storing results in the transposition table during the quiesce search will more quickly fill the table thereby preventing more valuable information from being stored. However, that can be remedied by a proper replacement strategy.
Yes, that's a good summary.

Currently I'm probing the TT at every QS node. I've now started an experiment: use TT only at depth 0 (root move of the QS where my QS behaves differently as it generates some quiet checks). It seems to hurt very slightly time to depth wise, but perhaps that would be compensated (especially at long time controls) by the TT getting filled up slower. Although in theory my TT replacement strategy should compensate this.

Well, only testing will tell: running 1000 games at 12"+0.2" with 32 MB Hash.

User avatar
lucasart
Posts: 3141
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: TT question?

Post by lucasart » Sun May 20, 2012 8:35 am

lucasart wrote:
syzygy wrote:
Kempelen wrote:What is the reason for not using transposition table in quiesce search? most programs don't use it, but I have seen very few that use it.
Probing the transposition table in the quiesce search will hurt nps, but should lower total node count. So it's a trade-off. For engines that don't do it, the effective gain was likely found to be negative.

Another reason could be that storing results in the transposition table during the quiesce search will more quickly fill the table thereby preventing more valuable information from being stored. However, that can be remedied by a proper replacement strategy.
Yes, that's a good summary.

Currently I'm probing the TT at every QS node. I've now started an experiment: use TT only at depth 0 (root move of the QS where my QS behaves differently as it generates some quiet checks). It seems to hurt very slightly time to depth wise, but perhaps that would be compensated (especially at long time controls) by the TT getting filled up slower. Although in theory my TT replacement strategy should compensate this.

Well, only testing will tell: running 1000 games at 12"+0.2" with 32 MB Hash.
Both versions were close, but the test version was slightly weaker (below error bar). So I'd rather keep the original version where I use TT in all QS nodes.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: TT question?

Post by ZirconiumX » Sun May 20, 2012 8:40 am

FruitFly probes (doesn't write) the TT, and uses that as a guided stand-pat.

One experiment I did in the abandoned firstchess based magic was giving QS a dedicated TT. I guess that might be something to try again, if only for the move ordering benefits.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Mincho Georgiev
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: TT question?

Post by Mincho Georgiev » Sun May 20, 2012 8:47 am

Kempelen wrote:What is the reason for not using transposition table in quiesce search? most programs don't use it, but I have seen very few that use it.

thanks.
Fermin
For me in particular, the reason is that I don't see any benefit for using the main transposition table for that purpose elowise. When I refresh my attempts on the subject /which I did extensively in the past/ and came up with an useful implementation, that could change though.

Post Reply