Author: Gian-Carlo Pascutto
Date: 10:44:43 06/19/00
Go up one level in this thread
On June 19, 2000 at 13:09:09, Flemming Rodler wrote: >Dear all > >Below there is a thread about increasing the search depth by fractional plys >during iterative deepening. Could someone please explain to me how you search >to fractional plys? While it is of course impossible to look ahead half a move (actually half a halfmove I suppose...lets just suppose moves=plys for simplicity), the fractional interative deepening assumes that a program uses fractional extensions. Let me explain what that is first. When deciding whether to extend the search at a certain move, it may be that something interesting is happening, and this should be accounted for, but whatever is happening is not enough to warrant an extra ply. Take for example a position where the king is checked but has a lot of escape squares. If you extend a full ply, you risk getting very big search trees. If you don't, you might miss some tactics. So what do we do? We extend half a move. This 'half of a move' doesn't exist of course, you cannot cut a move in two. But the idea is that if this happens twice during the search, the two halfmoves make one whole move. So we extend a full move. You might have extensions of a quarter move too, so it takes four of them to trigger the extension. This allows you to tune the search more gradually. A lot of top software uses this kind of fractional extensions. Now, back to the question. Suppose a chessprogram is searching a branch to a nominal depth of 10 ply. There were several extensions, amounting for 2.2 extra plys to be searched. As we cannot cut moves in half, we stop searching at 12 ply. At another branch, the extensions amount to 2.8 extra ply. Again, we stop searching at 12 ply. (no roundoff's here ;) Now, at the next iteration, we start searching to a nominal depth of 10.5 ply. At the branch from the first example, we will still search 12 ply deep. (10.5 + 2.2 = 12.7) At the brach from the second example, we will now search 13 ply deep. (10.5 + 2.8 = 13.3) So by using fractional iterative deepening, we will avoid looking too much at the less interesting branch (those with only 2.2 extensions), but we will look deeper at the more interesting branch (the one with 2.8 extensions) A normal chessprogram that uses whole ply increments would have no way of distinguishing this kind of positions. I hope this clears it up a bit. PS. I got the idea for the fractional extensions by thinking bout Alpha-beta- conspiracy search, where fractional plys are quite normal. But looks like it has even been tried before in normal alpha-beta search before. -- GCP
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.