Author: Andrew Dados
Date: 11:08:38 03/23/00
Go up one level in this thread
On March 23, 2000 at 13:54:03, Tom Kerrigan wrote: >On March 23, 2000 at 13:49:59, Andrew Dados wrote: > >>On March 23, 2000 at 13:37:02, Tom Kerrigan wrote: >> >>>On March 23, 2000 at 13:18:52, Andrew Dados wrote: >>> >>>>On March 23, 2000 at 13:08:51, John Coffey wrote: >>>> >>>>>Does interative deepening insure that a program will pick the fastest >>>>>improvement? I.e. if a program can improve its position by .1 pawn in 3 moves, >>>>>how do I know that it won't choose a .1 improvement in 5 moves instead? >>>>> >>>>>John Coffey >>>> >>>> Any brute-force search (including alpha-beta) guarantees it by definition :) >>> >>>I don't think so. The brute force searches that people do in computer chess rely >>>on evaluation functions that do not distinguish between depths. >>> >>>-Tom >> >>The question as I understood was: When there is an improvement within e.g. 3 >>plies, can we be sure that our search won't miss it (searching 3 plies deep). >>And _that_ we can be sure. >> >>two remarks: >>1) null move pruning <> brute-force search. >>2) 'improvement' is defined by program solely: evaluation function, qsearch and >>all horizon effects, not by us. > >That's not the way I read the question. > >"if a program can improve its position by .1 pawn in 3 moves, how do I know that >it won't choose a .1 improvement in 5 moves instead?" > >This doesn't imply that the program missed anything at either depth. > >And if a program is searching 5 moves deep, then it will always choose the move >that improves the position _after_ 5 moves. Whether or not this also improves >its position after 3 moves is up for grabs. > >-Tom Seems I misunderstood the question. Sorry. Then again: if program found move X that improves score by 0.1 at ply 3 and at ply 5 it has no better score for some other move then for best move X (searched already at ply 5), it will stick to 'old best' X. So in rare case of exact scores iterative deepening will choose fastest improvement indeed (alpha-beta will not know of 'exact scores' anyway. it will only know that other move didn't improve score). (In practice there is that bad effect of odd/even plies which usually causes switching between 2 close moves and lotsa re-searches).
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.