Author: martin fierz
Date: 01:32:24 10/29/03
Go up one level in this thread
On October 29, 2003 at 03:15:23, Jorge Pichard wrote: >"Experiments in Chinook show that there comes a point where increased search >depth provides diminishing returns." this is in reference to a paper by the chinook authors which IMO is not accurate. i once calculated the error bars on their match results, and concluded that their results were not statistically significant (they ran matches of 40 games at different search depths, giving error margins of 5 or 6% in the winning probability IIRC). then again, their conclusion seems to be correct: i repeated their experiment with my checkers program in much longer matches, and got the same result, only this time with statistical significance. i did this a long time ago (3 years?) when i only had access to a 6-piece endgame database. however, there is more to this story than simple statistics: 1) checkers has rules which enforce a player to capture if he can. 2) checkers endgame databases have been computed for 8-pc endings already back in 1994 by the chinook team. in the meantime they have even computed the 10pc database, while the "rest of the world" has at least the 8pc database. 1) implies that 2) is important: unlike chess, where endgame databases hardly matter, you already hit the endgame database in checkers in the initial position due to this "convergence" property of checkers. it follows that with the endgame database you do not have many moves in a checkers game where you can make mistakes - perhaps the first 10-20 moves on average. now, when you are testing this "diminishing returns" theory in checkers by increasing the search depth, you are reducing a) the probability of the program making a losing move and b) the number of moves in the game where it can make an error at all - because after a couple of moves it cannot play losing moves any more because it recognizes them as losses in the endgame database. b) is different in checkers than in chess, because you only have so few moves where you can go wrong. in chess, before you hit EGTBs you probably have typically 100 moves or so, therefore it doesn't matter whether you search 9 ply or 19 ply - you are reducing the number of positions where you can make errors from 100 to 90. in checkers, you reduce them from 20 to 10, or even less. diminishing returns in checkers might be due to the classical diminishing returns theory that a program gains less from searching 19 instead of 17 ply compared to 15 vs 13 ply for example. but they might also be due to the fact that computers are approaching perfection in the game of checkers, i.e. that 19 vs 17 is in principle the same difference in "bad-move-frequency" as 15 vs 13, but because you only have e.g. 8 moves to make errors in 19 vs 17 compared to 10 moves in 15 vs 13, you will see diminishing returns because of this. IMO this reduction of the number of moves where you can go wrong at all is what produces the diminishing returns in checkers. if this is true, we will not see it happen in chess. cheers martin
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.