1 /***************************************************************************
3 * Open \______ \ ____ ____ | | _\_ |__ _______ ___
4 * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5 * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6 * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
10 * Copyright (C) 2007-2009 Joshua Simmons <mud at majidejima dot com>
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version 2
15 * of the License, or (at your option) any later version.
17 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
18 * KIND, either express or implied.
20 ****************************************************************************/
31 unsigned int board_width
= MAX_BOARD_SIZE
;
32 unsigned int board_height
= MAX_BOARD_SIZE
;
34 /* Board has 'invalid' markers around each border */
35 unsigned char board_data
[(MAX_BOARD_SIZE
+ 2) * (MAX_BOARD_SIZE
+ 2)];
36 int white_captures
= 0;
37 int black_captures
= 0;
39 uint8_t board_marks
[(MAX_BOARD_SIZE
+ 2) * (MAX_BOARD_SIZE
+ 2)];
40 uint8_t current_mark
= 255;
42 /* there can't be any changes off of the board, so no need to add the
44 uint8_t board_changes
[MAX_BOARD_SIZE
* MAX_BOARD_SIZE
];
46 unsigned short ko_pos
= INVALID_POS
;
48 /* forward declarations */
49 static void setup_marks (void);
50 static void make_mark (unsigned short pos
);
51 static int get_liberties_helper (unsigned short pos
, unsigned char orig_color
);
52 static int flood_fill_helper (unsigned short pos
, unsigned char orig_color
,
56 /* these aren't "board marks" in the marks on the SGF sense, they are used
57 internally to mark already visited points and the like (such as when
58 doing liberty counting for groups)
60 We avoid having to clear the entire array every time by storing the
61 "current_mark" number and defining marked as "== current_mark". We
62 still need to clear the whole array once per "cycle" though, or we'd get
63 false positives sometimes
72 if (current_mark
== 0)
76 for (y
= 0; y
< board_height
; ++y
)
78 for (x
= 0; x
< board_width
; ++x
)
80 board_marks
[POS (x
, y
)] = 0;
87 make_mark (unsigned short pos
)
89 board_marks
[pos
] = current_mark
;
93 is_marked (unsigned short pos
)
95 return board_marks
[pos
] == current_mark
;
103 /* for the borders */
104 rb
->memset(board_data
, INVALID
, sizeof(board_data
));
106 /* now make the actual board part */
107 for (y
= 0; y
< board_height
; ++y
)
109 for (x
= 0; x
< board_width
; ++x
)
111 board_data
[POS (x
, y
)] = EMPTY
;
118 ko_pos
= INVALID_POS
;
122 set_size_board (int width
, int height
)
124 if (width
< MIN_BOARD_SIZE
|| width
> MAX_BOARD_SIZE
||
125 height
< MIN_BOARD_SIZE
|| height
> MAX_BOARD_SIZE
)
132 board_height
= height
;
139 get_point_board (unsigned short pos
)
141 return board_data
[pos
];
145 set_point_board (unsigned short pos
, unsigned char color
)
147 board_data
[pos
] = color
;
151 on_board (unsigned short pos
)
153 if (pos
< POS (0, 0) ||
154 pos
> POS (board_width
- 1, board_height
- 1) ||
155 get_point_board (pos
) == INVALID
)
166 get_liberties_board (unsigned short pos
)
168 if (!on_board (pos
) || get_point_board (pos
) == EMPTY
)
176 unsigned char orig_color
= get_point_board (pos
);
178 empty_stack (&parse_stack
);
179 push_pos_stack (&parse_stack
, pos
);
181 /* Since we only ever test for liberties in order to determine
182 captures and the like, there's no reason to count any liberties
183 higher than 2 (we sometimes need to know if something has 1 liberty
184 for dealing with ko) */
185 while (pop_pos_stack (&parse_stack
, &pos
) && ret_val
< 2)
187 ret_val
+= get_liberties_helper (NORTH (pos
), orig_color
);
188 ret_val
+= get_liberties_helper (SOUTH (pos
), orig_color
);
189 ret_val
+= get_liberties_helper (EAST (pos
), orig_color
);
190 ret_val
+= get_liberties_helper (WEST (pos
), orig_color
);
193 /* if there's more than two liberties, the stack isn't empty, so empty
195 empty_stack (&parse_stack
);
201 get_liberties_helper (unsigned short pos
, unsigned char orig_color
)
203 if (on_board (pos
) &&
204 get_point_board (pos
) != OTHER (orig_color
) && !is_marked (pos
))
208 if (get_point_board (pos
) == EMPTY
)
214 push_pos_stack (&parse_stack
, pos
);
223 flood_fill_board (unsigned short pos
, unsigned char color
)
225 if (!on_board (pos
) || get_point_board (pos
) == color
)
230 empty_stack (&parse_stack
);
234 unsigned char orig_color
= get_point_board (pos
);
236 set_point_board (pos
, color
);
238 push_pos_stack (&parse_stack
, pos
);
240 while (pop_pos_stack (&parse_stack
, &pos
))
242 ret_val
+= flood_fill_helper (NORTH (pos
), orig_color
, color
);
243 ret_val
+= flood_fill_helper (SOUTH (pos
), orig_color
, color
);
244 ret_val
+= flood_fill_helper (EAST (pos
), orig_color
, color
);
245 ret_val
+= flood_fill_helper (WEST (pos
), orig_color
, color
);
253 flood_fill_helper (unsigned short pos
, unsigned char orig_color
,
256 if (on_board (pos
) && get_point_board (pos
) == orig_color
)
258 set_point_board (pos
, color
);
259 push_pos_stack (&parse_stack
, pos
);
267 legal_move_board (unsigned short pos
, unsigned char color
, bool allow_suicide
)
269 /* you can always pass */
275 if (!on_board (pos
) || (color
!= BLACK
&& color
!= WHITE
))
280 if (pos
== ko_pos
&& color
== current_player
)
285 if (get_point_board (pos
) != EMPTY
)
290 /* don't need to save the current state, because it's always empty
291 since we tested for that above */
292 set_point_board (pos
, color
);
294 /* if we have liberties, it can't be illegal */
295 if (get_liberties_board (pos
) > 0 ||
296 /* if we can capture something, it can't be illegal */
297 (get_point_board (NORTH (pos
)) == OTHER (color
) &&
298 !get_liberties_board (NORTH (pos
))) ||
299 (get_point_board (SOUTH (pos
)) == OTHER (color
) &&
300 !get_liberties_board (SOUTH (pos
))) ||
301 (get_point_board (EAST (pos
)) == OTHER (color
) &&
302 !get_liberties_board (EAST (pos
))) ||
303 (get_point_board (WEST (pos
)) == OTHER (color
) &&
304 !get_liberties_board (WEST (pos
))) ||
305 /* if we're allowed to suicide, only multi-stone suicide is legal
306 (no ruleset allows single-stone suicide that I know of) */
307 (allow_suicide
&& (get_point_board (NORTH (pos
)) == color
||
308 get_point_board (SOUTH (pos
)) == color
||
309 get_point_board (EAST (pos
)) == color
||
310 get_point_board (WEST (pos
)) == color
)))
312 /* undo our previous set */
313 set_point_board (pos
, EMPTY
);
318 /* undo our previous set */
319 set_point_board (pos
, EMPTY
);
326 WRAP (unsigned short pos
)
342 else if ((unsigned int) x
>= board_width
)
349 y
= board_height
- 1;
351 else if ((unsigned int) y
>= board_height
)