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