Author: Robert Hyatt
Date: 19:04:15 04/30/04
Go up one level in this thread
On April 30, 2004 at 18:39:16, J. Wesley Cleveland wrote: >On April 30, 2004 at 14:05:50, Robert Hyatt wrote: > >>On April 30, 2004 at 13:41:03, J. Wesley Cleveland wrote: >> >>>On April 30, 2004 at 10:43:52, Robert Hyatt wrote: >>> >>>>On April 30, 2004 at 01:26:15, rasjid chan wrote: >>>> >>>>>On April 29, 2004 at 11:25:47, Robert Hyatt 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. >>>>>> >>>>>>That is all well and good. But the fact remains that D+1 is _always_ better >>>>>>than D. How much better really doesn't matter, IMHO. Just the fact that it is >>>>>>better makes it worthwhile... >>>>> >>>>>I have a question which I'm not sure relates to diminishing returns. >>>>> >>>>>You posted in the past that Crafty don't evaluate pins and you >>>>>mentioned something about depths... nowadays .. reaching 12/14 plys... >>>>>I think your reasoning was invalid. >>>> >>>>My reasoning is based on probability theory. >>>> >>>>I am _certain_ to play the first move in a PV my search returns. My opponent is >>>>not forced to play the second move, however. And I am not forced to play the >>>>third. Etc. IE the more moves there are in the PV, the lower the probability >>>>that the move will actually be played in the real game. Or, to put it another >>>>way, the farther out in the PV some tactical trick happens, the more likely it >>>>is that I can vary earlier in the sequence and avoid the trick completely... >>>> >>>> >>>> >>>> >>>>> >>>>>Searching deeper clears 1 pin but then there is the next.. and the next. >>>>>So even if we search till 24 plys, if eval pins is beneficial, it will >>>>>be beneficial at whatever plys we reached even with super hardware. >>>> >>>> >>>>While your idea is basically correct, probability is that the farther out the >>>>pin is pushed, the less likely it is to actually influence the real game... >>>> >>>>Just play a game with any program and for each move, write down the PV and then >>>>compute how many times the second move is actually played, then the third. >>>>You'll see the probability drops steadily and quickly... >>>> >>>I ran an experiment playing crafty against itself (1 hr/game, 1 min increment >>>with ponder off on my AMD64 3000) and got this data >>> >>>ply pv is the same number of occurences >>>0 68 >>>1 37 >>>2 34 >>>3 20 >>>4 13 >>>5 14 >>>6 11 >>>7 7 >>>8 8 >>>9 4 >>>10 1 >>>11 6 >>>12 1 >>>13 3 >>>14 0 >>>15 0 >>>16 1 >>>228 records >> >> >>I'm not sure how to interpret that. IE what is ply 0? Is that the second move >>in the PV (the predicted move) and how many times it was actually played by the >>opponent? >Not quite. Ply 0 is the number of times the second move in the PV (the predicted >move) is *not* played. Ply 1 is the number of times the second move in the PV >(the predicted move) is played, but the third move is not played. More simply >put, the first column is the number of ply the pv agrees with the pv from >searching the next move, and the second column is the number of times this >occured in the sample. OK. Makes sense and supports the point I was making about probabilities of actually playing moves that are deep along a PV.
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.