Author: Robert Hyatt
Date: 12:50:21 02/20/02
Go up one level in this thread
On February 20, 2002 at 15:14:07, Uri Blass wrote: > >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. > For good reason. :) > >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. OK. 5000 lines per rule, there are over 7,000 possible different moves on a chess board. 7,000 * 5,000 is how big? 35,000,000 you say? I say that is _intractable_. > > >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 I did a simple experiment a couple of years ago. Near the tips only, after searching many moves at a specific ply without getting any sort of cutoff, I would just arbitrarily throw away the last N remaining moves. Even with N=1, it changed the root move/score frequently, which means the _last_ move searched was important in enough cases to make this work poorly. I tried lots of different ways of doing this, and without fail, they all made the search go far faster and deeper. And without fail, they screwed up the search as well. The first test I did was Crafty (normal) vs Crafty dropping the last 8 moves at any ply within 3 of the max search depth (ie for a 12 ply search, I dropped the last 8 moves at plies 10,11 and 12.) I used normal move ordering so that I had already tried the hash move, good captures, even exchanges, killer moves, and history moves. Then out of what was left, the last 8 would get tossed near the frontier. And the normal Crafty just blew that one away badly. Even though that one didn't do too badly on test suites. Those errors were _way_ out in the tree. And with a typical move count of 40, there was an 80% probability of searching the important moves way out there. And it played badly. The idea needs more study, but as implemented with varying N, it certainly was a bummer...
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.