Author: Robert Hyatt
Date: 11:03:24 02/20/02
Go up one level in this thread
On February 20, 2002 at 13:05:48, Gian-Carlo Pascutto wrote: >On February 20, 2002 at 11:51:05, Robert Hyatt wrote: > >>On February 20, 2002 at 02:48:16, Gian-Carlo Pascutto wrote: >> >>>On February 19, 2002 at 23:27:00, Robert Hyatt wrote: >>> >>>>OK if you talk about null-move I assume _nobody_ says that it doesn't add >>>>its own unique errors into the search. I certainly see enough of them. :) >>> >>>Perhaps. But you are still using it... >> >>Sure. But would you prefer to play with your program doing 13 ply searches >>_with_ null move, or 13 plies _without_??? There is no question which would >>win more games. I have run the experiment already... > >I do not think the question is pratically valid. If I can play with >my program doing 13 ply searches without nullmove, I'll also be able >to play with nullmove and go deeper. You are in the wrong context. We were talking about a program today doing far less NPS than DB, but using forward-pruning to play better than them. I don't believe that is possible... > >>null-move is not a forward pruning algorithm. Not in the context of any >>AI reference to forward pruning. Because null-move doesn't just throw out >>moves ad hoc, it simply searches to a reduced depth instead, which is >>significantly different from "forward pruning" or "selective search" as the >>terms are traditionally used. > >Ok, didn't know this, my fault. Whenever I said 'forward pruning' or >'selective search' I was also (and mostly) talking about algorithms >like nullmove. > >>>For one, Chess Tiger seems to be searching nowadays with a branching >>>factor that's very close to 2 and sometimes even below that. It's >>>obviously not getting any kind of huge error rate that causes it to >>>lose each game by playing losing blunders. Far from it, even. >> >>I doubt it is getting a branching factor of 2 where it is trying to extend >>wild checking lines to 60 plies. Can't possibly happen. That was the point. >>There are _lots_ of lines in the Kf1 analysis, not just one very narrow line >>that goes to 60 plies. There are a _bunch_ of them. > >Mmm. ChessTiger doesn't seem to output that information, but Fritz 7 >does. It is at ply 20 now, and reports a maximum depth of 53 ply, so >it was at least extending some lines to that depth. yes... but not the _right_ ones, unfortunately, because of the quiet moves at the end. > >>>I see no reason not to believe this can't be pushed further down. >>> >>>Now think about it. Once you consistently go below 2, each simple >>>speedup will result in more and more plies. >>> >> >>And as you go below 2, you are doing so at great risk of making gross >>errors as well. > >I'm not seeing a lot of them for sure :) > >>>You won't need to see the full 60 (or 36) ply in every variation >>>here. The draw by repetition is going to have a lot of checks in >>>it which should allow a program to find it faster. >> >>Yes you do if you are trying to _prove_ that Kf1 draws. > >It only needs to prove in every sidebranch that white is at >best drawing. That doesn't necessarily take 60 ply in >_every_ variation. No, but it takes 60 plies in variations where there is one or more quiet moves beyond ply=40, and that truncates the search there before the repetition is found. > >>It is the _quiet_ moves that are the problem in this particular game >>position, not the repeated checks which are not hard to handle at all. But >>if you have to search a string of checks, followed by two consecutive quiet >>moves, followed by another long string of checks, today's searches simply are >>not capable of doing that. At least in finite time searches... > >Why not? There just has to be enough leftover depth after the first >checking sequence to get over the two quiet moves, after which the >next sequence will be extended as well. Then you have a non-terminating search. If you extend one ply for every ply of search, to depth 40, you can forget about playing in a real game. Most programs are aggressive when they extend one ply for every two plies of search, one ply to get out of check, no extension for the next checking move, so you drop one ply for every two searched. By the time you get to 40, you are fresh out of plies... > >>>I'm assuming a 30 ply nominal search might suffice. That is not so >>>far out as you might think. Seeing it's at 22 ply after half a day, >>>it'll need (2^8) / 2 = 128 days as a rough estimate. >> >>Except for the quiet moves, you would be right. But they happen way out >>into the tree, say at ply 50. Which means you have to reach that depth >>with some search left over to catch the quiet moves and get beyond them >>into the checks again. >> >>Not easy at all. >> >>In fact, nearly impossible. > >Perhaps. Perhaps not. The truth is in the experiment, as they say :) > >-- >GCP
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.