Author: Uri Blass
Date: 12:14:07 02/20/02
Go up one level in this thread
On February 20, 2002 at 14:34:00, Robert Hyatt wrote: >On February 20, 2002 at 00:27:36, Uri Blass wrote: > >>On February 19, 2002 at 17:00:18, Robert Hyatt wrote: >> >>>On February 19, 2002 at 15:40:33, Gian-Carlo Pascutto wrote: >>> >>>>On February 19, 2002 at 14:13:36, Robert Hyatt wrote: >>>> >>>>>I claim that such is _impossible_. You might get the error down to .0001% if >>>>>you are very lucky. But that is not zero, and it will fail. >>>> >>>>Just a quick question. I didn't manage to read the whole thread >>>>so I don't know the whole context, but is there any reason why >>>>the pruning rules aren't allowed to fail, ever? >>> >>>The discussion was about creating "perfect pruning rules" that do not >>>fail. I maintain there is no such thing, for obvious reasons... and even >>>if they only fail in .01 % of the cases, that is a killer if you have 1000 >>>pruning rules where each has that probability of going astray.... >>> >>> >>>> >>>>>>The pruning rules should detect illogical moves and reduce the size of the chess >>>>>>tree. >>>>>> >>>>>>They should not resuce it to 0. >>>>>> >>>>>>If you prune in every move only 40% of the possible moves you are goinbg to >>>>>>reduce the size of the chess tree significantly but you are not going to solve >>>>>>chess. >>>>> >>>>>Correct. The error rate will be so huge that it won't prove anything at all >>>>>about the game. >>>> >>>>Wow, wow, hold on a little here. Sure, it won't prove anything. Still, >>>>I'm pruning >80% of my moves, and my program still plays damned fine >>>>chess. Sure, I'm not proving anything, but it's still winning games >>>>nicely. And you know what? You are, too.\ >>> >>> >>>wrong kind of pruning. You are talking about _backward_ pruning using >>>alpha/beta. I am talking about forward-pruning as in selective search. >>>There is a huge difference. Backward pruning is provably correct and doesn't >>>cause errors. Forward pruning is a different story. >>> >>> >>> >>> >>>> >>>>>>I do not think that you need billions of lines and I believe that some millions >>>>>>may be enough because one rule can be good for many position. >>>>> >>>>>Pick an iron-clad position where you can eliminate a move for a specific >>>>>reason. And let's see if we can break it. Then you fix it. Then we >>>>>break it. And this goes on almost forever... >>>> >>>>Sure, sure, if you can't possibly accept that it'll never fail. But >>>>I'll be happy as soon as it's correct more than it fails, i.e. when >>>>it starts getting productive. >>> >>> >>>In that case, play me (me being a human) using your program. Set it to >>>generate a random number between 1 and 100. If N is <= 51, then you play >>>the move alpha/beta says is best. If N > 51, then you play a random move >>>in the current position. I'll bet you whatever you want on the result of >>>such games. :) >>> >>>Just because something works more often than it fails is not a terriffic >>>endorsement of the idea. :) One bad move can lose a game, even if you >>>played the correct move every other chance you had. That is the bad thing >>>about chess... >>> >>> >>> >>> >>> >>>> >>>>>No it isn't. Any good software engineering book will explain the problems and >>>>>why software is in the shape it is in today. The concept of a "bug-free >>>>>program" is and always will be an oxymoron, when "program" means something with >>>>>thousands of lines. >>>> >>>>Insert obligatory Knuth quote here ;) >>>> >>>>>>>Note that Junior5 pruned under promotions in it search and in I think that in >>>>>>more than 99% of the games it caused no problems. >>>>> >>>>>but in 1% it caused it to blunder. The more you prune, the more those >>>>>probabilities add up... >>>> >>>>The more the gains add up, too ... >>> >>>Yes, but if you play the best move 50% of the time, you aren't guaranteed to >>>win. If you play a bad move once, you most likely will lose... >>> >>> >>> >>> >>> >>>> >>>>>And 1000 rules isn't going to be even _close_ to what you need. >>>> >>>>You did some kind of experiment to support this hypothesis, >>>>or is it just an unfounded unsubstantiated claim to support >>>>whatever point you're trying to make? >>>> >>>>-- >>>>GCP >>> >>>I once had a selective search program. The selective part of the program >>>went _way_ beyond 50,000 lines of code. And the special cases were still >>>being found on a daily basis. >> >> >>I am sure that the pruning rules were not based on analysis of millions of >>games. >> >>My idea is simply to find rules like >>Bg2-f1 is illogical if... >>Bg2-h3 is illogical if... > > >That is 100% intractable. I won't begin to estimate the number of zeroes >in the number of lines of code such a specific pattern-matching test will >produce. It could _easily_ be billions. That approach to pattern matching >was given up on years ago in AI, for obvious reasons. It won't work today >for the same reason. I agree that the number of lines is too big for one or two programmers but I believe that if you have some million of dollars and hire 100 programmers then it is possible to do the job. Maybe I am wrong in what I believe but it is my guess. We will never know because I believe that nobody tried it. > > >> >>the condition may be complicated so 50 line per condition may not be enough and >>every condition should be checked in every position that Bg2-f1,Bg2-h3 and other >>moves are possible. > >50 lines of code won't touch the qualification for such a pruning rule. You >might need six more zeroes after that number to get close. I agree that 50 lines are not going to be enough (this is exactly what I said in response to what you said that the selective part of your program had beyond 50000 lines) but I do not believe that you will need more than 2 0's after that number. 5000 lines of code for every rule should be enough. > > > >> >>finding all the positions when Bg2-f1 is possible based on a database of >>millions of chess games is easy for chess programs. > > >And those millions of games represent a tiny fraction of the positions the >engine has to be absolutely right in for the pruning rules to work. I believe that if it is right in positions from games then it will probably be right in almost every position and even if it is wrong in 0.01% of the cases the small part of lines that the same side has 2 illogical moves by the rules is going to be so small that you can practically prune it(you practically have sometimes hash collisions in the search(one hash collision per some billions of nodes) and usually one hash collision does not cause problem so I think that you need to prune many good moves in the search to notice practical problems). Here is a simple experiment that may be interesting to do. 1)search a position for 3 minutes 2)search the position for 3 minutes when x random node are prunned by the assumption that there is no threat when there is practically a threat. What is the probability that you choose a different move as a function of x Uri
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.