Stress test for hashtable, checkmates, node counting.

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
michiguel
Posts: 6389
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Stress test for hashtable, checkmates, node counting.

Post by michiguel » Thu Apr 17, 2008 12:25 am

hgm wrote:

Code: Select all

tellics say     Joker 1.1.14 (f)
tellics say     Winboard version
tellics say     by H.G. Muller
tellics say     Hash size = 256MB

post
new
setboard 8/8/8/8/3k4/8/8/4K2R w - - 0 1
level 40 40 0
time 5000000
go
tell       - - - - - - - - - - - -
tell       - - - - - - - - - - - -
tell       - - . . . . . . . . - -
tell       - - . . . . . . . . - -
tell       - - . . . . . . . . - -
tell       - - . . . . . . . . - -
tell       - - . . . k . . . . - -
tell       - - . . . . . . . . - -
tell       - - . . . . . . . . - -
tell       - - . . . . K . . R - -
tell       - - - - - - - - - - - -
tell       - - - - - - - - - - - -

 1*     93        0          2  h1g1
 1*     99        0         14  e1f2
 1*    100        0         15  e1e2
 1     100        0         17  e1e2
 2*    100        0         24  e1e2 d4e5
 2     100        0         71  e1e2 d4e5
 3*     99        0        104  e1e2 d4e4 h1g1
 3*    100        1        381  e1d2 d4e4 d2c3
 3     100        1        394  e1d2 d4e4 d2c3
 4*    101        1        557  e1d2 d4e4 h1h4 e4e5 d2e3
 4     101        1       1316  e1d2 d4e4 h1h4 e4e5 d2e3
 5*    102        1       1874  e1d2 d4e4 d2c3 e4d5 h1e1 d5c5
 5     102        6       4195  e1d2 d4e4 d2c3 e4d5 h1e1 d5c5
 6*    104        6       5991  e1d2 d4e4 h1h4 e4f5 d2e3 f5e5 h4h5 e5d6
 6     104        8      10780  e1d2 d4e4 h1h4 e4f5 d2e3 f5e5 h4h5 e5d6
 7*    105        9      14836  e1d2 d4e4 h1h4 e4d5 d2e3 d5c5 e3e4 c5c4
 7     105       13      25856  e1d2 d4e4 h1h4 e4d5 d2e3 d5c5 e3e4 c5c4
 8*    106       16      34523  e1d2 d4e4 h1h4 e4d5 d2e3 d5e5 h4h5 e5d6 e3e4
 8     106       27      53293  e1d2 d4e4 h1h4 e4d5 d2e3 d5e5 h4h5 e5d6 e3e4
 9*    107       38      74291  e1d2 d4e4 h1h4 e4e5 d2e3 e5f5 h4e4 f5g5 e4e5 g5f6
                                e3d4
 9     107       58     102511  e1d2 d4e4 h1h4 e4e5 d2e3 e5f5 h4e4 f5g5 e4e5 g5f6
                                e3d4
10*    107       79     137030  e1d2 d4e4 h1h4 e4d5 d2e3 d5c5 e3e4 c5c4 e4e5 c4c5
                                h4g4 c5b5
10*    107       91     147202  e1e2 d4e4 h1h5 e4d4 e2f3 d4c3 f3e4 c3c4 h5g5 c4c3
10     107      118     188988  e1e2 d4e4 h1h5 e4d4 e2f3 d4c3 f3e4 c3c4 h5g5 c4c3
11*    108      145     234524  e1e2 d4e4 h1h5 e4d4
11     108      179     298792  e1e2 d4e4 h1h5 e4d4
12*    108      217     379986  e1e2 d4e4 h1h5 e4d4 e2f3 d4d3 h5h4 d3c2 f3e3 c2b3
12     108      278     491399  e1e2 d4e4 h1h5 e4d4 e2f3 d4d3 h5h4 d3c2 f3e3 c2b3
13*    109      344     619547  e1e2 d4e5 e2e3 e5d5 h1h5 d5e6 e3d4 e6f6 d4e4 f6e6
13*    110      413     741548  h1h5 d4d3 e1f2 d3e4 f2e2 e4d4 e2f3 d4d3 h5d5 d3c4
                                f3e4 c4c3 d5h5 c3c4 e4e3 c4b3
13     110      429     754978  h1h5 d4d3 e1f2 d3e4 f2e2 e4d4 e2f3 d4d3 h5d5 d3c4
                                f3e4 c4c3 d5h5 c3c4 e4e3 c4c3 e3e4 c3c4 e4e3 c4c3 e3e4
14*    110      457     803123  h1h5 d4d3 e1f2 d3e4 f2e2
14*    114      561    1009493  e1d2 d4e4 h1h4 e4e5 d2e3 e5d5 h4h5 d5e6 e3f4
                                e6d6 f4e4 d6c6 e4d4
14     114      614    1099995  e1d2 d4e4 h1h4 e4e5 d2e3 e5d5 h4h5 d5e6 e3f4 e6d6
                                f4e4 d6c6 e4d4 c6d6
15*    114      697    1255571  e1d2 d4e4 h1h4 e4d5 d2e3 d5e5 h4h5 e5e6 e3f4
                                e6d6 f4e4 d6c6 e4d4
15*    114      747    1338899  e1e2 d4e4 h1h5 e4d4 e2f3 d4d3 h5d5 d3c4 f3e4 c4c3
                                d5c5 c3d2 c5c7 d2e1 c7c2 e1d1 c2h2
15     114      807    1441301  e1e2 d4e4 h1h5 e4d4 e2f3 d4d3 h5d5 d3c4 f3e4 c4c3
                                d5c5 c3d2 c5c7 d2e1 c7c2 e1d1 c2h2 d1e1 h2a2 e1d1 e4e3
16*    115      904    1646855  e1e2 d4e4 h1h5 e4d4 e2f3 d4d3 h5d5 d3c3 f3e3 c3c4
                                d5f5
16     115     1086    1966597  e1e2 d4e4 h1h5 e4d4 e2f3 d4d3 h5d5 d3c3 f3e3 c3c4
                                d5f5 c4c3 f5f4 c3c2
17*    142     1442    2678225  e1e2 d4e4 h1d1 e4f4 d1d4 f4f5 e2f3 f5e5 f3e3 e5f5
                                d4d5 f5f6 e3d4 f6f7 d4e5 f7g6 e5e6 g6h7 d5e5 h7g6 e5c5
17*    143     1630    3008740  e1d2 d4e4 d2c3 e4e5 h1e1 e5f6 c3d4 f6f5 e1f1 f5e6
                                f1f2 e6d6 f2f6 d6e7 f6h6
17     143     1763    3250041  e1d2 d4e4 d2c3 e4e5 h1e1 e5f6 c3d4 f6f5 e1f1 f5e6
                                f1f2 e6d6 f2f6 d6e7 f6h6 e7f7
18*  10017     2384    4412331  e1d2 d4e4 h1h4 e4f5 h4d4 f5f6 d2d3 f6f5 d4d5 f5f6 
                                d3e3 f6e6 e3e4 e6f6 d5d4 f6g5 d4d6 g5g4 d6d5
18*  10014     2431    4479177  h1h5 d4d3 h5h4 d3e3 h4a4 e3d3 e1d1 d3e3 d1c2
                                e3f2 c2d3 f2g1
18   10014     2591    4730099  h1h5 d4d3 h5h4 d3e3 h4a4 e3d3 e1d1 d3e3 d1c2
                                e3f2 c2d3 f2g1
19*  10014     3025    5572310  h1h5 d4c4 e1e2 c4d4 e2f3 d4d3 h5h4 d3d2 h4c4
                                d2d3 c4e4 d3d2 e4e3 d2c1 e3e2 c1b1 f3e3 b1c1 e3d4
19   10014     3339    6120124  h1h5 d4c4 e1e2 c4d4 e2f3 d4d3 h5h4 d3d2 h4c4
                                d2d3 c4e4 d3d2 e4e3 d2c1 e3e2 c1b1 f3e3 b1c1 e3d4 c1d1
20*  10013     4105    7681329  h1h5 d4e4 e1e2 e4d4 e2f3 d4d3 h5h4 d3d2 h4d4
                                d2c2 f3e2 c2c1
20   10013     4553    8460288  h1h5 d4e4 e1e2 e4d4 e2f3 d4d3 h5h4 d3d2 h4d4
                                d2c2 f3e2 c2c1
21*  10013     7078   13531798  h1h5 d4d3 h5h4 d3e3 h4a4 e3d3 e1f2 d3c3 f2e3
                                c3b3 a4e4 b3c2
21   10013     7833   14807085  h1h5 d4d3 h5h4 d3e3 e1d1 e3f3
22*  10012    10622   20431157  h1h5 d4d3 h5h4 d3e3 h4a4 e3d3 e1f2 d3c2 a4a3
                                c2b1 f2e1 b1c2
22   10012    11729   22201605  h1h5 d4d3 h5h4 d3e3 h4a4 e3d3 e1f2 d3c2 a4a3
                                c2b1 f2e1 b1c1
I tried this on a 1GHz Athlon XP with slow memory (no DDR); on my real computer (Core 2 Duo 2.4GHz) it would be approximately 3 times faster.

Joker finds the first mate score (mate-in-18) at 18 ply after 24 sec (4.4M nodes), there. (Note that 10017 means mate-in-18, as Joker reports the mating distance as it is after its move. I.e. a score of 10000 would mean it mated the opponent with this move.)

The mate-in-13 is found at 22 ply after 106 sec (20.4M nodes).
Then something is wrong with Gaviota. Maybe the move ordering. The middlegame ordering is basically stupid for this type of endgame. If that is the case, is not a problem from a strength perspective but I will try to find out. Are you using nullmove at all? (The side with the only king) or any other type of selective search (futility etc. etc.)?. Mine are all disable at this point.

Miguel

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

Re: Stress test for hashtable, checkmates, node counting.

Post by hgm » Thu Apr 17, 2008 7:18 am

This might be a difference: Joker allows null-move for the side with the Rook. (In general, for the side that has at least one slider.) Futility is done at d=1.

Joker uses IID for move ordering. This is not tied to any particular game phase, and adapts automatically. And of course the evaluation is such that even very low-depth searches already prefer to drive the bare King to the corner, and put the own King in the center. So the move ordering by IID will be in general quite good.

It could be that the delayed-loss bonus in Joker also helps in preferring moves that lead to the same sub-goal quickly over those that achieve it more slowly.

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Stress test for hashtable, checkmates, node counting.

Post by Tord Romstad » Thu Apr 17, 2008 9:00 am

michiguel wrote:Then something is wrong with Gaviota. Maybe the move ordering. The middlegame ordering is basically stupid for this type of endgame. If that is the case, is not a problem from a strength perspective but I will try to find out. Are you using nullmove at all? (The side with the only king) or any other type of selective search (futility etc. etc.)?. Mine are all disable at this point.
It could have something to do with your evaluation function, too. Glaurung announces mate in 13 after just one second, not because of any sophisticated search tricks, but simply by using a specialized evaluation function for positions where one side has only the king left. This evaluation function gives the attacking king a penalty for being close to the defending king, and the defending king a penalty for being close to the edges of the board. This makes the program drive the enemy king to the edge very efficiently, which makes it easy to see the mate quickly.

Of course, this doesn't matter at all for practical playing strength.

Glaurung's analysis:

Code: Select all

18    +80.66   00:00    1044k Rh4+ Kd5 Kf2 Kc6 Ke3 Kd5 Rh5+ Kd6 Ke4 Kc6 Kd4 Kd6
                              Rh6+ Kd7 Ke5 Kc7 Kd5 Kd7 Rh7+ Kd8 Kd6 Ke8
18    +80.71   00:00    1510k Kf2 Ke4 Rd1 Ke5 Ke3 Kf5 Rd5+ Ke6 Ke4 Kf6 Rd6+ Kg5
                              Re6 Kg4 Rg6+ Kh5 Rg2 Kh4 Kf5 Kh3 Rc2
19    +80.76   00:00    1907k Kf2 Ke4 Rd1 Ke5 Ke3 Kf5 Rd5+ Ke6 Ke4 Kf6 Rd6+ Kg5
                              Re6 Kg4 Rg6+ Kh5 Kf5 Kh4 Kf4 Kh3 Rg4 Kh2
19    +80.81   00:00    2612k Rh5 Ke4 Ke2 Kd4 Kf3 Kc3 Ke3 Kc4 Ke4 Kb4 Kd3 Kb3
                              Rb5+ Ka4 Kc4 Ka3 Rb6 Ka2 Kc3 Ka1
20    +80.81   00:00    2714k Rh5 Ke4 Ke2 Kd4 Kf3 Kc3 Ke3 Kc4 Ke4 Kb4 Kd3 Kb3
                              Rb5+ Ka4 Kc4 Ka3 Rb6 Ka2 Kc3 Ka1 Rh6
21    +80.81   00:00    4179k Rh5 Ke4 Ke2 Kd4 Kf3 Kc3 Ke3 Kc4 Ke4 Kc3 Rc5+ Kd2
                              Rc8 Ke2 Rc2+ Ke1 Ke3 Kf1 Re2 Kg1 Rf2 Kh1 Kf3
22    +80.81   00:01    5652k Rh5 Ke4 Ke2 Kd4 Kf3 Kc3 Ke3 Kc4 Ke4 Kc3 Rc5+ Kd2
                              Rc8 Ke2 Rc2+ Kd1 Kd3 Ke1 Ke3 Kf1 Rf2+ Kg1 Kf3 Kh1
                              Kg3
23       #13   00:01    6653k Rh5 Ke4 Ke2 Kd4 Kf3 Kc3 Ke3 Kc4 Re5 Kb3 Kd3 Kb4
                              Rh5 Kb3 Rh4 Kb2 Rb4+ Ka3 Kc3 Ka2 Ra4+ Kb1 Ra7 Kc1
                              Ra1#
24       #13   00:01    6869k Rh5 Ke4 Ke2 Kd4 Kf3 Kc3 Ke3 Kc4 Re5 Kb3 Kd3 Kb4
                              Rh5 Kb3 Rh4 Kb2 Rb4+ Ka3 Kc3 Ka2 Ra4+ Kb1 Ra7 Kc1
                              Ra1#
25       #13   00:01    7352k Rh5 Ke4 Ke2 Kd4 Kf3 Kc3 Ke3 Kc4 Re5 Kb3 Kd3 Kb4
                              Rh5 Kb3 Rh4 Kb2 Rb4+ Ka3 Kc3 Ka2 Ra4+ Kb1 Ra7 Kc1
                              Ra1#
26       #13   00:01    8169k Rh5 Ke4 Ke2 Kd4 Kf3 Kc3 Ke3 Kc4 Re5 Kb3 Kd3 Kb4
                              Rh5 Kb3 Rh4 Kb2 Rb4+ Ka3 Kc3 Ka2 Ra4+ Kb1 Ra7 Kc1
                              Ra1#
Tord

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

Re: Stress test for hashtable, checkmates, node counting.

Post by hgm » Thu Apr 17, 2008 10:04 am

I suppose you mean to say that the attacking King gets a bonus for being close to the bare King?

Post Reply