ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Memory-PV-Search
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Onno Garms



Joined: 12 Mar 2007
Posts: 224
Location: Bonn, Germany

PostPost subject: Memory-PV-Search    Posted: Sun Mar 13, 2011 7:44 pm Reply to topic Reply with quote

search". It would take some time to implement it. Also the algorithmic
concept is not yet complete and needs to be elaborated.

My thoughts are the following:

1. There are relatively few PV nodes. Even fewer of them are close to
the root. This would allow to keep a large portion of the PV nodes in
the memory. I am not talking of the transposition table or similar. I
am talking of keeping everything, i.e. a tree containing all PV nodes
that are close to the root.


2. Changes in the PV are expensive (take a lot of time in
search).

Suppose at depth 1 to 16 move A is the best. All other moves fail
low. At depth 17, a tactical refutation of move A is found, so we have
to go for an alternative. But as all the remaining moves have always
failed low, they are hardly sorted. Suppose the last of these moves,
Z, is the best. A conventional search will search them all with depth
17 immediately.

Sure, there is internal iterative deeping. But this first searches
move B with depth 1, 3, 5, ..., 17, then searches move C with these
depths etc. It would be better to search all moves B, C, ..., Z with
depth 1, then all of them with depth 3 etc. This way, move Z could go to
an early position at a low depth, and we could use cutoffs at larger
depths for the other moves B, ..., Y.

This means that at a PV node, we should remember for each of the
children the largest depth D for that it was searched as a PV
node. Maybe we should additionally remember the scout search values
for each depth. If A's value has dropped and B fails high, resume
searching of B at depth D+1.


3. An additional problem are search extensions that are only done in
the PV, and pruning techniques (namely bad pruning) that are only done
outside the PV. This means, that depth d for move A is not comparable
to depth d for move B.

Suppose A leads to few extensions. That means, you arrive at large
search depths soon. (Further moves have pruning and no extensions
outside PV, so they normally take much less time than A.) At some
depth, the scout search reports that B is better than A, so we start a
PV search for B. But B leads to many extensions. Before B actually
becomes PV, the PV search must finish. But because of the extensions,
this takes a very long time. Users have reported positions where
Onno virtually hangs at some depth, that means after arriving at depth
d quickly and seeing that move A is bad at depth d, Onno does not
update the PV with move B for hours.

The suggestion in 2. would make an engine search not just B but also
C, D, ... But this alone does not help. We would also have to update
the PV earlier. I do not yet have an idea how to do this.


4. All of above might be possible without keeping a tree of PV nodes
in memory. But when the PV switches and switches back, it is certainly
good to have the old PV nodes still in memory. Based on the node
counting by type I think that this is possible for PV nodes that are
close to the root.
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
Memory-PV-Search Onno Garms Sun Mar 13, 2011 7:44 pm
      Re: Memory-PV-Search Gerd Isenberg Sun Mar 13, 2011 10:57 pm
            Re: Memory-PV-Search Gerd Isenberg Mon Mar 14, 2011 6:47 am
            Re: Memory-PV-Search Onno Garms Sun Mar 20, 2011 10:21 am
                  Re: Memory-PV-Search Dann Corbit Sun Mar 20, 2011 11:01 am
                        Re: Memory-PV-Search Onno Garms Sun Mar 20, 2011 11:27 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads