Author: leonid
Date: 18:05:06 05/07/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: I will try to keep this name in the memory. Already for few times I met this name (killer heuristic) here and never knew what it exactly mean. Don't be surprised, I am still not that sure what is all this "alpha" and "beta" all about. I presume that it is nothing more but what I indicate in my program as maxium and minimum value in the ply. I should overcome my laziness and go for absorbtion of all those names that I still miss. Your second statement (not so good for mate solver) make me think about my big doubts before I used "killer heuristic" in my mate solver. I was not at all sure that it will help. At least it worked. Now I wait to try second idea that is not new for me, since I used it in my second part of chess program. It consist in looking if previous best move still existe, generate it and try it. I have many doubts about success of this idea but only direct trying will say final word. >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. Here I am pretty lost. In my mate solver no value is used. It is only number moves and check oriented. >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? Will try later once again to read this passage. I still miss here basic idea but it is my fault. >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. Heiner, I loose a lot of what you are saying but it is more that interesting to read. Practically what you say now contain a lot of concentrated thought that come from your experience. Very useful! >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. Nothing like this in my logic. >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. 100% different, this part. >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. Actually when I wrote my solver, I expected at that time that every chess program contain it inside. It was Bob Hyatt that explained me that I was wrong. Was very surprised. In one word, mate solver I regarded as initial part of every chess program and base for writing speedy and flauless move generator. In first guess I was wrong but in second probably not. >> 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!'' You was lucky man! Programming is the most beautiful and best way to find that your ideas have real sense. When you speak to the humans it is not that clear. Very often psychology of the responding to your logic bring to completely illogical replies. This can give you paintful sensation that something is wrong with you. Asking mate solver to go after your logic give you complet insurance that your thinking is reliable. >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. I hope it will be done one day. Cheers from Montreal! Leonid. >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.