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, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.