| 1 | @menu |
| 2 | * Board Data Structures:: Board Data Structures |
| 3 | * The Board Array:: One-dimensional board array |
| 4 | * Incremental Board:: Incremental board data structures |
| 5 | * Some Board Functions:: Explanation of some board functions |
| 6 | @end menu |
| 7 | |
| 8 | The foundation of the GNU Go engine is a library of very efficient |
| 9 | routines for handling go boards. This board library, called |
| 10 | @file{libboard}, can be used for those programs that only need a |
| 11 | basic go board but no AI capability. One such program is |
| 12 | @file{patterns/joseki.c}, which compiles joseki pattern |
| 13 | databases from SGF files. |
| 14 | |
| 15 | If you want to use the board library in your own program, you need all |
| 16 | the .c-files listed under libboard_SOURCES in engine/Makefile.am, and |
| 17 | the files in the directories sgf/ and utils/. Then you should include |
| 18 | engine/board.h in your code. |
| 19 | |
| 20 | The library consists of the following files: |
| 21 | |
| 22 | @itemize |
| 23 | @item @file{board.h} |
| 24 | @quotation |
| 25 | The public interface to the board library. |
| 26 | @end quotation |
| 27 | |
| 28 | @item @file{board.c} |
| 29 | @quotation |
| 30 | The basic board code. It uses incremental algorithms for keeping track |
| 31 | of strings and liberties on the go board. |
| 32 | @end quotation |
| 33 | |
| 34 | @item @file{boardlib.c} |
| 35 | @quotation |
| 36 | This contains all global variable of the board library. |
| 37 | @end quotation |
| 38 | |
| 39 | @item @file{hash.c} |
| 40 | @quotation |
| 41 | Code for hashing go positions. |
| 42 | @end quotation |
| 43 | |
| 44 | @item @file{sgffile.c} |
| 45 | @quotation |
| 46 | Implementation of output file in SGF format. |
| 47 | @end quotation |
| 48 | |
| 49 | @item @file{printutils.c} |
| 50 | @quotation |
| 51 | Utilities for printing go boards and other things. |
| 52 | @end quotation |
| 53 | |
| 54 | @end itemize |
| 55 | |
| 56 | To use the board library, you must include @file{liberty.h} just like |
| 57 | when you use the whole engine, but of course you cannot use all the |
| 58 | functions declared in it, i.e. the functions that are part of the |
| 59 | engine, but not part of the board library. You must link your |
| 60 | application with @code{libboard.a}. |
| 61 | |
| 62 | @node Board Data Structures |
| 63 | @section Board Data structures |
| 64 | |
| 65 | The basic data structures of the board correspond tightly to the |
| 66 | @code{board_state} struct described in @xref{The Board State}. They are all |
| 67 | stored in global variables for efficiency reasons, the most important of which |
| 68 | are: |
| 69 | |
| 70 | @example |
| 71 | @group |
| 72 | |
| 73 | int board_size; |
| 74 | Intersection board[MAXSIZE]; |
| 75 | int board_ko_pos; |
| 76 | |
| 77 | float komi; |
| 78 | int white_captured; |
| 79 | int black_captured; |
| 80 | |
| 81 | Hash_data hashdata; |
| 82 | @end group |
| 83 | @end example |
| 84 | |
| 85 | The description of the @code{Position} struct is applicable to these |
| 86 | variables also, so we won't duplicate it here. All these variables are |
| 87 | globals for performance reasons. Behind these variables, there are a |
| 88 | number of other private data structures. These implement incremental |
| 89 | handling of strings, liberties and other properties |
| 90 | (@pxref{Incremental Board}). The variable @code{hashdata} contains information |
| 91 | about the hash value for the current position (@pxref{Hashing}). |
| 92 | |
| 93 | These variables should never be manipulated directly, since they are |
| 94 | only the front end for the incremental machinery. They can be read, but |
| 95 | should only be written by using the functions described in the next |
| 96 | section. If you write directly to them, the incremental data structures |
| 97 | will become out of sync with each other, and a crash is the likely |
| 98 | result. |
| 99 | |
| 100 | @node The Board Array |
| 101 | @section The Board Array |
| 102 | |
| 103 | GNU Go represents the board in a one-dimensional array called |
| 104 | @code{board}. For some purposes a two dimensional indexing of the |
| 105 | board by parameters @code{(i,j)} might be used. |
| 106 | |
| 107 | The @code{board} array includes out-of-board markers around the |
| 108 | board. To make the relation to the old two-dimensional board |
| 109 | representation clear, this figure shows how the 1D indices correspond |
| 110 | to the 2D indices when MAX_BOARD is 7. |
| 111 | |
| 112 | @example |
| 113 | @group |
| 114 | j -1 0 1 2 3 4 5 6 |
| 115 | i +---------------------------------- |
| 116 | -1| 0 1 2 3 4 5 6 7 |
| 117 | 0| 8 9 10 11 12 13 14 15 |
| 118 | 1| 16 17 18 19 20 21 22 23 |
| 119 | 2| 24 25 26 27 28 29 30 31 |
| 120 | 3| 32 33 34 35 36 37 38 39 |
| 121 | 4| 40 41 42 43 44 45 46 47 |
| 122 | 5| 48 49 50 51 52 53 54 55 |
| 123 | 6| 56 57 58 59 60 61 62 63 |
| 124 | 7| 64 65 66 67 68 69 70 71 72 |
| 125 | @end group |
| 126 | @end example |
| 127 | |
| 128 | To convert between a 1D index @code{pos} and a 2D index @code{(i,j)}, |
| 129 | the macros @code{POS}, @code{I}, and @code{J} are provided, defined as |
| 130 | below: |
| 131 | |
| 132 | @example |
| 133 | #define POS(i, j) ((MAX_BOARD + 2) + (i) * (MAX_BOARD + 1) + (j)) |
| 134 | #define I(pos) ((pos) / (MAX_BOARD + 1) - 1) |
| 135 | #define J(pos) ((pos) % (MAX_BOARD + 1) - 1) |
| 136 | @end example |
| 137 | |
| 138 | All 1D indices not corresponding to points on the board have the out |
| 139 | of board marker value @code{GRAY}. Thus if @code{board_size} and |
| 140 | @code{MAX_BOARD} both are 7, this looks like |
| 141 | |
| 142 | @example |
| 143 | @group |
| 144 | j -1 0 1 2 3 4 5 6 |
| 145 | i +---------------------------------- |
| 146 | -1| # # # # # # # # |
| 147 | 0| # . . . . . . . |
| 148 | 1| # . . . . . . . |
| 149 | 2| # . . . . . . . |
| 150 | 3| # . . . . . . . |
| 151 | 4| # . . . . . . . |
| 152 | 5| # . . . . . . . |
| 153 | 6| # . . . . . . . |
| 154 | 7| # # # # # # # # # |
| 155 | @end group |
| 156 | @end example |
| 157 | |
| 158 | The indices marked @samp{#} have value @code{GRAY}. |
| 159 | If @code{MAX_BOARD} is 7 and @code{board_size} is only 5: |
| 160 | |
| 161 | @example |
| 162 | @group |
| 163 | j -1 0 1 2 3 4 5 6 |
| 164 | i +---------------------------------- |
| 165 | -1| # # # # # # # # |
| 166 | 0| # . . . . . # # |
| 167 | 1| # . . . . . # # |
| 168 | 2| # . . . . . # # |
| 169 | 3| # . . . . . # # |
| 170 | 4| # . . . . . # # |
| 171 | 5| # # # # # # # # |
| 172 | 6| # # # # # # # # |
| 173 | 7| # # # # # # # # # |
| 174 | @end group |
| 175 | @end example |
| 176 | |
| 177 | Navigation on the board is done by the @code{SOUTH}, @code{WEST}, |
| 178 | @code{NORTH}, and @code{EAST} macros, |
| 179 | |
| 180 | @example |
| 181 | #define NS (MAX_BOARD + 1) |
| 182 | #define WE 1 |
| 183 | #define SOUTH(pos) ((pos) + NS) |
| 184 | #define WEST(pos) ((pos) - 1) |
| 185 | #define NORTH(pos) ((pos) - NS) |
| 186 | #define EAST(pos) ((pos) + 1) |
| 187 | @end example |
| 188 | |
| 189 | There are also shorthand macros @code{SW}, @code{NW}, @code{NE}, |
| 190 | @code{SE}, @code{SS}, @code{WW}, @code{NN}, @code{EE} for two step |
| 191 | movements. |
| 192 | |
| 193 | Any movement from a point on the board to an adjacent or diagonal |
| 194 | vertex is guaranteed to produce a valid index into the board array, and |
| 195 | the color found is GRAY if it is not on the board. To do explicit tests |
| 196 | for out of board there are two macros |
| 197 | |
| 198 | @example |
| 199 | #define ON_BOARD(pos) (board[pos] != GRAY) |
| 200 | #define ON_BOARD1(pos) (((unsigned) (pos) < BOARDSIZE) && board[pos] != GRAY) |
| 201 | @end example |
| 202 | |
| 203 | where the first one should be used in the algorithms and the second |
| 204 | one is useful for assertion tests. |
| 205 | |
| 206 | The advantage of a one-dimensional board array is that it gives a |
| 207 | significant performance advantage. We need only one variable to determine |
| 208 | a board position, which means that many functions need less arguments. Also, |
| 209 | often one computation is sufficient for 1D-coordinate where we would need |
| 210 | two with two 2D-coordinates: If we, for example, want to have the |
| 211 | coordinate of the upper right of @code{pos}, we can do this with |
| 212 | @code{NORTH(EAST(pos))} instead of @code{(i+1, j-1)}. |
| 213 | |
| 214 | @strong{Important}: The 2D coordinate @code{(-1,-1)}, which is used for |
| 215 | pass and sometimes to indicate no point, maps to the 1D coordinate |
| 216 | @code{0}, not to @code{-1}. Instead of a plain @code{0}, use one of the |
| 217 | macros @code{NO_MOVE} or @code{PASS_MOVE}. |
| 218 | |
| 219 | A loop over multiple directions is straightforwardly written: |
| 220 | |
| 221 | @example |
| 222 | for (k = 0; k < 4; k++) @{ |
| 223 | int d = delta[k]; |
| 224 | do_something(pos + d); |
| 225 | @} |
| 226 | @end example |
| 227 | |
| 228 | The following constants are useful for loops over the entire board and |
| 229 | allocation of arrays with a 1-1 mapping to the board. |
| 230 | |
| 231 | @example |
| 232 | #define BOARDSIZE ((MAX_BOARD + 2) * (MAX_BOARD + 1) + 1) |
| 233 | #define BOARDMIN (MAX_BOARD + 2) |
| 234 | #define BOARDMAX (MAX_BOARD + 1) * (MAX_BOARD + 1) |
| 235 | @end example |
| 236 | |
| 237 | @code{BOARDSIZE} is the actual size of the 1D board array, |
| 238 | @code{BOARDMIN} is the first index corresponding to a point on the |
| 239 | board, and @code{BOARDMAX} is one larger than the last index corresponding to |
| 240 | a point on the board. |
| 241 | |
| 242 | Often one wants to traverse the board, carrying out some function |
| 243 | at every vertex. Here are two possible ways of doing this: |
| 244 | |
| 245 | @example |
| 246 | int m, n; |
| 247 | for (m = 0; m < board_size; m++) |
| 248 | for (n = 0; n < board_size; n++) @{ |
| 249 | do_something(POS(m, n)); |
| 250 | @} |
| 251 | @end example |
| 252 | |
| 253 | Or: |
| 254 | |
| 255 | @example |
| 256 | int pos; |
| 257 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) @{ |
| 258 | if (ON_BOARD(pos)) |
| 259 | do_something(pos); |
| 260 | @} |
| 261 | @end example |
| 262 | |
| 263 | |
| 264 | @node Incremental Board |
| 265 | @section Incremental Board data structures |
| 266 | |
| 267 | In addition to the global board state, the algorithms in @file{board.c} |
| 268 | implement a method of incremental updates that keeps track of the |
| 269 | following information for each string: |
| 270 | |
| 271 | @itemize @bullet |
| 272 | @item The color of the string. |
| 273 | @item Number of stones in the string. |
| 274 | @item Origin of the string, i.e. a canonical reference point, defined |
| 275 | to be the stone with smallest 1D board coordinate. |
| 276 | @item A list of the stones in the string. |
| 277 | @item Number of liberties. |
| 278 | @item A list of the liberties. If there are too many liberties the list is |
| 279 | truncated. |
| 280 | @item The number of neighbor strings. |
| 281 | @item A list of the neighbor strings. |
| 282 | @end itemize |
| 283 | |
| 284 | The basic data structure is |
| 285 | |
| 286 | @example |
| 287 | struct string_data @{ |
| 288 | int color; /* Color of string, BLACK or WHITE */ |
| 289 | int size; /* Number of stones in string. */ |
| 290 | int origin; /* Coordinates of "origin", i.e. */ |
| 291 | /* "upper left" stone. */ |
| 292 | int liberties; /* Number of liberties. */ |
| 293 | int libs[MAX_LIBERTIES]; /* Coordinates of liberties. */ |
| 294 | int neighbors; /* Number of neighbor strings */ |
| 295 | int neighborlist[MAXCHAIN]; /* List of neighbor string numbers. */ |
| 296 | int mark; /* General purpose mark. */ |
| 297 | @}; |
| 298 | |
| 299 | struct string_data string[MAX_STRINGS]; |
| 300 | @end example |
| 301 | |
| 302 | It should be clear that almost all information is stored in the |
| 303 | @code{string} array. To get a mapping from the board coordinates to the |
| 304 | @code{string} array we have |
| 305 | |
| 306 | @example |
| 307 | static int string_number[BOARDMAX]; |
| 308 | @end example |
| 309 | |
| 310 | @noindent |
| 311 | which contains indices into the @code{string} array. This information is only |
| 312 | valid at nonempty vertices, however, so it is necessary to first |
| 313 | verify that @code{board[pos] != EMPTY}. |
| 314 | |
| 315 | The @code{string_data} structure does not include an array of the stone |
| 316 | coordinates. This information is stored in a separate array: |
| 317 | |
| 318 | @example |
| 319 | static int next_stone[BOARDMAX]; |
| 320 | @end example |
| 321 | |
| 322 | This array implements cyclic linked lists of stones. Each vertex |
| 323 | contains a pointer to another (possibly the same) vertex. Starting at |
| 324 | an arbitrary stone on the board, following these pointers should |
| 325 | traverse the entire string in an arbitrary order before coming back to |
| 326 | the starting point. As for the 'string_number' array, this information |
| 327 | is invalid at empty points on the board. This data structure has the |
| 328 | good properties of requiring fixed space (regardless of the number of |
| 329 | strings) and making it easy to add a new stone or join two strings. |
| 330 | |
| 331 | Additionally the code makes use of some work variables: |
| 332 | |
| 333 | @example |
| 334 | static int ml[BOARDMAX]; |
| 335 | static int liberty_mark; |
| 336 | static int string_mark; |
| 337 | static int next_string; |
| 338 | static int strings_initialized = 0; |
| 339 | @end example |
| 340 | |
| 341 | The @code{ml} array and @code{liberty_mark} are used to "mark" liberties on |
| 342 | the board, e.g. to avoid counting the same liberty twice. The convention is |
| 343 | that if @code{ml[pos]} has the same value as @code{liberty_mark}, then |
| 344 | @code{pos} is marked. To clear all marks it suffices to increase the value |
| 345 | of @code{liberty_mark}, since it is never allowed to decrease. |
| 346 | |
| 347 | The same relation holds between the @code{mark} field of the @code{string_data} |
| 348 | structure and @code{string_mark}. Of course these are used for marking |
| 349 | individual strings. |
| 350 | |
| 351 | @code{next_string} gives the number of the next available entry in the |
| 352 | @code{string} array. Then @code{strings_initialized} is set to one when |
| 353 | all data structures are known to be up to date. Given an arbitrary board |
| 354 | position in the @samp{board} array, this is done by calling |
| 355 | @code{incremental_board_init()}. It is not necessary to call this |
| 356 | function explicitly since any other function that needs the information |
| 357 | does this if it has not been done. |
| 358 | |
| 359 | The interesting part of the code is the incremental update of the data |
| 360 | structures when a stone is played and subsequently removed. To |
| 361 | understand the strategies involved in adding a stone it is necessary |
| 362 | to first know how undoing a move works. The idea is that as soon as |
| 363 | some piece of information is about to be changed, the old value is |
| 364 | pushed onto a stack which stores the value and its address. The stack |
| 365 | is built from the following structures: |
| 366 | |
| 367 | @example |
| 368 | struct change_stack_entry @{ |
| 369 | int *address; |
| 370 | int value; |
| 371 | @}; |
| 372 | |
| 373 | struct change_stack_entry change_stack[STACK_SIZE]; |
| 374 | int change_stack_index; |
| 375 | @end example |
| 376 | |
| 377 | @noindent |
| 378 | and manipulated with the macros |
| 379 | |
| 380 | @example |
| 381 | BEGIN_CHANGE_RECORD() |
| 382 | PUSH_VALUE(v) |
| 383 | POP_MOVE() |
| 384 | @end example |
| 385 | |
| 386 | Calling @code{BEGIN_CHANGE_RECORD()} stores a null pointer in the address |
| 387 | field to indicate the start of changes for a new move. As mentioned |
| 388 | earlier @code{PUSH_VALUE()} stores a value and its corresponding address. |
| 389 | Assuming that all changed information has been duly pushed onto the |
| 390 | stack, undoing the move is only a matter of calling @code{POP_MOVE()}, |
| 391 | which simply assigns the values to the addresses in the reverse order |
| 392 | until the null pointer is reached. This description is slightly |
| 393 | simplified because this stack can only store 'int' values and we need |
| 394 | to also store changes to the board. Thus we have two parallel stacks |
| 395 | where one stores @code{int} values and the other one stores |
| 396 | @code{Intersection} values. |
| 397 | |
| 398 | When a new stone is played on the board, first captured opponent |
| 399 | strings, if any, are removed. In this step we have to push the board |
| 400 | values and the @code{next_stone} pointers for the removed stones, and |
| 401 | update the liberties and neighbor lists for the neighbors of the |
| 402 | removed strings. We do not have to push all information in the |
| 403 | 'string' entries of the removed strings however. As we do not reuse |
| 404 | the entries they will remain intact until the move is pushed and they |
| 405 | are back in use. |
| 406 | |
| 407 | After this we put down the new stone and get three distinct cases: |
| 408 | |
| 409 | @enumerate |
| 410 | @item The new stone is isolated, i.e. it has no friendly neighbor. |
| 411 | @item The new stone has exactly one friendly neighbor. |
| 412 | @item The new stone has at least two friendly neighbors. |
| 413 | @end enumerate |
| 414 | |
| 415 | The first case is easiest. Then we create a new string by using the |
| 416 | number given by @code{next_string} and increasing this variable. The string |
| 417 | will have size one, @code{next_stone} points directly back on itself, the |
| 418 | liberties can be found by looking for empty points in the four |
| 419 | directions, possible neighbor strings are found in the same way, and |
| 420 | those need also to remove one liberty and add one neighbor. |
| 421 | |
| 422 | In the second case we do not create a new string but extend the |
| 423 | neighbor with the new stone. This involves linking the new stone into |
| 424 | the cyclic chain, if needed moving the origin, and updating liberties |
| 425 | and neighbors. Liberty and neighbor information also needs updating |
| 426 | for the neighbors of the new stone. |
| 427 | |
| 428 | In the third case finally, we need to join already existing strings. |
| 429 | In order not to have to store excessive amounts of information, we |
| 430 | create a new string for the new stone and let it assimilate the |
| 431 | neighbor strings. Thus all information about those can simply be left |
| 432 | around in the 'string' array, exactly as for removed strings. Here it |
| 433 | becomes a little more complex to keep track of liberties and neighbors |
| 434 | since those may have been shared by more than one of the joined |
| 435 | strings. Making good use of marks it all becomes rather |
| 436 | straightforward anyway. |
| 437 | |
| 438 | The often used construction |
| 439 | |
| 440 | @example |
| 441 | pos = FIRST_STONE(s); |
| 442 | do @{ |
| 443 | ... |
| 444 | pos = NEXT_STONE(pos); |
| 445 | @} while (!BACK_TO_FIRST_STONE(s, pos)); |
| 446 | @end example |
| 447 | |
| 448 | @noindent |
| 449 | traverses the stones of the string with number @samp{s} exactly once, |
| 450 | with @code{pos} holding the coordinates. In general @code{pos} is |
| 451 | used as board coordinate and @samp{s} as an index into the |
| 452 | @code{string} array or sometimes a pointer to an entry in the |
| 453 | @code{string} array. |
| 454 | |
| 455 | @node Some Board Functions |
| 456 | @section Some Board Functions |
| 457 | |
| 458 | @strong{Reading}, often called @strong{search} in computer game |
| 459 | theory, is a fundamental process in GNU Go. This is the process |
| 460 | of generating hypothetical future boards in order to determine |
| 461 | the answer to some question, for example "can these stones live." |
| 462 | Since these are hypothetical future positions, it is important |
| 463 | to be able to undo them, ultimately returning to the present |
| 464 | board. Thus a move stack is maintained during reading. When |
| 465 | a move is tried, by the function @code{trymove}, or its |
| 466 | variant @code{tryko}. This function pushes the current board |
| 467 | on the stack and plays a move. The stack pointer @code{stackp}, |
| 468 | which keeps track of the position, is incremented. The function |
| 469 | @code{popgo()} pops the move stack, decrementing @code{stackp} and |
| 470 | undoing the last move made. |
| 471 | |
| 472 | Every successful @code{trymove()} must be matched with a @code{popgo()}. |
| 473 | Thus the correct way of using this function is: |
| 474 | |
| 475 | @example |
| 476 | @group |
| 477 | |
| 478 | if (trymove(pos, color, ... )) @{ |
| 479 | ... [potentially lots of code here] |
| 480 | popgo(); |
| 481 | @} |
| 482 | |
| 483 | @end group |
| 484 | @end example |
| 485 | |
| 486 | @noindent |
| 487 | |
| 488 | In case the move is a ko capture, the legality of the capture is subject to |
| 489 | the komaster scheme (@pxref{Ko}). |
| 490 | |
| 491 | @itemize @bullet |
| 492 | @item @code{int trymove(int pos, int color, const char *message)} |
| 493 | @findex trymove |
| 494 | @quotation |
| 495 | Returns true if @code{(pos)} is a legal move for @code{color}. In that |
| 496 | case, it pushes the board on the stack and makes the move, incrementing |
| 497 | @code{stackp}. If the reading code is recording reading variations (as |
| 498 | with @option{--decide-string} or with @option{-o}), the string |
| 499 | @code{*message} will be inserted in the SGF file as a comment. The |
| 500 | comment will also refer to the string at @code{str} if this is not |
| 501 | @code{0}. The value of @code{str} can be NO_MOVE if it is not needed but |
| 502 | otherwise the location of @code{str} is included in the comment. |
| 503 | @end quotation |
| 504 | @item @code{int tryko(int pos, int color, const char *message)} |
| 505 | @findex tryko |
| 506 | @quotation |
| 507 | @code{tryko()} pushes the position onto the stack, and makes a move |
| 508 | @code{pos} of @code{color}. The move is allowed even if it is an |
| 509 | illegal ko capture. It is to be imagined that @code{color} has made an |
| 510 | intervening ko threat which was answered and now the continuation is to |
| 511 | be explored. Return 1 if the move is legal with the above |
| 512 | caveat. Returns zero if it is not legal because of suicide. |
| 513 | @end quotation |
| 514 | |
| 515 | @item @code{void popgo()} |
| 516 | @findex popgo |
| 517 | @quotation |
| 518 | Pops the move stack. This function must (eventually) be called after a |
| 519 | succesful @code{trymove} or @code{tryko} to restore the board |
| 520 | position. It undoes all the changes done by the call to |
| 521 | @code{trymove/tryko} and leaves the board in the same state as it was |
| 522 | before the call. |
| 523 | |
| 524 | @strong{NOTE}: If @code{trymove/tryko} returns @code{0}, i.e. the tried |
| 525 | move was not legal, you must @strong{not} call @code{popgo}. |
| 526 | @end quotation |
| 527 | |
| 528 | @item @code{int komaster_trymove(int pos, int color, const char *message, int str, int *is_conditional_ko, int consider_conditional_ko)} |
| 529 | @findex komaster_trymove |
| 530 | @quotation |
| 531 | Variation of @code{trymove}/@code{tryko} where ko captures (both |
| 532 | conditional and unconditional) must follow a komaster scheme |
| 533 | (@pxref{Ko}). |
| 534 | @end quotation |
| 535 | |
| 536 | @end itemize |
| 537 | |
| 538 | As you see, @code{trymove()} plays a move which can be easily |
| 539 | retracted (with @code{popgo()}) and it is call thousands of |
| 540 | times per actual game move as GNU Go analyzes the board position. |
| 541 | By contrast the function @code{play_move()} plays a move which |
| 542 | is intended to be permanent, though it is still possible to |
| 543 | undo it if, for example, the opponent retracts a move. |
| 544 | |
| 545 | @itemize @bullet |
| 546 | @item @code{void play_move(int pos, int color)} |
| 547 | @findex play_move |
| 548 | @quotation |
| 549 | Play a move. If you want to test for legality you should first call |
| 550 | @code{is_legal()}. This function strictly follows the algorithm: |
| 551 | @enumerate |
| 552 | @item Place a stone of given color on the board. |
| 553 | @item If there are any adjacent opponent strings without liberties, |
| 554 | remove them and increase the prisoner count. |
| 555 | @item If the newly placed stone is part of a string without liberties, |
| 556 | remove it and increase the prisoner count. |
| 557 | @end enumerate |
| 558 | In spite of the name ``permanent move'', this move can (usually) be |
| 559 | unplayed by @code{undo_move()}, but it is significantly more costly than |
| 560 | unplaying a temporary move. There are limitations on the available |
| 561 | move history, so under certain circumstances the move may not be |
| 562 | possible to unplay at a later time. |
| 563 | @end quotation |
| 564 | @item @code{int undo_move(int n)} |
| 565 | @findex undo_move |
| 566 | @quotation |
| 567 | Undo @samp{n} permanent moves. Returns 1 if successful and 0 if it fails. |
| 568 | If @samp{n} moves cannot be undone, no move is undone. |
| 569 | @end quotation |
| 570 | @end itemize |
| 571 | |
| 572 | Other board functions are documented in @xref{Board Utilities}. |
| 573 | |