Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: here it is.

Author: Heiner Marxen

Date: 03:09:08 01/18/01

Go up one level in this thread


On January 17, 2001 at 22:58:10, leonid wrote:

>On January 17, 2001 at 22:27:36, Heiner Marxen wrote:
>
>>On January 17, 2001 at 19:41:34, leonid wrote:
>>
>>>On January 17, 2001 at 18:43:43, Paul wrote:
>>>
>>>>On January 17, 2001 at 18:18:34, leonid wrote:
>>>>
>>>>>On January 17, 2001 at 18:10:38, Paul wrote:
>>>>>>
>>>>>>My program says mate in 9 for black ... here's a line:
>>>>>>
>>>>>>1... Qxb4 2. Rg8+ Ne8 3. Nxe4 Ncxb3+ 4. cxb3 Nxb3+ 5. axb3 Qxa3+
>>>>>>6. bxa3 Qcc3+ 7. Nxc3 Qxc3+ 8. Ka2 Rd2+ 9. Bc2 Qexb3x
>>>>>>
>>>>>>Paul
>>>>>
>>>>>Can you indicate by what program you solved and all basic data about solution?
>>>>>Selective or brute force search, hash table, special mate solver or usual chess
>>>>>game. Speed of your computer.
>>>>>
>>>>>Thanks,
>>>>>Leonid.
>>>>
>>>>Hi Leonid ...
>>>>
>>>>It's my own program 'Pretz', selective nullmove search, 48MB hash, usual
>>>>chess program, 400MHz PII. So it's possible there's a shorter mate.
>>>>
>>>>Don't know the exact solving time, cause I had more things running
>>>>at the same time, but it was a couple of minutes.
>>>>
>>>>Paul
>>>
>>>Thanks!
>>>
>>>Pretty new for me to see that nullmove could be used as some kind of selective
>>>search for mate.
>>>
>>>It is possible that 9 moves is the shortest move. I only found that mate is
>>>between 11 moves and 7. Six moves I looked through brute force. In six mate not
>>>existe.
>>>
>>>Brute force, even 6 moves took on mine around 6 minutes. Branching factor looked
>>>very bad for this position. With similar branching factor and having no hash in
>>>the program, I thought that looking for exact solution will be too long.
>>
>>Chest says there is no mate in 7.  214 seconds K7/600 with 20 MB hash table.
>>Since I have already running a long job, it will take some time to
>>complete depth=8.
>>
>>Heiner
>
>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.
>
>Leonid.

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!

Heiner



This page took 0.01 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.