TT management ?

[Chessnut1071]

TT is a very indirect lookup from a hash to a position.
I wish people started to research more into storing the tree in memory all the time.

Sounds wasteful at first glance - but pruning and walking the positions becomes much faster - and nothing is forgotten ever, making cooperation possible where alphabeta is limited.
It is only usable starting from 32gb of ram - and with the use of memory mapped IO and pcie 4.0 SSDs there is no reason to not go to 512GB or beyond.

Once you can do IO with a few GB/s you can grow and read a tree without performance loss.

I'm not sure how successful that would be. Alpha beta relies a lot on previous lines that have been examined. With conditions different at every node, Move ordering, alpha beta bounds, reductions, etc. etc. all depend on the result of previous searches, so storing the tree might not actually help you because you might have to rewrite it again anyways due to different bounds. If you can make it work though I would be excited to see what you come up with.

You mentioned "always replace" as a more efficient TT option. Let's say I have a key with opposite scores, success and failure [checkmate & no checkmate]. How can you ever use that key again, there's no way to guarantee a unique outcome. When I tried that about 1/6 of solutions failed. Am I missing something?

[AAce3]

TT is a very indirect lookup from a hash to a position.
I wish people started to research more into storing the tree in memory all the time.

Sounds wasteful at first glance - but pruning and walking the positions becomes much faster - and nothing is forgotten ever, making cooperation possible where alphabeta is limited.
It is only usable starting from 32gb of ram - and with the use of memory mapped IO and pcie 4.0 SSDs there is no reason to not go to 512GB or beyond.

Once you can do IO with a few GB/s you can grow and read a tree without performance loss.

I'm not sure how successful that would be. Alpha beta relies a lot on previous lines that have been examined. With conditions different at every node, Move ordering, alpha beta bounds, reductions, etc. etc. all depend on the result of previous searches, so storing the tree might not actually help you because you might have to rewrite it again anyways due to different bounds. If you can make it work though I would be excited to see what you come up with.

You mentioned "always replace" as a more efficient TT option. Let's say I have a key with opposite scores, success and failure [checkmate & no checkmate]. How can you ever use that key again, there's no way to guarantee a unique outcome. When I tried that about 1/6 of solutions failed. Am I missing something?

It looks like you're running into hash collisions. Do you store the key in the entry and check for equality when probing? If they are not equal you cannot use it, which is the reason for replacement strategies in the first place. You have to do the search again. Otherwise hash collisions should be extremely rare.

[Chessnut1071]

TT is a very indirect lookup from a hash to a position.
I wish people started to research more into storing the tree in memory all the time.

Sounds wasteful at first glance - but pruning and walking the positions becomes much faster - and nothing is forgotten ever, making cooperation possible where alphabeta is limited.
It is only usable starting from 32gb of ram - and with the use of memory mapped IO and pcie 4.0 SSDs there is no reason to not go to 512GB or beyond.

Once you can do IO with a few GB/s you can grow and read a tree without performance loss.

I'm not sure how successful that would be. Alpha beta relies a lot on previous lines that have been examined. With conditions different at every node, Move ordering, alpha beta bounds, reductions, etc. etc. all depend on the result of previous searches, so storing the tree might not actually help you because you might have to rewrite it again anyways due to different bounds. If you can make it work though I would be excited to see what you come up with.

You mentioned "always replace" as a more efficient TT option. Let's say I have a key with opposite scores, success and failure [checkmate & no checkmate]. How can you ever use that key again, there's no way to guarantee a unique outcome. When I tried that about 1/6 of solutions failed. Am I missing something?

It looks like you're running into hash collisions. Do you store the key in the entry and check for equality when probing? If they are not equal you cannot use it, which is the reason for replacement strategies in the first place. You have to do the search again. Otherwise hash collisions should be extremely rare.

When I'm working on 20-ply and above I can have thousands of collisions and trillions of nodes to cope with. I have a hash key which points to the hash code [ulong int.], ply, success or failure, and disabled/enabled. If the collision has opposite results I eliminate the key. If it has the same result it doesn't need to be eliminated.

[JVMerlino]

FYI
My delete conflicting keys, keys with both success and failure codes, apparently worked! My best solution time deleting an overflowed bucked was 48,363 seconds. The delete conflicting keys clocked 1,285 seconds to solution. I'm searching for your recommendation "linear rehash" for some improvement. I never got to 22-ply before with a solution under 8 hours.

I still need millions of nodes to solve the 18-ply mate that Myriddin solved in 7 seconds examining only 75,000 + nodes. Not sure how he did that unless he's using a multiprocessor which I don't have right now.

Are you talking about this position?
[d] 1n3r2/3k2pp/pp1P4/1p4b1/1q3B2/5Q2/PPP2PP1/R4RK1 w - - 0 1

If so, that's only a 13-ply mate. And it is easily solved with a check extension, since every move in the solution checks (or checkmates) the enemy king. I think most engines in Myrddin's elo range (~2600) would find the solution just as quickly. The King (CM9000) is, for some reason, ludicrously fast at these kinds of positions, and in this case it announces mate after searching only 2,182 nodes.

Another example is this position, which is also a mate in 7 and each move checks or checkmates the enemy king. The King announces mate in 1,849 nodes, and Myrddin needs only 5,271 nodes. This one is particularly easy because in each case the enemy king only has one legal move.
[d] 7k/3b3p/1p6/3p1P1P/2p3r1/2P1R3/7r/2RK4 b - - 0 1

But if you're talking about completely a different position, please refresh my memory.

jm

[Chessnut1071]

FYI
My delete conflicting keys, keys with both success and failure codes, apparently worked! My best solution time deleting an overflowed bucked was 48,363 seconds. The delete conflicting keys clocked 1,285 seconds to solution. I'm searching for your recommendation "linear rehash" for some improvement. I never got to 22-ply before with a solution under 8 hours.

I still need millions of nodes to solve the 18-ply mate that Myriddin solved in 7 seconds examining only 75,000 + nodes. Not sure how he did that unless he's using a multiprocessor which I don't have right now.

Are you talking about this position?
[d] 1n3r2/3k2pp/pp1P4/1p4b1/1q3B2/5Q2/PPP2PP1/R4RK1 w - - 0 1

If so, that's only a 13-ply mate. And it is easily solved with a check extension, since every move in the solution checks (or checkmates) the enemy king. I think most engines in Myrddin's elo range (~2600) would find the solution just as quickly. The King (CM9000) is, for some reason, ludicrously fast at these kinds of positions, and in this case it announces mate after searching only 2,182 nodes.

Another example is this position, which is also a mate in 7 and each move checks or checkmates the enemy king. The King announces mate in 1,849 nodes, and Myrddin needs only 5,271 nodes. This one is particularly easy because in each case the enemy king only has one legal move.
[d] 7k/3b3p/1p6/3p1P1P/2p3r1/2P1R3/7r/2RK4 b - - 0 1

But if you're talking about completely a different position, please refresh my memory.

jm

this one: FEN[2109] = "5r2/pb3p1k/1pn3p1/2p1PP2/8/b2RQ3/qP4PP/5R1K w - - 0 1"; // Talk Chess Sept., 2023 unknown author

the one I was having trouble with is a 22-ply

[hgm]

I still need millions of nodes to solve the 18-ply mate that Myriddin solved in 7 seconds examining only 75,000 + nodes. Not sure how he did that unless he's using a multiprocessor which I don't have right now.

I really appreciate all the suggestions, I'm a light year ahead of where I started over a year ago; however, everyone here else seems to be a light year ahead of me.

I think one of the reasons for this vast performance difference is the use of extensions and reductions. If all moves in the solution of this mate in 17 ply are checks, an engine that uses check extension (which Myrddin no doubt does) would find it at 9 ply. And you need an enormously smaller number of nodes to do a 9-ply search with check extension compared to an 17-ply search without one.

It would perhaps be possible to get more specific advice if you would actually post the positions you are talking about...

[Chessnut1071]

I still need millions of nodes to solve the 18-ply mate that Myriddin solved in 7 seconds examining only 75,000 + nodes. Not sure how he did that unless he's using a multiprocessor which I don't have right now.

I really appreciate all the suggestions, I'm a light year ahead of where I started over a year ago; however, everyone here else seems to be a light year ahead of me.

I think one of the reasons for this vast performance difference is the use of extensions and reductions. If all moves in the solution of this mate in 17 ply are checks, an engine that uses check extension (which Myrddin no doubt does) would find it at 9 ply. And you need an enormously smaller number of nodes to do a 9-ply search with check extension compared to an 17-ply search without one.

It would perhaps be possible to get more specific advice if you would actually post the positions you are talking about...

from the prior post

FEN[2109] = "5r2/pb3p1k/1pn3p1/2p1PP2/8/b2RQ3/qP4PP/5R1K w - - 0 1"; // Talk Chess Sept., 2023 unknown author - 9 move checkmate

[Chessnut1071]

I still need millions of nodes to solve the 18-ply mate that Myriddin solved in 7 seconds examining only 75,000 + nodes. Not sure how he did that unless he's using a multiprocessor which I don't have right now.

I really appreciate all the suggestions, I'm a light year ahead of where I started over a year ago; however, everyone here else seems to be a light year ahead of me.

I think one of the reasons for this vast performance difference is the use of extensions and reductions. If all moves in the solution of this mate in 17 ply are checks, an engine that uses check extension (which Myrddin no doubt does) would find it at 9 ply. And you need an enormously smaller number of nodes to do a 9-ply search with check extension compared to an 17-ply search without one.

It would perhaps be possible to get more specific advice if you would actually post the positions you are talking about...

Actually, I can actually beat Myrddin's time and node count: - .0021 seconds ; 49,322 nodes to solution
The function is only looks at check moves for white. The reason why I think Myrddin is so fast is it uses a check pruning function in a parallel search. Check extension will also work. However, I need a generic function and pruning and special cases would be nice on a parallel processor, not my main thread.

[JVMerlino]

I still need millions of nodes to solve the 18-ply mate that Myriddin solved in 7 seconds examining only 75,000 + nodes. Not sure how he did that unless he's using a multiprocessor which I don't have right now.

I really appreciate all the suggestions, I'm a light year ahead of where I started over a year ago; however, everyone here else seems to be a light year ahead of me.

I think one of the reasons for this vast performance difference is the use of extensions and reductions. If all moves in the solution of this mate in 17 ply are checks, an engine that uses check extension (which Myrddin no doubt does) would find it at 9 ply. And you need an enormously smaller number of nodes to do a 9-ply search with check extension compared to an 17-ply search without one.

It would perhaps be possible to get more specific advice if you would actually post the positions you are talking about...

Actually, I can actually beat Myrddin's time and node count: - .0021 seconds ; 49,322 nodes to solution
The function is only looks at check moves for white. The reason why I think Myrddin is so fast is it uses a check pruning function in a parallel search. Check extension will also work. However, I need a generic function and pruning and special cases would be nice on a parallel processor, not my main thread.

Ok, I think you might be getting positions and test results confused. For the position you posted (which I know very well), Myrddin (one core) needs 11 seconds to find Qh3, but doesn't announce Mate in 9 until 36.9 seconds, needing just under 90M nodes for that result.

For the Mate-in-7 position that I posted, where each move by Black is a check and each move by White is forced (meaning, only one legal reply), Myrddin (with only one core) does not need any special code (other than a check extension and a single reply extension - both very easy to implement) to announce Mate in 7 essentially instantly at depth 4. If I disable those extensions, then Myrddin needs to get to depth 14 to announce the mate, but it is still very fast and only requires about 112K nodes.

This is the position I'm referring to.
[d]7k/3b3p/1p6/3p1P1P/2p3r1/2P1R3/7r/2RK4 b - - 0 1

[hgm]

I still need millions of nodes to solve the 18-ply mate that Myriddin solved in 7 seconds examining only 75,000 + nodes. Not sure how he did that unless he's using a multiprocessor which I don't have right now.

I really appreciate all the suggestions, I'm a light year ahead of where I started over a year ago; however, everyone here else seems to be a light year ahead of me.

I think one of the reasons for this vast performance difference is the use of extensions and reductions. If all moves in the solution of this mate in 17 ply are checks, an engine that uses check extension (which Myrddin no doubt does) would find it at 9 ply. And you need an enormously smaller number of nodes to do a 9-ply search with check extension compared to an 17-ply search without one.

It would perhaps be possible to get more specific advice if you would actually post the positions you are talking about...

Actually, I can actually beat Myrddin's time and node count: - .0021 seconds ; 49,322 nodes to solution
The function is only looks at check moves for white. The reason why I think Myrddin is so fast is it uses a check pruning function in a parallel search. Check extension will also work. However, I need a generic function and pruning and special cases would be nice on a parallel processor, not my main thread.

Indeed. Shogi mating problems are usually in this form ('tsume'), and my engine HaChu can be switched to such a mode.

For Chess problems this is no requirement, though, and often considered bad form. So in Tsume mode you probably could not solve most problems. While Myrddin no doubt solves them all.