Author: Anthony Cozzie
Date: 07:24:59 04/29/04
Go up one level in this thread
On April 29, 2004 at 09:26:21, Tony Werten wrote: >On April 29, 2004 at 08:40:03, Anthony Cozzie wrote: > >>On April 29, 2004 at 03:13:07, Tony Werten wrote: >> >>>Hi all, >>> >>>a while ago we had some discussions about diminishing returns in search for >>>chess. >>> >>>My opinion was that you can't prove that with programs searching d vs d+1 ply >>>depth because the advantage of the d+1 program gets smaller. ie at d=1 it has a >>>100% depth advantage, at d=2 it's 50% etc. >>> >>>Some people claimed that you can't compare it that way because bla bla >>>exponential something bla :) >>> >>>Well, I found an easier way to explain it. >>> >>>A few assumption: >>> >>>The easiest way to win is when you see a trick, your opponent doesn't see. >>> >>>The depth that needs to be searched to see a trick is equally divided. ie there >>>are as many tricks hidden 1 ply away as there are tricks at 2 ply ( it doesn't >>>really matter but it's easier to visualize ) >>> >>>w is player d+1 >>>b is player d >>> >>>d=1: b sees tricks 1 ply away, w sees ply 1 and 2 => w sees 2.0x as many tricks >>>d=2: b:1,2 w:1,2,3 => w: 1.5x >>>d=3: b:1,2,3 w:1,2,3,4 => w: 1.3x >>>... >>>d=10: b: 1..10 w: 1..11 => w:1.1 x >>> >>> >>> >>>Conclusion: There may or may not be diminishing returns in chess, but d vs d+1 >>>are not going to prove it, because those matches by itself are a clear example >>>of diminishing returns regardless what game is played. >>> >>>disclamer: I know chess isn't only about tricks, but it is an advantage to see >>>more of them then your opponent. Clearly the win percentage is depending on >>>other (random) stuff as well. BUT When you see less more, the advantage becomes >>>less. >>> >>>Tony >> >>I'm not even sure I agree with "the tricks are equally divided". > >Me neither, but for the thinking it is easier. > >>It would be >>possible to get some sort of statistics for this, but my guess is trick % >>declines with depth :( >> >>Even so, just the extra positional help makes more depth worth it IMO. > >It's the same. Replace "depth to see tricks" with "depth needed to find the >correct positional move" and the same story holds. > >Don't misunderstand, I know an extra ply of depth gives more strength. But every >extra ply will give less extra strength. Not because of chess ( or checkers or >whatever ), it's just a logical consequence that comes from search. > >Maybe not even search alone. > >If you drive 10 km/h faster than me, it makes a big diffence if I'm driving 10 >km/h. You will get there twice as fast. When driving 50, the difference is a lot >smaller. Certain researchers should call that "diminishing returns in car >driving" if they are consequent. > >Tony > >> >>anthony I think you are right, I was just pulling a Uri and nitpicking :) Also, I think the diminishing effects of search are greatly tied to eval. If you have a perfect eval, any search beyond depth 1 is wasted. It seems logical that the better your eval, the less you need to search. If you have a pst program, you will probably get a big boost from going from 18 -> 19 ply. This is why I think it would be very interesting to redo the move-change-with-depth experiment. IMHO, search is becoming less interesting _if_ you have a good parallel search and a good eval. With a good implementation of DTS, it seems like it is possible to get a 6X speedup on an 8-way opteron. This means that even a slow program will be able to get 13-14 ply without forward pruning. A faster program will be getting 16+. And those are middlegame depths - it would be more like 20 and 25 in the ending. That finds almost anything :) anthony
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.