Author: leonid
Date: 20:21:16 05/06/01
Go up one level in this thread
On May 06, 2001 at 17:53:02, Heiner Marxen wrote: >On May 06, 2001 at 13:12:35, leonid wrote: > >>On May 06, 2001 at 11:17:37, Heiner Marxen wrote: >> >>>On May 06, 2001 at 06:39:02, leonid wrote: >>> >>>> >>>>Thanks, Heiner! Very appreciated. I will try to solve this position later in 7. >>>>Was not even sure if mine will have enough time to do this. Had very bad >>>>branching factor for this one. Just to give you an idea: >>>> >>>>3 moves - 0.1 sec >>>> branching factor - 66 >>>>4 moves - 6.59 sec >>>> - 38.6 >>>>5 moves - 4 min 14 sec >>>> >>>>And this is where and why I stopped searching by brute froce the last time. >>>> >>>>Cheers, >>>>Leonid. >>> >>>I don't know, why your effective branching factor is so much worse than >>>mine, but here is my data for comparison: >>> >>>depth seconds speed >>># 3 0.05 0.98 110- 0 >>># 4 1.03 1.05 2162- 0 >>># 5 21.94 1.21 52287- 0 >>># 6 470.91 1.51 1467975- 11 >>># 7 8123.31 1.68 27139229- 18391335 >>> >>>As you can see from the "speed" (estimated hash table speed up) the hash >>>table is not the main difference this time. More data for you to compare: >>>the executed moves per depth to go: >>> >>> black white >>>mvx 7: 108 133 [108.000 1.231] mvskip lvskip >>>mvx 6: 2191 2615 [ 16.474 1.194] >>>mvx 5: 61015 60627 [ 23.333 0.994] 1101 >>>mvx 4: 1629538 1488284 [ 26.878 0.913] 37238 10 >>>mvx 3: 30390508 27233557 [ 20.420 0.896] >>>mvx 2: 409525400 71961657 [ 15.038 0.176] >>>mvx 1: 84923563 0 [ 1.180 ] >>> >>>The defender (white) manages to nearly always check the defender. >>>Whenever I start to generate legal moves I look, how often the side to >>>move is in check: >>> >>>mg 352166449 W; inchk: 240798413 none 109366513 one 2001523 double >>>mg 27752191 B; inchk: 4158972 none 23475046 one 118173 double >>> >>>Of 27.7 million times generated black moves, black is only 4.1 million times >>>not in check. >>> >>>I know, that you try check moves first. When there are multiple check moves, >>>do you sort them? There are good checks and bad checks: the goal is to >>>have more check moves the next time, also. >> >>Only in the plys that are "very responsive" previous "best move" is put at the >>head of the line, if he still existe. If previous "best move" is checking move, >>it is put at the head of only checking moves. To see what kind of usage of >>previosly found "best move" is the most sutable can be found only by long >>statistics. Usage of previous "best one" I started only with my last version. It >>permitted to speed my brute force and selective search but not all the time. >>Speeding is comfortable and reasonable but only "statistically speaking". In >>some position new version even loose in time. > >Aha. If I understand correctly, this is a sort of "killer heuristic". >That is a good thing for playing programs, but not so good for a mate solver. >I will explain this somewhat surprising statement: > >The typical mate solver will follow only one defender move, while a playing >program will follow all of them, except it gets a "fail high". The mate >solver typically gets its "fail high" (move did defend against the mate) >with the first move it tries, nearly _regardless_ of what this move is. >Nearly always the job of the attacker is absurd, and the defender has no >problem to defend. Any of its moves will work. > >BUT: they will span differently large trees. Some are huge, some are small, >and all of them refute the mate. > >Now, when I start with a move that does refute (as most others would do also), >note the refutation success, and next time try this one again... well it >may refute again, but that was to expect anyway! The important question is: >will it span a small tree? > >And since we did not look at more than one alternative, we have no data >to decide what is a small and what is a huge tree here around. > >Therefore it is important to either >(a) come up with a defender move that does span a small tree, first, or >(b) gather statistical data that allows a prediction for the tree size > of all candidate moves, such that we can pick the expected best one. > >It took some time until I understood this problem. Statistics over the >success of refutation moves most often is worthless. It will pay off, >if/when refutations are rare, and the mate is hard to avoid, >but that occurs very rarely during the analysis of a mate solver. > >Statistics over the tree size of defender moves is of more interest, but >should be used to compare candidates, which therefore need to be measured >already... uh. > >Therefore I rely on a score function for defender moves, much like the >static eval function of playing programs, although it is a bit different, >of course. This function evaluates moves, not positions, and tries to >estimate the expected tree size. > >Chest gives the usual material bonuses for captured material (1/3/3/5/9), >gives a bonus for checking single (6) or double (9), and yet another point >if the checking piece is near the checked king. It gives or takes a bonus >point for more/less flight squares of the king. Then it prefers the >defender move with the most points. > >While this is not directly an estimate of the tree size, it works remarkably >well, when we talk about the defender of a mate in two (the most frequent >case). > >If the remaining depth is larger than two, Chest starts to seriously estimate >the tree size. That is of course a lot more complex, but also quite >important for the success and speed of Chest. > >>My biggest problem with the mate solver is that I never came back (with one >>exception) to rewrite it. Only some real work make a difference. > >Sure, but some extension is not a complete rewrite, or is it for you? >Of course you have to set priorities when you also aim at a playing program, >which you do. > >> And when I >>wrote it, it look just too far ahead of every professional program mate solving >>capacity to even think about improving it. Just one direct example to give you >>real idea of what I am been talking about. I will not speak about my selective >>aearch (it look as good as difficult to compare) but about brute force search >>that is more comparable. I have no data about this position but one before it >>(easy 9 moves position) brute force search was: >> >>LLchess "One professional program" >>4 moves - 0.55 sec 6 sec >>5 moves - 0,76 sec 2 min 30 sec >>6 moves - 12 sec 53 min 37 sec. >> >>Numbers here are typical. > >I see. That is a vast difference. But the others did not invest any >significant effort into the development of fast mate solvers. For practical >play that was just not significant. There appeared to be no demand. > >>At least, now I can see some serious mate solving program from your side to even >>feel some desire for moving ahead. I hope it will help. > >I have never tried to be better than other programs, because there were just >no serious contenders. My goal was always to solve nearly all of the >problems which appear in chess magazines. I wanted Chest to be helpful >to problem composers, enabling them to check their newest beast for correctness >and lack of duals. I'm still not quite there. > >My very first mate-in-2 Fortran program in 1975 in fact were used at the >small university nearby (where I were allowed to get some computer time >on an IBM-1130) as a demo program for visitors: ``Look, it can even solve >chess problems!'' ``Wow, how amazing!'' > >Really. > > >>Weak mate solving capability in professional programs rely (I guess so) on the >>obvious fact that mate solver is not in demand. There were so many chess >>championships in the recent years but probably never for mate solvers. If one >>day it will be changed, abundance of good mate solvers could be first result of >>this change. >> >>Salut from Montreal! >>Leonid. > >A mate solver championship for computers... what an idea ;-O >Never occured to me. Can't really imagine it. > >Prost from Berlin! >Heiner Thanks, Heiner! You have said here so many interesting things about inside of mate solver that I will come back tomorrow to read it once again. Now it is too late. Could have some call from my work in the morning. Good night! 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.