[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] The killer heuristic
|
From: |
Evan Berggren Daniel |
|
Subject: |
[gnugo-devel] The killer heuristic |
|
Date: |
Fri, 24 Jan 2003 11:02:25 -0500 (EST) |
The following patch implements the killer heuristic in tactical move
ordering.
The heuristic works like this: if black plays move A1, and white finds a
successful response in move B, then when black tries A2 instead, it is
reasonable to assume that B is a good response, and should be tried as the
first move.
Unfortunately, trying the move first doesn't work very well because we
have to make sure it gets generated. So the patch just adds a bonus in
order_moves. I have an earlier version that immediately adds the move at
high value, but it has regression changes, presumably from cases where the
move would not be tried as a response normally. The performance increase
is greater than the current version, but I don't believe it is worth the
unpredictability in tactical moves tried.
The patch provides a 2-5% decrease in reading nodes depending on the test
suite; I don't have numbers for current cvs without the patch, though, so
the 2-5% comes from comparison with the numbers listed in the html views.
There is no regression change; numbers are from current cvs (as of
arend_3_16.1).
On a related note, I tried the history heuristic as well, but was unable
to find an implementation that improved results.
Either the killer heuristic or the history heuristic could probably be
applied to move ordering in the owl code; I haven't investigated it.
Thanks
Evan Daniel
- implement killer heuristic for tactical move ordering
Full results:
reading 16.70 83332 0 0
owl 385.16 19779260 18969 86461
owl_rot 5.98 287428 104 1524
ld_owl 87.48 2687515 11418 529
optics 8.30 260755 0 886
filllib 45.18 1099029 880 7718
atari_atari 38.89 1717353 1444 7158
connection:101 FAIL 0 [1 M3]
connection 83.26 4926377 0 42935
blunder 84.17 2427969 2096 11090
trevora 311.20 14250753 56632 54101
nngs1 950.15 50903112 63943 219975
strategy 906.20 45873636 69175 234166
endgame 40.81 567940 505 6246
heikki 20.23 1302028 1523 5236
neurogo 563.61 23338574 54790 70588
arb 78.22 3299179 4003 12008
rosebud 25.92 1945067 1561 9018
golife 80.41 3113594 11972 3978
arion 135.03 5216006 5796 17781
viking 205.25 8872124 12979 30042
ego 131.89 6601356 7471 42056
dniwog 167.72 7182423 17911 21102
lazarus 463.39 19085746 40803 63673
trevorb 514.00 24468012 31009 128439
strategy2 1021.57 41721563 81072 163111
nicklas1 529.37 24340891 37859 120917
nicklas2 78.31 2557598 6301 3923
nicklas3 18.58 527706 1680 185
nicklas4 212.53 7179897 12602 32600
nicklas5 297.64 12428263 18172 62994
manyfaces 218.86 9011214 16486 42063
niki 299.28 15861657 16316 82927
trevor 331.54 14966522 36360 47996
tactics 135.93 7174073 4500 40533
buzco 161.23 8479873 11806 28864
nngs 2550.79 136167122 161530 572866
trevorc 989.02 51734794 82122 277113
strategy3 588.61 26320516 40917 114299
capture 2.93 24865 0 0
connect 23.24 898908 0 7738
global 751.75 31937555 62475 128510
vie 137.95 6287413 4923 28539
arend 731.92 42341732 33871 262975
13x13 976.43 46711723 127627 218283
semeai 69.65 3829443 2355 21241
trevord 1367.09 76983274 49865 477582
strategy4 1393.62 83807888 82063 424629
owl1:296 FAIL 0 [1 E5|D8]
owl1 68.73 3273282 4643 16197
handtalk 448.30 23440538 28823 136365
nngs2 1179.84 54032968 91929 213010
nngs3 2969.10 152618803 234461 721729
nngs4 561.96 24349249 50014 70168
strategy5:226 FAIL S3 [F5]
strategy5 432.54 22985580 32399 111950
century2002 540.73 22453277 55201 81152
auto01 38.02 2173481 1418 15673
auto02 53.30 2905228 3297 20715
auto03 33.01 2179419 1132 16324
auto04 22.06 1514446 477 11382
auto_handtalk 55.16 3091335 2245 25744
safety 50.30 2595103 4663 16384
ninestones 809.33 43722118 65526 222904
tactics1 43.89 1927656 3514 8386
manyfaces1 345.79 17045773 31700 80230
gunnar 355.50 17659436 21479 68252
arend2 136.00 7796129 8145 26103
Total nodes: 1306346879 1946952 6099266
Total time: 26380.52
Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.101
diff -u -r1.101 reading.c
--- engine/reading.c 18 Jan 2003 11:39:45 -0000 1.101
+++ engine/reading.c 24 Jan 2003 03:13:07 -0000
@@ -188,7 +188,8 @@
static void double_atari_chain2_moves(int str,
struct reading_moves *moves);
static void order_moves(int str, struct reading_moves *moves,
- int color, const char *funcname, int first_move);
+ int color, const char *funcname, int first_move,
+ int killer);
static int simple_ladder_attack(int str, int *move, int komaster, int kom_pos);
static int simple_ladder_defend(int str, int *move, int komaster, int kom_pos);
static int in_list(int move, int num_moves, int *moves);
@@ -1004,7 +1005,7 @@
static int
do_find_defense(int str, int *move, int komaster, int kom_pos)
{
- int xpos;
+ int xpos = NO_MOVE;
int dcode = 0;
int liberties;
int found_read_result;
@@ -1014,6 +1015,9 @@
RTRACE("Can we rescue %1m?\n", str);
+ if (move && ON_BOARD(*move) && board[*move] == EMPTY)
+ xpos = *move;
+
/* We first check if the number of liberties is larger than four. In
* that case we don't cache the result and to avoid needlessly
* storing the position in the hash table, we must do this test
@@ -1158,7 +1162,7 @@
break_chain_moves(str, &moves);
set_up_snapback_moves(str, lib, &moves);
- order_moves(str, &moves, color, read_function_name, 0);
+ order_moves(str, &moves, color, read_function_name, 0, NO_MOVE);
for (k = 0; k < moves.num; k++) {
int new_komaster;
@@ -1229,7 +1233,7 @@
defend2(int str, int *move, int komaster, int kom_pos)
{
int color, other;
- int xpos;
+ int xpos = NO_MOVE;
int liberties;
int libs[2];
int liberties2;
@@ -1240,6 +1244,7 @@
int savecode = 0;
int k;
int r;
+ int suggest_move = NO_MOVE;
SETUP_TRACE_INFO("defend2", str);
reading_node_counter++;
@@ -1262,6 +1267,7 @@
* 2. Chain breaking moves.
* 3. Second order liberties moving up from first line to second.
* 4. Edge clamps.
+ * 5. Killer Heuristic
*/
for (k = 0; k < liberties; k++) {
moves.pos[k] = libs[k];
@@ -1281,8 +1287,8 @@
if (stackp <= backfill_depth)
special_rescue2_moves(str, libs, &moves);
-
- order_moves(str, &moves, color, read_function_name, 0);
+
+ order_moves(str, &moves, color, read_function_name, 0, NO_MOVE);
for (k = 0; k < moves.num; k++) {
int new_komaster;
@@ -1295,13 +1301,15 @@
komaster, kom_pos, &new_komaster, &new_kom_pos,
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+ int acode = do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos);
popgo();
CHECK_RESULT(savecode, savemove, acode, xpos, move,
"defense effective - A");
}
else {
- if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+ if (do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -1341,7 +1349,7 @@
}
/* Only order and test the new set of moves. */
- order_moves(str, &moves, other, read_function_name, saved_num_moves);
+ order_moves(str, &moves, other, read_function_name, saved_num_moves,
NO_MOVE);
for (k = saved_num_moves; k < moves.num; k++) {
int new_komaster;
@@ -1353,13 +1361,15 @@
komaster, kom_pos, &new_komaster, &new_kom_pos,
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+ int acode = do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos);
popgo();
CHECK_RESULT(savecode, savemove, acode, xpos, move,
"defense effective - B");
}
else {
- if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+ if (do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -1416,7 +1426,7 @@
}
/* Only order and test the new set of moves. */
- order_moves(str, &moves, other, read_function_name, saved_num_moves);
+ order_moves(str, &moves, other, read_function_name, saved_num_moves,
NO_MOVE);
for (k = saved_num_moves; k < moves.num; k++) {
int new_komaster;
@@ -1428,13 +1438,15 @@
komaster, kom_pos, &new_komaster, &new_kom_pos,
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+ int acode = do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos);
popgo();
CHECK_RESULT(savecode, savemove, acode, xpos, move,
"defense effective - A");
}
else {
- if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+ if (do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -1460,7 +1472,7 @@
defend3(int str, int *move, int komaster, int kom_pos)
{
int color, other;
- int xpos;
+ int xpos = NO_MOVE;
int liberties;
int libs[3];
struct reading_moves moves;
@@ -1468,6 +1480,7 @@
int savemove = 0;
int savecode = 0;
int k;
+ int suggest_move = NO_MOVE;
SETUP_TRACE_INFO("defend3", str);
reading_node_counter++;
@@ -1490,6 +1503,7 @@
* 2. Chain breaking moves.
* 3. Second order liberties moving up from first line to second.
* 4. Edge clamps.
+ * 5. Killer Heuristic.
*/
for (k = 0; k < liberties; k++) {
moves.pos[k] = libs[k];
@@ -1505,7 +1519,7 @@
if (stackp <= backfill2_depth)
hane_rescue_moves(str, libs, &moves);
- order_moves(str, &moves, color, read_function_name, 0);
+ order_moves(str, &moves, color, read_function_name, 0, *move);
for (k = 0; k < moves.num; k++) {
int new_komaster;
@@ -1521,13 +1535,15 @@
&new_komaster, &new_kom_pos,
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+ int acode = do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos);
popgo();
CHECK_RESULT(savecode, savemove, acode, xpos, move,
"defense effective - A");
}
else {
- if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+ if (do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -1622,7 +1638,7 @@
}
/* Only order and test the new set of moves. */
- order_moves(str, &moves, other, read_function_name, saved_num_moves);
+ order_moves(str, &moves, other, read_function_name, saved_num_moves, *move);
for (k = saved_num_moves; k < moves.num; k++) {
int new_komaster;
@@ -1634,13 +1650,15 @@
komaster, kom_pos, &new_komaster, &new_kom_pos,
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+ int acode = do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos);
popgo();
CHECK_RESULT(savecode, savemove, acode, xpos, move,
"defense effective - A");
}
else {
- if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+ if (do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -1686,7 +1704,7 @@
break_chain3_moves(str, &moves);
/* Only order and test the new set of moves. */
- order_moves(str, &moves, other, read_function_name, saved_num_moves);
+ order_moves(str, &moves, other, read_function_name, saved_num_moves, *move);
for (k = saved_num_moves; k < moves.num; k++) {
int new_komaster;
@@ -1698,13 +1716,15 @@
komaster, kom_pos, &new_komaster, &new_kom_pos,
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+ int acode = do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos);
popgo();
CHECK_RESULT(savecode, savemove, acode, xpos, move,
"defense effective - A");
}
else {
- if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+ if (do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -1731,13 +1751,14 @@
defend4(int str, int *move, int komaster, int kom_pos)
{
int color, other;
- int xpos;
+ int xpos = NO_MOVE;
int liberties;
int libs[4];
struct reading_moves moves;
int savemove = 0;
int savecode = 0;
int k;
+ int suggest_move = NO_MOVE;
SETUP_TRACE_INFO("defend4", str);
reading_node_counter++;
@@ -1758,6 +1779,7 @@
/* Collect moves to try in the first batch.
* 1. First order liberties.
* 2. Chain breaking moves.
+ * 3. Killer Heuristic.
*/
for (k = 0; k < liberties; k++) {
moves.pos[k] = libs[k];
@@ -1775,7 +1797,7 @@
#endif
}
- order_moves(str, &moves, color, read_function_name, 0);
+ order_moves(str, &moves, color, read_function_name, 0, *move);
for (k = 0; k < moves.num; k++) {
int new_komaster;
@@ -1791,13 +1813,15 @@
&new_komaster, &new_kom_pos,
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+ int acode = do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos);
popgo();
CHECK_RESULT(savecode, savemove, acode, xpos, move,
"defense effective - A");
}
else {
- if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+ if (do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -2838,7 +2862,7 @@
do_attack(int str, int *move, int komaster, int kom_pos)
{
int color = board[str];
- int xpos;
+ int xpos = NO_MOVE;
int libs;
int result = 0;
int found_read_result;
@@ -2848,6 +2872,9 @@
ASSERT1(color != 0, str);
+ if (move && ON_BOARD(*move) && board[*move] == EMPTY)
+ xpos = *move;
+
if (color == 0) /* if assertions are turned off, silently fails */
return 0;
@@ -3089,7 +3116,7 @@
int color = board[str];
int other = OTHER_COLOR(color);
int hpos;
- int xpos;
+ int xpos = NO_MOVE;
int liberties, r;
int libs[2];
int libs2[2];
@@ -3103,6 +3130,7 @@
int adjacent_liberties = 0;
int pass;
int saved_num_moves = 0;
+ int suggest_move = NO_MOVE;
SETUP_TRACE_INFO("attack2", str);
reading_node_counter++;
@@ -3223,7 +3251,7 @@
}
if (pass != 3) {
- order_moves(str, &moves, other, read_function_name, saved_num_moves);
+ order_moves(str, &moves, other, read_function_name, saved_num_moves,
NO_MOVE);
for (k = saved_num_moves; k < moves.num; k++) {
int new_komaster;
@@ -3235,7 +3263,8 @@
komaster, kom_pos, &new_komaster, &new_kom_pos,
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- dcode = do_find_defense(str, NULL, new_komaster, new_kom_pos);
+ dcode = do_find_defense(str, &suggest_move, new_komaster,
+ new_kom_pos);
if (dcode != WIN
&& do_attack(str, NULL, new_komaster, new_kom_pos)) {
popgo();
@@ -3246,7 +3275,8 @@
popgo();
}
else {
- if (do_find_defense(str, NULL, new_komaster, new_kom_pos) != WIN
+ if (do_find_defense(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN
&& do_attack(str, NULL, new_komaster, new_kom_pos) != 0) {
savemove = apos;
savecode = KO_B;
@@ -3288,7 +3318,8 @@
popgo();
if (trymove(xpos, other, "attack2-D", str, komaster,
kom_pos)) {
- dcode = do_find_defense(str, NULL, komaster, kom_pos);
+ dcode = do_find_defense(str, &suggest_move, komaster,
+ kom_pos);
if (dcode != WIN
&& do_attack(str, NULL, komaster, kom_pos)) {
popgo();
@@ -3305,7 +3336,8 @@
else {
dcode = do_find_defense(str, NULL, komaster, kom_pos);
if (dcode != WIN
- && do_attack(str, NULL, komaster, kom_pos)) {
+ && do_attack(str, &suggest_move, komaster,
+ kom_pos)) {
popgo();
CHECK_RESULT(savecode, savemove, dcode, apos, move,
"attack effective");
@@ -3350,7 +3382,7 @@
int color = board[str];
int other = OTHER_COLOR(color);
int adj, adjs[MAXCHAIN];
- int xpos;
+ int xpos = NO_MOVE;
int liberties;
int libs[3];
int r;
@@ -3361,6 +3393,7 @@
int savecode = 0;
int pass;
int saved_num_moves = 0;
+ int suggest_move = NO_MOVE;
SETUP_TRACE_INFO("attack3", str);
reading_node_counter++;
@@ -3458,7 +3491,7 @@
if (pass == 0 || pass == 1 || pass == 2) {
- order_moves(str, &moves, other, read_function_name, saved_num_moves);
+ order_moves(str, &moves, other, read_function_name, saved_num_moves,
NO_MOVE);
/* Try the moves collected so far. */
for (k = saved_num_moves; k < moves.num; k++) {
@@ -3474,7 +3507,8 @@
&new_kom_pos, &ko_move,
stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
- dcode = do_find_defense(str, NULL, new_komaster, new_kom_pos);
+ dcode = do_find_defense(str, &suggest_move, new_komaster,
+ new_kom_pos);
if (dcode != WIN
&& do_attack(str, NULL, new_komaster, new_kom_pos)) {
popgo();
@@ -3485,7 +3519,8 @@
popgo();
}
else {
- if (do_find_defense(str, NULL, new_komaster, new_kom_pos) != WIN
+ if (do_find_defense(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN
&& do_attack(str, NULL, new_komaster, new_kom_pos) != 0) {
savemove = xpos;
savecode = KO_B;
@@ -3521,7 +3556,8 @@
popgo();
if (trymove(xpos, other, "attack3-F", str,
komaster, kom_pos)) {
- dcode = do_find_defense(str, NULL, komaster, kom_pos);
+ dcode = do_find_defense(str, &suggest_move, komaster,
+ kom_pos);
if (dcode != WIN
&& do_attack(str, NULL, komaster, kom_pos)) {
popgo();
@@ -3537,7 +3573,8 @@
}
else {
dcode = do_find_defense(str, NULL, komaster, kom_pos);
- if (dcode != WIN && do_attack(str, NULL, komaster, kom_pos)) {
+ if (dcode != WIN && do_attack(str, &suggest_move, komaster,
+ kom_pos)) {
popgo();
CHECK_RESULT(savecode, savemove, dcode, apos, move,
"attack effective");
@@ -3564,7 +3601,7 @@
{
int color = board[str];
int other = OTHER_COLOR(color);
- int xpos;
+ int xpos = NO_MOVE;
int r;
int k;
int liberties;
@@ -3576,6 +3613,7 @@
int savecode = 0;
int pass;
int saved_num_moves = 0;
+ int suggest_move = NO_MOVE;
SETUP_TRACE_INFO("attack4", str);
@@ -3645,7 +3683,7 @@
}
if (pass == 0 || pass == 1) {
- order_moves(str, &moves, other, read_function_name, saved_num_moves);
+ order_moves(str, &moves, other, read_function_name, saved_num_moves,
*move);
/* Try the moves collected so far. */
for (k = saved_num_moves; k < moves.num; k++) {
@@ -3675,8 +3713,10 @@
popgo();
}
else {
- if (do_find_defense(str, NULL, new_komaster, new_kom_pos) != WIN
- && do_attack(str, NULL, new_komaster, new_kom_pos) != 0) {
+ if (do_find_defense(str, &suggest_move, new_komaster,
+ new_kom_pos) != WIN
+ && do_attack(str, &suggest_move, new_komaster,
+ new_kom_pos) != 0) {
savemove = xpos;
savecode = KO_B;
}
@@ -4685,7 +4725,7 @@
break_chain_moves(str, &moves);
set_up_snapback_moves(str, lib, &moves);
- order_moves(str, &moves, color, read_function_name, 0);
+ order_moves(str, &moves, color, read_function_name, 0, NO_MOVE);
for (k = 0; k < moves.num; k++) {
int ko_capture;
@@ -4932,7 +4972,7 @@
static void
order_moves(int str, struct reading_moves *moves, int color,
- const char *funcname, int first_move)
+ const char *funcname, int first_move, int killer)
{
int string_color = board[str];
int string_libs = countlib(str);
@@ -5094,6 +5134,8 @@
else
moves->score[r] += attack_save_score[5];
}
+ if (moves->pos[r] == killer)
+ moves->score[r] += 50;
}
/* Now sort the moves. We use selection sort since this array will
@@ -5522,7 +5564,7 @@
for (k = 0; k < 2; k++)
ADD_CANDIDATE_MOVE(libs[k], 0, moves);
- order_moves(str, &moves, other, read_function_name, 0);
+ order_moves(str, &moves, other, read_function_name, 0, NO_MOVE);
for (k = 0; k < moves.num; k++) {
int new_komaster;
@@ -5586,7 +5628,7 @@
moves.num = 1;
break_chain_moves(str, &moves);
- order_moves(str, &moves, color, read_function_name, 0);
+ order_moves(str, &moves, color, read_function_name, 0, NO_MOVE);
for (k = 0; k < moves.num; k++) {
int new_komaster;
- [gnugo-devel] The killer heuristic,
Evan Berggren Daniel <=