[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] yet another speedup in board.c
From: |
pogonyshev |
Subject: |
[gnugo-devel] yet another speedup in board.c |
Date: |
Thu, 20 Mar 2003 17:20:42 +0100 (MET) |
- speed optimization in do_play_move()
- bugfix do_commit_suicide()
it's a long time since the last speed optimization patch ;) the idea
of this one was to use the fact that do_play_move() is mainly called
from do_trymove(), which handles suicidal moves itself (claims they
are illegal). so i rewrote do_play_move() and it now plays only non-
suicidal moves (play_move_no_history() plays suicides through
do_commit_suicide()).
i also fixed do_commit_suicide() to count the suicidal stone as captured.
before (profiles on nngs.tst):
6.98 61.32 61.32 138574088 0.00 0.00 scan_for_patterns
5.56 110.15 48.83 397423301 0.00 0.00 fastlib
[ 4.31 148.02 37.87 157980659 0.00 0.00 do_play_move ]
3.55 179.17 31.15 644720 0.00 0.00
compute_connection_distances
3.40 209.02 29.85 137787887 0.00 0.00 order_moves
-----------------------------------------------
0.00 0.00 14542/157980659 play_move_no_history
[692]
37.87 42.98 157966117/157980659 do_trymove [31]
[55] 9.2 37.87 42.98 157980659 do_play_move [55]
2.98 15.65 19332027/19332027 do_remove_string [111]
10.64 0.00 65885833/65885833 create_new_string [145]
7.65 0.00 145154520/212378758 remove_liberty [143]
6.06 0.00 157980659/186488829 hashdata_invert_stone
[160]
0.00 0.00 194/43172815 update_liberties [140]
-----------------------------------------------
after:
7.05 60.51 60.51 138574088 0.00 0.00 scan_for_patterns
...
3.26 230.88 27.96 169365412 0.00 0.00
incremental_order_moves
2.81 255.03 24.15 997991 0.00 0.00 accumulate_influence
[ 2.62 277.51 22.48 157980659 0.00 0.00 do_play_move ]
2.58 299.67 22.16 157966117 0.00 0.00 undo_trymove
2.50 321.13 21.46 181443 0.00 0.00 do_push_owl
-----------------------------------------------
0.00 0.00 14542/157980659 play_move_no_history
[672]
22.48 41.54 157966117/157980659 do_trymove [33]
[59] 7.5 22.48 41.55 157980659 do_play_move [59]
2.94 14.81 19332027/19332027 do_remove_string [111]
10.52 0.00 65885833/65885833 create_new_string [145]
7.74 0.00 145154520/212378750 remove_liberty [143]
5.54 0.00 157980659/186488829 hashdata_invert_stone
[165]
0.00 0.00 204/43172887 update_liberties [142]
-----------------------------------------------
to a total speedup of around 1.5%. i haven't rerun the regressions, but
there
must not be any changes (works as should on reading.tst and nngs.tst).
Paul
--- ../engine/board.c.orig 2003-03-20 13:37:29.000000000 +0200
+++ ../engine/board.c 2003-03-20 14:18:20.000000000 +0200
@@ -300,7 +300,8 @@ static void undo_trymove(void);
static void new_position(void);
static int propagate_string(int stone, int str);
static void find_liberties_and_neighbors(int s);
-static int do_remove_string(int s);
+static int do_remove_string(int str);
+static void do_commit_suicide(int pos, int color);
static void do_play_move(int pos, int color);
static int slow_approxlib(int pos, int color, int maxlib, int *libs);
@@ -939,7 +940,10 @@ play_move_no_history(int pos, int color)
ASSERT1(board[pos] == EMPTY, pos);
/* Do play the move. */
- do_play_move(pos, color);
+ if (!is_suicide(pos, color))
+ do_play_move(pos, color);
+ else
+ do_commit_suicide(pos, color);
#if CHECK_HASHING
/* Check the hash table to see if it equals the previous one. */
@@ -3856,8 +3860,9 @@ remove_liberty(int str_number, int pos)
*/
static int
-do_remove_string(int s)
+do_remove_string(int str)
{
+ int s = string_number[str];
int pos;
int k;
@@ -4275,27 +4280,36 @@ assimilate_neighbor_strings(int pos)
}
-/* Suicide at pos. Remove the neighboring friendly strings.
+/* Suicide at `pos' (the function assumes that the move is indeed
suicidal).
+ * Remove the neighboring friendly strings.
*/
static void
do_commit_suicide(int pos, int color)
{
if (board[SOUTH(pos)] == color)
- do_remove_string(string_number[SOUTH(pos)]);
+ do_remove_string(SOUTH(pos));
if (board[WEST(pos)] == color)
- do_remove_string(string_number[WEST(pos)]);
+ do_remove_string(WEST(pos));
if (board[NORTH(pos)] == color)
- do_remove_string(string_number[NORTH(pos)]);
+ do_remove_string(NORTH(pos));
if (board[EAST(pos)] == color)
- do_remove_string(string_number[EAST(pos)]);
+ do_remove_string(EAST(pos));
+
+ /* Count the stone we "played" as captured. */
+ if (color == WHITE)
+ white_captured++;
+ else
+ black_captured++;
}
-/* Play a move without legality checking. Suicide is allowed.
+/* Play a move without legality checking. This is a low-level function,
+ * it assumes that the move is not a suicide. Such cases must be handled
+ * where the function is called.
*/
static void
@@ -4304,103 +4318,78 @@ do_play_move(int pos, int color)
int other = OTHER_COLOR(color);
int captured_stones = 0;
int neighbor_allies = 0;
- int have_liberties = 0;
int s = -1;
- int south = SOUTH(pos);
- int west = WEST(pos);
- int north = NORTH(pos);
- int east = EAST(pos);
-
- /* Remove captured stones and check for suicide.*/
- if (board[south] == other && LIBERTIES(south) == 1)
- captured_stones += do_remove_string(string_number[south]);
-
- if (board[west] == other && LIBERTIES(west) == 1)
- captured_stones += do_remove_string(string_number[west]);
-
- if (board[north] == other && LIBERTIES(north) == 1)
- captured_stones += do_remove_string(string_number[north]);
-
- if (board[east] == other && LIBERTIES(east) == 1)
- captured_stones += do_remove_string(string_number[east]);
-
-
- if (captured_stones == 0) {
- if (LIBERTY(south)
- || (board[south] == color && LIBERTIES(south) > 1))
- have_liberties = 1;
- else if (LIBERTY(west)
- || (board[west] == color && LIBERTIES(west) > 1))
- have_liberties = 1;
- else if (LIBERTY(north)
- || (board[north] == color && LIBERTIES(north) > 1))
- have_liberties = 1;
- else if (LIBERTY(east)
- ||(board[east] == color && LIBERTIES(east) > 1))
- have_liberties = 1;
- }
- else
- have_liberties = 1;
-
- /* No captures and no liberties -> suicide. */
- if (have_liberties == 0 && captured_stones == 0) {
- do_commit_suicide(pos, color);
- return;
- }
-
- /* Put down the stone. */
- DO_ADD_STONE(pos, color);
-
- /* Count the number of adjacent strings of my color and remove
- * pos as liberty for the adjacent opponent strings.
- */
+ /* Clear string mark. */
string_mark++;
- if (UNMARKED_COLOR_STRING(south, color)) {
+ /* Look in all directions. Count the number of neighbor strings of the
same
+ * color, remove captured strings and remove `pos' as liberty for
opponent
+ * strings that are not captured.
+ */
+ if (board[SOUTH(pos)] == color) {
neighbor_allies++;
- s = string_number[south];
- MARK_STRING(south);
+ s = string_number[SOUTH(pos)];
+ MARK_STRING(SOUTH(pos));
}
- else if (UNMARKED_COLOR_STRING(south, other)) {
- remove_liberty(string_number[south], pos);
- MARK_STRING(south);
- }
-
- if (UNMARKED_COLOR_STRING(west, color)) {
+ else if (board[SOUTH(pos)] == other) {
+ if (LIBERTIES(SOUTH(pos)) > 1) {
+ remove_liberty(string_number[SOUTH(pos)], pos);
+ MARK_STRING(SOUTH(pos));
+ }
+ else
+ captured_stones += do_remove_string(SOUTH(pos));
+ }
+
+ if (UNMARKED_COLOR_STRING(WEST(pos), color)) {
neighbor_allies++;
- s = string_number[west];
- MARK_STRING(west);
+ s = string_number[WEST(pos)];
+ MARK_STRING(WEST(pos));
}
- else if (UNMARKED_COLOR_STRING(west, other)) {
- remove_liberty(string_number[west], pos);
- MARK_STRING(west);
- }
-
- if (UNMARKED_COLOR_STRING(north, color)) {
+ else if (UNMARKED_COLOR_STRING(WEST(pos), other)) {
+ if (LIBERTIES(WEST(pos)) > 1) {
+ remove_liberty(string_number[WEST(pos)], pos);
+ MARK_STRING(WEST(pos));
+ }
+ else
+ captured_stones += do_remove_string(WEST(pos));
+ }
+
+ if (UNMARKED_COLOR_STRING(NORTH(pos), color)) {
neighbor_allies++;
- s = string_number[north];
- MARK_STRING(north);
+ s = string_number[NORTH(pos)];
+ MARK_STRING(NORTH(pos));
}
- else if (UNMARKED_COLOR_STRING(north, other)) {
- remove_liberty(string_number[north], pos);
- MARK_STRING(north);
- }
-
- if (UNMARKED_COLOR_STRING(east, color)) {
+ else if (UNMARKED_COLOR_STRING(NORTH(pos), other)) {
+ if (LIBERTIES(NORTH(pos)) > 1) {
+ remove_liberty(string_number[NORTH(pos)], pos);
+ MARK_STRING(NORTH(pos));
+ }
+ else
+ captured_stones += do_remove_string(NORTH(pos));
+ }
+
+ if (UNMARKED_COLOR_STRING(EAST(pos), color)) {
neighbor_allies++;
- s = string_number[east];
+ s = string_number[EAST(pos)];
#if 0
- MARK_STRING(east);
+ MARK_STRING(EAST(pos));
#endif
}
- else if (UNMARKED_COLOR_STRING(east, other)) {
- remove_liberty(string_number[east], pos);
+ else if (UNMARKED_COLOR_STRING(EAST(pos), other)) {
+ if (LIBERTIES(EAST(pos)) > 1) {
+ remove_liberty(string_number[EAST(pos)], pos);
#if 0
- MARK_STRING(east);
+ MARK_STRING(EAST(pos));
#endif
- }
-
+ }
+ else
+ captured_stones += do_remove_string(EAST(pos));
+ }
+
+ /* Put down the stone. */
+ DO_ADD_STONE(pos, color);
+
/* Choose strategy depending on the number of friendly neighbors. */
if (neighbor_allies == 0)
create_new_string(pos);
--
+++ GMX - Mail, Messaging & more http://www.gmx.net +++
Bitte lächeln! Fotogalerie online mit GMX ohne eigene Homepage!
- [gnugo-devel] yet another speedup in board.c,
pogonyshev <=