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 #include <stdio.h> 00020 #include <stdlib.h> 00021 #include <string.h> 00022 #include <assert.h> 00023 #include <gdk/gdkkeysyms.h> 00024 00025 #include "game.h" 00026 #include "aaball.h" 00027 00028 #define OTHELLO_CELL_SIZE 55 00029 #define OTHELLO_NUM_PIECES 2 00030 00031 #define OTHELLO_BOARD_WID 8 00032 #define OTHELLO_BOARD_HEIT 8 00033 00034 char othello_colors[6] = {200, 200, 200, 140, 140, 140}; 00035 00036 int othello_init_pos [OTHELLO_BOARD_WID*OTHELLO_BOARD_HEIT] = 00037 { 00038 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00039 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00040 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00041 0 , 0 , 0 , 2 , 1 , 0 , 0 , 0 , 00042 0 , 0 , 0 , 1 , 2 , 0 , 0 , 0 , 00043 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00044 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00045 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00046 }; 00047 00048 #define OTHELLO_WP 1 00049 #define OTHELLO_BP 2 00050 #define OTHELLO_EMPTY 0 00051 00052 00053 int othello_getmove (Pos *, int, int, GtkboardEventType, Player, byte **, int **); 00054 int othello_getmove_kb (Pos *pos, int key, Player player, byte **movp, int **rmovp); 00055 void othello_init (); 00056 ResultType othello_who_won (Pos *, Player, char **); 00057 ResultType othello_eval (Pos *, Player, float *); 00058 ResultType othello_eval_incr (Pos *, Player, byte *, float *); 00059 byte * othello_movegen (Pos *); 00060 char ** othello_get_pixmap (int, int); 00061 guchar *othello_get_rgbmap (int, int); 00062 gboolean othello_use_incr_eval (Pos *pos, Player player); 00063 00064 Game Othello = { OTHELLO_CELL_SIZE, OTHELLO_BOARD_WID, OTHELLO_BOARD_HEIT, 00065 OTHELLO_NUM_PIECES, 00066 othello_colors, othello_init_pos, NULL, "Othello", othello_init}; 00067 00068 00069 void othello_init () 00070 { 00071 game_getmove = othello_getmove; 00072 game_getmove_kb = othello_getmove_kb; 00073 game_who_won = othello_who_won; 00074 game_eval = othello_eval; 00075 game_eval_incr = othello_eval_incr; 00076 game_use_incr_eval = othello_use_incr_eval; 00077 game_movegen = othello_movegen; 00078 game_get_rgbmap = othello_get_rgbmap; 00079 game_white_string = "Red"; 00080 game_black_string = "Blue"; 00081 game_file_label = FILERANK_LABEL_TYPE_ALPHA; 00082 game_rank_label = FILERANK_LABEL_TYPE_NUM | FILERANK_LABEL_DESC; 00083 game_doc_about = 00084 "Othello\n" 00085 "Two player game\n" 00086 "Status: Fully implemented (but AI needs improvement)\n" 00087 "URL: "GAME_DEFAULT_URL ("othello"); 00088 game_doc_rules = 00089 "Othello rules\n" 00090 "\n" 00091 "Two players take turns in placing balls of either color. The objective is to get as many balls of your color as possible.\n" 00092 "\n" 00093 "When you place a ball in such a way that two of your balls sandwich one or more of the opponent's balls along a line (horizontal, vertical, or diagonal), then the sandwiched balls change to your color. You must move in such a way that at least one switch happens.\n" 00094 "\n" 00095 "If you don't have a move, you pass by hitting space or clicking on an empty square." 00096 ; 00097 game_doc_strategy = 00098 "Othello tips\n" 00099 "\n" 00100 "The number of balls of either color at a given time is, paradoxically, a _very_ poor indicator of who has the advantage. This is because balls can flip color en masse and wildly, especially during the last few moves.\n" 00101 "\n" 00102 "Indeed, in the beginning you should try to minimize the number of balls you have. The key is mobility. You must strive to maximize your number of legal moves so that you can try to force your opponent into making bad moves.\n" 00103 "\n" 00104 "The corners are key squares, because corner balls never flip. If your opponent blunders into giving you a corner before the final stages of the game, you are practically assured of a win.\n"; 00105 } 00106 00107 char ** othello_get_pixmap (int idx, int color) 00108 { 00109 int fg, bg, i; 00110 char *colors; 00111 static char pixbuf[OTHELLO_CELL_SIZE*(OTHELLO_CELL_SIZE)+1]; 00112 colors = othello_colors; 00113 fg = (idx == OTHELLO_WP ? 0xee << 16 : 0xee); 00114 if (color == BLACK) colors += 3; 00115 for(i=0, bg=0;i<3;i++) 00116 { int col = colors[i]; if (col<0) col += 256; bg += col * (1 << (16-8*i));} 00117 return pixmap_ball_gen(55, pixbuf, fg, bg, 17.0, 30.0); 00118 } 00119 00120 guchar *othello_get_rgbmap (int idx, int color) 00121 { 00122 static guchar rgbbuf[3*OTHELLO_CELL_SIZE*OTHELLO_CELL_SIZE]; 00123 int fg, bg, i; 00124 char *colors; 00125 colors = othello_colors; 00126 fg = (idx == OTHELLO_WP ? 0xee << 16 : 0xee); 00127 if (color == BLACK) colors += 3; 00128 for(i=0, bg=0;i<3;i++) 00129 { int col = colors[i]; if (col<0) col += 256; bg += col * (1 << (16-8*i));} 00130 rgbmap_ball_shadow_gen(55, rgbbuf, fg, bg, 17.0, 30.0, 3); 00131 return rgbbuf; 00132 } 00133 00134 static int incx[] = { -1, -1, -1, 0, 0, 1, 1, 1}; 00135 static int incy[] = { -1, 0, 1, -1, 1, -1, 0, 1}; 00136 00137 static int get_sandwich_len (Pos *pos, int x0, int y0, int dx, int dy, byte player) 00138 { 00139 int x = x0 + dx, y = y0+dy, len=0; 00140 byte state; 00141 for (; x >= 0 && y >= 0 && x < board_wid && y < board_heit; 00142 x+=dx, y+=dy, len++) 00143 { 00144 if ((state = pos->board[y * board_wid + x]) == 0) 00145 return -1; 00146 else if (state == player) 00147 return len; 00148 } 00149 return -1; 00150 } 00151 00152 // does player have a move in this position 00153 static gboolean hasmove (Pos *pos, Player player) 00154 { 00155 int i, x, y, found = FALSE; 00156 for (x=0; x<board_wid && !found; x++) 00157 for (y=0; y<board_heit && !found; y++) 00158 { 00159 if (pos->board [y * board_wid + x] != OTHELLO_EMPTY) 00160 continue; 00161 for (i=0; i<8; i++) 00162 { 00163 if (get_sandwich_len (pos, x, y ,incx[i], incy[i], 00164 player == WHITE ? OTHELLO_WP : OTHELLO_BP) > 0) 00165 { 00166 found = TRUE; 00167 break; 00168 } 00169 } 00170 } 00171 return found; 00172 } 00173 00174 int othello_getmove_kb (Pos *pos, int key, Player player, byte **movp, int **rmovp) 00175 { 00176 static byte move[1]; 00177 if (key != GDK_space) return -1; 00178 if (hasmove (pos, player)) return -1; 00179 move[0] = -1; 00180 *movp = move; 00181 return 1; 00182 } 00183 00184 int othello_getmove (Pos *pos, int x, int y, GtkboardEventType type, Player to_play, 00185 byte **movp, int ** rmovep) 00186 { 00187 int i, j, sw_len, found=0; 00188 static byte move[128]; 00189 byte *temp = move; 00190 byte our = to_play == WHITE ? OTHELLO_WP : OTHELLO_BP; 00191 if (type != GTKBOARD_BUTTON_RELEASE) 00192 return 0; 00193 if (pos->board [y * board_wid + x] != OTHELLO_EMPTY) 00194 return -1; 00195 for (i=0; i<8; i++) 00196 { 00197 sw_len = get_sandwich_len (pos, x, y ,incx[i], incy[i], 00198 to_play == WHITE ? OTHELLO_WP : OTHELLO_BP); 00199 if (sw_len > 0) found = 1; 00200 for (j=1; j<=sw_len; j++) 00201 { 00202 *temp++ = x + incx[i] * j; 00203 *temp++ = y + incy[i] * j; 00204 *temp++ = our; 00205 } 00206 } 00207 if (!found) 00208 { 00209 if (hasmove (pos, to_play)) return -1; 00210 *temp++ = -1; 00211 *movp = move; 00212 } 00213 *temp++ = x; 00214 *temp++ = y; 00215 *temp++ = our; 00216 *temp++ = -1; 00217 *movp = move; 00218 return 1; 00219 } 00220 00221 ResultType othello_who_won (Pos *pos, Player to_play, char **commp) 00222 { 00223 static char comment[32]; 00224 int i, wscore = 0, bscore = 0, who_idx ,x, y; 00225 char *who_str [3] = { "Red won", "Blue won", "its a tie" }; 00226 int found = 0; 00227 for (i=0; i<board_wid * board_heit; i++) 00228 if (pos->board[i] == OTHELLO_WP) 00229 wscore++; 00230 else if (pos->board[i] == OTHELLO_BP) 00231 bscore++; 00232 if (! (wscore == 0 || bscore == 0 00233 || wscore + bscore == board_wid * board_heit)) 00234 { 00235 snprintf (comment, 32, "%d : %d", wscore, bscore); 00236 *commp = comment; 00237 return RESULT_NOTYET; 00238 } 00239 if (wscore > bscore) who_idx = 0; 00240 else if (wscore < bscore) who_idx = 1; 00241 else who_idx = 2; 00242 snprintf (comment, 32, "%s (%d : %d)", who_str [who_idx], wscore, bscore); 00243 *commp = comment; 00244 if (wscore > bscore) 00245 return RESULT_WHITE; 00246 if (wscore < bscore) 00247 return RESULT_BLACK; 00248 return RESULT_TIE; 00249 } 00250 00251 byte * othello_movegen (Pos *pos) 00252 { 00253 int i, j, x, y, sw_len; 00254 byte movbuf [4096]; 00255 byte *movlist, *movp = movbuf; 00256 Player player = pos->player; 00257 byte our = player == WHITE ? OTHELLO_WP : OTHELLO_BP; 00258 gboolean game_over = TRUE; 00259 for (x=0; x<board_wid; x++) 00260 for (y=0; y<board_wid; y++) 00261 { 00262 gboolean found = FALSE; 00263 if (pos->board [y * board_wid + x] != OTHELLO_EMPTY) 00264 continue; 00265 game_over = FALSE; 00266 for (i=0; i<8; i++) 00267 { 00268 sw_len = get_sandwich_len (pos, x, y ,incx[i], incy[i], 00269 player == WHITE ? OTHELLO_WP : OTHELLO_BP); 00270 if (sw_len > 0) found = TRUE; 00271 for (j=1; j<=sw_len; j++) 00272 { 00273 *movp++ = x + incx[i] * j; 00274 *movp++ = y + incy[i] * j; 00275 *movp++ = our; 00276 } 00277 } 00278 if (!found) 00279 continue; 00280 *movp++ = x; 00281 *movp++ = y; 00282 *movp++ = our; 00283 *movp++ = -1; 00284 } 00285 /* if we want to pass, we must return an empty move, NOT no move */ 00286 if (movp == movbuf && !game_over) 00287 *movp++ = -1; 00288 *movp++ = -2; 00289 movlist = (byte *) (malloc (movp - movbuf)); 00290 memcpy (movlist, movbuf, (movp - movbuf)); 00291 return movlist; 00292 } 00293 00294 static float othello_eval_count (Pos *pos) 00295 { 00296 int i, sum=0; 00297 for (i=0; i<board_wid * board_heit; i++) 00298 if (pos->board [i] == OTHELLO_WP) 00299 sum++; 00300 else if (pos->board [i] == OTHELLO_BP) 00301 sum--; 00302 return sum; 00303 } 00304 00305 static int othello_eval_mobility_count (Pos *pos, int color) 00306 { 00307 int i, x, y, found, sum = 0; 00308 byte our = (color == WHITE ? OTHELLO_WP : OTHELLO_BP); 00309 for (x=0; x<board_wid; x++) 00310 for (y=0; y<board_heit; y++) 00311 { 00312 if (pos->board [y * board_wid + x] != our) 00313 continue; 00314 found = 0; 00315 for (i=0; i<8; i++) 00316 if (get_sandwich_len (pos, x, y ,incx[i], incy[i], our) > 0) 00317 { 00318 found = 1; 00319 break; 00320 } 00321 if (found) 00322 sum++; 00323 } 00324 return sum; 00325 } 00326 00327 static float othello_eval_mobility (Pos *pos) 00328 { 00329 return othello_eval_mobility_count (pos, WHITE) - 00330 othello_eval_mobility_count (pos, BLACK); 00331 } 00332 00334 static float othello_eval_liberty (Pos *pos) 00335 { 00336 int i, j, k; 00337 int liberty = 0; 00338 for (i=0; i<board_wid; i++) 00339 for (j=0; j<board_heit; j++) 00340 { 00341 if (pos->board [j * board_wid + i] != OTHELLO_EMPTY) 00342 continue; 00343 for (k=0; k<8; k++) 00344 { 00345 int x = i + incx[k], y = j + incy[k]; 00346 int val; 00347 if (!ISINBOARD (x, y)) continue; 00348 if ((val = pos->board [y * board_wid + x]) == OTHELLO_EMPTY) 00349 continue; 00350 liberty += (val == OTHELLO_WP ? -1 : 1); 00351 } 00352 } 00353 return liberty; 00354 } 00355 00356 static int othello_eval_num_moves (Pos *pos) 00357 { 00358 int i, sum=0; 00359 for (i=0; i<board_wid * board_heit; i++) 00360 if (pos->board [i] != OTHELLO_EMPTY) 00361 sum++; 00362 return sum; 00363 } 00364 00365 enum { SAFE, UNSAFE, UNKNOWN }; 00366 00367 static byte * safe_cached; 00368 00369 00370 /* TODO recursion sucks. reimplement this */ 00371 static int othello_eval_is_safe (Pos *pos, int x, int y, byte our) 00372 { 00373 if (x < 0 || y < 0 || x >= board_wid || y >= board_heit) 00374 return SAFE; 00375 if (pos->board [y * board_wid + x] != our) 00376 { return (safe_cached [y * board_wid + x] = UNSAFE);} 00377 if (safe_cached [y * board_wid + x] != UNKNOWN) 00378 return safe_cached [y * board_wid + x]; 00379 00380 /* crucial to avoid infinite recursion */ 00381 safe_cached [y * board_wid + x] = UNSAFE; 00382 if (othello_eval_is_safe (pos, x - 1, y - 1, our) == UNSAFE 00383 && othello_eval_is_safe (pos, x + 1, y + 1, our) == UNSAFE) 00384 { return (safe_cached [y * board_wid + x] = UNSAFE);} 00385 if (othello_eval_is_safe (pos, x + 1, y - 1, our) == UNSAFE 00386 && othello_eval_is_safe (pos, x - 1, y + 1, our) == UNSAFE) 00387 { return (safe_cached [y * board_wid + x] = UNSAFE);} 00388 if (othello_eval_is_safe (pos, x - 1, y, our) == UNSAFE 00389 && othello_eval_is_safe (pos, x + 1, y, our) == UNSAFE) 00390 { return (safe_cached [y * board_wid + x] = UNSAFE);} 00391 if (othello_eval_is_safe (pos, x, y - 1, our) == UNSAFE 00392 && othello_eval_is_safe (pos, x, y + 1, our) == UNSAFE) 00393 { return (safe_cached [y * board_wid + x] = UNSAFE);} 00394 return (safe_cached [y * board_wid + x] = SAFE); 00395 } 00396 00397 static float othello_eval_safe (Pos *pos) 00398 { 00399 int i, x, y, sum=0; 00400 if (pos->board [0 * board_wid + 0] == OTHELLO_EMPTY && 00401 pos->board [0 * board_wid + 7] == OTHELLO_EMPTY && 00402 pos->board [7 * board_wid + 0] == OTHELLO_EMPTY && 00403 pos->board [7 * board_wid + 7] == OTHELLO_EMPTY ) 00404 return 0; 00405 safe_cached = (byte *) malloc (board_wid * board_heit); 00406 assert (safe_cached); 00407 for (i=0; i<board_wid * board_heit; i++) 00408 safe_cached [i] = UNKNOWN; 00409 00410 for (x=0; x<board_wid; x++) 00411 for (y=0; y<board_heit; y++) 00412 if (pos->board [y * board_wid + x] == OTHELLO_WP && 00413 othello_eval_is_safe (pos, x, y, OTHELLO_WP) == SAFE) 00414 sum++; 00415 else if (pos->board [y * board_wid + x] == OTHELLO_BP && 00416 othello_eval_is_safe (pos, x, y, OTHELLO_BP) == SAFE) 00417 sum --; 00418 free (safe_cached); 00419 return sum; 00420 } 00421 00422 /*static float othello_eval_dangerous (Pos *pos) 00423 { 00424 int i, j; 00425 float danger = 0; 00426 for (i=1; i<=6; i+=5) 00427 for (j=1; j<=6; j+=5) 00428 { 00429 if (pos->board[j * board_wid + i] == OTHELLO_WP) danger++; 00430 else if (pos->board[j * board_wid + i] == OTHELLO_BP) danger--; 00431 } 00432 for (i=1; i<=6; i+=5) 00433 for (j=0; j<=7; j+=7) 00434 { 00435 if (pos->board[j * board_wid + i] == OTHELLO_WP) danger += 0.3; 00436 else if (pos->board[j * board_wid + i] == OTHELLO_BP) danger -= 0.3; 00437 } 00438 for (i=0; i<=7; i+=7) 00439 for (j=1; j<=6; j+=5) 00440 { 00441 if (pos->board[j * board_wid + i] == OTHELLO_WP) danger += 0.3; 00442 else if (pos->board[j * board_wid + i] == OTHELLO_BP) danger -= 0.3; 00443 } 00444 return -danger; 00445 }*/ 00446 00447 static float othello_eval_material (Pos *pos) 00448 { 00449 int i, material = 0; 00450 for (i=0; i<board_wid * board_heit; i++) 00451 { 00452 if (pos->board[i] == OTHELLO_WP) 00453 material++; 00454 else if (pos->board[i] == OTHELLO_BP) 00455 material--; 00456 } 00457 return material; 00458 } 00459 00460 static float othello_eval_weights (Pos *pos) 00461 { 00462 static int weights [4][4] = 00463 { 00464 { 500, -240, 85, 69 }, 00465 { 0 , -130, 49, 23 }, 00466 { 0 , 0, 1, 9 }, 00467 { 0 , 0, 0, 32 }, 00468 }; 00469 00470 int i, j, wtsum = 0; 00471 00472 for (i=0; i<board_wid; i++) 00473 for (j=0; j<board_heit; j++) 00474 { 00475 int val = pos->board[j * board_wid + i]; 00476 int x = i, y = j; 00477 if (val == OTHELLO_EMPTY) 00478 continue; 00479 if (x > 3) x = 7-x; 00480 if (y > 3) y = 7-y; 00481 if (x > y) {int tmp = y; y = x; x = tmp;} 00482 wtsum += weights [x][y] * (val == OTHELLO_WP ? 1 : -1); 00483 } 00484 return wtsum; 00485 } 00486 00487 ResultType othello_eval (Pos *pos, Player player, float *eval) 00488 { 00489 int i; 00490 gboolean found; 00491 assert (board_wid == 8 && board_heit == 8); 00492 00493 if (pos->num_moves >= 64) 00494 { 00495 for (i=0, found=FALSE; i<board_wid*board_heit; i++) 00496 if (pos->board [i] == OTHELLO_EMPTY) {found = TRUE; break;} 00497 if (!found) 00498 { 00499 *eval = othello_eval_material (pos); 00500 *eval *= GAME_EVAL_INFTY; 00501 if (*eval > 0) return RESULT_WHITE; 00502 if (*eval < 0) return RESULT_BLACK; 00503 return RESULT_NOTYET; 00504 } 00505 } 00506 00507 *eval = 00508 10 * othello_eval_liberty (pos) 00509 //10 * othello_eval_mobility (pos) 00510 + 100 * othello_eval_safe (pos) 00511 + othello_eval_weights (pos); 00512 return RESULT_NOTYET; 00513 } 00514 00515 ResultType othello_eval_incr (Pos *pos, Player player, byte *move, float *eval) 00516 { 00517 int i; 00518 for (i=0; move[3*i] != -1; i++) 00519 ; 00520 if (i == 0) 00521 *eval = 0; 00522 else 00523 *eval = (player == WHITE ? (2 * i - 1) : - (2 * i - 1)); 00524 return RESULT_NOTYET; 00525 } 00526 00527 gboolean othello_use_incr_eval (Pos *pos, Player player) 00528 { 00529 return pos->num_moves > 50 ? TRUE : FALSE; 00530 }