Author: Walter Faxon
Date: 01:04:20 04/07/05
Go up one level in this thread
On April 06, 2005 at 20:15:52, John Merlino wrote: >On April 06, 2005 at 19:51:24, Anthony Cozzie wrote: > >>On April 06, 2005 at 19:31:27, Walter Faxon wrote: >> >>>In a recent thread (http://www.talkchess.com/forums/1/message.html?419679), the >>>problem of on-line lookup of 6-man endgame tablebases was discussed. The >>>consensus was that for computer play, you could (maybe) load blocks of related >>>positions from near the root, not make individual requests for the value of >>>specific positions, since even fast net access is a snail compared to a good >>>hard disk. >>> >>>Either way, it takes a good block of time. To a much lesser degree, even >>>looking up the hash value for the current position can lose if its cache line >>>isn't already loaded. Main memory lookup can require hundreds of processor >>>cycles on modern hardware. (Probably a reason why Hyper-Threading(R) technology >>>works so well for computer chess. When one thread stalls the other might be >>>able to continue.) >>> >>>In between is the standard situation where a particular position in the tree has >>>multi-depth subsearches returning with widely varying scores and suggested >>>moves. You've reached a "hard" position. Or maybe before you've done any >>>searching on a position, you've somehow statically determined that it is "hard" >>>(like it will require a disk lookup). Either way, what should you do? >>> >>>My question is: Is it ever reasonable to just say "I'm going to leave the >>>evaluation of this position until later, if necessary." And continue the >>>search. It is possible and in many cases likely that the remaining search will >>>cut off at least some of the hard positions, and you will discover that you >>>never really needed to evaluate these in the first place. Maybe the search tree >>>could be marked so that when the "easy" search has been completed you can then >>>return to try to understand the remaining hard positions, in an order of how >>>they affect the remaining tree. >>> >>>Has anybody written code that addresses this? >>> >>>-- Walter >> >>Move ordering is very interesting, because you don't really want to search the >>best move first, you want to search the move that will provide a cutoff with the >>least amount of work. Unfortunately, this seems like a really hard problem . . >>. >> >>anthony > >The King always searches the best move from the previous depth first. Why would >you NOT want to do that? Wouldn't your biggest priority when reaching a new >depth be verifying what you have accomplished on the previous depth -- >especially if time is a consideration (and it usually is)? > >jm What if the "hard" position is at the frontier? I guess I'm proposing a more intelligent eval function that puts differing amounts of effort into reasonable vs. the often ridiculous positions full-width search variants produce. And perhaps explicitly retaining more of the search tree so the program can move around in it. Not the current search paradigm that produces a huge amount of information only to throw most of it away (keeping some implicitly to speed further searching only). I know things like this have been proposed before, back in ancient prehistoric times (before 1990). I'm not new to this game. I just don't know of any methods for handling "incomplete" trees where certain "critical" nodes have yet to be evaluated. If we can reduce the search to the point where the eval depends on a handful of hard/critical nodes, we've gone a long way towards directing the total search effort and achieving more logical, dare I say human, play. This leads more in the direction of programs like Steven Edward's "Symbolic", so Anthony may want to tune out now. :) -- Walter
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.