TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Onno Garms

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

 Post subject: Memory-PV-Search    Posted: Sun Mar 13, 2011 7:44 pm 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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Onno Garms Sun Mar 13, 2011 7:44 pm
Gerd Isenberg Sun Mar 13, 2011 10:57 pm
Gerd Isenberg Mon Mar 14, 2011 6:47 am
Onno Garms Sun Mar 20, 2011 10:21 am
Dann Corbit Sun Mar 20, 2011 11:01 am
Onno Garms Sun Mar 20, 2011 11:27 am

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumChess Players ForumForum Help and Suggestions
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