Author: Heiner Marxen
Date: 09:41:47 02/21/00
Go up one level in this thread
On February 21, 2000 at 11:37:52, Mark Taylor wrote: >Can anyone help me with a tree searching problem? I am about to start my first >chess program soon, and have a question from working on my checkers program >over the last 10 years. > >The problem is that when the static evaluation was passed back up the tree, it >hardly changed the behaviour of the program, because the tree search showed that >that benefit could usually be gained "later" - so "good" moves did not get >played until the opponent was about to steal the advantage, then the program >would play the "right move" just in time! A known problem, which has been discussed in this forum. I do not remember the exact result of that discussion, so if I miss something important, pleaso correct me. >An idea I had was to have a small incrmental value subtracted from the eval, >this small increment getting larger the deeper into the tree search the eval was >returned from. I had already done this for the values WON & LOST, but I >hesitated doing it for positional evaluation because a) it seemed a debugging >nightmar; and b) it didn't seem correct "penalising" an eval the deeper search >it was returned from - intuitively deeper searches are to be trusted more than >shallow searches. Yes. Sounds ugly for me. >What I did in the end I made the first search iteration look at positional eval >& material eval, then subsequent iterations looked at material eval only - but >this was really a cop out. > >What do other people do? When two moves searched yield the same value, we want to prefer that one, that realizes that value earlier in its path, right? That may be translated to: take that one, which has had the better value in a more shallow search. Where you really do select between moves (at the top), you should already do an iterative deepening. If now at the start of the next iteration (one ply deeper) we sort the moves by their search value, that should do it. Unfortunately, except for the PV move, we may not have values, but just bounds... and computing always those values would be quite expensive. If you start with a sorted move list by true ply-1 search values (or static evaluations), and continue to pull new best moves to the front of the list, the problem may already disappear practically. Now I'm stuck, sorry. Just wanted to share my thoughts. Regards, Heiner >Thanks, >Mark.
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.