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