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: [snip] >>> >>>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 > >Thanks! > >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: 1.Ncxb3+ 1.fxg1=Q 1.fxg1=R 1.Qxg2 1.Qxb4 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# Heiner > 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. > >Leonid.
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.