Any good positions to test hash tables?

bob · Post by **bob** » Tue Jan 04, 2011 11:31 pm

JVMerlino wrote:
bob wrote:
Mark wrote:Just implemented hash tables in my program. While I can now solve Fine #70, I'm not really seeing any improvements in the wac test suite. My eval is basically material and piece-square tables.

Are there any other good positions or test suites to see if my hash is working correctly?

Thanks!
Fine is a really good test. You should hit depths of 30+ instantly if it is working. Hashing should help on other positions once you have a "best move" stored to improve your move ordering. That should be a measurable gain in terms of getting to a specific depth quicker...
Really "instantly"? My engine takes about 3.6 seconds to reach depth 30, although it finds Kb1 at depth 22 in about 0.2 seconds.

jm

yep

some examples on my laptop, using just one CPU:

Code: Select all

               39->   0.22   2.74   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. Kh5 Kf6 15. Kg4 Ke7 16. Kf3 Kf7
                                    17. Ke4 Ke7 18. Ke3 Kf7 19. Kf4 Kf6
                                    20. Ke4
               43->   0.88   6.07   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Kf8 22. Ke6
               44->   1.01   6.23   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Ke8 22. Ke6 Kf8
               48->  18.58  13.30   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. f7+ Kf8 21. Kxd6 Kxf7 22. Kc7 Kf6
                                    23. d6 Ke6 24. d7 Kd5 25. d8=Q+ Kc4

michiguel · Post by **michiguel** » Tue Jan 04, 2011 11:45 pm

bob wrote:

JVMerlino wrote:
bob wrote:
Mark wrote:Just implemented hash tables in my program. While I can now solve Fine #70, I'm not really seeing any improvements in the wac test suite. My eval is basically material and piece-square tables.

Are there any other good positions or test suites to see if my hash is working correctly?

Thanks!
Fine is a really good test. You should hit depths of 30+ instantly if it is working. Hashing should help on other positions once you have a "best move" stored to improve your move ordering. That should be a measurable gain in terms of getting to a specific depth quicker...
Really "instantly"? My engine takes about 3.6 seconds to reach depth 30, although it finds Kb1 at depth 22 in about 0.2 seconds.

jm

yep

some examples on my laptop, using just one CPU:

Code: Select all

               39->   0.22   2.74   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. Kh5 Kf6 15. Kg4 Ke7 16. Kf3 Kf7
                                    17. Ke4 Ke7 18. Ke3 Kf7 19. Kf4 Kf6
                                    20. Ke4
               43->   0.88   6.07   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Kf8 22. Ke6
               44->   1.01   6.23   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Ke8 22. Ke6 Kf8
               48->  18.58  13.30   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. f7+ Kf8 21. Kxd6 Kxf7 22. Kc7 Kf6
                                    23. d6 Ke6 24. d7 Kd5 25. d8=Q+ Kc4

I do not think time to reach 30 plies is a fair test to check whether the tables are working properly. I am sure that Crafty's knowledge and pruning is more advanced than Myrddin. That will contribute a lot to quickly advance through the iterations.

A search with material only and no pruning will make more sense to check whether the HT is working properly. Jon's numbers do not seem to be bad. In addition, time should not be compared, but nodes. Crafty is particularly fast.

Miguel

JVMerlino · Post by **JVMerlino** » Wed Jan 05, 2011 4:37 am

michiguel wrote:
bob wrote:
JVMerlino wrote:
bob wrote:
Mark wrote:Just implemented hash tables in my program. While I can now solve Fine #70, I'm not really seeing any improvements in the wac test suite. My eval is basically material and piece-square tables.

Are there any other good positions or test suites to see if my hash is working correctly?

Thanks!
Fine is a really good test. You should hit depths of 30+ instantly if it is working. Hashing should help on other positions once you have a "best move" stored to improve your move ordering. That should be a measurable gain in terms of getting to a specific depth quicker...
Really "instantly"? My engine takes about 3.6 seconds to reach depth 30, although it finds Kb1 at depth 22 in about 0.2 seconds.

jm
yep

some examples on my laptop, using just one CPU:
Code: Select all
               39->   0.22   2.74   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. Kh5 Kf6 15. Kg4 Ke7 16. Kf3 Kf7
                                    17. Ke4 Ke7 18. Ke3 Kf7 19. Kf4 Kf6
                                    20. Ke4
               43->   0.88   6.07   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Kf8 22. Ke6
               44->   1.01   6.23   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Ke8 22. Ke6 Kf8
               48->  18.58  13.30   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. f7+ Kf8 21. Kxd6 Kxf7 22. Kc7 Kf6
                                    23. d6 Ke6 24. d7 Kd5 25. d8=Q+ Kc4
I do not think time to reach 30 plies is a fair test to check whether the tables are working properly. I am sure that Crafty's knowledge and pruning is more advanced than Myrddin. That will contribute a lot to quickly advance through the iterations.

A search with material only and no pruning will make more sense to check whether the HT is working properly. Jon's numbers do not seem to be bad. In addition, time should not be compared, but nodes. Crafty is particularly fast.

Miguel

As it turns out, the version I was using to report those times was broken. Here's what the version I've sent to Leo for WBEC reports:

20 84 12 31355 a1b2 a7b6 b2c3 b6b7 c3c4 b7b6 c4c3
21 84 15 45714 a1b2 a7a8 b2c2 a8b8 c2c3 b8b7
21 109 18 53527 a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f7 d3c4 f7g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6e6 f4g4 d5d6
22 105 20 58344 a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f7 d3c4 f7g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6e6 f4g4 d5d6 g4f4
23 105 25 78700 a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7d8 c2c3 d8c7 c3d3 c7b7 d3e2 b7c7 e2d3 c7b6 d3c4 b6a6 c4d3 a6b6 d3e2 b6c7 e2d1
24 145 28 90817 a1b1!
24 188 34 135752 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2f2 b8c7 f2g3 c7d7 g3h4 d7d8 h4g5 d8e7 g5f5 e7f7
25 197 40 160273 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2f2 b8c7 f2g3 c7d7 g3h4 d7d8 h4g5 d8e7 g5f5 e7f7 f5g5 f7f8 f4f5 f8g7 f5f6 g7g8
26 197 51 201953 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2e3 b8c7 e3d3 c7d7 d3c4 d7c7 c4b3 c7d7 b3c4 d7c7 c4b3
27 198 64 267235 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2f2 b8c7 f2g3 c7d7 g3h4 d7e7 h4g5 e7f7 g5f5 f7e7
28 198 76 315454 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2f2 b8c7 f2g3 c7d7 g3h4 d7e7 h4g5 e7f7 g5f5 f7e7 f5g5 e7e8 g5f6 e8d7 f6f5
29 199 99 399507 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7g8 g5g6 g8f8
30 199 117 477278 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7e8 g5g6 e8d7 g6f5 d7c7
31 199 145 608653 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8
32 201 232 949861 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8
33 201 316 1296102 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g6 f8g8 g6h5 g8h8 h5g5 h8h7 g5f5
34 201 542 2252444 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g6 f8g8 g6h5 g8h8 h5g5 h8h7 g5f5 h7g8
35 241 989 4039459 a1b1!
35 201 1115 4632753 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5e4 f7g6 e4f3 g6g7 f4f5 g7f6 f3g4 f6f7 g4g5
36 241 1586 6324885 a1b1!
36 201 1723 6852771 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b6 d3c4 b6a6 c4d3 a6b6 d3e2 b6c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5e4
37 201 2513 9571800 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b6 d3c4 b6a6 c4d3 a6b6
38 241 4602 17051040 a1b1!
38 301 7753 29476891 a1b1 a7b7 b1c1 b7c7 c1d1 c7b8 d1e2 b8c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5e4 f7g6 e4d3 g6f5 d3c4 f5e4 c4b5 e4d4 b5c6 d4e4 c6d6 e4f5 d6c5 f5f6 d5d6 f6f7 c5b5 f7e6
39 341 11257 42042398 a1b1!
39 326 12447 46032585 a1b1 a7b7 b1c1 b7c8 c1d2 c8c7 d2d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5e4 f7f8 e4e3 f8g7 e3d3 g7g6 d3e4
40 366 12464 46114594 a1b1!
40 286 12486 46253606 a1b1? a7b7
40 254 12586 46816286 a1b1 a7b7 b1c1 b7c7 c1d2 c7d7 d2c3 d7c7 c3c4 c7b6 c4d3 b6c7 d3c4 c7b6 c4d3 b6c7 d3e2 c7d7 e2f2 d7e7 f2e2 e7f7 e2d3 f7g6 d3c4 g6h5 c4b5 h5g4 b5c6 g4f4 c6d6 f4e4 d6c5 f5f4 d5d6 f4f3 d6d7 f3f2 d7d8Q f2f1Q d8a5

So, 1.17 seconds to reach depth 30 is not exactly Crafty speed, but much better than previously reported.

jm

Mark · Post by **Mark** » Wed Jan 05, 2011 7:41 pm

hgm wrote:
Mark wrote:Thanks! I must have a problem since I'm not getting any improvement in the opening position.
Are you sure yo suppress e.p. rights when there is no enemy Pawn next to the one that just moved? In the opening position ignoring this is very detrimental for hit rate

I'm pretty sure I've got the ep rights covered, since I loop through the whole board to generate the key when I need it! I'll change that to an incremental update this weekend. My son is home for winter break from college and he made a few suggested changes to my code. Now from the opening position, with hash on I get to 11 ply in 40% of the nodes and to 12 ply in 25% of the nodes (compared to hash off), so the hash seems to be working now.

Mark · Post by **Mark** » Wed Jan 05, 2011 9:03 pm

JVMerlino wrote:
bob wrote:
Mark wrote:Just implemented hash tables in my program. While I can now solve Fine #70, I'm not really seeing any improvements in the wac test suite. My eval is basically material and piece-square tables.

Are there any other good positions or test suites to see if my hash is working correctly?

Thanks!
Fine is a really good test. You should hit depths of 30+ instantly if it is working. Hashing should help on other positions once you have a "best move" stored to improve your move ordering. That should be a measurable gain in terms of getting to a specific depth quicker...

Really "instantly"? My engine takes about 3.6 seconds to reach depth 30, although it finds Kb1 at depth 22 in about 0.2

Mark:
It also took me .2 seconds to see Kb1, but 75 seconds to reach 30 ply. The times seem pretty sensitive to the hash seed. If I randomize the hash seed, the times jump around a lot: up to 9 seconds to see Kb1 sometimes...

bob · Post by **bob** » Wed Jan 05, 2011 10:20 pm

michiguel wrote:
bob wrote:
JVMerlino wrote:
bob wrote:
Mark wrote:Just implemented hash tables in my program. While I can now solve Fine #70, I'm not really seeing any improvements in the wac test suite. My eval is basically material and piece-square tables.

Are there any other good positions or test suites to see if my hash is working correctly?

Thanks!
Fine is a really good test. You should hit depths of 30+ instantly if it is working. Hashing should help on other positions once you have a "best move" stored to improve your move ordering. That should be a measurable gain in terms of getting to a specific depth quicker...
Really "instantly"? My engine takes about 3.6 seconds to reach depth 30, although it finds Kb1 at depth 22 in about 0.2 seconds.

jm
yep

some examples on my laptop, using just one CPU:
Code: Select all
               39->   0.22   2.74   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. Kh5 Kf6 15. Kg4 Ke7 16. Kf3 Kf7
                                    17. Ke4 Ke7 18. Ke3 Kf7 19. Kf4 Kf6
                                    20. Ke4
               43->   0.88   6.07   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Kf8 22. Ke6
               44->   1.01   6.23   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Ke8 22. Ke6 Kf8
               48->  18.58  13.30   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. f7+ Kf8 21. Kxd6 Kxf7 22. Kc7 Kf6
                                    23. d6 Ke6 24. d7 Kd5 25. d8=Q+ Kc4
I do not think time to reach 30 plies is a fair test to check whether the tables are working properly. I am sure that Crafty's knowledge and pruning is more advanced than Myrddin. That will contribute a lot to quickly advance through the iterations.

A search with material only and no pruning will make more sense to check whether the HT is working properly. Jon's numbers do not seem to be bad. In addition, time should not be compared, but nodes. Crafty is particularly fast.

Miguel

I've not seen any program that doesn't get to 30+ instantly on modern hardware. It is certainly possible to not do this if you use a very slow language or implementation. Null-move doesn't help since there are no pieces. Reductions and forward pruning help, but still, 30 plies should go by pretty quickly I would think...

bob · Post by **bob** » Wed Jan 05, 2011 10:20 pm

JVMerlino wrote:
michiguel wrote:
bob wrote:
JVMerlino wrote:
bob wrote:
Mark wrote:Just implemented hash tables in my program. While I can now solve Fine #70, I'm not really seeing any improvements in the wac test suite. My eval is basically material and piece-square tables.

Are there any other good positions or test suites to see if my hash is working correctly?

Thanks!
Fine is a really good test. You should hit depths of 30+ instantly if it is working. Hashing should help on other positions once you have a "best move" stored to improve your move ordering. That should be a measurable gain in terms of getting to a specific depth quicker...
Really "instantly"? My engine takes about 3.6 seconds to reach depth 30, although it finds Kb1 at depth 22 in about 0.2 seconds.

jm
yep

some examples on my laptop, using just one CPU:
Code: Select all
               39->   0.22   2.74   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. Kh5 Kf6 15. Kg4 Ke7 16. Kf3 Kf7
                                    17. Ke4 Ke7 18. Ke3 Kf7 19. Kf4 Kf6
                                    20. Ke4
               43->   0.88   6.07   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Kf8 22. Ke6
               44->   1.01   6.23   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. Kxd6 Kf7 21. Ke5 Ke8 22. Ke6 Kf8
               48->  18.58  13.30   1. Kb1 Kb7 2. Kc1 Kc7 3. Kd1 Kd7 4.
                                    Kc2 Kc7 5. Kd3 Kb7 6. Ke3 Kc7 7. Kf3
                                    Kd7 8. Kg3 Ke7 9. Kh4 Kf7 10. Kg5 Kg7
                                    11. Kxf5 Kf7 12. Kg5 Kg7 13. f5 Kf7
                                    14. f6 Kf8 15. Kg4 Kg8 16. Kf4 Kf8
                                    17. Kg5 Kf7 18. Kf5 Kf8 19. Ke6 Ke8
                                    20. f7+ Kf8 21. Kxd6 Kxf7 22. Kc7 Kf6
                                    23. d6 Ke6 24. d7 Kd5 25. d8=Q+ Kc4
I do not think time to reach 30 plies is a fair test to check whether the tables are working properly. I am sure that Crafty's knowledge and pruning is more advanced than Myrddin. That will contribute a lot to quickly advance through the iterations.

A search with material only and no pruning will make more sense to check whether the HT is working properly. Jon's numbers do not seem to be bad. In addition, time should not be compared, but nodes. Crafty is particularly fast.

Miguel
As it turns out, the version I was using to report those times was broken. Here's what the version I've sent to Leo for WBEC reports:

20 84 12 31355 a1b2 a7b6 b2c3 b6b7 c3c4 b7b6 c4c3
21 84 15 45714 a1b2 a7a8 b2c2 a8b8 c2c3 b8b7
21 109 18 53527 a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f7 d3c4 f7g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6e6 f4g4 d5d6
22 105 20 58344 a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f7 d3c4 f7g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6e6 f4g4 d5d6 g4f4
23 105 25 78700 a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7d8 c2c3 d8c7 c3d3 c7b7 d3e2 b7c7 e2d3 c7b6 d3c4 b6a6 c4d3 a6b6 d3e2 b6c7 e2d1
24 145 28 90817 a1b1!
24 188 34 135752 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2f2 b8c7 f2g3 c7d7 g3h4 d7d8 h4g5 d8e7 g5f5 e7f7
25 197 40 160273 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2f2 b8c7 f2g3 c7d7 g3h4 d7d8 h4g5 d8e7 g5f5 e7f7 f5g5 f7f8 f4f5 f8g7 f5f6 g7g8
26 197 51 201953 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2e3 b8c7 e3d3 c7d7 d3c4 d7c7 c4b3 c7d7 b3c4 d7c7 c4b3
27 198 64 267235 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2f2 b8c7 f2g3 c7d7 g3h4 d7e7 h4g5 e7f7 g5f5 f7e7
28 198 76 315454 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7b8 e2f2 b8c7 f2g3 c7d7 g3h4 d7e7 h4g5 e7f7 g5f5 f7e7 f5g5 e7e8 g5f6 e8d7 f6f5
29 199 99 399507 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7g8 g5g6 g8f8
30 199 117 477278 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7e8 g5g6 e8d7 g6f5 d7c7
31 199 145 608653 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8
32 201 232 949861 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8
33 201 316 1296102 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g6 f8g8 g6h5 g8h8 h5g5 h8h7 g5f5
34 201 542 2252444 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5g5 f7g7 f4f5 g7f7 f5f6 f7f8 g5g6 f8g8 g6h5 g8h8 h5g5 h8h7 g5f5 h7g8
35 241 989 4039459 a1b1!
35 201 1115 4632753 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5e4 f7g6 e4f3 g6g7 f4f5 g7f6 f3g4 f6f7 g4g5
36 241 1586 6324885 a1b1!
36 201 1723 6852771 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b6 d3c4 b6a6 c4d3 a6b6 d3e2 b6c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f7 h4g5 f7g7 g5f5 g7f7 f5e4
37 201 2513 9571800 a1b1 a7a8 b1b2 a8b7 b2c3 b7c7 c3d3 c7b6 d3c4 b6a6 c4d3 a6b6
38 241 4602 17051040 a1b1!
38 301 7753 29476891 a1b1 a7b7 b1c1 b7c7 c1d1 c7b8 d1e2 b8c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5e4 f7g6 e4d3 g6f5 d3c4 f5e4 c4b5 e4d4 b5c6 d4e4 c6d6 e4f5 d6c5 f5f6 d5d6 f6f7 c5b5 f7e6
39 341 11257 42042398 a1b1!
39 326 12447 46032585 a1b1 a7b7 b1c1 b7c8 c1d2 c8c7 d2d3 c7b7 d3e2 b7c7 e2f2 c7d7 f2g3 d7e7 g3h4 e7f6 h4h5 f6f7 h5g5 f7g7 g5f5 g7f7 f5e4 f7f8 e4e3 f8g7 e3d3 g7g6 d3e4
40 366 12464 46114594 a1b1!
40 286 12486 46253606 a1b1? a7b7
40 254 12586 46816286 a1b1 a7b7 b1c1 b7c7 c1d2 c7d7 d2c3 d7c7 c3c4 c7b6 c4d3 b6c7 d3c4 c7b6 c4d3 b6c7 d3e2 c7d7 e2f2 d7e7 f2e2 e7f7 e2d3 f7g6 d3c4 g6h5 c4b5 h5g4 b5c6 g4f4 c6d6 f4e4 d6c5 f5f4 d5d6 f4f3 d6d7 f3f2 d7d8Q f2f1Q d8a5
So, 1.17 seconds to reach depth 30 is not exactly Crafty speed, but much better than previously reported.

jm

That looks more reasonable, so good find.

bob · Post by **bob** » Wed Jan 05, 2011 10:22 pm

Mark wrote:
JVMerlino wrote:
bob wrote:
Mark wrote:Just implemented hash tables in my program. While I can now solve Fine #70, I'm not really seeing any improvements in the wac test suite. My eval is basically material and piece-square tables.

Are there any other good positions or test suites to see if my hash is working correctly?

Thanks!
Fine is a really good test. You should hit depths of 30+ instantly if it is working. Hashing should help on other positions once you have a "best move" stored to improve your move ordering. That should be a measurable gain in terms of getting to a specific depth quicker...

Really "instantly"? My engine takes about 3.6 seconds to reach depth 30, although it finds Kb1 at depth 22 in about 0.2

Mark:
It also took me .2 seconds to see Kb1, but 75 seconds to reach 30 ply. The times seem pretty sensitive to the hash seed. If I randomize the hash seed, the times jump around a lot: up to 9 seconds to see Kb1 sometimes...
This is not so much about finding Kb1 as getting to depth 30. If you have optimal move ordering, this will take to depth 26 or so to find Kb1. If your move ordering is worse, then you will actually find it at a shallower depth due to search grafting. I can explain how if you are interested. But John now gets to depth 30 in 1 second or so which seems reasonable...

JVMerlino · Post by **JVMerlino** » Wed Jan 05, 2011 10:31 pm

bob wrote:This is not so much about finding Kb1 as getting to depth 30. If you have optimal move ordering, this will take to depth 26 or so to find Kb1. If your move ordering is worse, then you will actually find it at a shallower depth due to search grafting. I can explain how if you are interested. But John now gets to depth 30 in 1 second or so which seems reasonable...

Ok, since Myrddin finds Rb1 at depth 21, I'm now very curious to know why this is possibly a bad thing.

Move ordering in Myrddin is, like the rest of the engine, fairly primitive. But it does use history and killers, plus has the normal move-type ordering:

PV move
Hash move
Capture (MVV/LVA), with killers after good captures and before bad captures
Checks
Quiet moves

jm

bob · Post by **bob** » Wed Jan 05, 2011 11:13 pm

JVMerlino wrote:
bob wrote:This is not so much about finding Kb1 as getting to depth 30. If you have optimal move ordering, this will take to depth 26 or so to find Kb1. If your move ordering is worse, then you will actually find it at a shallower depth due to search grafting. I can explain how if you are interested. But John now gets to depth 30 in 1 second or so which seems reasonable...
Ok, since Myrddin finds Rb1 at depth 21, I'm now very curious to know why this is possibly a bad thing.

Move ordering in Myrddin is, like the rest of the engine, fairly primitive. But it does use history and killers, plus has the normal move-type ordering:

PV move
Hash move
Capture (MVV/LVA), with killers after good captures and before bad captures
Checks
Quiet moves

jm

OK, here is how you find the solution.

I assume you have looked at the position and PV carefully and understand that with best play by both sides, this position requires 13 non-capturing/non-checking moves by each side, and on the 27th ply (first ply of q-search) white finally captures a pawn. I think this is covered in Newborn's book on computer chess where he talks about his endgame-specific program called "peasant"...

In 21 plies you can't possibly win a pawn, so how does the search see it?

Suppose your move ordering for black is really bad, so that at each ply white makes a good move and black makes a lousy move. By the time you get to (say) depth 19, which discovers it can win a pawn. But that is not so useful, since black gets opportunities at each ply to find better moves to improve it's score, right? But along comes the hash table and along that PV you store the result that says "if I can reach this position, I win a pawn". And while with best play by both sides, you can't force the win of a pawn, you will discover that with best play by both sides you _can_ reach one of those positions where you found you win a pawn if black had played poorly. You graft that score onto the current position. Suppose we are at ply=21 for white, and from this position it takes another 6 plies to win the pawn. With a depth=21 search, you can't see this. But if black played like a patzer, you might have reached this position at depth=12 and saw "aha, I win a pawn." Now with best play you force that position (that you saw at ply=12) to happen, and remember you were still doing a 21 ply search, so that you searched 9 plies further and spotted the pawn win. Now at depth=21, you forced the game to reach that position you previously encountered at depth=12, and use that hash entry. Which, by the way, has a "draft" of 9 plies don't forget. You graft that onto the current 21 ply search, and actually pull off a 30 ply search on iteration 21, and spot the win.

If you had not first searched lousy moves for black, then you would not know that position is won, and your 21 ply search would still show Kb2 as the best move and white simply a single pawn ahead, as in the starting position.

Ugly, but effective.

Bob

Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?

Re: Any good positions to test hash tables?