Author: Andrew Williams
Date: 06:04:55 07/12/01
Go up one level in this thread
On July 12, 2001 at 07:19:02, Marcus Heidkamp wrote: >Has anyone experience with the killer heuristics in an MTD(f) driven search? I >am wondering if it would make any sense, because good cutoffs are stored into >the trasposition tables anyway, and each call to the driver either fails high or >low. So my (rather vague) guess would be that the cutoff ratio for killers will >be small or even zero, because transposition cutoffs are done first. > >With history heuristics it's different, because history directly relates to move >ordering, where killers seem to me to affect mostly the cutoffs. > >I already did a quick and dirty implementation of killers in my program, and it >seemed not to outweight the overhead of move validation. But maybe I had a bug >in there... :-(. > >Comments are very welcome. > >Marcus Suppose you have this position (1) in a search somewhere: [D] rnq1k1nr/pp3ppp/4p3/1N1p4/3P4/4P3/PP1B1PPP/R2Q1RK1 b kq - It is black's turn and he first tries Nf6 which leads us to this position (2): [D]rnq1k2r/pp3ppp/4pn2/1N1p4/3P4/4P3/PP1B1PPP/R2Q1RK1 w kq - Naturally, white replies Nd6 winning the Queen for the Knight. (Note that the first time this position is encountered, this might not be the *first* move that is attempted). Because Nd6 gives a beta cutoff, this move is stored in the hash table entry for position 2. The cutoff means the search returns to position 1; black now knows that Nf6?? is no good, so he tries Nc6. The hash move can't help now, because it belongs to a different position (ie position 2), but a *killer* would help in this position. The killer would have recorded Nd6 as a good move, because it occurred at ply 2 in the search following Nf6. So one of the first moves tried after black tried Nc6 would be Nd6, with the same result as before. So the answer to your question is emphatically YES, killers can help in MTD(f) programs; their utility is certainly no less than for other approaches. In my MTD(f) program, I use two killers per ply. Andrew
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.