Author: leonid
Date: 15:33:46 01/18/01
Go up one level in this thread
On January 18, 2001 at 13:41:04, Heiner Marxen wrote: >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. Probably in your program it have some sense. It could be as well that I will come to this. Only one thing I see as practical why saving the moves that lead to given position, is the taken of pawn "en passant". There you need "previous" move to know if it pawn should be taken. But probably the best way is just to recognize position that can end with this kind of taken and never save it on the first place. >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. It could be that here is my mistake. I consider that positions could be compared only where previous identical position was searched at the same depth. For instance, search is done for some position 10 plys deep. First hash table will be at ply 8 (counting goes 10, 9 ,8...). At ply 8 program will save each position and all three moves that lead to it. Three moves on ply 10, 9 and 8. Only when some new position on ply 8 will coincide with hash position in ply 8 that it will be used. Identical position from hash in ply 5 will be no use. Search after ply 5 went not so deep as after ply 8. I already found what it was wrong with my segment. Nothing! Bug is simply in some other place. Still must clean my code. Do this slowly by creating special spying tools and looking in. >Isn't it the main purpose of a TT to recognize the same board, >when reached on _different_pathes_? Here you killed me with "TT" bug. I am weak in special words. >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. Ha! Your mate solver should be pretty different. Mine don't use any value. Your could be easely (just guess) changed into chess program. >(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 Good! Mine gave me impression that it will take a lot of time. If even on move 6 it took 6 minutes and branching factor, from move 5 6, jumped to around 50. Today came back to make one mate position and later will put it here. In it also not found shortest mate. Position this time is very easy to be solved but, like before, not that easy for finding shortest mate. Leonid. >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 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.