gnugo-devel
[Top][All Lists]
Advanced

[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!





reply via email to

[Prev in Thread] Current Thread [Next in Thread]