Author: Robert Hyatt
Date: 10:37:53 04/20/04
Go up one level in this thread
On April 20, 2004 at 13:01:57, Dieter Buerssner wrote: >On April 20, 2004 at 12:52:47, Robert Hyatt wrote: > >>On April 20, 2004 at 11:50:29, Dieter Buerssner wrote: >> >>>On April 20, 2004 at 06:10:05, Omid David Tabibi wrote: >>> >>>>In his article "PEASANT: An endgame program for kings and pawns", Newborn >>>>writes: "Position 70 would require a 30-ply search (25,000 hours)" >>> >>>I did the experiment. A search without transposition tables, without >>>pruning/extensions and with material only eval (I forgot, if I used qsearch or >>>not). A pawn capture was found at depth 26 (after 8 hours, IIRC). >> >>I assume you mean depth=26, not ply=26? IE white wins the pawn and I had >>thought that this happens on ply=27, which means the first ply of q-search. > >Correct. Also, I used a qsearch in that experiment. > >>I will try to run this myself as it would be nice to know exactly how deep this >>is precisely, verified by multiple programs... >> >> >>> With hash, it >>>is almost guaranteed, that you find it at lower depth. Every second ply, you >>>will have to search all moves, and many inferior moves will be refuted by seeing >>>the pawn capture earlier. These refutations will be in the HT, and will be >>>grabbed in the other more decent lines, to find the solution at lower depth. >>> >>>For my engine, even 1000 entries in the HT is enough, to solve the problem in >>>practically no time. >> >>Theoretically if you search a perfectly ordered tree, the hash table should not >>let you solve it at a shallower than normal depth, although it should cut the >>time dramatically as we all see... > >I don't agree here. See my argument, that every second ply, you have to search >all moves, and that this will help you, to find abbrevations (especially, or >perhaps only, when using fail soft search). If you search a perfectly ordered tree this can not possibly happen. The first thing you search is the path toward the win. Other sub-trees have not yet been searched and they can't influence the score. There was a paper written a long time ago on this subject. It was basically asking the question "how can a search find an N ply solution in less than N plies?" The answer was as I have explained in the past. On fine 70, as a test case, I can search Kb2 first, but search sub-optimal moves by black and reach a position where I can win. But as I back up thru the tree, I discover that black has better moves and I can't force the game to that winning position. But after searching Kb1, I can force the game to the winning position but I can't see deep enough to see that it is won, unless the hash table retains that critical entry that tells me this... > >I did another experiment. Again with material only eval, this time with TTs. I >disabled repetition detection for that experiment (because they don't play a >role when you can win, really, and because they can introduce things more >difficult to interprete - as we both know TTs don't handle them correctly in >general). The move was found at depth 23 with score of a pawn winning with my >normal move ordering (which will be worse in this experiment, because of >material only evaluation, than normally). When I changed the move ordering to >really random ordering, the solution was found at depth 26 (but still rather >fast). > >Regards, >Dieter
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.