KILLT & HISTORY

[Chua Kong Sian]

At present, the KILLT and HISTORY heuristics overlapped (see genmoves.c).
I would like to suggest that these two heuristics be separated. Let
HISTORY only refer to history data and nothing to do with killer moves.
What this means is that in MoveList() and VMoveList(), those #ifdef
HISTORY blocks should be commented out (or removed).

This makes it necessary to include -DKILLT in the Makefile to activate
killer moves heuristics. The history heuristic can then be activated
using -DHISTORY and this will not interfere with the killer heuristics.

I also think that the current implementation of HISTORY is buggy. After
some experimentation, this is what I would like to suggest. In search(),
at the bottom where the history[] array is being calculated, replace

if (history[j] < HISTORYLIM)
history[j] += (unsigned short) 1 << depth;

with

if (history[j] < ((unsigned short) 1 << depth))
history[j] = ((unsigned short) 1 << depth);

So instead of incrementing history[j] everytime, we set history[j] to the
maximum value that is seen. In a few test positions, this gives much
better cuts than the original code.

Kong Sian

[Chua Kong Sian]

As a refinement to the KILLT code, I noticed that the KILLT tables
for both white and black is exactly the same (see Initialize_killt()
in init.c). As the killt tables are always restored after a move
generation, then there is no need to have different tables for both
white and black, i.e. they can use the same tables.

Hence in genmoves.c, there is no need to perform any of the [mv | sidebit]
operations. We should be able to remove the sidebit variable safely.

Kong Sian

[Jacques Grove]

Chua Kong Sian (nsr...@leonis.nus.sg) wrote:

: At present, the KILLT and HISTORY heuristics overlapped (see genmoves.c).

: I would like to suggest that these two heuristics be separated. Let
: HISTORY only refer to history data and nothing to do with killer moves.
: What this means is that in MoveList() and VMoveList(), those #ifdef
: HISTORY blocks should be commented out (or removed).

[rest deleted]

I would like to ask a question here. Isn't the history heuristic
supposed to be much better than the killer heuristic? I seem to
recall an article by J. Schaeffer (sp?) some (actually many) years
ago in which this was asserted (and there were also some experimental
data given to back this up). Is this true? And if so, why is the
killer heuristic still in Gnuchess?

Jacques

University of Stellenbosch
SOUTH AFRICA

INTERNET: gro...@itu.sun.ac.za / gro...@cs.sun.ac.za

[Chua Kong Sian]

Jacques Grove (gro...@cs.sun.ac.za) wrote:
: I would like to ask a question here. Isn't the history heuristic

: supposed to be much better than the killer heuristic? I seem to
: recall an article by J. Schaeffer (sp?) some (actually many) years
: ago in which this was asserted (and there were also some experimental
: data given to back this up). Is this true? And if so, why is the
: killer heuristic still in Gnuchess?

Unfortunately I don't have the journal with me right now (its at home).
Its an ICCA 1984 article. If I'm not mistaken, the history heuristic
is used in supplement to the killer heuristic, not to replace it.
Perhaps someone else can confirm this. Anyway, I'll go home and read
it again and clear this up.

Kong Sian