Suggestion for hash tables and analysis.

[bob]

If your confused by something I wrote, or I failed to explain some aspect with sufficient clarity for you to understand it, you can ask, I'll clarify my statements, and then you'll no longer have reason to be at a loss.

Do I really need to repeat your statement?

The only way a position from an earlier part of the search can match a position in the later part of the search, is if no pawn moves or captures have been made.

That is only true if "earlier part" is "branch from root to current node".

A more sensible definition of "earlier part" for the purpose of TT is "the part of the tree searched before the current node". That part may contain lots of occurrences of the current position even through pawn moves/unmoves and captures/uncaptures.

I figure if someone from the Stockfish development team thinks this is worth trying they have sufficient resources to do it without my assistance.

Sure, they are always looking for vague ideas by people not willing or able to implement them and that nobody else is convinced by.

I almost believe he is thinking about repetitions here, not transpositions. I can capture a pawn at ply 2, then in another path play something else at ply 2 and capture the pawn at ply 4 and still transpose to the same position.

If this were about repetitions and reversible moves, his comment makes sense. But not in the context of transpositions. One can transpose the order of several different captures and reach the same final position.

[Zenmastur]

Well, those statements were a response to the bold part of these statements:

Using two TTs seems to always have a harmful effect.

(1) if you probe both, you will actually have more overhead when the first (small) fails.

(2) if you ONLY probe the local table, you miss a LOT of possible transpositions and that causes the tree to expand...

…

That is what most refer to as a "thread local TT approach". It really doesn't work. If you only probe the small TT, you get very few hits, as it contains no entries from the early part of the search.

and this...

... (Well... if you are going to have two TTs that both have to be accessed, ...)

The point I'm was making with those comments IS THIS:

I see no need to probe the L2 TT when conducting the last n-plies of the search. (e.g. when conducting a 45-ply search, when I probe the L1 TT at ply 42, 43, 44, or 45 and don't get a hit, then “IF” I probe the L2 TT and get a hit that occurred at a depth of say 40-plies or 38-plies, or an even shallower depth, this is either a repeated position or a hash collision.) So, why should I bother making the second probe into the L2 TT when I know that no entry contains data from depths greater than 41 have been written to it.

These comments have NOTHING TO DO with finding transpositions, they are an explanation of why I don't feel a need to probe both TT's.

Regards,

Zen

[bob]

Well, those statements were a response to the bold part of these statements:

Using two TTs seems to always have a harmful effect.

(1) if you probe both, you will actually have more overhead when the first (small) fails.

(2) if you ONLY probe the local table, you miss a LOT of possible transpositions and that causes the tree to expand...

…

That is what most refer to as a "thread local TT approach". It really doesn't work. If you only probe the small TT, you get very few hits, as it contains no entries from the early part of the search.

and this...

... (Well... if you are going to have two TTs that both have to be accessed, ...)

The point I'm was making with those comments IS THIS:

I see no need to probe the L2 TT when conducting the last n-plies of the search. (e.g. when conducting a 45-ply search, when I probe the L1 TT at ply 42, 43, 44, or 45 and don't get a hit, then “IF” I probe the L2 TT and get a hit that occurred at a depth of say 40-plies or 38-plies, or an even shallower depth, this is either a repeated position or a hash collision.) So, why should I bother making the second probe into the L2 TT when I know that no entry contains data from depths greater than 41 have been written to it.

These comments have NOTHING TO DO with finding transpositions, they are an explanation of why I don't feel a need to probe both TT's.

Regards,

Zen

I do not follow your reasoning regarding either collision or repetition.

Path 1: I start with a capture, then play 10 other moves. Let's call these moves A through J.

Path 2. I start with move B then go through J, and then finally play move A. That is a classic transpositions. Doesn't matter whether we have just one capture (move A) or several. All that matters is that we change the order of the moves but reach the same position.

Again, you seem to be confusing repetition with transposition. They are completely unrelated. No, you can't repeat a position after a capture with a position before the capture. But you can get thousands of transpositions across one or more captures.

If you don't probe the big TT in the q-search, you will miss ALL of those kinds of transpositions. You can test this on fine 70 where the pawn capture gets done at different plies once you see deeply enough.

[Zenmastur]

I do not follow your reasoning regarding either collision or repetition.

Yes, I can see that. We're having a serious communication problem. I'm tired of trying to explain my self. So lets cut to the chase!

Path 1: I start with a capture, then play 10 other moves. Let's call these moves A through J.

Path 2. I start with move B then go through J, and then finally play move A. That is a classic transpositions. Doesn't matter whether we have just one capture (move A) or several. All that matters is that we change the order of the moves but reach the same position.

That's a nice fantasy story you have going on there. You have what amounts to an infinite size TT, and there is no search that can interfere with you finding the transposition by overwriting your TT entries. There is no engine telling you, “oops, sorry but your transposition didn't make it into the TT because the moves are so flawed that LMR, Null move, or futility pruned them away.” Your A, B, C, moves aren't any more real than the transposition they're meant to be a part of.

So let's get real.

Here is a real position:

[d]1q2r1k1/1b1nr1bp/pp1np1p1/3p1pN1/PPpN1PP1/2PPB1QP/4PRB1/2R3K1 b - - 0 26

You make it out like finding 10-ply transpositions is a piece of cake. Let's forget the fact that the ones we've been talking about up till now have been buried at the bottom of a deep search. You have claimed 10-ply transpositions are SO EASY to find, so you should have no problem finding tons of them. You can use as large a TT as you like. There are only two restrictions. 1.) The transposition has to start and end with at least half the material still on the board. (i.e. you can't reduce the material to an endgame position to make them easier to find.) 2.) At least 2 variations that lead to the transposed position have to be playable. (i.e. no blunders that drop material just for the sake of completing the transposition.) This task is at least 7 orders of magnitude less hard than if it were at the bottom of a long search.

The real test:

You get 16 gigabytes of TT space not one byte more. You have to conduct a “real” search with a real engine that will write real entries all over you carefully prepared but flawed transposition. It will have all of it's normal pruning methods turned on so it can put the ax to all those theoretical transpositions you seem to think will make it into the TT . Your job is to report how many 10-ply transposition are found by a normal TT with the first move of the transposition being at a MINIMUM depth of 33-plies into the search. The line of play leading to the first ply of the transpositions CAN NOT contain blunders that drop material.

I have no doubt that your going to find out that all those fantasy transpositions either don't make into the TT to start with and the few that actually pass muster will be quickly overwritten.

The point I'm making is that you are comparing a “fantasy” TT to a real one. When you compare a “real” TT that is highly over-subscribed to a “real” one that isn't the shoe will be on the other foot.

Feel free to prove me wrong.

We could argue this point, or the point about split TT's in general, to death. But I see little point in it. It's complicated enough that arguments alone are insufficient to be convincing.

Regards,

Zen

[hgm]

2.) At least 2 variations that lead to the transposed position have to be playable. (i.e. no blunders that drop material just for the sake of completing the transposition.)

That doesn't sound very much like what is going on in an engine. Most of the tree actually looks like a game between a random mover and a turn passer. The random mover will jump aimlessly around with its pieces, blundering them away all the time, but getting away with it because the opponent is happy already without the piece, and just keeps it as a hostage. Occasionally the random mover will move a piece it already moved before, and often there then are multiple paths to the location it ends up on. And when it moves different pieces, it could usually have moved those in any order, as the opponent is just sitting and waiting. Only arrival of certain pieces on certain squares would trigger a response, usually that the piece will be captured there, always in the same way.

And yes, that would lead to lots of transpositions. Of course 10-move transpositions could be stretching it a bit, as engine can just barely search 10 ply deep...

[Zenmastur]

...Of course 10-move transpositions could be stretching it a bit, as engine can just barely search 10 ply deep...

Precisely!

They're not nearly as easy to find as Bob's hypothetical example would leave you to believe.

As far as random number generators go, engines are not as random as you think. The EBF of a strong engine is less than two which is much smaller than the average number of moves in the "average" position. That's why we should let a "real" engine be the arbiter of what gets let into the TT.

Regards,

Zen

[hgm]

Well, that only shows how much engines are lying about their depth. The average number of moves they do consider in a typical all-node is of course far, far greater than 2. It would be more like 35. They get the low EBF only by not expanding most leave nodes in going from one iteration to the next. And even if they would hard-prune moves in internal nodes, they would tend to prune the same moves in nodes at any level. So all levels would still search the same set of moves, which could be nicely transposed.

I don't really see your point. What difference does it make if the average branch length is 8 or 10? Bob just mentioned 10 as an arbitrary number, his message is that transpositions do occur with moves at the root just as easily as with moves near the leaves, and how large the distance between those is, is pretty immaterial. If your argument lives by virtue of the fact that current engines cannot reach 10 ply, just let them think that much longer that they do, and the argument evaporates entirely...

[bob]

I do not follow your reasoning regarding either collision or repetition.

Yes, I can see that. We're having a serious communication problem. I'm tired of trying to explain my self. So lets cut to the chase!

Path 1: I start with a capture, then play 10 other moves. Let's call these moves A through J.

Path 2. I start with move B then go through J, and then finally play move A. That is a classic transpositions. Doesn't matter whether we have just one capture (move A) or several. All that matters is that we change the order of the moves but reach the same position.

That's a nice fantasy story you have going on there. You have what amounts to an infinite size TT, and there is no search that can interfere with you finding the transposition by overwriting your TT entries. There is no engine telling you, “oops, sorry but your transposition didn't make it into the TT because the moves are so flawed that LMR, Null move, or futility pruned them away.” Your A, B, C, moves aren't any more real than the transposition they're meant to be a part of.

So let's get real.

Here is a real position:

[d]1q2r1k1/1b1nr1bp/pp1np1p1/3p1pN1/PPpN1PP1/2PPB1QP/4PRB1/2R3K1 b - - 0 26

You make it out like finding 10-ply transpositions is a piece of cake. Let's forget the fact that the ones we've been talking about up till now have been buried at the bottom of a deep search. You have claimed 10-ply transpositions are SO EASY to find, so you should have no problem finding tons of them. You can use as large a TT as you like. There are only two restrictions. 1.) The transposition has to start and end with at least half the material still on the board. (i.e. you can't reduce the material to an endgame position to make them easier to find.) 2.) At least 2 variations that lead to the transposed position have to be playable. (i.e. no blunders that drop material just for the sake of completing the transposition.) This task is at least 7 orders of magnitude less hard than if it were at the bottom of a long search.

The real test:

You get 16 gigabytes of TT space not one byte more. You have to conduct a “real” search with a real engine that will write real entries all over you carefully prepared but flawed transposition. It will have all of it's normal pruning methods turned on so it can put the ax to all those theoretical transpositions you seem to think will make it into the TT . Your job is to report how many 10-ply transposition are found by a normal TT with the first move of the transposition being at a MINIMUM depth of 33-plies into the search. The line of play leading to the first ply of the transpositions CAN NOT contain blunders that drop material.

I have no doubt that your going to find out that all those fantasy transpositions either don't make into the TT to start with and the few that actually pass muster will be quickly overwritten.

The point I'm making is that you are comparing a “fantasy” TT to a real one. When you compare a “real” TT that is highly over-subscribed to a “real” one that isn't the shoe will be on the other foot.

Feel free to prove me wrong.

We could argue this point, or the point about split TT's in general, to death. But I see little point in it. It's complicated enough that arguments alone are insufficient to be convincing.

Regards,

Zen

I very carefully hang on to tt entries with deep drafts. And I very carefully allow those to be probed near the tips. This is common enough that it is what lets a program solve fine #70 WAY before the exhaustive search can force the loss of a black pawn with best play by both sides.

So they DO happen. With your case they will NEVER happen. In the last few plies you will NEVER recognize a position that occurred earlier in the tree. Seems wrong to me...

[bob]

...Of course 10-move transpositions could be stretching it a bit, as engine can just barely search 10 ply deep...

Precisely!

They're not nearly as easy to find as Bob's hypothetical example would leave you to believe.

As far as random number generators go, engines are not as random as you think. The EBF of a strong engine is less than two which is much smaller than the average number of moves in the "average" position. That's why we should let a "real" engine be the arbiter of what gets let into the TT.

Regards,

Zen

Again, they are easy enough to find. Just run fine #70 with the normal hash approach and with your approach. I suspect you will be surprised.

As far as your "prove me wrong" that's not going to work. YOU prove that your idea is better and folks will look at it. The idea of such a split tt is inherently wrong IMHO. One for near the tips and one for the rest misses out on too many transpositions.

[Zenmastur]

I very carefully hang on to tt entries with deep drafts. And I very carefully allow those to be probed near the tips. This is common enough that it is what lets a program solve fine #70 WAY before the exhaustive search can force the loss of a black pawn with best play by both sides.

So they DO happen. With your case they will NEVER happen. In the last few plies you will NEVER recognize a position that occurred earlier in the tree. Seems wrong to me...

Again, they are easy enough to find. Just run fine #70 with the normal hash approach and with your approach. I suspect you will be surprised.

As far as your "prove me wrong" that's not going to work. YOU prove that your idea is better and folks will look at it. The idea of such a split tt is inherently wrong IMHO. One for near the tips and one for the rest misses out on too many transpositions.

I have no doubt that 10-ply transpositions exist. I also have no doubt that you won't be finding many of them deep in a search with a highly over-subscribed TT.

I have run fine #70 with a very small TT.

Code: Select all

2016-06-15 17&#58;35&#58;00.701<--1&#58;info depth 11 seldepth 13 multipv 1 score cp 55 nodes 9132 nps 3044000 tbhits 0 time 3 pv a1b1 a7b7 b1c2 b7b6 c2d2 b6c7 d2e2 c7d8 e2d3 d8c7 d3c3 c7b7 c3b37 c3d3 c7b6 d3e3 b6c7 e3f3 c7d7 f3g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6.......

If finds the correct move in 3 milliseconds and stays with it. Notice the node count is 9,132.

If all of chess was as simple as Fine#70 the OP wouldn't be complaining, chess would be solved, and no chess engine would need more than a 1mb TT.

Regards,

Zen