Author: Uri Blass
Date: 15:27: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. Easy to do. Here is an idea how to decide about the positions. 1)play 100 random games of chess(every side plays random moves when the game is finished only by the 50 move rule or by stalemate or by checkmate 2)give chess programs the pgn of the games 3)the problem for chess program is going to be: finding the number of mate in x when x<=5,6,7,8. It is possible that there is going to be more than one champion because it is possible that the fastest program for solving short mates is not the same as the fastest program that solves long mates. Uri > >Prost from Berlin! >Heiner
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.