This is the doxygen documentation for gtkboard.
.00001 /* This file is a part of gtkboard, a board games system. 00002 Copyright (C) 2003, Arvind Narayanan <arvindn@users.sourceforge.net> 00003 00004 This program is free software; you can redistribute it and/or modify 00005 it under the terms of the GNU General Public License as published by 00006 the Free Software Foundation; either version 2 of the License, or 00007 (at your option) any later version. 00008 00009 This program is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 GNU General Public License for more details. 00013 00014 You should have received a copy of the GNU General Public License 00015 along with this program; if not, write to the Free Software 00016 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA 00017 00018 */ 00019 00022 #include <stdio.h> 00023 #include <string.h> 00024 #include <assert.h> 00025 #include <stdlib.h> 00026 #include <unistd.h> 00027 00028 #include "game.h" 00029 #include "aaball.h" 00030 00031 #define PENTALINE_CELL_SIZE 40 00032 #define PENTALINE_NUM_PIECES 2 00033 00034 #define PENTALINE_BOARD_WID 12 00035 #define PENTALINE_BOARD_HEIT 12 00036 00037 #define PENTALINE_RP 1 00038 #define PENTALINE_BP 2 00039 #define PENTALINE_EMPTY 0 00040 00041 char pentaline_colors[9] = {200, 220, 200, 200, 220, 200, 0, 0, 0}; 00042 00043 00044 void pentaline_init (); 00045 00046 Game Pentaline = { PENTALINE_CELL_SIZE, PENTALINE_BOARD_WID, PENTALINE_BOARD_HEIT, 00047 PENTALINE_NUM_PIECES, 00048 pentaline_colors, NULL, NULL, "Pentaline", pentaline_init}; 00049 00050 00051 static int pentaline_getmove (Pos *, int, int, GtkboardEventType, Player, byte **, int **); 00052 static ResultType pentaline_who_won (Pos *, Player , char **); 00053 static void pentaline_set_init_pos (Pos *pos); 00054 unsigned char * pentaline_get_rgbmap (int idx, int color); 00055 ResultType pentaline_eval_incr (Pos *, Player, byte *, float *); 00056 byte * pentaline_movegen (Pos *); 00057 ResultType pentaline_eval (Pos *, Player, float *); 00058 void *pentaline_newstate (Pos *pos, byte *move); 00059 00060 typedef struct 00061 { 00062 // length, open/closed, white/black 00063 byte chains[5][2][2]; 00064 } Pentaline_state; 00065 00066 00067 void pentaline_init () 00068 { 00069 game_eval = pentaline_eval; 00070 game_movegen = pentaline_movegen; 00071 game_getmove = pentaline_getmove; 00072 game_who_won = pentaline_who_won; 00073 game_get_rgbmap = pentaline_get_rgbmap; 00074 game_draw_cell_boundaries = TRUE; 00075 // game_eval_incr = pentaline_eval_incr; 00076 game_white_string = "Red"; 00077 game_black_string = "Blue"; 00078 game_stateful = TRUE; 00079 game_state_size = sizeof (Pentaline_state); 00080 game_newstate = pentaline_newstate; 00081 game_allow_flip = TRUE; 00082 game_doc_about = 00083 "Pentaline\n" 00084 "Two player game\n" 00085 "Status: Fully implemented (But AI needs improvement)\n" 00086 "URL: "GAME_DEFAULT_URL("pentaline"); 00087 game_doc_rules = 00088 "Pentaline rules\n" 00089 "\n" 00090 "Two players take turns in placing balls of either color. The first to get 5 balls in a row wins.\n\n" 00091 "This game is the same as the free-style variant of GoMoku.\n"; 00092 } 00093 00094 byte * pentaline_movegen (Pos *pos) 00095 { 00096 int i, j, k, l, x, y; 00097 byte movbuf [1024]; 00098 byte *movlist, *movp = movbuf; 00099 int val, found = 0; 00100 int incx[4] = { 0, 1, 1, -1}; 00101 int incy[4] = { 1, 0, 1, 1}; 00102 int nbrx[] = { -1, -1, -1, 0, 0, 1, 1, 1}; 00103 int nbry[] = { -1, 0, 1, -1, 1, -1, 0, 1}; 00104 byte *board = pos->board; 00105 Player player = pos->player; 00106 for (i=0; i<board_wid; i++) 00107 for (j=0; j<board_heit; j++) 00108 { 00109 if (board [j * board_heit + i] == PENTALINE_EMPTY) 00110 continue; 00111 for (k=0; k<4; k++) 00112 { 00113 int found = 1, val; 00114 for (l=0; l<5; l++) 00115 { 00116 if (j + l * incy[k] >= board_heit || i + l * incx[k] >= board_wid) 00117 { found = 0; break; } 00118 val = board [(j + l * incy[k]) * board_wid + i + l * incx[k]]; 00119 if (val == PENTALINE_EMPTY) {found = 0; break;} 00120 if (val != board [j * board_wid + i]) { found = 0; break; } 00121 } 00122 if (found) { break; } 00123 } 00124 } 00125 if (!found) 00126 { 00127 for (i=0; i<board_wid; i++) 00128 for (j=0; j<board_heit; j++) 00129 { 00130 if (board[j * board_wid + i] != PENTALINE_EMPTY) continue; 00131 for (k=0; k<8; k++) 00132 { 00133 x = i + nbrx[k]; 00134 y = j + nbry[k]; 00135 if (x >= 0 && y >= 0 && x < board_wid && y < board_heit 00136 && board [y * board_wid + x] != PENTALINE_EMPTY) 00137 { 00138 *movp++ = i; 00139 *movp++ = j; 00140 *movp++ = (player == WHITE ? PENTALINE_RP : PENTALINE_BP); 00141 *movp++ = -1; 00142 } 00143 } 00144 } 00145 } 00146 if (movp == movbuf) // empty board 00147 { 00148 *movp++ = board_wid / 2 - random() % 2; 00149 *movp++ = board_heit / 2 - random() % 2; 00150 *movp++ = (player == WHITE ? PENTALINE_RP : PENTALINE_BP); 00151 *movp++ = -1; 00152 } 00153 *movp++ = -2; 00154 movlist = (byte *) (malloc (movp - movbuf)); 00155 memcpy (movlist, movbuf, (movp - movbuf)); 00156 return movlist; 00157 } 00158 00159 ResultType pentaline_who_won (Pos *pos, Player to_play, char **commp) 00160 { 00161 int i, j, k, l; 00162 int incx[4] = { 0, 1, 1, -1}; 00163 int incy[4] = { 1, 0, 1, 1}; 00164 for (i=0; i<board_wid; i++) 00165 for (j=0; j<board_heit; j++) 00166 for (k=0; k<4; k++) 00167 { 00168 int found = 1, val; 00169 for (l=0; l<5; l++) 00170 { 00171 if (j + l * incy[k] >= board_heit || i + l * incx[k] >= board_wid) 00172 { found = 0; break; } 00173 val = pos->board [(j + l * incy[k]) * board_wid + i + l * incx[k]]; 00174 if (val == PENTALINE_EMPTY) {found = 0; break; } 00175 if (val != pos->board [j * board_wid + i]) { found = 0; break; } 00176 } 00177 if (found) {*commp = (to_play == WHITE ? "Blue won" : "Red won"); 00178 return (to_play == WHITE ? RESULT_BLACK : RESULT_WHITE);} 00179 } 00180 *commp = NULL; 00181 /* { 00182 int len, open, color; 00183 for (color = 0; color < 2 && pos->state; color++) 00184 { 00185 printf ("player = %s: ", color==0?"Red ":"Blue"); 00186 for (open = 0; open < 2; open++) 00187 { 00188 printf ("open=%d: ", open+1); 00189 for (len = 0; len < 5; len++) 00190 printf ("%d ", 00191 ((Pentaline_state *)pos->state)->chains[len][open][color]); 00192 printf ("\t"); 00193 } 00194 printf ("\n"); 00195 } 00196 printf ("\n"); 00197 } 00198 */ 00199 return RESULT_NOTYET; 00200 } 00201 00202 int pentaline_getmove (Pos *pos, int x, int y, GtkboardEventType type, Player to_play, byte **movp, int ** rmovep) 00203 { 00204 int val; 00205 static byte move[4]; 00206 if (type != GTKBOARD_BUTTON_RELEASE) 00207 return 0; 00208 if (pos->board [y * board_wid + x] != PENTALINE_EMPTY) 00209 return -1; 00210 move[0] = x; 00211 move[1] = y; 00212 move[2] = to_play == WHITE ? PENTALINE_RP : PENTALINE_BP; 00213 move[3] = -1; 00214 if (movp) 00215 *movp = move; 00216 return 1; 00217 } 00218 00219 unsigned char * pentaline_get_rgbmap (int idx, int color) 00220 { 00221 int fg, bg, i; 00222 char *colors; 00223 static char rgbbuf[3 * PENTALINE_CELL_SIZE * PENTALINE_CELL_SIZE]; 00224 colors = pentaline_colors; 00225 fg = (idx == PENTALINE_RP ? 0xee << 16 : 0xee); 00226 if (color == BLACK) colors += 3; 00227 for(i=0, bg=0;i<3;i++) 00228 { int col = colors[i]; if (col<0) col += 256; bg += col * (1 << (16-8*i));} 00229 rgbmap_ball_shadow_gen(PENTALINE_CELL_SIZE, rgbbuf, fg, bg, 13.0, 30.0, 2); 00230 return rgbbuf; 00231 } 00232 00233 static float eval_line (byte *board, int x, int y, int incx, int incy) 00234 { 00235 int open = 0; 00236 int newx, newy; 00237 int len, val, sgn; 00238 newx = x - incx, newy = y - incy; 00239 val = board [y * board_wid + x]; 00240 if (val == PENTALINE_EMPTY) return 0; 00241 sgn = (val == PENTALINE_RP ? 1 : -1); 00242 if (newx >= 0 && newy >= 0 && newx < board_wid && newy < board_heit) 00243 { 00244 if(board [newy * board_wid + newx] == val) 00245 return 0; 00246 if(board [newy * board_wid + newx] == PENTALINE_EMPTY) 00247 open = 1; 00248 } 00249 for (len = 0; ; x+= incx, y+=incy, len++) 00250 { 00251 if (x < 0 || y < 0 || x >= board_wid || y >= board_heit) break; 00252 if (board [y * board_wid + x] != val) break; 00253 } 00254 if (!(x < 0 || y < 0 || x >= board_wid || y >= board_heit) 00255 && board [y * board_wid + x] == PENTALINE_EMPTY) 00256 open++; 00257 if (len >= 5) return GAME_EVAL_INFTY * sgn; 00258 return open * open * (1 << len) * sgn; 00259 } 00260 00261 static float eval_line_bidir (byte *board, int x, int y, int incx, int incy) 00262 { 00263 int val = board[y * board_wid + x]; 00264 do 00265 { 00266 x -= incx; 00267 y -= incy; 00268 } 00269 while (x >= 0 && y >= 0 && x < board_wid && y < board_heit 00270 && board [y * board_wid + x] == val); 00271 x += incx; 00272 y += incy; 00273 return eval_line (board, x, y, incx, incy); 00274 } 00275 00276 static float eval_runs (byte *board) 00277 { 00278 int i, j, k; 00279 int incx[4] = { 0, 1, 1, -1 }; 00280 int incy[4] = { 1, 0, 1, 1 }; 00281 float eval = 0; 00282 for (i=0; i<board_wid; i++) 00283 for (j=0; j<board_heit; j++) 00284 { 00285 if (board [j * board_wid + i] == PENTALINE_EMPTY) 00286 continue; 00287 for (k=0; k<4; k++) 00288 eval += eval_line (board, i, j, incx[k], incy[k]); 00289 } 00290 return eval; 00291 } 00292 00293 static int incx[4] = { 0, 1, 1, -1 }; 00294 static int incy[4] = { 1, 0, 1, 1 }; 00295 00296 ResultType pentaline_eval_incr (Pos *pos, Player to_play, byte *move, float *eval) 00297 { 00298 int k; 00299 float val = 0; 00300 pos->board [move[1] * board_wid + move[0]] = move[2]; 00301 for (k=0; k<4; k++) 00302 val += eval_line_bidir (pos->board, move[0], move[1], incx[k], incy[k]); 00303 pos->board [move[1] * board_wid + move[0]] = 0; 00304 *eval = val; 00305 return RESULT_NOTYET; 00306 } 00307 00308 ResultType pentaline_eval (Pos *pos, Player player, float *eval) 00309 { 00310 #define FIRST_WON { *eval = player == WHITE ? (1 << 20) : - (1 << 20); return player == WHITE ? RESULT_WHITE : RESULT_BLACK; } 00311 #define SECOND_WON { *eval = player == WHITE ? - (1 << 20) : (1 << 20); return player == WHITE ? RESULT_BLACK : RESULT_WHITE; } 00312 int color = player == WHITE ? 0 : 1; 00313 int len, open; 00314 Pentaline_state *state; 00315 *eval = 0; 00316 state = ((Pentaline_state *)pos->state); 00317 00318 // 5 in a row 00319 if (state->chains[4][1][color] > 0 || state->chains[4][0][color] > 0) 00320 { 00321 *eval = player == WHITE ? (1 << 20) : - (1 << 20); 00322 return player == WHITE ? RESULT_WHITE : RESULT_BLACK; 00323 } 00324 00325 // opponent: 5-in-a-row 00326 if (state->chains[4][1][1-color] > 0 || state->chains[4][0][1-color] > 0) 00327 { 00328 *eval = player == WHITE ? - (1 << 20) : (1 << 20); 00329 return player == WHITE ? RESULT_BLACK : RESULT_WHITE; 00330 } 00331 00332 // 4-in-a-row 00333 if (state->chains[3][1][color] > 0 || state->chains[3][0][color] > 0) 00334 { 00335 *eval = player == WHITE ? (1 << 20) : - (1 << 20); 00336 return player == WHITE ? RESULT_WHITE : RESULT_BLACK; 00337 } 00338 00339 // opponent: 4-in-a-row, both sides open 00340 if (state->chains[3][1][1-color] > 0) 00341 *eval += (player == WHITE ? -(1 << 18) : (1 << 18)); 00342 00343 // opponent: 2 4-in-a-row's 00344 if (state->chains[3][0][1-color] > 1) 00345 *eval += (player == WHITE ? -(1 << 18) : (1 << 18)); 00346 00347 // 3-in-a-row, both sides open; opponent doesn't have 4-in-a-row 00348 if (state->chains[2][1][color] > 0 && state->chains[3][0][1-color] == 0) 00349 *eval += (player == WHITE ? (1 << 16) : - (1 << 16)); 00350 00351 // opponent: 2 3-in-a-row's, both sides open 00352 if (state->chains[2][1][1-color] > 1) 00353 *eval += (player == WHITE ? -(1 << 14) : (1 << 14)); 00354 00355 // opponent: a 4 and a doubly open 3 00356 if (state->chains[3][0][1-color] > 0 && state->chains[2][1][1-color] > 0) 00357 *eval += (player == WHITE ? - (1 << 12) : (1 << 12)); 00358 00359 // These seem to be all the winning patterns. Can't find any more. 00360 00361 *eval = 0; 00362 for (len = 0; len < 4; len++) 00363 for (open = 0; open < 2; open++) 00364 { 00365 *eval += state->chains[len][open][0] * (1 + open) * (1 + open) * (1 << len); 00366 *eval -= state->chains[len][open][1] * (1 + open) * (1 + open) * (1 << len); 00367 } 00368 return RESULT_NOTYET; 00369 } 00370 00371 00372 // given a square and a direction, find the length of the chain it defines {0, 1, ... 4} and the number of ends of the chain that are unoccupied {0, 1, 2} 00373 static void get_chain_info (byte *board, int x, int y, int dx, int dy, 00374 int *len, int *open, int *color) 00375 { 00376 int i; 00377 int val = board [y * board_wid + x]; 00378 *open = 0; 00379 *len = 0; 00380 if (!ISINBOARD (x, y)) 00381 return; 00382 if (val == PENTALINE_EMPTY) 00383 return; 00384 *color = (val == PENTALINE_RP ? 0 : 1); 00385 00386 do 00387 { 00388 x -= dx; 00389 y -= dy; 00390 } 00391 while (ISINBOARD (x, y) && board [y * board_wid + x] == val); 00392 if (ISINBOARD (x, y) && board [y * board_wid + x] == PENTALINE_EMPTY) (*open)++; 00393 00394 do 00395 { 00396 x += dx; 00397 y += dy; 00398 (*len)++; 00399 } 00400 while (ISINBOARD (x, y) && board [y * board_wid + x] == val); 00401 if (ISINBOARD (x, y) && board [y * board_wid + x] == PENTALINE_EMPTY) (*open)++; 00402 (*len)--; 00403 } 00404 00405 static void update_state (byte chains[5][2][2], int len, int open, int color, int inc) 00406 { 00407 if (len == 0) return; 00408 if (len >= 5) 00409 { 00410 len = 5; 00411 open = 1; 00412 } 00413 if (open == 0) return; 00414 if (inc == -1) assert (chains[len-1][open-1][color] > 0); 00415 chains[len-1][open-1][color] += inc; 00416 } 00417 00418 void *pentaline_newstate (Pos *pos, byte *move) 00419 { 00420 int k=0; 00421 static Pentaline_state state; 00422 Pentaline_state def_state = 00423 {{{{0, 0},{0, 0}},{{0, 0},{0, 0}},{{0, 0},{0, 0}},{{0, 0},{0, 0}}, 00424 }}; 00425 int len, open; 00426 int newcolor, oldcolor; 00427 int val = move[2]; 00428 if (pos->state) 00429 memcpy (&state, pos->state, sizeof (Pentaline_state)); 00430 else 00431 memcpy (&state, &def_state, sizeof (Pentaline_state)); 00432 for (k=0; k<4; k++) 00433 { 00434 get_chain_info (pos->board, move[0] + incx[k], move[1] + incy[k], 00435 incx[k], incy[k], &len, &open, &oldcolor); 00436 /* if (len != 0 && len <= 5 && open != 0) 00437 { 00438 if (len > 5) len = 5; 00439 assert (state.chains[len-1][open-1][oldcolor] > 0); 00440 state.chains[len-1][open-1][oldcolor]--; 00441 } 00442 */ 00443 update_state (state.chains, len, open, oldcolor, -1); 00444 get_chain_info (pos->board, move[0] - incx[k], move[1] - incy[k], 00445 -incx[k], -incy[k], &len, &open, &oldcolor); 00446 /* if (len != 0 && len <= 5 && open != 0) 00447 { 00448 if (len > 5) len = 5; 00449 assert (state.chains[len-1][open-1][oldcolor] > 0); 00450 state.chains[len-1][open-1][oldcolor]--; 00451 } 00452 */ 00453 update_state (state.chains, len, open, oldcolor, -1); 00454 } 00455 00456 pos->board [move[1] * board_wid + move[0]] = move[2]; 00457 for (k=0; k<4; k++) 00458 { 00459 int x = move[0], y = move[1]; 00460 if (ISINBOARD (x + incx[k], y + incy[k]) 00461 && pos->board [(y + incy[k]) * board_wid + (x + incx[k])] != val) 00462 { 00463 get_chain_info (pos->board, move[0] + incx[k], move[1] + incy[k], 00464 incx[k], incy[k], &len, &open, &oldcolor); 00465 /* if (len != 0 && len <= 5 && open != 0) 00466 { 00467 if (len > 5) len = 5; 00468 state.chains[len-1][open-1][oldcolor]++; 00469 } 00470 */ 00471 update_state (state.chains, len, open, oldcolor, +1); 00472 } 00473 if (ISINBOARD (x - incx[k], y - incy[k]) 00474 && pos->board [(y - incy[k]) * board_wid + (x - incx[k])] != val) 00475 { 00476 get_chain_info (pos->board, move[0] - incx[k], move[1] - incy[k], 00477 -incx[k], -incy[k], &len, &open, &oldcolor); 00478 /* if (len != 0 && len <= 5 && open != 0) 00479 { 00480 if (len > 5) len = 5; 00481 state.chains[len-1][open-1][oldcolor]++; 00482 } 00483 */ 00484 update_state (state.chains, len, open, oldcolor, +1); 00485 } 00486 get_chain_info (pos->board, move[0], move[1], 00487 incx[k], incy[k], &len, &open, &newcolor); 00488 /* if (len != 0 && len <= 5 && open != 0) 00489 { 00490 if (len > 5) len = 5; 00491 state.chains[len-1][open-1][newcolor]++; 00492 } 00493 */ 00494 update_state (state.chains, len, open, newcolor, +1); 00495 } 00496 pos->board [move[1] * board_wid + move[0]] = 0; 00497 return &state; 00498 }