Computer Chess Club Archives




Subject: Re: here it is: a mate in 8

Author: Heiner Marxen

Date: 10:41:04 01/18/01

Go up one level in this thread

On January 18, 2001 at 07:52:22, leonid wrote:

>On January 18, 2001 at 06:09:08, Heiner Marxen wrote:
>>On January 17, 2001 at 22:58:10, leonid wrote:
>>>Pretty good!
>>>Heiner, and how much you think that you can save the time on your mate solver
>>>with hash while looking 7 moves deep? I speek about brute force.
>>>Recently I was puzzled and disappointed when I found, in one initial trial of
>>>hash table (still few questions to solve there), that hash can speed my program
>>>(not mate solver) only inside of few initial plys. More deeply plys have too
>>>efficent branching factor to be happy with hash. I probably miss there something
>>>very simple.
>>I do not have the numbers for depth=7, just for depth=6 (5.4 seconds):
>>acm statistics:
>>   30394/   53825 searched
>>    5601/    8763 found (18.4/16.3),    14371 compared [1.000/found]
>>   24793/       0 in/out    24793 alive,  499494 free
>>apx costs: done 1433844, saved 910258 (0.635), ovhd 84219, speed 1.61
>>cost done per sec =  264059.7
>>info  made- used- upgr- forg-   made+ used+ forg+
>>   1  24785     0 24785     0       8     1     0
>>   2  24747  9687  3512     0      22     0     0
>>   3   3512   999   598     0       0     0     0
>>   4    598    89    80     0       0     0     0
>>   5     80     0     1     0       0     0     0
>>   6      1     0     0     0       0     0     0
>>  63     16     0     0     0       0     0     0
>>info       cnt-      cost-       avg-       cnt+      cost+       avg+
>>   1      24785 7.5581e+04 3.0495e+00          8 4.0000e+01 5.0000e+00
>>   2      24747 1.0987e+06 4.4399e+01         22 3.7800e+02 1.7182e+01
>>   3       3512 1.3740e+06 3.9124e+02          0 0.0000e+00 0.0000e+00
>>   4        598 1.4188e+06 2.3726e+03          0 0.0000e+00 0.0000e+00
>>   5         80 1.4309e+06 1.7887e+04          0 0.0000e+00 0.0000e+00
>>   6          1 1.4338e+06 1.4338e+06          0 0.0000e+00 0.0000e+00
>>  63         16 6.4000e+01 4.0000e+00          0 0.0000e+00 0.0000e+00
>>end of acm statistics.
>>In this case savings are not dramatic.  Factor 1.61 (or more).
>>Recall rate around 17% (hit rate).
>>In my experience, the TT (transposition table == hash table) saves a bad
>>move ordering, i.e. a good move ordering lets the TT look bad.
>>Also, I do not probe/enter TT entries below some depth.
>>Probing does cost, and the probably saved work better be more expensive
>>than the probe itself.
>>I enter "mate in 2" jobs along with their results, but not "mate in 1",
>>since these are just too fast, anyhow.
>>Also, during mate search I think it is best to only store the boards,
>>where white (the attacker) is to move, and not to store the others.
>>For a playing program I would store all (if expensive enough).
>>You see, there are plenty of things to consider, and many chances
>>to make mistakes.  ;-)  Heads up!
>Just one expression surprised me. I had the impression that you said "store the
>boards". Do you save in hash table entire chess board position, or just three
>moves that lead to it?

Your impression was correct.  Yes, I store complete boards.
Since Chest is a "mate prover" it shall not guess, but must be sure.
Correctness is very important for Chest.
Therefore the complete exact board is stored.
A TT entry in Chest is 40 bytes large.

Chest still uses hash codes to address the hash table, and as a fast check
for a hit.

For a chess playing program that is all different.  Rare errors (false hits)
can be tolerated, and having more smaller entries is a good thing, here.

>In my trying of hash, program was saving three moves that lead to certain
>position, to be later compared,

Uh.  The moves that lead to the position?  I do not understand.

Isn't it the main purpose of a TT to recognize the same board,
when reached on _different_pathes_?

I usually look at the TT as a cache for a function.
This function typically is called "search()".
It gets in a board, a search depth, and two bounds, and calculates a value.
The TT tries to cache this for the case, that another call to search()
stuffs in the same board, and a depth that is not larger than the first.
I.e. basically we store a mapping (board, depth) --> value.
(For the bounds this is a bit more complex).
(Besides the value thare are often also other things stored, like a best move).
And a playing program often replaces the rather big "board" (ca 32 byte)
by a hash code (6-8 byte).  That allowes for false hits, but that rare
error is accepted by most programs.

There are no moves involved in this, as far as I can see.

Aah, I just checked the output of Chest, and it has found a mate in 8!
Any of the following moves leads to mate in 8:

Used 13.5 hours K7/600 with 20 MB TT.
It is still spitting out megabytes of solution tree ;-)
Here is the first line:
Ncxb3+ Qxb3 fxg1=Q Nab5 Qxb1+ Nxb1 Nxb3+ axb3 Qcxc2 Rg8+ Qxg8 Ka2 Qa4+ N1a3 Qb1#


> and two additional variables. One variable is
>value obtained for saved position and one is maximum value that limited search
>in lower ply. This lower ply is the ply just under three plys which moves are
>saved in hash. Even when during the first trial I dropped this "maximum" value,
>that limit well coincidence rate, still my hash was effective only for few first
>"three plys pairs".
>Expect to put my hash in mate solver after finding what is wrong for chess
>program. Anyway, I expect to rewrite everything for Linux. There will be no more
>hassle with segments, like with my hash now.

This page took 0.02 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.