Author: Bernhard Bauer
Date: 02:51:49 06/01/99
Go up one level in this thread
On June 01, 1999 at 02:26:43, Christophe Theron wrote: >On June 01, 1999 at 01:47:16, Bernhard Bauer wrote: > >>On May 31, 1999 at 12:26:02, Christophe Theron wrote: >> >(snip) >>>You can find many other positions where Crafty will fail badly because of the >>>null move algorithm. The fact that Crafty is able to solve this position does >>>not prove that my explanation is wrong. >>> >> >>Yes, there are positions where Crafty fails because of null move. >>Yes, the fact that Crafty solves this position does *not* prove that your >>explanation of the null move algorithm is wrong. >>But, it shows that there are other ways to do and it shows that your explanation >>is incomplete. > >It was not meant to be complete. I cannot give a complete explanation on how >alphabeta and null move works in a few generally understandable sentences. >Somebody was asking why Fritz did not find the solution, I tried to explain >briefly why, and why it was not really a bug. Somebody else asked why Fritz >could find the move in infinite analysis with several variants, and I tried also >to explain why in less than 10 pages. > >My goal was only to explain that this kind of problem could arise, and give some >intuitive indications to understand why it could happen. > >I thought it was interesting to make it understandable for people that have not >written a chess program, but of course it is easy to say I didn't prove >anything... > > Hmm, did I say you didn't prove anything? You explained the use of null move, a question that comes up again and again, so nothing wrong with that. >>>I repeat that finding it or not depends on 2 things at least: >>>* The evaluation: a small change in evaluation from one program to another gives >>>different values for alpha and beta, and depending on these values the program >>>could solve the problem or not. >>>* The "zugzwang detection" rule. A programmer may choose a more risky rule, >>>because it generally gives a program that play better. But of course you could >>>find more positions where the program fails. >>> >> >>And it simply depends whether you use null move or not. >>In the above position it's a poor idea to use null move. >>Generally, if the mobility of the pieces is small, may be due to few pieces >>you should *not* use null move. > >I would like to hear the rules you would use to avoid null move problems. I'm >prepared to anything, but you should be aware that I have tried a lot myself. It >is amazing how apparently good rules like "mobility of pieces is small" don't >work. > >I mean that by trying to avoid the null move problem with new rules you often >make your program much weaker in the endgame. I have experienced it myself. Did >you? Have you found something valuable you are willing to explain? > > You surely know how Crafty uses null move. From search.c you can see: ---------------------------------------------------------- | | | first, we try a null move to see if we can get a quick | | cutoff with only a little work. this operates as | | follows. instead of making a legal move, the side on | | move 'passes' and does nothing. the resulting position | | is searched to a shallower depth than normal (usually | | one ply less but settable by the operator) this should | | result in a cutoff or at least should set the lower | | bound better since anything should be better than not | | doing anything. | | | | this is skipped for any of the following reasons: | | | | 1. the side on move is in check. the null move | | results in an illegal position. | | 2. no more than one null move can appear in succession | | or else the search will degenerate into nothing. | | 3. the side on move has little material left making | | zugzwang positions more likely. | | | | the null-move search is also used to detect certain | | types of threats. the original idea of using the value | | returned by the null-move search was reported by C. | | Donninger, but was modified by Bruce Moreland (Ferret) | | in the following way: if the null-move search returns | | a score that says "mated in N" then this position is a | | dangerous one, because not moving gets the side to move | | mated. we extend the search one ply in this case, al- | | though, as always, no more than one ply of extensions | | are allowed at any one level in the tree. note also | | that this "threat" condition is hashed so that later, | | if the hash table says "don't try the null move because | | it likely will fail low, we still know that this is a | | threat position and that it should be extended. | | | ---------------------------------------------------------- Bob Hyatt doesn't use null move if there are "few" pieces on the board. That could be viewed as low mobility. Of course other views are possible. Zugzwang detection is another thing that may help. >>>I could even add to this list: >>>* The hash table policy: it can affect such positions, especially if you don't >>>clear your hash tables from one search to the next one. >>> >>>You can find blunders like this one in any program. It's always funny to find >>>one, but this implies nothing about the program's strength or quality. >>> >> >>May be there are blunders in *any* program. But I don't want do get used to it. >>I simly do not accept it. A blunder is a blunder. Humans do not like blunders >>in there play. Programs should not make such poor blunders like above. >>However, I agree with you that this does nothing imply about strengt. >> >>>You can call this a bug if you want, but it is not a bug. The programmer is >>>aware of the problem but has choosen consciently to keep the algorithm because >>>it is an improvement overall. >>> >> >>Ok lets call it a missing feature. The programmer accept some flaws in his >>program. Using null move in situations where it should not be used is hardly >>an overall improvement - while it generally may be an improvment. >> >>>As a chess programmer myself I make this kind of choice everyday. It is always >>>sad to discover that a new algorithm fails to solve a given position, but if the >>>program is generally stronger (wins more games) I would be a fool to reject >>>it... >>> >>You should not do "this kind of choice everyday" because it's a poor choice >>even your program is very strong and may become champion. > >It is not a poor choice. If it makes my program stronger it is a smart choice. > This "smart" choice makes you (and the users of your program) sad when your program fails to solve a certain position. >There may be an even smarter choice if I can make my program stronger AND also >solve this kind of positions. But if I have not found the "magic rule" yet, I >always choose to make my program stronger in real games. > This smarter choice is what I want to see. > >>Anyway a program >>should be able to play chess and win such an easy position. >>IMHO you would not be a fool if you would do it right. > >For your information Chess Tiger solves the given problem instantly (ply depth >2, time 0.00s, number of position searched 289, evaluation: mate in 2). > I didn't doubt that you can solve this simple position. I think you are a clever programmer and Tiger is a very good program -:) > >>>So believe it or not, it's not a bug, it's a feature... And it is true. It is >>>not a bad excuse. Why would I give a wrong explanation to defend Fritz, which >>>will be one of my enemies in the next World Championship??? >> >>The explanation "the computer can't do it" has proven wrong in decades. > >I don't understand why you say this... Did I say that the computer can't do it? >My program does it for example. > No you haven't said this. I do not argue against you. I simply don't like the holes in the programs. I want them to disapea. > >>The question remains: what is the best way to do it. There are ways that will >>not slow down your program and will succeed in other positions. > >I am all hears. Tell us how it is possible. > See above and have a look at Tiger. As Tiger solves the 2-mover you have allready implemented something thats better than in Fritz. > >>So I hope you can understand my point of view. > >Not if you tell me that I'm taking poor decisions. > A decision that leads to the wrong result for the gain of speed is poor. Finding a result in a somewhat long time is better than finding it never. > >>The commercial aspect could be: Many users want a reliable analysis tool. >>They are not content with a program that solves 99% of positions in incredible >>short time, they want to be sure that there is no bug in the analysis. If there >>is a bug they will not be glad of the fact that their program solves some >>different positions faster than another program. >> >>Kind regards >>Bernhard > >This time I can agree with you. The problem is that programs are often judged by >their abilities to win games. To win more games programmers have to do >compromises. It looks like people see onlý some meaningless elo numbers, not whether the program plays good ore bad, so you may be right. > >On the other hand, users also want analysis tools, in which compromises are not >welcome. > >So I would suggest that chess programs can be set either for "best play in >games" or "best play on analysis". > >So I will be free to keep on making poor choices. > > Fully agreed. Kind regards Bernhard > > Christophe
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.