Author: Vasik Rajlich
Date: 00:47:11 12/29/03
Go up one level in this thread
On December 28, 2003 at 21:07:34, Tom Likens wrote: >On December 28, 2003 at 16:55:49, Tord Romstad wrote: > >>Hi Tom! >> >>That's precisely what I am doing in Gothmog, as you probably know. I'm glad >>to hear that you try similar ideas, and that your first results are promising. >>I've found that it takes lots of tuning and testing before it works well, >>but I think such techniques have great potential in the long run. If it's >>done right, most of the improvements you do in your evaluation function will >>automatically improve the accuracy of your search. > >When I first started experimenting with this idea I was *very* aggressive. >Interesting it didn't really hurt the programs tactics and it seemed to >reach much deeper depths while searching, so I was very excited. >Unfortunately, when I played the new version against the older non-pruning >version it lost rather badly. So, now I'm starting out in a more >conservative fashion and tuning the reductions based on actual games. > >>>My (obvious) question, how do other programmers deal with this phenomenon? >>>I suppose ignoring it is one option, but I'm hoping there is a better >>>solution. >> >>I agree that this problem is extremely annoying, and I have spent lots of >>time and effort trying to find a solution. Unfortunately, I still haven't >>found any good ideas. I asked a question about exactly this problem here in >>CCC just a couple of days ago, but the only person who replied was Dieter >>Bürssner, who also hadn't found a better solution than just ignoring the >>problem and hoping it wasn't too important. >> >>Tord > >The fact that neither yourself nor Dieter have found a satisfactory solution >illustrates the difficulty of the problem. It may be possible to tag these >nodes when they are saved into the hash table and simply use them for move >ordering, as Uri suggested. I need to gather some data before I can make >any kind of intelligent decision. I do agree though that the concept has >*massive* potential. I wouldn't be surprised if this wasn't part of the >"secret" of the commercial programs, (especially that Tiger fella) ;-) > >--tom Hello, It seems to me that there is a way to deal with this. Let's say you're at node A going to node B. You can statically evaluate node A, statically evaluate the move (A->B) in the context of node A, apply the appropriate reduction/extension, and enter node B with the already extended/reduced search depth. In this case, node B will go into the hash table with that new remaining search depth. If I understand the issue correctly, you'd also like to statically evaluate node B before deciding on the reduction/extension for move (A->B). However, I am not sure that that is necessary. Let's consider the typical node which is a candidate for reduction. It should have one of two qualities: A) it is extremely static B) it looks unpromising, ie score somewhat below alpha. In the case of very static nodes, it's pretty clear that you shouldn't need to also look at the next move/node. In the case of an unpromising node, I was thinking that you could do something like identify the few factors which could change the evaluation. For example, if you're down two pawns but there are some vague attacking prospects, then king safety would be that factor, and moves that attack the king would be extended/not reduced, while moves which attack pawns on the queenside are reduced. If you have an advanced passed pawn, then pushing that pawn or supporting its advance would be the one way to bring the score back, and moves which support that would be extended/not reduced. In all of these cases, it seems to me to be enough to only consider the original node (node A) and the moves themselves. The static evaluation of the next node can then be done already knowing the new depth. Unfortunately I haven't started to implement this, so there might be some issues here. At any rate, any reports on your experience in implementing this are welcome. There appears to be almost nothing in the chess literature about this. The best I found was Ed Schroeder's description of the pruning in Rebel, but he concentrates on pruning positions with very bad scores rather than on pruning irrelevant moves. It does also seem to me that this is "the key" to a good program, or at least that it could be "a key". Vas
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.