Computer Chess Club Archives




Subject: Killer modifications reduced tree size by 8% (with identical results)

Author: Artem Pyatakov

Date: 22:15:31 03/31/04

Hello again CCC,

I've been doing some simple last-minute experiments for my thesis, and stumbled
onto this interesting idea. It's in the area of the killer move heuristic.

My original engine (the one I wrote 3 years ago), used the same killer move
scheme as the one used by Crafty (2 killers per ply). As I mentioned in my
previous post, I began experimenting with using the moves from plies ply-2,
ply-4 and ply+2 as well, with very nice results (about 3% tree size reduction on
both WAC and Bratko-Kopec). I decided to then go further and implemented this
scheme: In addition to the regular Crafty-style (replace-always) killers, I
decided to add a limited number of killer moves on each ply that where the least
"popular" killer move would be replaced in favor of the new. I tried different
numbers of these popularity-based moves (starting with 10), but it seemed that
(with a very small dataset of a couple problems) the optimal number of these
additional killers was only 2.

With these additions, I ran the WAC and Bratko-Kope testsuites and found they
had reduced the node count by 8%, which I was excited about.

Yes, these results need to be taken with a grain of salt. Yes, this is not even
my original program - but one that I actually made simpler (and dumber) by
taking out a lot of chess-specific heuristics. But I still think this is a
promising result. Someone else care to try this in their engine? Any comments?


This page took 0.05 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.