Any good positions to test hash tables?

[Michel]

GnuChess (with table bases disabled) needs zero seconds to see the win!

Code: Select all

1 316 0 2  Ke5!
1 316 0 4  Ke5
1 327 0 6  Kd5
2 315 0 28  Kd6 Kd8
3 321 0 52  Kd6 Kd8 Kd5
4 309 0 160  Ke5 Kd8 Kd6 Kc8
5 311 0 312  Ke5 Kc7 Kd5 Kd8 Kd4
6 295 0 593  Ke5 Kd8 Kd6 Kc8 c7 Kb7
7 289 0 931  Ke5 Kd8 Kd6 Kc8 c7 Kb7 Kd7
8 310 0 1448  Ke5 Kc7 Kd5 Kc8 Ke6 Kc7 Ke5 Kd8
9 309 0 2206  Ke5 Kc7 Kd5 Kc8 Ke6 Kc7 Ke5 Kb8 Kd6 Kc8
10 321 0 3444  Ke5 Kc7 Kd5 Kc8 Ke6 Kc7 Ke5 Kc8 Kd6 Kd8 Kd5
11 468 0 5507  c7!
11 652 0 5533  c7!
11 677 0 5598  c7!
11 820 0 5673  c7!
11 865 0 5738  c7!
11 998 0 5832  c7!
11 1004 0 6187  c7 Kxc7 Ke7 Kc8 Kd6 Kb7 Kd7 Kb8 Kc6 Ka7 Kc7 Ka8 Kxb6 Kb8
12 349 0 8310  :-(
12 300 0 8756  :-(
12 1005 0 9815  c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Ka6 Kc7 Ka7 Kc8 b6

[jacobbl]

Hm...
This was a bit painful reading.
My engine (Sjakk) finds the solution at depth 19, but I think that's just luck, because the evaluation doesn't rise before depth 23. But what's nagging me is that I need 16,11 seconds to find it. And I'm using hash tables. I know my engine is slow (written in Visual Basic, and probably not a very good code either....), but on this test it's doing about 243 kN/s. If I understand you correctly I should have reached depth 23 much faster.

What am I doing wrong? Bugs in the hash tables? Bad move ordering? something else?

I'd be greatful for any sugestions.

[Chan Rasjid]

Hm...
This was a bit painful reading.
My engine (Sjakk) finds the solution at depth 19, but I think that's just luck, because the evaluation doesn't rise before depth 23. But what's nagging me is that I need 16,11 seconds to find it. And I'm using hash tables. I know my engine is slow (written in Visual Basic, and probably not a very good code either....), but on this test it's doing about 243 kN/s. If I understand you correctly I should have reached depth 23 much faster.

What am I doing wrong? Bugs in the hash tables? Bad move ordering? something else?

I'd be greatful for any sugestions.

Rule out minor things like move ordering or evaluation - I think only material matters. Very likely (as this is supposed to test TT hashing) it is a simple hash bug.

depth 19 score cp +302 time 395 msec nodes 70203 nps 177729 pv 1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kd8 4.Ke5 Kc7
depth 20 score cp +302 time 435 msec nodes 80327 nps 184659 pv 1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kd8 4.Ke5 Kc7
depth 21 score cp +803 time 606 msec nodes 176285 nps 290899 pv 1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kb7 4.Kd7 Kb8 5.Kc6 Kc8 6.Kxb6 Kd7 7.Kb7 Ke7 8.Kc8 Ke6 9.Kc7 Ke5 10.b6
depth 22 score cp +990 time 1324 msec nodes 796795 nps 601808 pv 1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kb7 4.Kd7 Kb8 5.Kc6 Ka7 6.Kc7 Ka8 7.Kxb6 Kb8 8.Ka6 Kc7 9.Ka7 Kd7 10.b6 Kd6 11.b7 Kc5 12.b8Q Kd5
depth 23 score cp +1005 time 1917 msec nodes 1539358 nps 803003 pv 1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kb7 4.Kd7 Kb8 5.Kc6 Ka7 6.Kc7 Ka8 7.Kxb6 Kb8 8.Ka6 Kc7 9.Ka7 Kd6 10.b6 Ke5 11.b7 Ke4 12.b8Q

My program Cowrie finds the correct move
c7 in 0.6 seconds at depth 21 with the score jumping from +3.0 to +8.0. The nps was not high, just 290000 nps.

I think Anthony Cozzie of Zappa once said chess programming is a struggle against bugs and my experience seems to convince me that it is so. I have tons of asserts and it troubles me if I cannot understand why they are triggered. I have to clear every single asserts before I am at ease to proceed - there is no motivation to try to get more elo when there are still uncleared bugs.

Unless one is an above average programmer, expect bugs in your program. The most important areas to debug:-
1) evaluation color symmetry test - a must- have.
2) following PV/ pv nodes and collecting the triangular pv[ply][ply].
3) collecting the best move - seems simple (just a single move) but critical and may be
bug-prone.

There are much more ways to introduce bugs than we can list.

Rasjid

[michiguel]

Hm...
This was a bit painful reading.
My engine (Sjakk) finds the solution at depth 19, but I think that's just luck, because the evaluation doesn't rise before depth 23. But what's nagging me is that I need 16,11 seconds to find it. And I'm using hash tables. I know my engine is slow (written in Visual Basic, and probably not a very good code either....), but on this test it's doing about 243 kN/s. If I understand you correctly I should have reached depth 23 much faster.

What am I doing wrong? Bugs in the hash tables? Bad move ordering? something else?

I'd be greatful for any sugestions.

We have to compare similar things. I disabled in Gaviota all the knowledge about kpk in search and eval (returns material only) to see exactly the effect of hashtable only.

I get the following

Code: Select all

tbuse off
setboard 2k5/8/1pP1K3/1P6/8/8/8/8 w - - 
force
sd 17
go
iterative deepening --> start, thread=0
set timer to 1000000.000000 , max_ply 17, panic time: 4999999.950000
        10   1:      0.0    +1.02  1.Kd5 [Q]
        34   2:      0.0    +1.02  1.Kd5 Kc7 [Q]
       115   3:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 [Q]
       265   4:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kd8 [Q]
       624   5:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kd8 3.Kd5 [Q]
      1325   6:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kd8 3.Kd4 Kc7 [Q]
      2291   7:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kd8 3.Kd4 Kc7 4.Kd5 [Q]
      2734   8       0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kd8 3.Kd4 Kc7 4.Kd5 Kd8
                                   [Q]
      3939   8:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kd8 3.Kd4 Kc7 4.Kd5 Kd8
                                   [Q]
      4782   9       0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Kd6 [Q]
      6213   9:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Kd6 [Q]
      7166  10       0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Kd6 Kd8 [Q]
      9210  10:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Kd6 Kd8 [Q]
     10312  11       0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Kd6 Kd8 6.c7+ Kc8 [Q]
     12822  11:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Kd6 Kd8 6.c7+ Kc8 [Q]
     15062  12       0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Ke5 Kd8 6.Kd6 Kc8 [Q]
     17185  12:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Ke5 Kd8 6.Kd6 Kc8 [Q]
     19804  13       0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Ke5 Kc7 6.Kd4 Kd8 7.Ke4 [Q]
     22221  13:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Ke5 Kc7 6.Kd4 Kd8 7.Ke4 [Q]
     25050  14       0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Ke5 Kc7 6.Kd4 Kd8 7.Ke4 Kc7 [Q]
     27628  14:      0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Ke5 Kc7 6.Kd4 Kd8 7.Ke4 Kc7 [Q]
     31908  15       0.0    +1.02  1.Kd5 Kc7 2.Ke5 Kc8 3.Kd4 Kc7 4.Kd5 Kc8
                                   5.Ke5 Kc7 6.Kd4 Kd8 7.Ke4 Kc7 8.Kf4 [Q]
     35763  15       0.0    +1.02  1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kd8 4.Kc6 Kc8
                                   5.Kxb6 Kb8 6.Ka6 Ka8 7.Kb6 Kb8
     36524  15:      0.1    +1.02  1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kd8 4.Kc6 Kc8
                                   5.Kxb6 Kb8 6.Ka6 Ka8 7.Kb6 Kb8
     37738  16       0.1      :-)  1.c7
     41160  16       0.1      :-)  1.c7
     43264  16       0.1      :-)  1.c7
     47586  16       0.1    +9.36  1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kd8 4.Kc6 Kc8
                                   5.Kxb6 Kb8 6.Ka6 Ka8 7.b6 Kb8 8.b7 Kc7
                                   9.Ka7 Kd8 [Q] 10.b8=Q+ Kd7
     48945  16:      0.1    +9.36  1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kd8 4.Kc6 Kc8
                                   5.Kxb6 Kb8 6.Ka6 Ka8 7.b6 Kb8 8.b7 Kc7
                                   9.Ka7 Kd8 [Q] 10.b8=Q+ Kd7
     52467  17       0.1    +9.36  1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kd8 4.Kc6 Kc8
                                   5.Kxb6 Kb8 6.Ka6 Ka8 7.b6 Kb8 8.b7 Kc7
                                   9.Ka7 Kd8 10.b8=Q+ [Q] Kd7
     53784  17:      0.1    +9.36  1.c7 Kxc7 2.Ke7 Kc8 3.Kd6 Kd8 4.Kc6 Kc8
                                   5.Kxb6 Kb8 6.Ka6 Ka8 7.b6 Kb8 8.b7 Kc7
                                   9.Ka7 Kd8 10.b8=Q+ [Q] Kd7

--------------------------------------------------------------------------
Score: 9.36 (2396)  Evals: 24114  Time: 0.1s  nps: 689538  Q/all: 0.05
hashtable attempts: 48967  hits: 92.9%  perfect: 54.5%
--------------------------------------------------------------------------

move c6c7
stats

HASH TABLE STATS
  Stores attempted       48535
  Stores overfilled          0
  Singles occupied        3475
  Singles maximum      4194304
  Hash memory filled      0.08 %

With material only, it is easy to see when the engine is "seeing" a real effect. In this case, it is at ply 16. Note in the hashtable stats, that very few slots are needed. Only 0.08% is filled of the 64 MB. That is 3475 distinct positions. With knowledge in, Gaviota sees this in 12 plies (~20 knodes). I think that Gnuchess may have special knowledge too (it sees it in 11 plies).

Test with a simple table that is "replace always" before trying anything more elaborated. That should work as well as any other complicated procedure. In fact, "replace always" worked better for me at the beginning of this week, when I was revamping the whole hash system. That was a red flag that I was doing something wrong. More later.

Miguel

[Michel]

I think that Gnuchess may have special knowledge too (it sees it in 11 plies).

Yes is has a kpk bitbase. This is obviously a great help in this position.

With a material only eval GnuChess sees c7 at ply 20 after 100k nodes and 0.05 seconds (the nps is much higher than usual with a mat only eval).

The hash table stats show a 92% hitrate.

Hash: Get=18834k Good=92% Put=4955k Coll= 2%

1 -100 0 2 Ke5
2 100 0 14 Ke5!
2 100 0 19 Ke5 Kc7
3 100 0 73 Kd6 Kd8 c7+ Kc8
4 100 0 133 Kd6 Kd8 Ke5 Kc8
5 0 0 419
5 0 0 478 Kd6 Kd8 c7+ Kc8 Ke5 Kxc7
6 0 0 601 Kd6 Kd8 c7+ Kc8 Ke5 Kxc7 Ke4
6 100 0 732 Ke5!
6 100 0 814 Ke5 Kc7 Ke4 Kd8 Kd4 Kc7
7 0 0 1460
7 0 0 1742 Kf6 Kd8 c7+ Kxc7 Ke5 Kc8 Kd6 Kd8
8 0 0 2323 Kf6 Kd8 c7+ Kxc7 Ke5 Kc8 Kd6 Kd8 Ke5 Kc7
8 100 0 2918 Kf5!
8 0 0 3026 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
9 0 0 3393 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
10 0 0 4314 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
11 0 1 5711 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
12 0 1 7827 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
13 0 1 10490 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
14 0 1 14539 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
15 0 1 19363 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
16 0 1 24377 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
17 0 2 29069 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
18 0 2 33896 Kf5 Kc7 Ke5 Kc8 Ke6 Kc7 Ke5
18 100 3 47674 Kd6!
18 0 3 50283 Kd6 Kd8 c7+ Kc8 Kd5 Kxc7 Ke6 Kc8 Kd6 Kd8 Kc6 Ke7 Kxb6 Ke6 Ka7 Kf6 b6 Kg5 b7 Kg4 b8=N
19 100 3 56669 Kd6!
19 350 3 59034 Kd6!
19 400 3 59419 Kd6!
19 550 3 59560 Kd6!
19 650 3 59723 Kd6!
19 700 3 60203 Kd6!
19 100 3 60785 Kd6 Kd8 c7+ Kc8 Kd5 Kxc7 Ke6 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Ka6 Ka8 b6 Kb8 b7 Kc7 Ka7 Kd7
20 700 4 81003 Kd6!
20 900 4 81172 Kd6!
20 950 5 89417 c7!
20 1000 5 93291 c7!
20 1050 5 97871 c7!
20 1100 5 97999 c7!
20 1100 5 102896 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Ka6 Ka8 b6 Kb8 b7 Kc7 Ka7 Kd7 b8=Q Ke7 Ka6 Kd7 Qb5+ Kc8

[gladius]

Wow, Garbochess JS failed miserably on this position, until I tested out your suggestion and moved to always replace. Then it solved it instantly.

Guess I have some work to do on my replacement strategy .

Code: Select all

Ply:1 Score:840 Nodes:11 NPS:733 Kf7
...
Ply:16 Score:905 Nodes:33211 NPS:203748 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Kc6 Kc8 b6 Kb8 b7
Ply:17 Score:905 Nodes:35258 NPS:208627 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Kc6 Kc8 b6 Kb8 b7
Ply:18 Score:10106 Nodes:75991 NPS:193854 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kd8 Ka7 Kd7 b6 Ke8 b7
...
Ply:30 Score:1999999 Nodes:8727824 NPS:317444 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Ka6 Kc7 b6+ Kc8 Ka7

[michiguel]

Wow, Garbochess JS failed miserably on this position, until I tested out your suggestion and moved to always replace. Then it solved it instantly.

Guess I have some work to do on my replacement strategy .

Code: Select all

Ply:1 Score:840 Nodes:11 NPS:733 Kf7
...
Ply:16 Score:905 Nodes:33211 NPS:203748 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Kc6 Kc8 b6 Kb8 b7
Ply:17 Score:905 Nodes:35258 NPS:208627 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Kc6 Kc8 b6 Kb8 b7
Ply:18 Score:10106 Nodes:75991 NPS:193854 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kd8 Ka7 Kd7 b6 Ke8 b7
...
Ply:30 Score:1999999 Nodes:8727824 NPS:317444 c7 Kxc7 Ke7 Kc8 Kd6 Kd8 Kc6 Kc8 Kxb6 Kb8 Ka6 Kc7 b6+ Kc8 Ka7

This may be the issue:

When you are going to store a position in the hashtable, see if that position is already there (i.e. same hash signature). If it is there with different information (possibly a lower depth), replace it on the spot, but DO NOT move the old one slot. The bottom line is, you do not want to have two slots filled with different information about the same position. In this endgame, this effect is devastating. In a middlegame it might not be a problem. Why? Here, you have very few distinctive positions that are evaluated over and over again. So, most positions flood the tables at the same slots and the half life of least frequent (but still important) positions is almost zero.

Miguel

[gladius]

This may be the issue:

When you are going to store a position in the hashtable, see if that position is already there (i.e. same hash signature). If it is there with different information (possibly a lower depth), replace it on the spot, but DO NOT move the old one slot. The bottom line is, you do not want to have two slots filled with different information about the same position. In this endgame, this effect is devastating. In a middlegame it might not be a problem. Why? Here, you have very few distinctive positions that are evaluated over and over again. So, most positions flood the tables at the same slots and the half life of least frequent (but still important) positions is almost zero.

Miguel

That was indeed the issue, thanks. I had that check in GarboChess 4, but had forgotten to use it in the JS version. Ah, all the little tricks that make so much difference .

[hgm]

It is hard to believe that the replacement scheme could have much todo with it. As you can see below, my new engine finds the solution after searching only 28k nodes. Even with 16-byte entries that corresponds to only 0.4MB hash, or 0.1% loading factor. There should be virtually no collisions.

Code: Select all

 24	+8.74	31417	0:00.11	c6c7 c8c7 e6e7 c7c8 e7d6 c8b7 d6d7 b7b8 d7c6 b8a7 c6c7 a7a8 c7b6 a8b8 b6a6 b8a8 b5b6 a8b8 b6b7
 23	+8.74	29132	0:00.10	c6c7 c8c7 e6e7 c7c8 e7d6 c8b7 d6d7
 22	+8.74	28187	0:00.10	c6c7 c8c7 e6e7 c7c8 e7d6 c8b7 d6d7 b7b8 d7c6
 21	+2.24	19135	0:00.08	e6d6 c8d8 d6e6 d8c7 e6e5 c7c8 e5e4 c8c7 e4d5 c7c8 d5e5 c8c7 e5e6
 20	+2.22	16238	0:00.07	e6d6 c8d8 d6e6 d8c7 e6e5 c7c8 e5e4 c8c7 e4d5
 19	+2.22	11789	0:00.06	e6d6 c8d8 d6e6 d8c7 e6e5 c7c8 e5e4 c8c7 e4d5
 18	+2.25	8491	0:00.05	e6e5 c8c7 e5d5 c7c8 d5d6 c8d8 d6e6 d8c7 e6e5 c7c8 e5d5 c8c7 d5e4 c7d8 e4f4 d8c7
 17	+2.25	6973	0:00.05	e6e5 c8c7 e5d5 c7c8 d5d6 c8d8 d6e6 d8c7
 16	+2.25	5503	0:00.05	e6e5 c8c7 e5d5 c7c8 d5e6 c8c7 e6e5 c7c8 e5d5 c8c7 d5e6 c7c8 e6d6 c8d8
 15	+2.29	3975	0:00.04	e6e5 c8c7 e5d5 c7c8 d5e6 c8c7 e6e5 c7c8 e5d5 c8c7 d5e6 c7c8 e6d6
 14	+2.29	3143	0:00.04	e6e5 c8c7 e5d5 c7c8 d5e6 c8c7 e6e5 c7c8 e5d5 c8c7 d5e6
 13	+2.32	2132	0:00.02	e6e5 c8c7 e5d5 c7c8 d5e6 c8c7
 12	+2.32	1742	0:00.02	e6e5 c8c7 e5d5 c7c8 d5e6 c8c7 e6e5
 11	+2.25	1283	0:00.02	e6d6 c8d8 d6d5 d8c7 d5e5 c7c8 e5e6 c8c7 e6d5 c7c8
 10	+2.25	1028	0:00.02	e6d6 c8d8 d6d5 d8c7 d5e5 c7c8 e5e6
  9	+2.25	719	0:00.02	e6d6 c8d8 d6d5 d8c7 d5e5 c7d8 e5e6
  8	+2.22	471	0:00.02	e6d6 c8d8 d6d5 d8c8 d5d4 c8c7
  7	+2.84	246	0:00.02	e6d6 c8d8 c6c7
  6	+2.83	163	0:00.00	e6d6 c8b8 d6d7 b8a7 c6c7
  5	+2.88	73	0:00.00	e6d6 c8d8
  4	+2.88	58	0:00.00	e6d6 c8d8 c6c7 d8c8
  3	+2.84	26	0:00.00	e6d6 c8d8 c6c7
  2	+2.25	15	0:00.00	e6d6 c8d8
  1	+2.35	5	0:00.00	e6e5
  1	+2.30	0	0:00.00	eval, dif=155, Pawns=75

[Chan Rasjid]

Maybe any replacement scheme would do the job as long as the scheme has no bug or serious flaw.

To have more than 1 slot storing the same position could be considered a serious bug. The correct way is always to test whether the position is already stored - if it is, then just replace if the current search with depth+type+etc has a higher priority.

Rasjid