Yet another tt issue

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.
User avatar
xr_a_y
Posts: 580
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Yet another tt issue

Post by xr_a_y » Sun Jun 10, 2018 10:08 am

Dear all,

following a previous post about some TT issue (viewtopic.php?f=7&t=67599), I started investigate my own implementation step by step. The current implementation is as follows (both at root and inside the tree):
Storing :
* tt_store at beta cut-off as bound_beta
* tt_store at the end of root moves loop as alphaRaised?bound_exact:bound_alpha
Getting :
* at root : only use bound_exact
* inside the tree : only use if

Code: Select all

(!fromPV || (ttt.t_type == Transposition::tt_exact && ttt.score > alpha && ttt.score < beta))
using depth without extension or reduction both for storing and getting an entry in the TT.

The problem is that :
* using TT just for getting best move (I mean just sorting the TT move first) both at root and in the tree is worth +120elo in Weini
* using TT only inside the tree to directly return a score under the previous condition is worth +90elo more
* BUT using TT at root in order to (I tried to differente implementations)
a) skip current depth of the iterative deepening loop, or
b) return a score in the window search (introducing the same condition on score as inside the tree)
both lead to a great elo loss (at least -80elo)

Any idea where I can be wrong ? I am wondering if it can be a time management issue. Very often (when pondering even more), when using TT at root, the move that is used is the TT one, because the first iterative depth that is not skipped is to long to fit in the available search time.

ps : Yesterday I switch Weini score from float to int without any impact on the engine strenght (so this is not the problem).

Sven
Posts: 3783
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Yet another tt issue

Post by Sven » Sun Jun 10, 2018 3:21 pm

xr_a_y wrote:
Sun Jun 10, 2018 10:08 am
Dear all,

following a previous post about some TT issue (viewtopic.php?f=7&t=67599), I started investigate my own implementation step by step. The current implementation is as follows (both at root and inside the tree):
Storing :
* tt_store at beta cut-off as bound_beta
* tt_store at the end of root moves loop as alphaRaised?bound_exact:bound_alpha
Getting :
* at root : only use bound_exact
* inside the tree : only use if

Code: Select all

(!fromPV || (ttt.t_type == Transposition::tt_exact && ttt.score > alpha && ttt.score < beta))
using depth without extension or reduction both for storing and getting an entry in the TT.
I would always store something in TT whenever you leave a node after having performed a search. That will also include PV and ALL nodes below the root which you do not seem to include in your implementation. Even ALL nodes can provide useful information (an upper bound for the score).

I hope you also have a condition to ensure that you only do a TT cutoff if your TT entry has a sufficient search depth.
xr_a_y wrote:
Sun Jun 10, 2018 10:08 am
The problem is that :
* using TT just for getting best move (I mean just sorting the TT move first) both at root and in the tree is worth +120elo in Weini
* using TT only inside the tree to directly return a score under the previous condition is worth +90elo more
* BUT using TT at root in order to (I tried to differente implementations)
a) skip current depth of the iterative deepening loop, or
b) return a score in the window search (introducing the same condition on score as inside the tree)
both lead to a great elo loss (at least -80elo)

Any idea where I can be wrong ?
Your results are as expected, I don't think there is anything wrong with it. In general doing a TT cutoff at the root node is not an excellent idea. If there is enough data present in the TT you will see that early iterations will be finished very quickly due to TT cutoffs at shallow nodes, e.g. at ply=1 nodes. So there is no need for any special handling of the root node at all. Additionally, the root node is a PV node by definition, and doing TT cutoffs at PV nodes is a waste and can also lead to surprising results. In your case the amount of "-80 elo" is somewhat surprising as well so maybe there are more problems causing that loss, but I would not care and simply treat the root node as any other PV node by not allowing TT cutoffs there.
xr_a_y wrote:
Sun Jun 10, 2018 10:08 am
I am wondering if it can be a time management issue. Very often (when pondering even more), when using TT at root, the move that is used is the TT one, because the first iterative depth that is not skipped is to long to fit in the available search time.
Here you are mentioning a point that seems to apply to several engines. People sometimes tend to not playing a best move from an incomplete iteration. I see no convincing argument for that. The first move that you search in iteration N is the best move M1 from iteration N-1. The following can occur:

a) If you get a timeout while still searching the subtree of M1 then you play M1 since it is still the best move from previous iteration.

b) If you finish searching the M1 subtree, start searching M2, and get a timeout before finishing it, then you obviously play M1 as well (best move from previous iteration and also best move of current one so far).

c) The interesting situation starts after finishing the M2 subtree and starting M3. Now you have completely searched the subtrees of two root moves in the new iteration. If score(M2) <= score(M1) then M1 still remains your best move. So now let's assume score(M2) > score(M1), making M2 your new best move of current iteration. Why would you *not* play M2 in the game, then, in case of a timeout? You have sufficient information to state that M2 is better than M1 under your search conditions. There might be even better moves but if you don't have enough time to search them then why ignore the information you already have?

It is getting slightly more complex if the new iteration is failing low, and you want to react properly to it. But in the "normal" case mentioned above it should be obvious that it is a valid strategy to play the best move from an incomplete iteration.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

zenpawn
Posts: 280
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

Re: Yet another tt issue

Post by zenpawn » Sun Jun 10, 2018 4:37 pm

Interesting. So, Sven, you only use the TT in zero-window/non-PV nodes? Also, what's the harm in using it at the root if the depth is appropriate, it's an exact type TT entry, and the score it holds is between alpha and beta? Feels like I've tried it every which way, and currently, I do use the TT in PV nodes and, as just described, at the root.
Erin Dame
Author of RookieMonster

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

Re: Yet another tt issue

Post by xr_a_y » Sun Jun 10, 2018 4:39 pm

Thanks for the detailed answer.

Here is some more inputs
I hope you also have a condition to ensure that you only do a TT cutoff if your TT entry has a sufficient search depth.
yes !
I would not care and simply treat the root node as any other PV node by not allowing TT cutoffs there.
I use TT score even inside PV but under the following condition : only exact hits (no out of bound), I am wrong ? I see this in many many engines

Code: Select all

(ttt.t_type == Transposition::tt_exact && ttt.score > alpha && ttt.score < beta)
I would always store something in TT whenever you leave a node after having performed a search
That's what I do, it can be a bound_beta in case of beta cut-off, a bound_alpha is alpha was not raised, or bound_exact if the search raised alpha.
the root node is a PV node by definition, and doing TT cutoffs at PV nodes is a waste and can also lead to surprising results
I don't understand how it can be a waste ? If there is a move in TT for root position ok for depth 10, the iterative deepening search at root will go directly to depth 11 and gain a lot of nodes that can now be used to try depth 11. At least that what I thought ...
Why would you *not* play M2 in the game, then, in case of a timeout?
I use this idea only when depth 1 of iterative deepening is not finished, this allow Weini to play very very fast if case time is missing in very end game. I wasn't sure if I can use that more widely.

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

Re: Yet another tt issue

Post by hgm » Sun Jun 10, 2018 5:10 pm

It doesn't really matter whether youe explicitly skip iterations in the root base on the depth of its hash hit. Because if you don't, all daughters should be in the TT at the required depth, and they would give a hash cut. So the iterations that could be cut will have a negligible number of nodes if you don't skip them.

I don't think it would hurt to use hash cuts in PV nodes; I always considered not taking them as a poor-man's kludge for avoiding clipped PVs.

The time management is a problem, though. If you are in a 'flexible' TC, it pays to give extra time when the score dropped significantly compared to the previous iteration. So most of my engines test for 'out-of-time' in 3 places: at the end of an iteration I don't start a new one if I am sure it will not be able to complete (due to the other two conditions) even if nothing special happens. After every move in the root, when the nominal thinking time for a move has elapsed, I abort the iteration (playing the best move so far) if the score is not far below that of the previous iteration. Finally there is the 'cold-turkey deadline', which can interrupt the search anywhere, causes it to abort, and play the last best move found.

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

Re: Yet another tt issue

Post by xr_a_y » Sun Jun 10, 2018 5:24 pm

hgm wrote:
Sun Jun 10, 2018 5:10 pm
I don't think it would hurt to use hash cuts in PV nodes; I always considered not taking them as a poor-man's kludge for avoiding clipped PVs.
Then I have to look for a bug somewhere ...
I have something like emergency time too, but there is no emergency when TT move score at root is just fine ...

Joost Buijs
Posts: 875
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Yet another tt issue

Post by Joost Buijs » Sun Jun 10, 2018 6:25 pm

In the past I tried many times using or not using the TT-values at the root, indeed when I used them my engine did the shallow iterations very quickly but somehow the last two iterations were always slower, and the net effect was almost zero. The effect on playing strength was also nil, so mainly for simplicity, I don't use the TT at the root at all. Since you seem to be losing >80 Elo when doing this, I get the impression that there must be something wrong, either with the TT or with time controls or occasionally picking a wrong move when the engine is in time trouble.

It is not clear to me why it is not allowed to return out of bound TT-values at PV nodes, in a normal a-b search out of bound values are returned frequently, also at PV nodes, and it really doesn't matter if these values come from the TT or not, at least in my engine I never saw any adversary effect when doing this. In practice though there are many subtle differences between engines, what works for one engine can hurt another and vice versa, so it all boils down to testing. I haven't been running test for years, but in the past I never had good results with self-play, running a gauntlet with (let's say 8) different engines of approx. the same strength always gave me the best indication about playing strength.

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

Re: Yet another tt issue

Post by xr_a_y » Mon Jun 11, 2018 6:06 am

So the iterations that could be cut will have a negligible number of nodes if you don't skip them.
Yes that's correct, and here's a screenshot with the engine 1 pondering in such way when engine 2 is using TT at root. They both end-up with the same move and same score. And indeed engine1 used only a few node do get there thanks to TT use inside the tree. Maybe something strange is that engine2 is able to use TT until depth7 while engine1 is starting to crunch node at depth6 ...
Attachments
TTponder.jpg
TTponder.jpg (74.8 KiB) Viewed 1630 times

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

Re: Yet another tt issue

Post by xr_a_y » Mon Jun 11, 2018 6:08 am

I think more and more this is something due to time control. If I use very small TC the problem seems to be worst while at longer TC it seems less...
I'll look at "stopflag" thing again probably ...

Sven
Posts: 3783
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Yet another tt issue

Post by Sven » Mon Jun 11, 2018 10:14 am

zenpawn wrote:
Sun Jun 10, 2018 4:37 pm
Interesting. So, Sven, you only use the TT in zero-window/non-PV nodes? Also, what's the harm in using it at the root if the depth is appropriate, it's an exact type TT entry, and the score it holds is between alpha and beta? Feels like I've tried it every which way, and currently, I do use the TT in PV nodes and, as just described, at the root.
At PV nodes I use the TT for move ordering but I don't do TT cutoffs there. SF, Senpai, Texel for instance don't do that as well, just to name some examples. There have been many discussions about that topic, and maybe there is no consensus about it yet. One of the more recent threads I found is this one.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Post Reply