Quick question about TT

[bob]

What if you start with a good capture move instead, which is actually the best move most of the time anyway. And you have not proven that the move you store is not a blunder. ...

Well, if the good capture move is proven do be a blunder at lower depth, I would think that on the average it is a waste of time to search it first. The move is first searched in QS, and my experience is that if a capture is bad in QS, it usually gets a really low upper bound. Captures typically need a very specific refutation E.g. if a NxB is bad because the N was pinned on Q, so that NxB is refuted by RxQ, then RxQ is usually the only move that refutes it, and almost always the move that is first tried to refute it. So you get an upper bound of -600, even when alpha was at +200.

It seems a bit foolhardy to search a move that scores < -600 at d=0 first at higher depths, in the hope it will give you a cutoff > +200. Even when I knew nothing at all about the other moves, I would still bet my money on one of those blindly rather than stick with the -600.

I can see that it might not always be good to search the move with the highest upper bound first. But I would expect that there is some merit in postponing moves that have upper bounds that fall more than a piece short of alpha And making the frst move with a reasonable upper bound hash move would achieve that. If that move doesn't do the trick becaus ethe upper bound was too optimistic, not much would be lost.

Several issues that are not worth arguing. You can believe this or not, at your own peril, which is ok.

In a _normal_ position, a capture is generally the best refutation move. In most positions, the move at the previous ply hangs a piece because this is an exhaustive search that tries everything. And capturing the hung piece is a quick way out. In many other positions, we are winning, and an even exchange (capture) is good enough to fail high as well.

In a _few_ cases, there might be a better move to try. And you are saying "let's try a completely random move, rather than the type of move that is best in the big majority of the cases."

You can _not_ use the score returned to a fail-low (ALL) node for anything useful. The score is a bound from the search below that position. It is not an _accurate_ bound. It is just a score that caused a cutoff. The true score could be _much_ worse. Why you would want to use this kind of score is a mystery. Ed used to do this in Rebel. We had this discussion years ago. He removed it and found it was significantly faster.

There is no "best" move at a fail-low node. There is no "good" move at a fail-low node. It is just the way alpha/beta works. Alpha/Beta is designed _only_ to find the best move at a root position and prove that all others are worse. It does _not_ prove how much worse they are. Unfortunately.

It simply does not work. Use it if you want, but it is a non-working idea, regardless of what you believe. Once you think about it for a while, you will begin to see why it just doesn't work. You are comparing random lower bounds (actually fail-high bounds from the next level down in the tree) when they are incomparable.

These "bad bounds" occur every other ply, by the time you get one back to ply-2, say, the bound is an approximation at ply 3, 5, 7, 9, ..., 51 or however deep this variation happened to go.

The simple solution is to test with and without over several thousand games to see what happens. You might have some success if you can somehow remember that some move appears to be very bad (particularly if it is a capture that SEE says is good which would order it early in a non-hashmove position, but how do you store that and where? We are talking about the "best move" at any given ply, and finding that at a fail-low node is hopeless, and that is the move we store as the best move. It had better be right or the search efficiency will go in the tank.

[hgm]

And you are saying "let's try a completely random move, rather than the type of move that is best in the big majority of the cases."

You leave out an important part of what I am saying. Because what I am saying is actually:

"let's try a completely random move, rather than the type of move that is best in the big majority of the cases, when we already know that we are dealing with a case where this latter move is very bad."

I am sure you know the story about the statician that drowned in a river that was on average only 3 feet deep.... You contracted Ebola, sir, but don't worry: it is an extremely rare disease. Not more than 0.0001% of the World's population dies of it each year. So you can feel quite safe, despite the mortality rate of 90%.

Statistical knowledge becomes completely irrelevant when one already has specific knowledge.

[jwes]

Well, starting with a random move not proven to be a blunder seems a better proposition then starting with a move that has already proven to be blunder. Even if the latter one would be sorted first statically.

What if you start with a good capture move instead, which is actually the best move most of the time anyway. And you have not proven that the move you store is not a blunder. You might _assume_ that at the next ply you search the best move first, so that the bound returned by fail-soft is accurate, but that is a poor (and incorrect) assumption. The current move gets refuted by a move that is good enough to produce a score > beta. There may well be another move that produces a much larger score.

This kind of test simply does not work. Unless you move away from alpha/beta.

So you are saying that a search at a node that fails low provides zero useful information for move ordering.

He's saying that you don't know for sure what is the best move, and if you don't know for sure, you should be careful about trying a random move instead of the move your normal move ordering would recommend.

I agree with Bob here. (And that doesn't happen a lot)

It just seems that after searching millions of nodes, there should be some clue which move that failed low last time may fail high. If nothing else, you could store the move you would try first with your normal move ordering and possibly save a move generation.

[bob]

And you are saying "let's try a completely random move, rather than the type of move that is best in the big majority of the cases."

You leave out an important part of what I am saying. Because what I am saying is actually:

"let's try a completely random move, rather than the type of move that is best in the big majority of the cases, when we already know that we are dealing with a case where this latter move is very bad."

I am sure you know the story about the statician that drowned in a river that was on average only 3 feet deep.... You contracted Ebola, sir, but don't worry: it is an extremely rare disease. Not more than 0.0001% of the World's population dies of it each year. So you can feel quite safe, despite the mortality rate of 90%.

Statistical knowledge becomes completely irrelevant when one already has specific knowledge.

It is quite one thing to know that a particularly move appears to be very bad, as opposed to knowing which of the remaining moves is the move to try first. That is the problem I don't see a solution for. Which of the remaining moves do you choose to store in the hash table? The one with the best "fail-low bound"? Not very good. The fail low bound is simply the first fail high bound at the next ply that was good enough to terminate the search. Has nothing to do with that move being the best move at that ply, just one that is "good enough" which is all we try to do with killers and the like.

So, you have a clue that the best SEE capture produced a pretty high fail-high bound at the next ply, how do you decide what to store in the hash move? Not by comparing fail-soft bounds, so what is left? It is one thing to know that one move looks bad, but that doesn't help figure out which one will look good.

[Gian-Carlo Pascutto]

If nothing else, you could store the move you would try first with your normal move ordering and possibly save a move generation.

This is a good idea, but only applicable for captures (not for killers and history moves, because those evolve).

Still, good idea!

[jwes]

Well, starting with a random move not proven to be a blunder seems a better proposition then starting with a move that has already proven to be blunder. Even if the latter one would be sorted first statically.

What if you start with a good capture move instead, which is actually the best move most of the time anyway. And you have not proven that the move you store is not a blunder. You might _assume_ that at the next ply you search the best move first, so that the bound returned by fail-soft is accurate, but that is a poor (and incorrect) assumption. The current move gets refuted by a move that is good enough to produce a score > beta. There may well be another move that produces a much larger score.

This kind of test simply does not work. Unless you move away from alpha/beta.

So you are saying that a search at a node that fails low provides zero useful information for move ordering.

Correct...

How is this different from the root where you do use information from fail-lows for move ordering?

[bob]

Well, starting with a random move not proven to be a blunder seems a better proposition then starting with a move that has already proven to be blunder. Even if the latter one would be sorted first statically.

What if you start with a good capture move instead, which is actually the best move most of the time anyway. And you have not proven that the move you store is not a blunder. You might _assume_ that at the next ply you search the best move first, so that the bound returned by fail-soft is accurate, but that is a poor (and incorrect) assumption. The current move gets refuted by a move that is good enough to produce a score > beta. There may well be another move that produces a much larger score.

This kind of test simply does not work. Unless you move away from alpha/beta.

So you are saying that a search at a node that fails low provides zero useful information for move ordering.

Correct...

How is this different from the root where you do use information from fail-lows for move ordering?

I don't. All I do is use the size of the tree being searched for each root move to order those moves, excepting that the PV move from the previous iteration is always tried first regardless of the size of the tree it produces. Where do you think you are seeing fail low information being used???

One other point. Note that the root is not a "fail low" position. We get a best move. That is far different from a ply where _every_ move fails low. The size of the sub-trees at those plies don't vary by the same margin as moves at the root or at a non-fail-low position.

[xsadar]

It just seems that after searching millions of nodes, there should be some clue which move that failed low last time may fail high. If nothing else, you could store the move you would try first with your normal move ordering and possibly save a move generation.

I don't know about others, but this wouldn't save me any move generation time whatsoever. I have to generate the move before I can tell that the move I generated is the same as the hash move.
However, if there was already a hash move for this position from a previous search, I think it would be useful to store it back in the TT along with the data from the new search. At least that way you're not losing information you already had.

[bob]

It just seems that after searching millions of nodes, there should be some clue which move that failed low last time may fail high. If nothing else, you could store the move you would try first with your normal move ordering and possibly save a move generation.

I don't know about others, but this wouldn't save me any move generation time whatsoever. I have to generate the move before I can tell that the move I generated is the same as the hash move.
However, if there was already a hash move for this position from a previous search, I think it would be useful to store it back in the TT along with the data from the new search. At least that way you're not losing information you already had.

I do exactly the opposite. In crafty:

1. If there is a hash move, I do a quick legality check (right piece on from/to squares, etc) and then make this move and search before I generate anything.

2. I then generate just captures and try those, but only the ones with a SEE evaluation >= 0.

3. I then try either or both of the two killer moves, again doing simple legality checking on both, before generating the rest of the moves.

1/3 above save a significant number of move generator calls and is worthwhile.

[xsadar]

It just seems that after searching millions of nodes, there should be some clue which move that failed low last time may fail high. If nothing else, you could store the move you would try first with your normal move ordering and possibly save a move generation.

I don't know about others, but this wouldn't save me any move generation time whatsoever. I have to generate the move before I can tell that the move I generated is the same as the hash move.
However, if there was already a hash move for this position from a previous search, I think it would be useful to store it back in the TT along with the data from the new search. At least that way you're not losing information you already had.

I do exactly the opposite. In crafty:

1. If there is a hash move, I do a quick legality check (right piece on from/to squares, etc) and then make this move and search before I generate anything.

2. I then generate just captures and try those, but only the ones with a SEE evaluation >= 0.

3. I then try either or both of the two killer moves, again doing simple legality checking on both, before generating the rest of the moves.

1/3 above save a significant number of move generator calls and is worthwhile.

Ah, you are right. I take roughly the same approach.. First heard the idea from you as a matter of fact.
For some reason I was thinking he was referring to not having to generate that one individual move when you generate the rest of the moves. I seem to be really bad at understanding people and thinking things through the last couple days. Must not be getting enough sleep.