The "Secret" TT-move Singular Extension

[Don]

I have heard that in stockfish it only make a very small difference but I don't know first-hand.

We are now doing a test with exclusion search disabled. This is done for an unrelated aim, but it happens match is ongoing just in these days

So we could provide our test results as soon test finishes.

Regarding point raisen by Bob, I agree that is not fully clear to us why SE works, but it works. It seems we are much more careful then Bob on the assumption: "If I don't understand why it should work then it does not work" but actually he has also much more experience then us.

Anyhow, just to come back to something practical, the argument of the 20% of TT hits is bogus because we should consider only the hit rate for nodes elegible for SE, and so for high depth nodes (in SF 8 plyes and higher).

I didn't say 20% were extended. I simply said that out of the total tree space of size N, only 20% of those nodes can be considered for the TT extension. The other 80% have no chance, even though many of those are relevant positions with good moves that deserve extension. This somewhat randomly chooses 20% of the search space for possible extension consideration, which seems way too ad-hoc to me.

In Hsu's implementation, which I mirrored (with great difficulty and effort) in the last two years of Cray Blitz, he took great pains to avoid being inconsistent about when a move is extended and when it is not. This approach (tt-extension) totally ignores any semblance of "fairness" about what gets extended vs what is not vs what can never be extended (if it isn't in the table at all).

Bob, I think you are too anal about this. Every extension in any program is arbitrary. And so is the margin Hsu uses to test for singularity. I could use your same argument and say that it doesn't make sense to extend a move just because it happens to be 50 points better than the others, but not extend it if it's 49 points better - it seems rather arbitrary but some value has to be chosen.

There is also the point that the same move in the same position may get extended on this iteration but not on the next. Or not when it occurs in another part of the tree. I don't have an a pirori reason to believe that is a bad thing. If I can extend only 20% of the moves that really need to be extended that is better than zero percent isn't it?

I don't believe you can build a strong chess program that is "correct." You can solve the GHI problem, but at the expense of a much weaker program. If you want a "correct" program then you cannot use LMR either, because the first move might change, and the move ordering can be arbitrary from node to node and the window can change after any move.

I don't see any problem with this, unless of course it just doesn't test well for you which seems to be the case. I'm more interested in why it works for some and not others.

This is not about being "anal". It is about being consistent.

I think you are anal about being consistent

Seriously, I don't think it matters here. I believe if I were to flip a coin to determine whether to do check extensions it would still be much stronger than not doing them. If I can be consistent of course I would try to be. But you take what you can get.

The reason you use the hash table move is because it provides you with a score - to test for singularity you don't have to first evaluate the move you are testing and then the siblings. The hash table move is not special except for the fact that a score is available that you can work with.

Any reasonable criterion could work for selecting moves to extend or reduce. But what about a random one?

It's not random, it's just not perfect. In fact it's far from random. It's a proven best move. It's like hiring someone to work for you. You check their references and make a judgement and hope you picked the best candidate. That's not random, but it's not perfect either. But it's far better than actually picking a candidate randomly.

Nobody says everything has to be correct, but when you extend checks, do you extend them all, or just the ones that were TT hits? I don't extend 'em all, but I am consistent in why (SEE score). But something tells me that it would be much less effective to extend a random check here and there as opposed to extending some consistent set of checks (possibly all). Extending random checks might provide some very small benefit, or it might hurt in the cases where you extend a bad one and don't extend an important one...

That was my point. What is found in the TT is pretty random. That certainly doesn't seem like a reasonable way to select a set of positions for potential extension.

In PV nodes what is found in the TT is very likely to be the best move - especially if it's singular.

Again, an opinion based on testing, with some supporting results, but still just an opinion, not a statement of fact. It might work for some. It didn't do anything for Crafty (didn't hurt, but didn't help). Was a minimal improvement for stockfish. Not much else I can say...

I tried testing the first move always for singularity, by first doing a reduced depth search to get a score (IID style) and then using a zero window search on the siblings. That's a consistent way to do it, but it did not seem to work for me. I don't know why it's better to just use the hash table score.

[mjlef]

Well, you can indeed store a best move at all nodes. Just save the best move the search finds, even if it is below alpha.

[bob]

I have heard that in stockfish it only make a very small difference but I don't know first-hand.

We are now doing a test with exclusion search disabled. This is done for an unrelated aim, but it happens match is ongoing just in these days

So we could provide our test results as soon test finishes.

Regarding point raisen by Bob, I agree that is not fully clear to us why SE works, but it works. It seems we are much more careful then Bob on the assumption: "If I don't understand why it should work then it does not work" but actually he has also much more experience then us.

Anyhow, just to come back to something practical, the argument of the 20% of TT hits is bogus because we should consider only the hit rate for nodes elegible for SE, and so for high depth nodes (in SF 8 plyes and higher).

I didn't say 20% were extended. I simply said that out of the total tree space of size N, only 20% of those nodes can be considered for the TT extension. The other 80% have no chance, even though many of those are relevant positions with good moves that deserve extension. This somewhat randomly chooses 20% of the search space for possible extension consideration, which seems way too ad-hoc to me.

In Hsu's implementation, which I mirrored (with great difficulty and effort) in the last two years of Cray Blitz, he took great pains to avoid being inconsistent about when a move is extended and when it is not. This approach (tt-extension) totally ignores any semblance of "fairness" about what gets extended vs what is not vs what can never be extended (if it isn't in the table at all).

Bob, I think you are too anal about this. Every extension in any program is arbitrary. And so is the margin Hsu uses to test for singularity. I could use your same argument and say that it doesn't make sense to extend a move just because it happens to be 50 points better than the others, but not extend it if it's 49 points better - it seems rather arbitrary but some value has to be chosen.

There is also the point that the same move in the same position may get extended on this iteration but not on the next. Or not when it occurs in another part of the tree. I don't have an a pirori reason to believe that is a bad thing. If I can extend only 20% of the moves that really need to be extended that is better than zero percent isn't it?

I don't believe you can build a strong chess program that is "correct." You can solve the GHI problem, but at the expense of a much weaker program. If you want a "correct" program then you cannot use LMR either, because the first move might change, and the move ordering can be arbitrary from node to node and the window can change after any move.

I don't see any problem with this, unless of course it just doesn't test well for you which seems to be the case. I'm more interested in why it works for some and not others.

This is not about being "anal". It is about being consistent.

I think you are anal about being consistent

Seriously, I don't think it matters here. I believe if I were to flip a coin to determine whether to do check extensions it would still be much stronger than not doing them. If I can be consistent of course I would try to be. But you take what you can get.

The reason you use the hash table move is because it provides you with a score - to test for singularity you don't have to first evaluate the move you are testing and then the siblings. The hash table move is not special except for the fact that a score is available that you can work with.

Any reasonable criterion could work for selecting moves to extend or reduce. But what about a random one?

It's not random, it's just not perfect. In fact it's far from random. It's a proven best move. It's like hiring someone to work for you. You check their references and make a judgement and hope you picked the best candidate. That's not random, but it's not perfect either. But it's far better than actually picking a candidate randomly.

Nobody says everything has to be correct, but when you extend checks, do you extend them all, or just the ones that were TT hits? I don't extend 'em all, but I am consistent in why (SEE score). But something tells me that it would be much less effective to extend a random check here and there as opposed to extending some consistent set of checks (possibly all). Extending random checks might provide some very small benefit, or it might hurt in the cases where you extend a bad one and don't extend an important one...

That was my point. What is found in the TT is pretty random. That certainly doesn't seem like a reasonable way to select a set of positions for potential extension.

In PV nodes what is found in the TT is very likely to be the best move - especially if it's singular.

Again, an opinion based on testing, with some supporting results, but still just an opinion, not a statement of fact. It might work for some. It didn't do anything for Crafty (didn't hurt, but didn't help). Was a minimal improvement for stockfish. Not much else I can say...

I tried testing the first move always for singularity, by first doing a reduced depth search to get a score (IID style) and then using a zero window search on the siblings. That's a consistent way to do it, but it did not seem to work for me. I don't know why it's better to just use the hash table score.

One guiding principle I have adhered to over the years is "if I am going to do something, I am going to do it for a reason." I've tried a ton of SE approaches particularly last year. I have done everything in Crafty, except to do the full Hsu SE implementation. That was a lot of code to add to Cray Blitz... and I unfortunately lost all the source so it would have to be a "complete from scratch" implementation. It is really not so clear that it will ever be a significant gain, which means there are other ideas to examine first. Particularly the inverse SE idea, that of reducing some moves more than others... Got a lot of ideas to try there when I find time...

[bob]

Well, you can indeed store a best move at all nodes. Just save the best move the search finds, even if it is below alpha.

No, you can't. All you can store is some random move that seems to be best. But at ALL nodes, there is by definition, no "best move". And if you just happen to pick the one that has the best score that is <= alpha you are picking a pretty random move. If you search the real best move at an ALL node, and get the best reply, you get a low score. If you search a much worse move but in response you also look at a much worse move, then you get a better score backed up. it is wrong.

This topic comes up every year or two, I point this out every year or two, someone doesn't believe me every year or two, and they run the experiment. And they discover, every year or two, that it does not work. Having a _good_ move as the best move is important for ordering. If you store poor guesses, you get larger trees. Feel free to try it. Ed did (In Rebel) and discovered that what seemed to be a reasonable idea was actually costing him 10% in increased tree size.

This is just a bad idea. You can use the trick I use to get a little speed bonus, that of storing the _first_ move you search at an ALL node as "best". If it was a hash move, good, we try it first and if it doesn't cause a cutoff, oh well. If it was not a hash move, whatever I search first without a hash move is still a good thing to store and try first. But not some random move based on the old nonsense of "best = - inf" and then best = Max(best, value) where value comes from the recursive search return value...

It really doesn't work well.

[mcostalba]

Sounds badly wrong to me. 80% of your nodes are therefore "cut" nodes as opposed to "all" nodes (which have no best move)??? Also this would be more interesting with much longer searches to match the potential for large TT size...

If a node fails high a move is stored if, in a following search, the same node fails low this is recorded but the stored move is preserved.

Anyhow, how we say in Italy "There is no worse deaf than who doesn't want to hear" so I would suggest to stop it here.

Here is test results with SE disabled:

After 5415 games:
SE_disabled - original: 780 - 1104 - 3531 ELO -20 (+- 5.6)

[Don]

One guiding principle I have adhered to over the years is "if I am going to do something, I am going to do it for a reason." I've tried a ton of SE approaches particularly last year. I have done everything in Crafty, except to do the full Hsu SE implementation. That was a lot of code to add to Cray Blitz... and I unfortunately lost all the source so it would have to be a "complete from scratch" implementation. It is really not so clear that it will ever be a significant gain, which means there are other ideas to examine first. Particularly the inverse SE idea, that of reducing some moves more than others... Got a lot of ideas to try there when I find time...

I often do experiments just to see what happens - not expecting a particular result. Sometimes I do this to challenge my own intuition.

[Daniel Shawul]

Well your result is more or less same as before, isn't it ?
Also what is the time control ? Have you made any changes to selectivity since then that may contribute directly or indirectly to the overall effect?
I see it is also a self test game. I have no problem with that but you should also bear in mind that changes could be significantly magnified there!
I am very serious about that after a little experience I had with a change I considered minor.
Also the point of that discussion IIRC was to disprove a +70 elo SE gain?
We all agree that is not the case now. Sure you could gain some with it, but others like me didn't gain or infact lost some elo with it.
Also your form of SE don't make a lot of sense even to you (admitted by yourself), even though you are trying to justify why it works (+20 elo) .

I don't know if there are conditions that I am missing from your implementation. Is there any particular conditon that you want to emphasize,
like the depth above which TT is probed. I am willing to make the test on Scorpio and see if I get anything else. This is for my own satisfaction.
Not to contribute to the group who find SE not working for them Really that is pointless now. If it works for you stick with it, if not bad luck.
But to convince others , we must know the reasons, no ?


Atleast Stockfish is opensource and we can see what it does, but in the past we have seen claims of tricks like that giving a lot of improvement.
While that may not or may be true to a certain extent, I would never believe it unless verified by an independent tester.
So I belive you when you say +20, I belive bob when he said +5, I belive myself when I say -X. For me the matter is settled clear once no one reported a +70 elo.
Ok you didn't say that much but atleast +40.

[mcostalba]

Atleast Stockfish is opensource and we can see what it does

Probably this is the only sentence of your post that makes any sense.

I don't want to convince anybody. To convince somebody is my lowest priority, actually is not even a priority.

There was a thread (this one) that was discussing about a subject that, incidentally, we were testing at the same time, so I took the chance to add my contribute with the test result.

No more no less.

P.S: TC is 20" +0.1 on a QUAD.

[Daniel Shawul]

Probably this is the only sentence of your post that makes any sense. Smile

I don't want to convince anybody. To convince somebody is my lowest priority, actually is not even a priority.

oh snap... nice one Marco.

what say you ?

There is no worse deaf than who doesn't want to hear"

That sounds like a _desperate_ attempt to convince.

[mjlef]

Well, you can indeed store a best move at all nodes. Just save the best move the search finds, even if it is below alpha.

No, you can't. All you can store is some random move that seems to be best. But at ALL nodes, there is by definition, no "best move". And if you just happen to pick the one that has the best score that is <= alpha you are picking a pretty random move. If you search the real best move at an ALL node, and get the best reply, you get a low score. If you search a much worse move but in response you also look at a much worse move, then you get a better score backed up. it is wrong.

This topic comes up every year or two, I point this out every year or two, someone doesn't believe me every year or two, and they run the experiment. And they discover, every year or two, that it does not work. Having a _good_ move as the best move is important for ordering. If you store poor guesses, you get larger trees. Feel free to try it. Ed did (In Rebel) and discovered that what seemed to be a reasonable idea was actually costing him 10% in increased tree size.

This is just a bad idea. You can use the trick I use to get a little speed bonus, that of storing the _first_ move you search at an ALL node as "best". If it was a hash move, good, we try it first and if it doesn't cause a cutoff, oh well. If it was not a hash move, whatever I search first without a hash move is still a good thing to store and try first. But not some random move based on the old nonsense of "best = - inf" and then best = Max(best, value) where value comes from the recursive search return value...

It really doesn't work well.

I was just saying you CAN save a move. Not that it will necessarily be the best, any more than saying a move causing a beta cutoff is going to be the best. This is a fact. You CAN store it. Now does it help? Well at one point my testing said it did and another point it said it did not. It seems largely seems to depend on how well the fail hard/fail soft stuff is done. After criticizing me and being factually wrong, you then go and propose doing the same thing. Why all the drama Bob? How about just doing a run with a recent crafty and report the results. Say "Yes you can do it, but it does not hep, and here is the data".