Semi-Path Dependent Hashing: a semi-useless idea.

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Semi-Path Dependent Hashing: a semi-useless idea.

Post by Zach Wegner » Sat May 24, 2008 9:49 pm

Well, the topic of repetitions and their effects just came up in a thread with Bob, so I figured I'd write a little bit about my "proprietary" method, seeing as how anyone can already see it in my source code.

The idea is called semi-path dependent hashing or SPDH. The idea is to remove the bad effects of hashing when it comes to path dependent aspects of the search, such as repetitions and the 50 move rule, but still keep (most of) the benefits of the hash table.

What you do is to keep two hashkeys of the position at hand: The normal hashkey, based only on the position, and a path hashkey. The path hashkey can store any level of information you want, which is partly where the "semi" comes from. In my current implementation, I hash in the last 4 moves made. But theoretically you could hash every move in the whole game, as well as the fifty move counter, or maybe just the last move made. There is a whole continuum of possibilties, and my testing has only touched the surface.

So once you have these hashkeys, you must change the way you use the hashtable in order for them _both_ to be useful. You still store and probe based on the normal hashkey. Inside the hash entries, you keep part of the normal hashkey, and part of the path hashkey. If the normal hashkey matches the current position, you have a valid move that you can use for move ordering. Then, if the path hashkey matches as well, the score is safe to use, even for lines with repetitions and such.

It's pretty simple. I've never even heard of anyone using path information in their hashkey, so it's quite novel. The problem is, is that in my testing, with the parameters used, it slightly reduces strength. It is surprising to me though, that it doesn't dramatically reduce the search efficiency, even in the endgame. So with enough tuning, maybe the idea will be useful to someone.

I bring it up also because it elegantly solves the problem that Bob brought up. When the fifty move counter gets close to fifty, he runs through the hash table and invalidates old entries. Here's a better way to do this:

Code: Select all

if &#40;fifty_count < 80&#41; /* I.e. less than 40 reversible moves */
    path_hashkey = hashkey; /* No change, we can just accept cutoffs regardless of path */
else
    path_hashkey = hashkey ^ some_constant; /* If we are getting close to 50, then only accept cutoffs from newer searches, BUT, still use the hash move */
You can take this even further, and make the last line:

Code: Select all

path_hashkey = hashkey ^ some_constant&#91;fifty_count - 80&#93;;
So that when the fifty move count is big, we only accept searches with the exact same fifty count.

Does that sound interesting to anyone? I was pretty disappointed that it didn't at least help...

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by Pradu » Sat May 24, 2008 11:23 pm

Can you run both versions (typical hashing and your method) on this position:
[D]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - -

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by Zach Wegner » Sun May 25, 2008 12:03 am

Ha, what a position. Not really a fair test, because for some reason my engine has never solved it. I know that it must be because of some bug, but nevertheless, I will post it:

Normal hashing:

Code: Select all

Depth          Time     Score   PV &#40;nodes&#41;
 13/13        0.009     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kb7 4. Kd3 Kb6 5. Kc4 Kc7 6. Kb5 Kd8 7. Kxa5 Kc8H 8. Ka6H Kd8H 9. Ka7H &#40;11216&#41;
&#91;13/13&#93;       0.009     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kb7 4. Kd3 Kb6 5. Kc4 Kc7 6. Kb5 Kd8 7. Kxa5 Kc8H 8. Ka6H Kd8H 9. Ka7H &#40;11997&#41;
 14/14        0.010     +0.95   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kb7 4. Kd3 Kb6 5. Kd2 Ka7 6. Kc1 Kb8 7. Kb2 Kc7 8. Kc2H &#40;14241&#41;
&#91;14/14&#93;       0.010     +0.95   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kb7 4. Kd3 Kb6 5. Kd2 Ka7 6. Kc1 Kb8 7. Kb2 Kc7 8. Kc2H &#40;14279&#41;
 15/15        0.015     +0.97   1. Kb2 Kb8 2. Kc3 Kc7 3. Kd3 Kd8 4. Kc4 Kc8 5. Kb5 Kd8 6. Kxa5 Kc7 7. Kb5 Kd8 8. Ka6 &#40;22738&#41;
&#91;15/15&#93;       0.015     +0.97   1. Kb2 Kb8 2. Kc3 Kc7 3. Kd3 Kd8 4. Kc4 Kc8 5. Kb5 Kd8 6. Kxa5 Kc7 7. Kb5 Kd8 8. Ka6 &#40;22782&#41;
 16/19        0.019     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kd3 Kb7 4. Kc4 Kb6 5. Kb3 Ka7 6. Kc2 Kb8 7. Kd1 Kc8 8. Kc1 Kd8 9. Kd1H Kc8H &#40;30431&#41;
&#91;16/19&#93;       0.019     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kd3 Kb7 4. Kc4 Kb6 5. Kb3 Ka7 6. Kc2 Kb8 7. Kd1 Kc8 8. Kc1 Kd8 9. Kd1H Kc8H &#40;30965&#41;
 17/19        0.023     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kd3 Kb7 4. Kc2 Kc7 5. Kc3 Kb7 6. Kd3 Kb6 7. Kc4 Kc7 8. Kb5 Kd8 9. Kxa5 Kc8H 10. Ka6H Kb8H 11. a5H Kc7H 12. Kb5H Kb7H 13. Kc4H Ka6H &#40;38534&#41;
&#91;17/19&#93;       0.023     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kd3 Kb7 4. Kc2 Kc7 5. Kc3 Kb7 6. Kd3 Kb6 7. Kc4 Kc7 8. Kb5 Kd8 9. Kxa5 Kc8H 10. Ka6H Kb8H 11. a5H Kc7H 12. Kb5H Kb7H 13. Kc4H Ka6H &#40;38754&#41;
 18/19        0.027     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kd8 8. Kc4 Kc8 9. Kb5 Kd8 10. Kxa5 Kc8H 11. Ka6H Kb8H 12. a5H Kc7H 13. Kb5H Kb7H 14. Kc4H Ka6H &#40;48813&#41;
&#91;18/19&#93;       0.027     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kd8 8. Kc4 Kc8 9. Kb5 Kd8 10. Kxa5 Kc8H 11. Ka6H Kb8H 12. a5H Kc7H 13. Kb5H Kb7H 14. Kc4H Ka6H &#40;48907&#41;
 19/19        0.030     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc7 9. Kd3 Kb7 10. Kc3 &#40;55739&#41;
&#91;19/19&#93;       0.030     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc7 9. Kd3 Kb7 10. Kc3 &#40;56145&#41;
 20/21        0.039     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd3 Kb6 9. Kc4 Kc7 10. Kb5 Kd8 11. Kxa5 Kc8H 12. Ka6H Kb8H 13. a5H Kc7H 14. Kb5H Kb7H 15. Kc4H Ka6H &#40;78506&#41;
&#91;20/21&#93;       0.040     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd3 Kb6 9. Kc4 Kc7 10. Kb5 Kd8 11. Kxa5 Kc8H 12. Ka6H Kb8H 13. a5H Kc7H 14. Kb5H Kb7H 15. Kc4H Ka6H &#40;78598&#41;
 21/21        0.042     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd3 Kb6 9. Kc4 Kc7 10. Kb5 Kd8 11. Kxa5 Kc8H 12. Ka6H Kb8H 13. a5H Kc7H 14. Kb5H Kb7H 15. Kc4H Ka6H &#40;83661&#41;
&#91;21/21&#93;       0.043     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd3 Kb6 9. Kc4 Kc7 10. Kb5 Kd8 11. Kxa5 Kc8H 12. Ka6H Kb8H 13. a5H Kc7H 14. Kb5H Kb7H 15. Kc4H Ka6H &#40;83994&#41;
 22/23        0.058     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc8 7. Kc2 Kd8 8. Kd3 Ke7 9. Kc3 Kd8 10. Kc4 Kd7 11. Kb5 Kd8 12. Kxa5 Kc8H 13. Ka6H Kb8H 14. a5H Kc7H 15. Kb5H Kb7H 16. Kc4H Ka6H &#40;93952&#41;
&#91;22/23&#93;       0.058     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc8 7. Kc2 Kd8 8. Kd3 Ke7 9. Kc3 Kd8 10. Kc4 Kd7 11. Kb5 Kd8 12. Kxa5 Kc8H 13. Ka6H Kb8H 14. a5H Kc7H 15. Kb5H Kb7H 16. Kc4H Ka6H &#40;94325&#41;
 23/27        0.095     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kc8 9. Kc1 Kd8 10. Kc2 Kc7 11. Kb3 Kb7 12. Kc3 Kb6H 13. Kb3H &#40;176021&#41;
&#91;23/27&#93;       0.095     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kc8 9. Kc1 Kd8 10. Kc2 Kc7 11. Kb3 Kb7 12. Kc3 Kb6H 13. Kb3H &#40;177258&#41;
 24/27        0.101     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb1 Kc7 7. Kc1 Kd8 8. Kd1 Ke8 9. Kc2 Kf7 10. Kd3 Kg7 11. Kc4 Kg6 12. Kb5 Kf7 13. Kxa5H &#40;191186&#41;
&#91;24/27&#93;       0.101     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb1 Kc7 7. Kc1 Kd8 8. Kd1 Ke8 9. Kc2 Kf7 10. Kd3 Kg7 11. Kc4 Kg6 12. Kb5 Kf7 13. Kxa5H &#40;191526&#41;
 25/27        0.112     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kc8 9. Kc2 Kd8 10. Kd3 Ke7 11. Kd2 Kf7 12. Kc2 Kf6 13. Kd3 Ke7H &#40;219745&#41;
&#91;25/27&#93;       0.113     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kc8 9. Kc2 Kd8 10. Kd3 Ke7 11. Kd2 Kf7 12. Kc2 Kf6 13. Kd3 Ke7H &#40;220366&#41;
 26/27        0.122     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kc8 9. Kd3 Kc7 10. Kc2 Kd8 11. Kc1 Kc7 12. Kb1 Kd7 13. Ka1 Kd8 14. Ka2H Ke7H 15. Kb3H Kf6H 16. Kc3H Kg6H 17. Kc2H Kg7H 18. Kb1H Kg6H 19. Ka1H Kf7H 20. Kb2H Kf6H 21. Kc3H &#40;244047&#41;
&#91;26/27&#93;       0.123     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kc8 9. Kd3 Kc7 10. Kc2 Kd8 11. Kc1 Kc7 12. Kb1 Kd7 13. Ka1 Kd8 14. Ka2H Ke7H 15. Kb3H Kf6H 16. Kc3H Kg6H 17. Kc2H Kg7H 18. Kb1H Kg6H 19. Ka1H Kf7H 20. Kb2H Kf6H 21. Kc3H &#40;244635&#41;
 27/27        0.138     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kc8 9. Kc2 Kd8 10. Kd3 Ke7 11. Kc4 Kf6 12. Kc3 Kg6 13. Kd2 Kf6 14. Kd3 Ke7H &#40;281550&#41;
&#91;27/27&#93;       0.139     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kc8 9. Kc2 Kd8 10. Kd3 Ke7 11. Kc4 Kf6 12. Kc3 Kg6 13. Kd2 Kf6 14. Kd3 Ke7H &#40;282836&#41;
 28/29        0.169     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kb8 9. Kc1 Ka8 10. Kc2 Kb8 11. Kd2 Kc7 12. Kc1 Kc8 13. Kb1 Kc7 14. Ka1 Kd8 15. Ka2H Ke7H 16. Kb3H Kf6H 17. Kc3H Kg6H 18. Kc2H Kg7H 19. Kb1H Kg6H 20. Ka1H Kf7H 21. Kb2H Kf6H 22. Kc3H &#40;362404&#41;
&#91;28/29&#93;       0.170     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kd2 Kb8 9. Kc1 Ka8 10. Kc2 Kb8 11. Kd2 Kc7 12. Kc1 Kc8 13. Kb1 Kc7 14. Ka1 Kd8 15. Ka2H Ke7H 16. Kb3H Kf6H 17. Kc3H Kg6H 18. Kc2H Kg7H 19. Kb1H Kg6H 20. Ka1H Kf7H 21. Kb2H Kf6H 22. Kc3H &#40;363471&#41;
 29/29        0.215     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd1 Kb7 10. Kc1 Kc8 11. Kc2 Kd8 12. Kd3 Ke7 13. Ke2 Kf7 14. Kd2 Kf6 15. Kd3 Ke7H &#40;482352&#41;
&#91;29/29&#93;       0.215     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd1 Kb7 10. Kc1 Kc8 11. Kc2 Kd8 12. Kd3 Ke7 13. Ke2 Kf7 14. Kd2 Kf6 15. Kd3 Ke7H &#40;482502&#41;
 30/30        0.245     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Ke3 Kc7 12. Kf2 Kd8 13. Kg1 Kc7 14. Kh2 Kd7 15. Kh1 Kd8 16. Kg1H &#40;560534&#41;
&#91;30/30&#93;       0.245     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Ke3 Kc7 12. Kf2 Kd8 13. Kg1 Kc7 14. Kh2 Kd7 15. Kh1 Kd8 16. Kg1H &#40;560687&#41;
 31/43        0.507     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke3 Kd8 11. Kf2 Ke7 12. Ke2 Kf7 13. Ke3 Kf6 14. Kd2 Kg7 15. Kc3 Kf6 16. Kd3 Ke7H 17. Kc3H Kf6H &#40;1031808&#41;
&#91;31/43&#93;       0.508     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke3 Kd8 11. Kf2 Ke7 12. Ke2 Kf7 13. Ke3 Kf6 14. Kd2 Kg7 15. Kc3 Kf6 16. Kd3 Ke7H 17. Kc3H Kf6H &#40;1035067&#41;
 32/43        0.558     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb1 Kc7 7. Kc1 Kb6 8. Kb2 Ka7 9. Kc2 Kb7 10. Kd3 Kc7 11. Kd2 Kd8 12. Ke1 Ke8 13. Kd1 Kd8 14. Kc2 Kc7 15. Kb3 Kb7 16. Ka3 Kc7 &#40;1164552&#41;
&#91;32/43&#93;       0.559     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb1 Kc7 7. Kc1 Kb6 8. Kb2 Ka7 9. Kc2 Kb7 10. Kd3 Kc7 11. Kd2 Kd8 12. Ke1 Ke8 13. Kd1 Kd8 14. Kc2 Kc7 15. Kb3 Kb7 16. Ka3 Kc7 &#40;1166076&#41;
 33/43        0.603     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kb1 Kd8 13. Ka2 Ke7 14. Kb3 Kf6 15. Kc4 Ke7 16. Kc3 Kf6 17. Kd3 Ke7H 18. Kc3H &#40;1280519&#41;
&#91;33/43&#93;       0.604     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kb1 Kd8 13. Ka2 Ke7 14. Kb3 Kf6 15. Kc4 Ke7 16. Kc3 Kf6 17. Kd3 Ke7H 18. Kc3H &#40;1283318&#41;
 34/43        0.648     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kb6 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Kd2 Kc7 14. Kc1 Kd7 15. Kc2 Kd8 16. Kb3 Kc7 17. Ka3 Kd8 18. Kb3H &#40;1396066&#41;
&#91;34/43&#93;       0.649     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kb6 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Kd2 Kc7 14. Kc1 Kd7 15. Kc2 Kd8 16. Kb3 Kc7 17. Ka3 Kd8 18. Kb3H &#40;1398453&#41;
 35/43        0.737     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Kd2 Kd7 14. Ke1 Kd8 15. Ke2 Kd7 16. Ke3 Kc7 17. Kd3 Kb7 18. Kc3 Kb6H 19. Kb3H &#40;1631622&#41;
&#91;35/43&#93;       0.739     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Kd2 Kd7 14. Ke1 Kd8 15. Ke2 Kd7 16. Ke3 Kc7 17. Kd3 Kb7 18. Kc3 Kb6H 19. Kb3H &#40;1635953&#41;
 36/43        0.787     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Kd2 Kc7 14. Kc1 Kd7 15. Kb1 Kd8 16. Ka2 Kc8 17. Kb3 Kc7 18. Ka3 Kd8 19. Kb3H Kc7H &#40;1762000&#41;
&#91;36/43&#93;       0.789     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Kd2 Kc7 14. Kc1 Kd7 15. Kb1 Kd8 16. Ka2 Kc8 17. Kb3 Kc7 18. Ka3 Kd8 19. Kb3H Kc7H &#40;1765365&#41;
 37/43        0.987     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke3 Kd7 11. Kd2 Kd8 12. Ke2 Kd7 13. Ke1 Kd8 14. Kf2 Ke7 15. Kf3 Kf7 16. Ke3 Kf6 17. Kd3 Kg6 18. Kc3 Kh5 19. Kd3 Kg4H &#40;2282394&#41;
&#91;37/43&#93;       0.990     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke3 Kd7 11. Kd2 Kd8 12. Ke2 Kd7 13. Ke1 Kd8 14. Kf2 Ke7 15. Kf3 Kf7 16. Ke3 Kf6 17. Kd3 Kg6 18. Kc3 Kh5 19. Kd3 Kg4H &#40;2288668&#41;
 38/43        1.284     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Kg3 Kf6 13. Kh4 Kg6 14. Kh3 Kg7 15. Kh2 Kf7 16. Kh1 Kf8 17. Kg1 Kf7 18. Kh2 Kg7 19. Kh3 Kf7 20. Kg3H Kf6H &#40;3041028&#41;
&#91;38/43&#93;       1.286     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Kg3 Kf6 13. Kh4 Kg6 14. Kh3 Kg7 15. Kh2 Kf7 16. Kh1 Kf8 17. Kg1 Kf7 18. Kh2 Kg7 19. Kh3 Kf7 20. Kg3H Kf6H &#40;3044628&#41;
 39/43        1.439     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Ke3 Kd7 13. Kd2 Kd8 14. Kc1 Kc7 15. Kb1 Kd8 16. Ka2 Ke7 17. Kb3 Kf6 18. Kc4 Ke7 19. Kc3 Kf6 20. Kd3 Kg6H 21. Kc3H Kh5H 22. Kc4H Kg4H 23. Kb5H Kxf4H 24. Kc6H Ke4H 25. Kxd6H f4H 26. Kc5H f3H 27. d6H f2H 28. d7H f1=QH 29. d8=QH Kd3H 30. Qd6H Qc1+H 31. Kb6H Qd2H &#40;3438516&#41;
&#91;39/43&#93;       1.443     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Ke3 Kd7 13. Kd2 Kd8 14. Kc1 Kc7 15. Kb1 Kd8 16. Ka2 Ke7 17. Kb3 Kf6 18. Kc4 Ke7 19. Kc3 Kf6 20. Kd3 Kg6H 21. Kc3H Kh5H 22. Kc4H Kg4H 23. Kb5H Kxf4H 24. Kc6H Ke4H 25. Kxd6H f4H 26. Kc5H f3H 27. d6H f2H 28. d7H f1=QH 29. d8=QH Kd3H 30. Qd6H Qc1+H 31. Kb6H Qd2H &#40;3448027&#41;
 40/45        1.656     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Ke2 Kd7 14. Kf3 Ke7 15. Kg3 Kf6 16. Kh4 Kg6 17. Kh3 Kf6 18. Kg3 Kg6 19. Kh4 Kh6 20. Kh3 Kg6 21. Kh4H &#40;3991151&#41;
&#91;40/45&#93;       1.658     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Ke2 Kd7 14. Kf3 Ke7 15. Kg3 Kf6 16. Kh4 Kg6 17. Kh3 Kf6 18. Kg3 Kg6 19. Kh4 Kh6 20. Kh3 Kg6 21. Kh4H &#40;3995391&#41;
 41/45        1.855     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Ke3 Kd7 13. Ke2 Kd8 14. Kd2 Kd7 15. Ke3 Kd8 16. Kf2 Ke7 17. Kf3 Kf7 18. Ke3 Kf6 19. Kd3 Kg6 20. Kd2 Kh5 21. Kd3 Kg4H &#40;4498572&#41;
&#91;41/45&#93;       1.859     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Ke3 Kd7 13. Ke2 Kd8 14. Kd2 Kd7 15. Ke3 Kd8 16. Kf2 Ke7 17. Kf3 Kf7 18. Ke3 Kf6 19. Kd3 Kg6 20. Kd2 Kh5 21. Kd3 Kg4H &#40;4511137&#41;
 42/58        3.799     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Ke2 Kd7 14. Kf3 Ke7 15. Ke3 Kd8 16. Kd2 Kd7 17. Ke1 Kd8 18. Kf2 Ke7 19. Kg3 Kf6 20. Kh4 Kg6 21. Kh3 Kf7 22. Kg3H Kf6H &#40;7071135&#41;
&#91;42/58&#93;       3.802     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Ke2 Kd7 14. Kf3 Ke7 15. Ke3 Kd8 16. Kd2 Kd7 17. Ke1 Kd8 18. Kf2 Ke7 19. Kg3 Kf6 20. Kh4 Kg6 21. Kh3 Kf7 22. Kg3H Kf6H &#40;7076730&#41;
 43/58        4.177     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Ke3 Kd7 13. Ke2 Kd8 14. Ke1 Ke7 15. Kd2 Kd8 16. Kc1 Kc7 17. Kb1 Kd8 18. Ka2 Ke7 19. Kb3 Kf6 20. Kc4 Ke7 21. Kc3 Kf6 22. Kd3 Kg6H 23. Kc3H Kh5H 24. Kc4H Kg4H 25. Kb5H Kxf4H 26. Kc6H Ke4H 27. Kxd6H f4H 28. Kc5H f3H 29. d6H f2H 30. d7H f1=QH 31. d8=QH Kd3H 32. Qd6H Qc1+H 33. Kb6H Qd2H 34. Qc5H &#40;7989063&#41;
&#91;43/58&#93;       4.188     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Ke3 Kd7 13. Ke2 Kd8 14. Ke1 Ke7 15. Kd2 Kd8 16. Kc1 Kc7 17. Kb1 Kd8 18. Ka2 Ke7 19. Kb3 Kf6 20. Kc4 Ke7 21. Kc3 Kf6 22. Kd3 Kg6H 23. Kc3H Kh5H 24. Kc4H Kg4H 25. Kb5H Kxf4H 26. Kc6H Ke4H 27. Kxd6H f4H 28. Kc5H f3H 29. d6H f2H 30. d7H f1=QH 31. d8=QH Kd3H 32. Qd6H Qc1+H 33. Kb6H Qd2H 34. Qc5H &#40;8017166&#41;
 44/58        4.657     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Ke2 Kd7 14. Kf3 Ke7 15. Ke3 Kd7 16. Kf2 Ke7 17. Kf3 Kf7 18. Ke3 Kf6 19. Kd3 Ke7 20. Kc3 Kf6 21. Kc4 Kf7 22. Kb5 Kg6 23. Kc6H Kh5H 24. Kxd6H Kh6H 25. Kc6H Kg6H 26. d6H Kf6H 27. d7H Ke7H &#40;8951537&#41;
&#91;44/58&#93;       4.660     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Kd2 Kd8 11. Kc1 Kc7 12. Kd1 Kd8 13. Ke2 Kd7 14. Kf3 Ke7 15. Ke3 Kd7 16. Kf2 Ke7 17. Kf3 Kf7 18. Ke3 Kf6 19. Kd3 Ke7 20. Kc3 Kf6 21. Kc4 Kf7 22. Kb5 Kg6 23. Kc6H Kh5H 24. Kxd6H Kh6H 25. Kc6H Kg6H 26. d6H Kf6H 27. d7H Ke7H &#40;8959240&#41;
 45/58        5.332     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Ke3 Kd7 13. Ke2 Kd8 14. Kd1 Kc8 15. Kc2 Kd8 16. Kd2 Kd7 17. Ke1 Kd8 18. Kf2 Ke7 19. Kf3 Kf7 20. Ke3 Kf6 21. Kd3 Kg6 22. Kd2 Kh5 23. Kd3 Kg4H &#40;10556494&#41;
&#91;45/58&#93;       5.348     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kb3 Ka7 5. Ka2 Kb8 6. Kb2 Kc7 7. Kc3 Kb7 8. Kc2 Kc8 9. Kd3 Kc7 10. Ke2 Kd7 11. Kf3 Ke7 12. Ke3 Kd7 13. Ke2 Kd8 14. Kd1 Kc8 15. Kc2 Kd8 16. Kd2 Kd7 17. Ke1 Kd8 18. Kf2 Ke7 19. Kf3 Kf7 20. Ke3 Kf6 21. Kd3 Kg6 22. Kd2 Kh5 23. Kd3 Kg4H &#40;10597276&#41;
...and so on...
SPDH:

Code: Select all

Depth          Time     Score   PV &#40;nodes&#41;
&#91; 9/ 9&#93;       0.007     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kd7 4. Kb5 Kd8 5. Kxa5 &#40;12250&#41;
 10/11        0.009     +0.99   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb8 4. Kd3 Kc7 5. Kd2 Kd8 6. Kc2H Kc7H 7. Kd3H Kd8H 8. Kc3H Kc7H &#40;16108&#41;
&#91;10/11&#93;       0.009     +0.99   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb8 4. Kd3 Kc7 5. Kd2 Kd8 6. Kc2H Kc7H 7. Kd3H Kd8H 8. Kc3H Kc7H &#40;16273&#41;
 11/11        0.011     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb8 4. Kb5 Kc8 5. Ka6 Kb8 6. Kxa5 &#40;20621&#41;
&#91;11/11&#93;       0.012     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb8 4. Kb5 Kc8 5. Ka6 Kb8 6. Kxa5 &#40;21096&#41;
 12/14        0.017     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kd3 Kc7 5. Kd2 Kd7 6. Kc1 Kd8 7. Kd1H Kc7H 8. Kc2H Kd7H 9. Kd2H Kd8H 10. Kc2H Kc7H 11. Kd3H Kd8H 12. Kc3H Kc7H &#40;30252&#41;
&#91;12/14&#93;       0.018     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc4 Kb6 4. Kd3 Kc7 5. Kd2 Kd7 6. Kc1 Kd8 7. Kd1H Kc7H 8. Kc2H Kd7H 9. Kd2H Kd8H 10. Kc2H Kc7H 11. Kd3H Kd8H 12. Kc3H Kc7H &#40;34220&#41;
 13/14        0.024     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kd7 4. Kb3 Kd8 5. Kc4 Kc7 6. Kb5 Kd8 7. Kxa5 Kc7H 8. Kb5H &#40;46475&#41;
&#91;13/14&#93;       0.025     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kd7 4. Kb3 Kd8 5. Kc4 Kc7 6. Kb5 Kd8 7. Kxa5 Kc7H 8. Kb5H &#40;47612&#41;
 14/15        0.033     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kd8 4. Kd3 Kc7 5. Kc3 Kd7 6. Kc4 Kc8 7. Kb5 Kd8 8. Kxa5 Kc7H 9. Kb5H &#40;67218&#41;
&#91;14/15&#93;       0.054     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kd8 4. Kd3 Kc7 5. Kc3 Kd7 6. Kc4 Kc8 7. Kb5 Kd8 8. Kxa5 Kc7H 9. Kb5H &#40;113364&#41;
 15/15        0.071     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kd8 4. Kb1 Kc7 5. Kc1 Kd8 6. Kc2 Kc8 7. Kd2 Kb8 8. Kd3 Kc7H 9. Kc3H Kd8H 10. Kc4H Ke8H 11. Kd3H Kd8H 12. Kd2H Kc7H 13. Kd3H Kd8H &#40;155261&#41;
&#91;15/15&#93;       0.085     +0.89   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kd8 4. Kb1 Kc7 5. Kc1 Kd8 6. Kc2 Kc8 7. Kd2 Kb8 8. Kd3 Kc7H 9. Kc3H Kd8H 10. Kc4H Ke8H 11. Kd3H Kd8H 12. Kd2H Kc7H 13. Kd3H Kd8H &#40;189763&#41;
 16/16        0.106     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kd8 4. Kb1 Kc8 5. Kc1 Kb7 6. Kd1 Kc7 7. Kd2 Kd7 8. Kc1 Kd8 9. Kd1H Kc7H &#40;241033&#41;
&#91;16/16&#93;       0.108     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kc2 Kd8 4. Kb1 Kc8 5. Kc1 Kb7 6. Kd1 Kc7 7. Kd2 Kd7 8. Kc1 Kd8 9. Kd1H Kc7H &#40;245289&#41;
 17/18        0.167     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kb3 Kb6 4. Kc4 Ka6 5. Kc3 Ka7 6. Kd3 Kb8 7. Kc4 Kc7 8. Kb5 Kd8 9. Kxa5 Kc8H 10. Kb6H Kb8H 11. Kc6H Ka8H 12. Kc7H &#40;383512&#41;
&#91;17/18&#93;       0.267     +0.90   1. Kb2 Kb8 2. Kc3 Kc7 3. Kb3 Kb6 4. Kc4 Ka6 5. Kc3 Ka7 6. Kd3 Kb8 7. Kc4 Kc7 8. Kb5 Kd8 9. Kxa5 Kc8H 10. Kb6H Kb8H 11. Kc6H Ka8H 12. Kc7H &#40;625330&#41;
 18/19        0.345     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kb3 Kb6 4. Kb2 Ka6 5. Kc3 Kb6 6. Kc4 Ka6 7. Kd3 Kb6 8. Kd2 Kc7 9. Kc1 Kd8 10. Kd1H Kc7H 11. Kc2H Kd8H 12. Kb1H Kc8H 13. Kc1H Kb7H 14. Kd1H Kc7H &#40;811327&#41;
&#91;18/19&#93;       0.354     +0.93   1. Kb2 Kb8 2. Kc3 Kc7 3. Kb3 Kb6 4. Kb2 Ka6 5. Kc3 Kb6 6. Kc4 Ka6 7. Kd3 Kb6 8. Kd2 Kc7 9. Kc1 Kd8 10. Kd1H Kc7H 11. Kc2H Kd8H 12. Kb1H Kc8H 13. Kc1H Kb7H 14. Kd1H Kc7H &#40;833009&#41;
 19/22        0.508     +0.91   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc3 Kb6 4. Kd3 Kc7 5. Kc4 Kb6 6. Kc3 Kc7 7. Kb3 Kb6 8. Kc2 Kc7 9. Kd2 Kd7 10. Kd3 Kc7H &#40;1191034&#41;
&#91;19/22&#93;       0.819     +0.91   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc3 Kb6 4. Kd3 Kc7 5. Kc4 Kb6 6. Kc3 Kc7 7. Kb3 Kb6 8. Kc2 Kc7 9. Kd2 Kd7 10. Kd3 Kc7H &#40;1955709&#41;
 20/22        1.171     +0.93   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc3 Kb6 4. Kc2 Kc7 5. Kd3 Kb6 6. Kc4 Ka6 7. Kb3 Kb6 8. Kb2 Kc7 9. Kb1 Kd7 10. Kc1 Kd8 11. Kd1H Kc7H 12. Kc2H Kd8H 13. Kb1H Kc8H 14. Kc1H Kb7H 15. Kd1H Kc7H &#40;2779994&#41;
&#91;20/22&#93;       1.216     +0.93   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc3 Kb6 4. Kc2 Kc7 5. Kd3 Kb6 6. Kc4 Ka6 7. Kb3 Kb6 8. Kb2 Kc7 9. Kb1 Kd7 10. Kc1 Kd8 11. Kd1H Kc7H 12. Kc2H Kd8H 13. Kb1H Kc8H 14. Kc1H Kb7H 15. Kd1H Kc7H &#40;2893430&#41;
 21/22        1.771     +0.89   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc3 Kb6 4. Kc2 Kc7 5. Kd3 Kb6 6. Ke2 Ka6 7. Kd2 Ka7 8. Kc2 Kb8 9. Kc1 Kc7 10. Kd2 Kb8 11. Kd3 Kc7H 12. Kc4H Kb6H 13. Kc3H Kc7H 14. Kb3H Kb6H 15. Kb2H Ka6H 16. Kc3H &#40;4234190&#41;
&#91;21/22&#93;       1.939     +0.89   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc3 Kb6 4. Kc2 Kc7 5. Kd3 Kb6 6. Ke2 Ka6 7. Kd2 Ka7 8. Kc2 Kb8 9. Kc1 Kc7 10. Kd2 Kb8 11. Kd3 Kc7H 12. Kc4H Kb6H 13. Kc3H Kc7H 14. Kb3H Kb6H 15. Kb2H Ka6H 16. Kc3H &#40;4645879&#41;
 22/23        2.547     +0.93   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kc3 Kc7 5. Kc2 Kd8 6. Kd3 Kc7 7. Kc3 Kb6 8. Kc4 Ka6 9. Kd3 Kb6 10. Kd2 Kc7 11. Kc1 Kd8 12. Kd1H Kc7H 13. Kc2H &#40;6075031&#41;
&#91;22/23&#93;       2.864     +0.93   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kc3 Kc7 5. Kc2 Kd8 6. Kd3 Kc7 7. Kc3 Kb6 8. Kc4 Ka6 9. Kd3 Kb6 10. Kd2 Kc7 11. Kc1 Kd8 12. Kd1H Kc7H 13. Kc2H &#40;6785453&#41;
 23/23        4.114     +0.97   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kc3 Kc7 5. Kb3 Kb6 6. Kb2 Ka6 7. Kc3 Ka7 8. Kd3 Kb8 9. Kc4 Kc7 10. Kb5 Kd7 11. Kxa5 Kd8 12. Ka6 Kc8H 13. Ka7H &#40;9524739&#41;
&#91;23/23&#93;       4.189     +0.97   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kc3 Kc7 5. Kb3 Kb6 6. Kb2 Ka6 7. Kc3 Ka7 8. Kd3 Kb8 9. Kc4 Kc7 10. Kb5 Kd7 11. Kxa5 Kd8 12. Ka6 Kc8H 13. Ka7H &#40;9702334&#41;
 24/25        5.925     +0.91   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kc3 Kc7 5. Kb3 Kb6 6. Kb2 Ka6 7. Kc3 Ka7 8. Kd3 Kb6 9. Ke2 Kc7 10. Kd1 Kd8 11. Kc2 Kc7 12. Kb1 Kd8 &#40;13886105&#41;
&#91;24/26&#93;      11.786     +0.91   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kc3 Kc7 5. Kb3 Kb6 6. Kb2 Ka6 7. Kc3 Ka7 8. Kd3 Kb6 9. Ke2 Kc7 10. Kd1 Kd8 11. Kc2 Kc7 12. Kb1 Kd8 &#40;28147113&#41;
 25/27       15.373     +0.97   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kd3 Kc7 5. Kd2 Kd7 6. Kc3 Kc7 7. Kd3 Kb6 8. Ke2 Kc7 9. Kf3 Kd8 10. Kg3 Kc7 11. Kh4 Kb6 12. Kg5 Ka6 13. Kxf5 Ka7H 14. Kg5H Ka6H 15. Kh5H &#40;36677604&#41;
&#91;25/27&#93;      15.715     +0.97   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kd3 Kc7 5. Kd2 Kd7 6. Kc3 Kc7 7. Kd3 Kb6 8. Ke2 Kc7 9. Kf3 Kd8 10. Kg3 Kc7 11. Kh4 Kb6 12. Kg5 Ka6 13. Kxf5 Ka7H 14. Kg5H Ka6H 15. Kh5H &#40;37306638&#41;
 26/28         1&#58;02     +0.93   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kd3 Kc7 5. Kd2 Kd7 6. Kc3 Kc7 7. Kb3 Kb6 8. Kc2 Kc7 9. Kc3 Kb6 10. Kc4 Ka6 11. Kd3 Kb6 12. Kd2 Kc7 13. Kc1 Kd8 14. Kd1H Kc7H 15. Kc2H Kd8H 16. Kd3H Kc7H &#40;144704020&#41;
&#91;26/28&#93;        1&#58;22     +0.93   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kd3 Kc7 5. Kd2 Kd7 6. Kc3 Kc7 7. Kb3 Kb6 8. Kc2 Kc7 9. Kc3 Kb6 10. Kc4 Ka6 11. Kd3 Kb6 12. Kd2 Kc7 13. Kc1 Kd8 14. Kd1H Kc7H 15. Kc2H Kd8H 16. Kd3H Kc7H &#40;191157970&#41;
 27/28         1&#58;42     +0.95   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kd3 Kc7 5. Kd2 Kd7 6. Kc3 Kc7 7. Kd3 Kb6 8. Ke2 Ka6 9. Ke1 Ka7 10. Kf2 Ka6 11. Kg3 Ka7 12. Kh4 Ka6 13. Kg5 Ka7 14. Kxf5 Kb6H 15. Kg4H &#40;236779679&#41;
&#91;27/28&#93;        1&#58;55     +0.95   1. Kb2 Kb8 2. Kb3 Kc7 3. Kc4 Kb6 4. Kd3 Kc7 5. Kd2 Kd7 6. Kc3 Kc7 7. Kd3 Kb6 8. Ke2 Ka6 9. Ke1 Ka7 10. Kf2 Ka6 11. Kg3 Ka7 12. Kh4 Ka6 13. Kg5 Ka7 14. Kxf5 Kb6H 15. Kg4H &#40;266854382&#41;
So it's still significantly slower, but it reaches the "key" depth of 26 in an almost reasonable time. I don't really mind if it's slow on positions like this, the problem is that it doesn't help strength overall.

I just have to figure out why this position isn't solved at all, now that I've been publicly embarrassed. ;)

bob
Posts: 20562
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by bob » Sun May 25, 2008 12:50 am

My response is the same as always here. Anything that reduces the efficiency of the hash table is a non-starter for me. Whether it be simple things like don't store exact mate scores, all the way to including path-dependent information to avoid known path-dependent issues. I have no idea how novel your idea is, although I have heard similar proposals in years gone by each time we get into a discussion about repetitions/draws and hash scoring. As the old saying goes, "the cure has to be better than the disease" or else the cure is not very useful. :)

There might be a day, as SMP systems grow faster and faster, where a true path-dependent TT can be used, and the inefficiency can be ignored completely because of the depths we might reach. But today, I'm personally not willing to give up anything for a problem that occurs so infrequently...

I've looked for unexpected draws in tens of thousands of my cluster games as I made the last repetition fix in Crafty a year ago or so, and once the repetition bugs were fixed, I simply did not find more than one or two cases in tens of thousands of games where Crafty draw a won game unexpectedly, that is where the score was positive and suddenly the game was over by repetition or 50 move draw. I found lots of games where it was ahead and drew, but it saw the drawing line well in advance and thought that was the best it could do...

bob
Posts: 20562
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by bob » Sun May 25, 2008 12:57 am

You need to figure out what is going on. This is winnible in 26 plies, counting the 27th ply as a capture your q-search will pick up. So with a 26 ply search, you must see winning a pawn, or else there is a serious bug that needs fixing... This really is the best test for hashing correctness, as most programs will find the solution in less than 26 plies because of poor move ordering and hash sub-tree grafting here and there. But if you reach 26 plies and can't see winning the pawn (or better) then something really needs attention...

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

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by hgm » Sun May 25, 2008 5:09 pm

Does that indicate that 'poor move ordering' is actually better?

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by Zach Wegner » Sun May 25, 2008 8:31 pm

OK, it's simply a null move issue. I was allowing null move in this position. I suppose I figured my null move scheme would take care of it.

Code: Select all

Depth          Time     Score   PV &#40;nodes&#41;
&#91;12/13&#93;       0.006     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kc4 Kb6 4. Kc3 Kb7 5. Kd3 Kc8 6. Kc2 Kc7 7. Kb2H Kc8H 8. Kc3H Kb7H &#40;11331&#41;
 13/13        0.009     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kd3 Kc8 4. Kc2 Kc7 5. Kc3 Kb7 6. Kc4 Kb6 7. Kd3 Ka6H 8. Kc2H Kb6H 9. Kc3H Ka6H 10. Kd3H &#40;18816&#41;
&#91;13/13&#93;       0.010     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kd3 Kc8 4. Kc2 Kc7 5. Kc3 Kb7 6. Kc4 Kb6 7. Kd3 Ka6H 8. Kc2H Kb6H 9. Kc3H Ka6H 10. Kd3H &#40;19327&#41;
 14/15        0.013     +1.00   1. Kb2 Kb8 2. Kc3 Kb7 3. Kd3 Ka7 4. Kd2 Kb8 5. Kc3 Kb7 6. Kd3 Kc8 7. Kc4 Kc7 8. Kb5H Kc8H 9. Kxa5H Kd8H 10. Ka6H &#40;27381&#41;
&#91;14/15&#93;       0.014     +1.00   1. Kb2 Kb8 2. Kc3 Kb7 3. Kd3 Ka7 4. Kd2 Kb8 5. Kc3 Kb7 6. Kd3 Kc8 7. Kc4 Kc7 8. Kb5H Kc8H 9. Kxa5H Kd8H 10. Ka6H &#40;28413&#41;
 15/15        0.020     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kc8 4. Kc4 Kb8 5. Kb5 Ka7 6. Kxa5 Kb7 7. Kb5 Kc8 8. Ka6 &#40;41060&#41;
&#91;15/15&#93;       0.020     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kc8 4. Kc4 Kb8 5. Kb5 Ka7 6. Kxa5 Kb7 7. Kb5 Kc8 8. Ka6 &#40;42245&#41;
 16/18        0.027     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Ka6 5. Kc3 Ka7 6. Kb2 Kb6 7. Kb3 Kc7 8. Kc2 Kd8 9. Kd2H Ke7H 10. Kd3H Kf8H 11. Kc4H Ke7H 12. Kb5H Kf6H 13. Kxa5H Kg6H 14. Ka6H &#40;55323&#41;
&#91;16/18&#93;       0.028     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Ka6 5. Kc3 Ka7 6. Kb2 Kb6 7. Kb3 Kc7 8. Kc2 Kd8 9. Kd2H Ke7H 10. Kd3H Kf8H 11. Kc4H Ke7H 12. Kb5H Kf6H 13. Kxa5H Kg6H 14. Ka6H &#40;57041&#41;
 17/18        0.051     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Ka6 5. Kc3 Ka7 6. Kd3 Kb8 7. Kc3 Kb7 8. Kc4 Kb6 9. Kd3 Ka7H 10. Kd2H Kb7H 11. Kc3H Ka7H &#40;110531&#41;
&#91;17/18&#93;       0.052     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Ka6 5. Kc3 Ka7 6. Kd3 Kb8 7. Kc3 Kb7 8. Kc4 Kb6 9. Kd3 Ka7H 10. Kd2H Kb7H 11. Kc3H Ka7H &#40;112978&#41;
 18/20        0.053     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kb3 Kb8 10. Kc4H Kb7H 11. Kb5H Kc8H 12. Kxa5H Kd8H 13. Ka6H &#40;115601&#41;
&#91;18/20&#93;       0.055     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kb3 Kb8 10. Kc4H Kb7H 11. Kb5H Kc8H 12. Kxa5H Kd8H 13. Ka6H &#40;119360&#41;
 19/20        0.057     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kc4 Kb6 10. Kd3 Ka7H 11. Kd2H Kb8H 12. Kc3H &#40;122416&#41;
&#91;19/20&#93;       0.059     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kc4 Kb6 10. Kd3 Ka7H 11. Kd2H Kb8H 12. Kc3H &#40;127243&#41;
 20/22        0.060     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Kb6 9. Kb3 Ka7 10. Kb2 Kb8 11. Kc3H &#40;129328&#41;
&#91;20/22&#93;       0.061     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Kb6 9. Kb3 Ka7 10. Kb2 Kb8 11. Kc3H &#40;131890&#41;
 21/22        0.082     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc4 Kb6 9. Kc3 Ka6 10. Kc4 Kb6 11. Kd3 Ka7H 12. Ke3H Kb8H 13. Kf2H Kb7H 14. Kg3H Kc8H 15. Kh4H Kb7H 16. Kg5H Ka7H 17. Kxf5H &#40;167913&#41;
&#91;21/22&#93;       0.084     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc4 Kb6 9. Kc3 Ka6 10. Kc4 Kb6 11. Kd3 Ka7H 12. Ke3H Kb8H 13. Kf2H Kb7H 14. Kg3H Kc8H 15. Kh4H Kb7H 16. Kg5H Ka7H 17. Kxf5H &#40;172568&#41;
 22/24        0.126     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kb3 Kb7 10. Kb2 Ka7 11. Kb3 Kb8 12. Kc4H Kb7H 13. Kb5H Kc8H 14. Kxa5H Kd8H 15. Ka6H &#40;248526&#41;
&#91;22/24&#93;       0.139     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kb3 Kb7 10. Kb2 Ka7 11. Kb3 Kb8 12. Kc4H Kb7H 13. Kb5H Kc8H 14. Kxa5H Kd8H 15. Ka6H &#40;276954&#41;
 23/26        0.309     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka6 4. Kc3 Kb7 5. Kb3 Kb6 6. Kc4 Ka6 7. Kd3 Kb7 8. Ke2 Kb8 9. Kd2 Ka7 10. Kd3 Kb7 11. Kc4 Kb6 12. Kd3 Kc7H 13. Kc4H Kb6H &#40;634811&#41;
&#91;23/26&#93;       0.338     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka6 4. Kc3 Kb7 5. Kb3 Kb6 6. Kc4 Ka6 7. Kd3 Kb7 8. Ke2 Kb8 9. Kd2 Ka7 10. Kd3 Kb7 11. Kc4 Kb6 12. Kd3 Kc7H 13. Kc4H Kb6H &#40;699513&#41;
 24/26        0.767     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Kb8 5. Kc3 Kb7 6. Kb3 Ka6 7. Kc2 Kb6 8. Kd2 Kc7 9. Kd3 Kb7 10. Ke2 Kb8 11. Kd1 Kc8 12. Kd2 Kd8 13. Kd3H Kc7H 14. Kc4H Kb6H 15. Kc3H Ka6H 16. Kb3H Kb6H 17. Kc4H Ka6H 18. Kd3H Kb7H &#40;1707889&#41;
&#91;24/26&#93;       0.769     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Kb8 5. Kc3 Kb7 6. Kb3 Ka6 7. Kc2 Kb6 8. Kd2 Kc7 9. Kd3 Kb7 10. Ke2 Kb8 11. Kd1 Kc8 12. Kd2 Kd8 13. Kd3H Kc7H 14. Kc4H Kb6H 15. Kc3H Ka6H 16. Kb3H Kb6H 17. Kc4H Ka6H 18. Kd3H Kb7H &#40;1713305&#41;
 25/28        3.052     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Kb8 5. Kc3 Kb7 6. Kb3 Ka7 7. Kc4 Kb6 8. Kd3 Kc7 9. Kd2 Kd8 10. Kc3 Kc7 11. Kb3 Kb7 12. Kc4 Kb6 13. Kd3 Kc7H &#40;7127555&#41;
&#91;25/28&#93;       3.054     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Kb8 5. Kc3 Kb7 6. Kb3 Ka7 7. Kc4 Kb6 8. Kd3 Kc7 9. Kd2 Kd8 10. Kc3 Kc7 11. Kb3 Kb7 12. Kc4 Kb6 13. Kd3 Kc7H &#40;7131532&#41;
 26/30        5.891     +0.99   1. Kb2 Ka8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Ka8 5. Kc3 Kb7 6. Kb3 Ka7 7. Kc4 Kb6 8. Kd3 Kc7 9. Kc4 Kb6 10. Kd3 Kc7 11. Kd2 Kc8 12. Ke3 Kd8 13. Kd2 Kc7 14. Kd3H Kb7H 15. Ke2H Kb8H 16. Kf2H Kb7H 17. Kg3H Kc8H 18. Kh4H Kb7H 19. Kg5H Ka7H 20. Kxf5H &#40;13104977&#41;
 26/30        5.987     +2.57   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc8 7. Kf2 Kd8 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kg7 11. Kg5 Kh8 12. Kxf5 Kh7 13. Kf6 Kh6 14. Kf7H &#40;13312204&#41;
&#91;26/30&#93;       5.990     +2.57   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc8 7. Kf2 Kd8 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kg7 11. Kg5 Kh8 12. Kxf5 Kh7 13. Kf6 Kh6 14. Kf7H &#40;13318697&#41;
 27/32        6.256     +1.36   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kb8 7. Kf2 Kb7 8. Kg3 Kc8 9. Kh4 Kb7 10. Kg5 Ka7 11. Kxf5 Kb8 12. Kf6 Kb7 13. Kf7 Kc7 14. Kf8 Kd7H &#40;13953590&#41;
&#91;27/32&#93;       6.261     +1.36   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kb8 7. Kf2 Kb7 8. Kg3 Kc8 9. Kh4 Kb7 10. Kg5 Ka7 11. Kxf5 Kb8 12. Kf6 Kb7 13. Kf7 Kc7 14. Kf8 Kd7H &#40;13965358&#41;
 28/32        9.874     +2.57   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc8 5. Kd2 Kd7 6. Kc3 Kc7 7. Kd3 Kb7 8. Ke2 Kc8 9. Kf2 Kd8 10. Kg3 Ke7 11. Kh4 Kf8 12. Kg5 Kg7 13. Kxf5 Kh7 14. Kf6 Kh6 15. Kf7H &#40;21691050&#41;
&#91;28/32&#93;       9.875     +2.57   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc8 5. Kd2 Kd7 6. Kc3 Kc7 7. Kd3 Kb7 8. Ke2 Kc8 9. Kf2 Kd8 10. Kg3 Ke7 11. Kh4 Kf8 12. Kg5 Kg7 13. Kxf5 Kh7 14. Kf6 Kh6 15. Kf7H &#40;21691739&#41;
 29/37       13.679     +2.14   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke3 Kc8 7. Kd2 Kd7 8. Kc3 Kc8 9. Kc4 Kb8 10. Kb5 Kb7 11. Kxa5 Ka7 12. Kb5 Kb7 13. a5 Kc7 14. Kc4 Kb7 15. Kd3 Ka8H &#40;29803504&#41;
&#91;29/37&#93;      13.773     +2.14   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke3 Kc8 7. Kd2 Kd7 8. Kc3 Kc8 9. Kc4 Kb8 10. Kb5 Kb7 11. Kxa5 Ka7 12. Kb5 Kb7 13. a5 Kc7 14. Kc4 Kb7 15. Kd3 Ka8H &#40;30013132&#41;
exit
&#91;30/37&#93;      20.912     +2.14   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke3 Kc8 7. Kd2 Kd7 8. Kc3 Kc8 9. Kc4 Kb8 10. Kb5 Kb7 11. Kxa5 Ka7 12. Kb5 Kb7 13. a5 Kc7 14. Kc4 Kb7 15. Kd3 Ka8H &#40;44954551&#41;
I don't know what's happening at ply 27, and it's still rather slow, but it's finding it. Yes, it's slower in this position with SPDH, but it's _adjustable_. You can turn it off in endgames like this, or you can make the path hashkey only based on the fifty move counter.

I'm glad, at least, that this one position totally kills any interest in the idea... :roll:

bob
Posts: 20562
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by bob » Sun May 25, 2008 8:45 pm

hgm wrote:Does that indicate that 'poor move ordering' is actually better?
Good question. Obviously no, as this depends on pure serendipity to find the solution and random bad order is going to hurt worse overall than it helps in fine 70.

This is a position I have studied in great detail using multiple programs Blitz, Cray Blitz, Duchess, Chess 4.x and Crafty. Once you look at the tree, knowing the actual solution moves, you can see how searching the wrong moves early cause you to solve the thing with a later move. Kb1 is the right move, but hardly anyone would order that first. There are many other unexpected best moves in the solution dealing with coordinated squares that a move generator will be clueless about (as will killer moves as they won't know a particular oddball move is best until after it has been proven to be best...)

Once you see how you solve it with less than 26 plies (there are obviously no extensions kicking in here either) you get the idea about bad move ordering. Perfect ordering will most likely take 26 plies. I might try to verify this by searching to depth=26, then clearing all scores and iterating back thru the depths without overwriting the hash table (making it big enough that there are no overwrites) so that perfect move ordering from depth=26 will be used everywhere, then see if it can solve it "early" (which I doubt).

I'll report back as the idea is interesting...

bob
Posts: 20562
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by bob » Sun May 25, 2008 8:51 pm

Zach Wegner wrote:OK, it's simply a null move issue. I was allowing null move in this position. I suppose I figured my null move scheme would take care of it.

Code: Select all

Depth          Time     Score   PV &#40;nodes&#41;
&#91;12/13&#93;       0.006     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kc4 Kb6 4. Kc3 Kb7 5. Kd3 Kc8 6. Kc2 Kc7 7. Kb2H Kc8H 8. Kc3H Kb7H &#40;11331&#41;
 13/13        0.009     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kd3 Kc8 4. Kc2 Kc7 5. Kc3 Kb7 6. Kc4 Kb6 7. Kd3 Ka6H 8. Kc2H Kb6H 9. Kc3H Ka6H 10. Kd3H &#40;18816&#41;
&#91;13/13&#93;       0.010     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kd3 Kc8 4. Kc2 Kc7 5. Kc3 Kb7 6. Kc4 Kb6 7. Kd3 Ka6H 8. Kc2H Kb6H 9. Kc3H Ka6H 10. Kd3H &#40;19327&#41;
 14/15        0.013     +1.00   1. Kb2 Kb8 2. Kc3 Kb7 3. Kd3 Ka7 4. Kd2 Kb8 5. Kc3 Kb7 6. Kd3 Kc8 7. Kc4 Kc7 8. Kb5H Kc8H 9. Kxa5H Kd8H 10. Ka6H &#40;27381&#41;
&#91;14/15&#93;       0.014     +1.00   1. Kb2 Kb8 2. Kc3 Kb7 3. Kd3 Ka7 4. Kd2 Kb8 5. Kc3 Kb7 6. Kd3 Kc8 7. Kc4 Kc7 8. Kb5H Kc8H 9. Kxa5H Kd8H 10. Ka6H &#40;28413&#41;
 15/15        0.020     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kc8 4. Kc4 Kb8 5. Kb5 Ka7 6. Kxa5 Kb7 7. Kb5 Kc8 8. Ka6 &#40;41060&#41;
&#91;15/15&#93;       0.020     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kc8 4. Kc4 Kb8 5. Kb5 Ka7 6. Kxa5 Kb7 7. Kb5 Kc8 8. Ka6 &#40;42245&#41;
 16/18        0.027     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Ka6 5. Kc3 Ka7 6. Kb2 Kb6 7. Kb3 Kc7 8. Kc2 Kd8 9. Kd2H Ke7H 10. Kd3H Kf8H 11. Kc4H Ke7H 12. Kb5H Kf6H 13. Kxa5H Kg6H 14. Ka6H &#40;55323&#41;
&#91;16/18&#93;       0.028     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Ka6 5. Kc3 Ka7 6. Kb2 Kb6 7. Kb3 Kc7 8. Kc2 Kd8 9. Kd2H Ke7H 10. Kd3H Kf8H 11. Kc4H Ke7H 12. Kb5H Kf6H 13. Kxa5H Kg6H 14. Ka6H &#40;57041&#41;
 17/18        0.051     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Ka6 5. Kc3 Ka7 6. Kd3 Kb8 7. Kc3 Kb7 8. Kc4 Kb6 9. Kd3 Ka7H 10. Kd2H Kb7H 11. Kc3H Ka7H &#40;110531&#41;
&#91;17/18&#93;       0.052     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Ka6 5. Kc3 Ka7 6. Kd3 Kb8 7. Kc3 Kb7 8. Kc4 Kb6 9. Kd3 Ka7H 10. Kd2H Kb7H 11. Kc3H Ka7H &#40;112978&#41;
 18/20        0.053     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kb3 Kb8 10. Kc4H Kb7H 11. Kb5H Kc8H 12. Kxa5H Kd8H 13. Ka6H &#40;115601&#41;
&#91;18/20&#93;       0.055     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kb3 Kb8 10. Kc4H Kb7H 11. Kb5H Kc8H 12. Kxa5H Kd8H 13. Ka6H &#40;119360&#41;
 19/20        0.057     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kc4 Kb6 10. Kd3 Ka7H 11. Kd2H Kb8H 12. Kc3H &#40;122416&#41;
&#91;19/20&#93;       0.059     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kc4 Kb6 10. Kd3 Ka7H 11. Kd2H Kb8H 12. Kc3H &#40;127243&#41;
 20/22        0.060     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Kb6 9. Kb3 Ka7 10. Kb2 Kb8 11. Kc3H &#40;129328&#41;
&#91;20/22&#93;       0.061     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Kb6 9. Kb3 Ka7 10. Kb2 Kb8 11. Kc3H &#40;131890&#41;
 21/22        0.082     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc4 Kb6 9. Kc3 Ka6 10. Kc4 Kb6 11. Kd3 Ka7H 12. Ke3H Kb8H 13. Kf2H Kb7H 14. Kg3H Kc8H 15. Kh4H Kb7H 16. Kg5H Ka7H 17. Kxf5H &#40;167913&#41;
&#91;21/22&#93;       0.084     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc4 Kb6 9. Kc3 Ka6 10. Kc4 Kb6 11. Kd3 Ka7H 12. Ke3H Kb8H 13. Kf2H Kb7H 14. Kg3H Kc8H 15. Kh4H Kb7H 16. Kg5H Ka7H 17. Kxf5H &#40;172568&#41;
 22/24        0.126     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kb3 Kb7 10. Kb2 Ka7 11. Kb3 Kb8 12. Kc4H Kb7H 13. Kb5H Kc8H 14. Kxa5H Kd8H 15. Ka6H &#40;248526&#41;
&#91;22/24&#93;       0.139     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Kb6 4. Kc2 Kc7 5. Kd3 Kb7 6. Kc3 Ka7 7. Kd3 Kb7 8. Kc3 Ka7 9. Kb3 Kb7 10. Kb2 Ka7 11. Kb3 Kb8 12. Kc4H Kb7H 13. Kb5H Kc8H 14. Kxa5H Kd8H 15. Ka6H &#40;276954&#41;
 23/26        0.309     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka6 4. Kc3 Kb7 5. Kb3 Kb6 6. Kc4 Ka6 7. Kd3 Kb7 8. Ke2 Kb8 9. Kd2 Ka7 10. Kd3 Kb7 11. Kc4 Kb6 12. Kd3 Kc7H 13. Kc4H Kb6H &#40;634811&#41;
&#91;23/26&#93;       0.338     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka6 4. Kc3 Kb7 5. Kb3 Kb6 6. Kc4 Ka6 7. Kd3 Kb7 8. Ke2 Kb8 9. Kd2 Ka7 10. Kd3 Kb7 11. Kc4 Kb6 12. Kd3 Kc7H 13. Kc4H Kb6H &#40;699513&#41;
 24/26        0.767     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Kb8 5. Kc3 Kb7 6. Kb3 Ka6 7. Kc2 Kb6 8. Kd2 Kc7 9. Kd3 Kb7 10. Ke2 Kb8 11. Kd1 Kc8 12. Kd2 Kd8 13. Kd3H Kc7H 14. Kc4H Kb6H 15. Kc3H Ka6H 16. Kb3H Kb6H 17. Kc4H Ka6H 18. Kd3H Kb7H &#40;1707889&#41;
&#91;24/26&#93;       0.769     +0.99   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Kb8 5. Kc3 Kb7 6. Kb3 Ka6 7. Kc2 Kb6 8. Kd2 Kc7 9. Kd3 Kb7 10. Ke2 Kb8 11. Kd1 Kc8 12. Kd2 Kd8 13. Kd3H Kc7H 14. Kc4H Kb6H 15. Kc3H Ka6H 16. Kb3H Kb6H 17. Kc4H Ka6H 18. Kd3H Kb7H &#40;1713305&#41;
 25/28        3.052     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Kb8 5. Kc3 Kb7 6. Kb3 Ka7 7. Kc4 Kb6 8. Kd3 Kc7 9. Kd2 Kd8 10. Kc3 Kc7 11. Kb3 Kb7 12. Kc4 Kb6 13. Kd3 Kc7H &#40;7127555&#41;
&#91;25/28&#93;       3.054     +0.98   1. Kb2 Kb8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Kb8 5. Kc3 Kb7 6. Kb3 Ka7 7. Kc4 Kb6 8. Kd3 Kc7 9. Kd2 Kd8 10. Kc3 Kc7 11. Kb3 Kb7 12. Kc4 Kb6 13. Kd3 Kc7H &#40;7131532&#41;
 26/30        5.891     +0.99   1. Kb2 Ka8 2. Kc3 Kb7 3. Kb3 Ka7 4. Kb2 Ka8 5. Kc3 Kb7 6. Kb3 Ka7 7. Kc4 Kb6 8. Kd3 Kc7 9. Kc4 Kb6 10. Kd3 Kc7 11. Kd2 Kc8 12. Ke3 Kd8 13. Kd2 Kc7 14. Kd3H Kb7H 15. Ke2H Kb8H 16. Kf2H Kb7H 17. Kg3H Kc8H 18. Kh4H Kb7H 19. Kg5H Ka7H 20. Kxf5H &#40;13104977&#41;
 26/30        5.987     +2.57   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc8 7. Kf2 Kd8 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kg7 11. Kg5 Kh8 12. Kxf5 Kh7 13. Kf6 Kh6 14. Kf7H &#40;13312204&#41;
&#91;26/30&#93;       5.990     +2.57   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kc8 7. Kf2 Kd8 8. Kg3 Ke7 9. Kh4 Kf6 10. Kh5 Kg7 11. Kg5 Kh8 12. Kxf5 Kh7 13. Kf6 Kh6 14. Kf7H &#40;13318697&#41;
 27/32        6.256     +1.36   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kb8 7. Kf2 Kb7 8. Kg3 Kc8 9. Kh4 Kb7 10. Kg5 Ka7 11. Kxf5 Kb8 12. Kf6 Kb7 13. Kf7 Kc7 14. Kf8 Kd7H &#40;13953590&#41;
&#91;27/32&#93;       6.261     +1.36   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke2 Kb8 7. Kf2 Kb7 8. Kg3 Kc8 9. Kh4 Kb7 10. Kg5 Ka7 11. Kxf5 Kb8 12. Kf6 Kb7 13. Kf7 Kc7 14. Kf8 Kd7H &#40;13965358&#41;
 28/32        9.874     +2.57   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc8 5. Kd2 Kd7 6. Kc3 Kc7 7. Kd3 Kb7 8. Ke2 Kc8 9. Kf2 Kd8 10. Kg3 Ke7 11. Kh4 Kf8 12. Kg5 Kg7 13. Kxf5 Kh7 14. Kf6 Kh6 15. Kf7H &#40;21691050&#41;
&#91;28/32&#93;       9.875     +2.57   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc8 5. Kd2 Kd7 6. Kc3 Kc7 7. Kd3 Kb7 8. Ke2 Kc8 9. Kf2 Kd8 10. Kg3 Ke7 11. Kh4 Kf8 12. Kg5 Kg7 13. Kxf5 Kh7 14. Kf6 Kh6 15. Kf7H &#40;21691739&#41;
 29/37       13.679     +2.14   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke3 Kc8 7. Kd2 Kd7 8. Kc3 Kc8 9. Kc4 Kb8 10. Kb5 Kb7 11. Kxa5 Ka7 12. Kb5 Kb7 13. a5 Kc7 14. Kc4 Kb7 15. Kd3 Ka8H &#40;29803504&#41;
&#91;29/37&#93;      13.773     +2.14   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke3 Kc8 7. Kd2 Kd7 8. Kc3 Kc8 9. Kc4 Kb8 10. Kb5 Kb7 11. Kxa5 Ka7 12. Kb5 Kb7 13. a5 Kc7 14. Kc4 Kb7 15. Kd3 Ka8H &#40;30013132&#41;
exit
&#91;30/37&#93;      20.912     +2.14   1. Kb1 Kb8 2. Kc2 Kc8 3. Kd2 Kd7 4. Kc3 Kc7 5. Kd3 Kb7 6. Ke3 Kc8 7. Kd2 Kd7 8. Kc3 Kc8 9. Kc4 Kb8 10. Kb5 Kb7 11. Kxa5 Ka7 12. Kb5 Kb7 13. a5 Kc7 14. Kc4 Kb7 15. Kd3 Ka8H &#40;44954551&#41;
I don't know what's happening at ply 27, and it's still rather slow, but it's finding it. Yes, it's slower in this position with SPDH, but it's _adjustable_. You can turn it off in endgames like this, or you can make the path hashkey only based on the fifty move counter.

I'm glad, at least, that this one position totally kills any interest in the idea... :roll:
1. still looks fishy as this should be solved prior to depth=26. At least every program I have ever tried solves it sooner. Although this might not mean much as when I just tried Crafty it found the Kb1 fail high at depth=25 with the particular hash size I used...

2. speed looks funny as well... Crafty finishes depth 30 in 1/2 second using one 2.0ghz core-2 processor...

3. This one position does not make me uninterested. The very idea of not using available hash information is what I don't like. Solving a very infrequent problem by making a change that affects each and every other move negatively is my issue with this idea... not to mention the cost involved in a second path signature...

BTW, under what possible circumstance could using a null-move in a pawn only ending ever be a good idea? king and pawn endings are all about zugzwang, which makes null-move useless. I would not consider using null-move with king and pawns only, as the verified version is going to have to verify almost every such search and increase the cost rather than helping.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Semi-Path Dependent Hashing: a semi-useless idea.

Post by Zach Wegner » Sun May 25, 2008 9:02 pm

bob wrote:3. This one position does not make me uninterested. The very idea of not using available hash information is what I don't like. Solving a very infrequent problem by making a change that affects each and every other move negatively is my issue with this idea... not to mention the cost involved in a second path signature...
But once again you seem to overlook that a certain implementation of this idea solves your fifty-move problem in a more correct way (i.e. not invalidating some valid entries that you would) and without the cost of running through the entire hash table.

This costs a few instructions total, and there are no other side effects. Middle game positions would work exactly the same as before.

Post Reply