Simple-Go

Simple-Go/src/simple-go.c
simple-go.c
⎇
Raw
1#include <simple-go/simple-go.h>
2
3go_board* create_board(go_coordinate size)
4{
5 go_board* board = malloc(sizeof(*board));
6 assert(board);
7 board->field_array = malloc(size*size*sizeof(*board->field_array));
8 assert(board->field_array);
9 for(go_coordinate i = 0; i < size*size; i++)
10 {
11 board->field_array[i] = EMPTY;
12 }
13 board->size = size;
14
15 return board;
16}
17
18void delete_board(go_board* board)
19{
20 free(board->field_array);
21 free(board);
22}
23
24game_state* create_game(go_coordinate size, float komi)
25{
26 game_state* game = malloc(sizeof(*game));
27 game->board = create_board(size);
28 game->black_turn = true;
29 game->komi = komi;
30 game->white_captured = 0;
31 game->black_captured = 0;
32
33 return game;
34}
35
36void delete_game(game_state* game)
37{
38 delete_board(game->board);
39 free(game);
40}
41
42bool check_bounds(const go_board* board, go_coordinate y, go_coordinate x)
43{
44 if(y < board->size && x < board->size)
45 return true;
46 else
47 return false;
48}
49
50void kill_group(game_state* game, const go_board* overlay)
51{
52 go_board* board = game->board;
53 double* captured = NULL;
54 for(go_coordinate y = 0; y < board->size; y++)
55 {
56 for(go_coordinate x = 0; x < board->size; x++)
57 {
58 if(get_board_at(overlay, y, x) == GROUP)
59 {
60 if(!captured)
61 captured = get_board_at(board, y, x) == BLACK ? &game->white_captured : &game->black_captured;
62 set_board_at(board, y, x, EMPTY);
63 (*captured)++;
64 }
65 }
66 }
67}
68
69void print_board(const go_board* board)
70{
71 for(go_coordinate y = 0; y < board->size; y++)
72 {
73 for(go_coordinate x = 0; x < board->size; x++)
74 {
75 putchar(get_board_at(board,y,x));
76 putchar(' ');
77 }
78 putchar('\n');
79 }
80}
81
82char* board_to_string(const go_board* board)
83{
84 size_t str_size = (board->size*2+6)*(board->size+2)+2;
85 char* ret = calloc(str_size+1,1);
86 unsigned int index = 0;
87 unsigned int board_index = 0;
88 ret[index++] = '\n';
89
90 for(unsigned int i = 0; i < board->size+2; i++)
91 {
92 if(i == 0 || i == board->size+1)
93 {
94 ret[index++] = ' ';
95 ret[index++] = ' ';
96 ret[index++] = ' ';
97
98 char current_char = 'A';
99 for(unsigned int j = 0; j < board->size; j++)
100 {
101 ret[index++] = (char)(current_char == 'I' ? current_char++, current_char++ : current_char++);
102 ret[index++] = ' ';
103 }
104
105 ret[index++] = ' ';
106 ret[index++] = ' ';
107 } else {
108 index += (unsigned int)sprintf(ret+index, "%2u", (unsigned int)(board->size+1-i));
109 ret[index++] = ' ';
110 for(unsigned int j = 0; j < board->size; j++)
111 {
112 ret[index++] = board->field_array[board_index++];
113 ret[index++] = ' ';
114 }
115 index += (unsigned int)sprintf(ret+index, "%-2u", (unsigned int)(board->size+1-i));
116 }
117 ret[index++] = '\n';
118 }
119
120 return ret;
121}
122
123
124bool group_attachable(const game_state* game, go_coordinate y, go_coordinate x)
125{
126 go_board* friendly_group = create_board(game->board->size);
127 find_group(game->board, friendly_group, y, x);
128 if(count_liberties(game->board, friendly_group) > 1)
129 {
130 delete_board(friendly_group);
131 return true;
132 } else {
133 delete_board(friendly_group);
134 return false;
135 }
136}
137
138bool group_killable(game_state* game, go_coordinate y, go_coordinate x)
139{
140 go_board* enemy_group = create_board(game->board->size);
141 find_group(game->board, enemy_group, y, x);
142 if(count_liberties(game->board, enemy_group) <= 1)
143 {
144 kill_group(game, enemy_group);
145 delete_board(enemy_group);
146 return true;
147 } else {
148 delete_board(enemy_group);
149 return false;
150 }
151}
152
153bool play_at(game_state* game, go_coordinate y, go_coordinate x, go_symbol color)
154{
155 //check out-of-bounds
156 if(!check_bounds(game->board, y, x))
157 return false;
158
159 //check if field is empty
160 if(get_board_at(game->board, y, x) != EMPTY)
161 return false;
162
163 bool can_place = false;
164
165 go_symbol enemy = color == NO_FIELD ? (game->black_turn ? WHITE : BLACK) : (color == BLACK ? WHITE : BLACK);
166 go_symbol friendly = color == NO_FIELD ? (game->black_turn ? BLACK : WHITE) : (color == BLACK ? BLACK : WHITE);
167
168 go_symbol up = y == 0 ? NO_FIELD : get_board_at(game->board, y-1, x);
169 go_symbol left = x == 0 ? NO_FIELD : get_board_at(game->board, y, x-1);
170 go_symbol down = y == game->board->size-1 ? NO_FIELD : get_board_at(game->board, y+1, x);
171 go_symbol right = x == game->board->size-1 ? NO_FIELD : get_board_at(game->board, y, x+1);
172
173 //first check for group to kill, then for empty field, and last for group with liberties
174
175 if(up == enemy && group_killable(game, y-1, x))
176 can_place = true;
177 else if(up == EMPTY)
178 can_place = true;
179 else if(up == friendly && group_attachable(game, y-1, x))
180 can_place = true;
181
182 if(left == enemy && group_killable(game, y, x-1))
183 can_place = true;
184 else if(left == EMPTY)
185 can_place = true;
186 else if(left == friendly && group_attachable(game, y, x-1))
187 can_place = true;
188
189 if(down == enemy && group_killable(game, y+1, x))
190 can_place = true;
191 else if(down == EMPTY)
192 can_place = true;
193 else if(down == friendly && group_attachable(game, y+1, x))
194 can_place = true;
195
196 if(right == enemy && group_killable(game, y, x+1))
197 can_place = true;
198 else if(right == EMPTY)
199 can_place = true;
200 else if(right == friendly && group_attachable(game, y, x+1))
201 can_place = true;
202
203 if(!can_place)
204 return false;
205
206 set_board_at(game->board, y, x, friendly);
207 game->black_turn = !game->black_turn;
208 return true;
209}
210
211go_symbol get_board_at(const go_board* board, go_coordinate y, go_coordinate x)
212{
213 if(check_bounds(board, y, x))
214 return board->field_array[y*board->size+x];
215 else
216 return NO_FIELD;
217}
218
219void set_board_at(go_board* board, go_coordinate y, go_coordinate x, go_symbol item)
220{
221 if(check_bounds(board,y,x))
222 board->field_array[y*board->size+x] = item;
223}
224
225void find_group(const go_board* board, go_board* overlay, go_coordinate y, go_coordinate x)
226{
227 assert(board->size == overlay->size);
228 if(check_bounds(board, y, x))
229 {
230 set_board_at(overlay, y, x, GROUP);
231 go_symbol field = get_board_at(board,y,x);
232
233 if(get_board_at(board,y-1,x) == field && get_board_at(overlay,y-1,x) == EMPTY)
234 find_group(board, overlay, y-1, x);
235
236 if(get_board_at(board,y,x-1) == field && get_board_at(overlay,y,x-1) == EMPTY)
237 find_group(board, overlay, y, x-1);
238
239 if(get_board_at(board,y+1,x) == field && get_board_at(overlay,y+1,x) == EMPTY)
240 find_group(board, overlay, y+1, x);
241
242 if(get_board_at(board,y,x+1) == field && get_board_at(overlay,y,x+1) == EMPTY)
243 find_group(board, overlay, y, x+1);
244 }
245}
246
247go_symbol group_belongs(const go_board* board, const go_board* overlay)
248{
249 assert(board->size == overlay->size);
250
251 go_symbol belongs = EMPTY;
252
253 for(go_coordinate y = 0; y < board->size; y++)
254 {
255 for(go_coordinate x = 0; x < board->size; x++)
256 {
257 if(get_board_at(overlay, y, x) == GROUP)
258 {
259 go_symbol up = get_board_at(board,y-1,x);
260 go_symbol left = get_board_at(board,y,x-1);
261 go_symbol down = get_board_at(board,y+1,x);
262 go_symbol right = get_board_at(board,y,x+1);
263
264 if(up == WHITE || up == BLACK)
265 {
266 belongs = (belongs == EMPTY) ? up : (up != belongs ? NO_FIELD : up);
267 }
268 if(left == WHITE || left == BLACK)
269 {
270 belongs = (belongs == EMPTY) ? left : (left != belongs ? NO_FIELD : left);
271 }
272 if(down == WHITE || down == BLACK)
273 {
274 belongs = (belongs == EMPTY) ? down : (down != belongs ? NO_FIELD : down);
275 }
276 if(right == WHITE || right == BLACK)
277 {
278 belongs = (belongs == EMPTY) ? right : (right != belongs ? NO_FIELD : right);
279 }
280 }
281 }
282 }
283 return belongs;
284}
285
286go_coordinate group_size(go_board* group)
287{
288 go_coordinate sum = 0;
289 for(go_coordinate y = 0; y < group->size; y++)
290 {
291 for(go_coordinate x = 0; x < group->size; x++)
292 {
293 if(get_board_at(group, y, x) == GROUP)
294 ++sum;
295 }
296 }
297 return sum;
298}
299
300go_coordinate count_liberties(const go_board* board, const go_board* overlay)
301{
302 assert(board->size == overlay->size);
303
304 go_board* tmpoverlay = create_board(board->size);
305 memcpy(tmpoverlay->field_array, overlay->field_array, board->size*board->size);
306
307 go_coordinate liberties = 0;
308
309 for(go_coordinate y = 0; y < board->size; y++)
310 {
311 for(go_coordinate x = 0; x < board->size; x++)
312 {
313 if(get_board_at(overlay, y, x) == GROUP)
314 {
315 if(get_board_at(board,y-1,x) == EMPTY && get_board_at(tmpoverlay,y-1,x) != COUNTED)
316 {
317 liberties++;
318 set_board_at(tmpoverlay,y-1,x,COUNTED);
319 }
320 if(get_board_at(board,y,x-1) == EMPTY && get_board_at(tmpoverlay,y,x-1) != COUNTED)
321 {
322 liberties++;
323 set_board_at(tmpoverlay,y,x-1,COUNTED);
324 }
325 if(get_board_at(board,y+1,x) == EMPTY && get_board_at(tmpoverlay,y+1,x) != COUNTED)
326 {
327 liberties++;
328 set_board_at(tmpoverlay,y+1,x,COUNTED);
329 }
330 if(get_board_at(board,y,x+1) == EMPTY && get_board_at(tmpoverlay,y,x+1) != COUNTED)
331 {
332 liberties++;
333 set_board_at(tmpoverlay,y,x+1,COUNTED);
334 }
335
336 }
337 }
338 }
339
340 delete_board(tmpoverlay);
341
342 return liberties;
343}
344
345go_score* score_game(const game_state* game)
346{
347 go_score* ret = malloc(sizeof(*ret));
348
349 ret->white_groups = new_vector();
350 ret->black_groups = new_vector();
351 ret->white_points = game->white_captured + game->komi;
352 ret->black_points = game->black_captured;
353
354 go_board* board = game->board;
355 go_board* current;
356 go_symbol belongs;
357
358 for(go_coordinate y = 0; y < board->size; y++)
359 {
360 for(go_coordinate x = 0; x < board->size; x++)
361 {
362 //if field is empty
363 if(get_board_at(board, y, x) == EMPTY)
364 {
365 //check if field is already counted
366 for(go_coordinate i = 0; i < ret->white_groups->length; i++)
367 {
368 current = vector_at(ret->white_groups, i);
369 if(get_board_at(current, y, x) == GROUP)
370 goto next_loop;
371 }
372 for(go_coordinate i = 0; i < ret->black_groups->length; i++)
373 {
374 current = vector_at(ret->black_groups, i);
375 if(get_board_at(current, y, x) == GROUP)
376 goto next_loop;
377 }
378
379 go_board* overlay = create_board(board->size);
380 find_group(board, overlay, y, x);
381
382 //check if field belongs to a group
383 if((belongs = group_belongs(board, overlay)) == WHITE)
384 {
385 vector_push(ret->white_groups, overlay);
386 ret->white_points += (double)group_size(overlay);
387 } else if(belongs == BLACK) {
388 vector_push(ret->black_groups, overlay);
389 ret->black_points += (double)group_size(overlay);
390 } else {
391 delete_board(overlay);
392 }
393 next_loop:;
394 }
395 }
396 }
397
398 return ret;
399}
400
401void delete_board_wrapper(void* board)
402{
403 delete_board(board);
404}
405
406void delete_score(go_score* score)
407{
408 delete_vector(score->white_groups, delete_board_wrapper);
409 delete_vector(score->black_groups, delete_board_wrapper);
410 free(score);
411}
412
413
414