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 00024 #include "game.h" 00025 #include "gdk/gdkkeysyms.h" 00026 #include "../pixmaps/chess.xpm" 00027 #include "../pixmaps/misc.xpm" 00028 00029 #define KNIGHTS_CELL_SIZE 54 00030 #define KNIGHTS_NUM_PIECES 3 00031 00032 #define KNIGHTS_BOARD_WID 7 00033 #define KNIGHTS_BOARD_HEIT 7 00034 00035 #define KNIGHTS_EMPTY 0 00036 #define KNIGHTS_CLOSED 1 00037 #define KNIGHTS_WN 2 00038 #define KNIGHTS_BN 3 00039 00040 char knights_colors[] = {200, 200, 130, 0, 140, 0}; 00041 00042 int knights_initpos [KNIGHTS_BOARD_WID*KNIGHTS_BOARD_HEIT] = 00043 { 00044 3 , 0 , 0 , 0 , 0 , 0 , 0 , 00045 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00046 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00047 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00048 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00049 0 , 0 , 0 , 0 , 0 , 0 , 0 , 00050 0 , 0 , 0 , 0 , 0 , 0 , 2 , 00051 }; 00052 00053 00054 char ** knights_pixmaps [] = 00055 { 00056 grey_square_54_xpm, 00057 chess_wn_54_xpm, 00058 chess_bn_54_xpm, 00059 }; 00060 00061 typedef struct 00062 { 00063 int num_pauses; 00064 }Knights_state; 00065 00066 static int knights_getmove (Pos *, int, int, GtkboardEventType, Player, byte **, int **); 00067 static int knights_getmove_kb (Pos *, int, Player, byte ** , int **); 00068 void knights_init (); 00069 static ResultType knights_who_won (Pos *, Player, char **); 00070 static ResultType knights_eval (Pos *, Player, float *eval); 00071 static ResultType knights_eval_real (Pos *, Player, float *eval, gboolean); 00072 static byte * knights_movegen (Pos *); 00073 static void *knights_newstate (Pos *, byte *); 00074 00075 Game Knights = { KNIGHTS_CELL_SIZE, KNIGHTS_BOARD_WID, KNIGHTS_BOARD_HEIT, 00076 KNIGHTS_NUM_PIECES, 00077 knights_colors, knights_initpos, knights_pixmaps, "Knights", knights_init}; 00078 00079 void knights_init () 00080 { 00081 game_getmove = knights_getmove; 00082 game_getmove_kb = knights_getmove_kb; 00083 game_who_won = knights_who_won; 00084 game_eval = knights_eval; 00085 game_movegen = knights_movegen; 00086 game_stateful = TRUE; 00087 game_state_size = sizeof (Knights_state); 00088 game_newstate = knights_newstate; 00089 game_draw_cell_boundaries = TRUE; 00090 game_file_label = FILERANK_LABEL_TYPE_ALPHA; 00091 game_rank_label = FILERANK_LABEL_TYPE_NUM | FILERANK_LABEL_DESC; 00092 game_doc_about = 00093 "Knights\n" 00094 "Two player game\n" 00095 "Status: Fully implemented\n" 00096 "URL: "GAME_DEFAULT_URL ("knights"); 00097 } 00098 00099 static int incx[] = { -2, -2, -1, -1, 1, 1, 2, 2}; 00100 static int incy[] = { -1, 1, -2, 2, -2, 2, -1, 1}; 00101 00102 static void *knights_newstate (Pos *pos, byte *move) 00103 { 00104 static Knights_state state; 00105 if (!pos->state) 00106 { 00107 state.num_pauses = 0; 00108 return &state; 00109 } 00110 if (move[0] == -1) 00111 state.num_pauses = ((Knights_state *)pos->state)->num_pauses + 1; 00112 else state.num_pauses = 0; 00113 return &state; 00114 } 00115 00116 static void get_cur_pos (byte *board, Player player, int *x, int *y) 00117 { 00118 int i=0, j=0; 00119 for (i=0; i<board_wid; i++) 00120 for (j=0; j<board_heit; j++) 00121 { 00122 if ((player == WHITE && board [j * board_wid + i] == KNIGHTS_WN) 00123 || (player == BLACK && board [j * board_wid + i] == KNIGHTS_BN)) 00124 { 00125 *x = i; 00126 *y = j; 00127 return; 00128 } 00129 } 00130 } 00131 00132 ResultType knights_who_won (Pos *pos, Player player, char **commp) 00133 { 00134 int i=0, j=0, k; 00135 float eval; 00136 ResultType result = knights_eval_real (pos, player, &eval, TRUE); 00137 if (result == RESULT_NOTYET) 00138 ; 00139 else if (result == RESULT_TIE) *commp = "Draw"; 00140 else if (result == RESULT_WHITE) *commp = "White won"; 00141 else if (result == RESULT_BLACK) *commp = "Black won"; 00142 return result; 00143 } 00144 00145 00146 int knights_getmove_kb (Pos *pos, int key, Player to_play, byte ** movp, int **rmovp) 00147 { 00148 int i, j, wx = 0, wy = 0, bx = 0, by = 0; 00149 static byte move[1] = {-1}; 00150 if (key != GDK_p) 00151 return 0; 00152 for (i=0; i<board_wid; i++) 00153 for (j=0; j<board_heit; j++) 00154 { 00155 if (pos->board[j * board_wid + i] == KNIGHTS_WN) 00156 wx = i, wy = j; 00157 if (pos->board[j * board_wid + i] == KNIGHTS_BN) 00158 bx = i, by = j; 00159 } 00160 if (abs ((wx - bx) * (wy - by)) != 2) 00161 return -1; 00162 *movp = move; 00163 return 1; 00164 } 00165 00166 int knights_getmove (Pos *pos, int x, int y, GtkboardEventType type, Player player, 00167 byte **movp, int **rmovp) 00168 { 00169 int curx = -1, cury = -1; 00170 static byte move[128]; 00171 byte *mp = move; 00172 if (type != GTKBOARD_BUTTON_RELEASE) 00173 return 0; 00174 if (pos->board[y * board_wid + x] != KNIGHTS_EMPTY) 00175 return -1; 00176 get_cur_pos (pos->board, player, &curx, &cury); 00177 if (abs ((curx - x) * (cury - y)) != 2) 00178 return -1; 00179 *mp++ = x; 00180 *mp++ = y; 00181 *mp++ = (player == WHITE ? KNIGHTS_WN : KNIGHTS_BN); 00182 *mp++ = curx; 00183 *mp++ = cury; 00184 *mp++ = KNIGHTS_CLOSED; 00185 *mp++ = -1; 00186 *movp = move; 00187 return 1; 00188 } 00189 00190 00191 byte * knights_movegen (Pos *pos) 00192 { 00193 int i, j, k; 00194 byte movbuf [64]; 00195 byte *movlist, *movp = movbuf; 00196 Player player = pos->player; 00197 get_cur_pos (pos->board, player, &i, &j); 00198 for (k=0; k<8; k++) 00199 { 00200 int x = i + incx[k], y = j + incy[k]; 00201 int val; 00202 if (!ISINBOARD (x, y)) continue; 00203 if ((val = pos->board[y * board_wid + x]) == KNIGHTS_EMPTY) 00204 { 00205 *movp++ = i; 00206 *movp++ = j; 00207 *movp++ = KNIGHTS_CLOSED; 00208 *movp++ = x; 00209 *movp++ = y; 00210 *movp++ = (player == WHITE ? KNIGHTS_WN : KNIGHTS_BN); 00211 *movp++ = -1; 00212 } 00213 else if (val == KNIGHTS_WN || val == KNIGHTS_BN) 00214 { 00215 *movp++ = -1; 00216 } 00217 } 00218 *movp++ = -2; 00219 movlist = (byte *) (malloc (movp - movbuf)); 00220 memcpy (movlist, movbuf, (movp - movbuf)); 00221 return movlist; 00222 } 00223 00224 static gboolean eval_disconnected (byte *theboard) 00225 { 00226 byte board[KNIGHTS_BOARD_WID * KNIGHTS_BOARD_HEIT]; 00227 int stack[KNIGHTS_BOARD_WID * KNIGHTS_BOARD_HEIT]; 00228 int stack_top = 0; 00229 int i, curx, cury, x, y; 00230 00231 for (i=0; i<board_wid * board_heit; i++) 00232 board[i] = theboard[i]; 00233 00234 get_cur_pos (board, WHITE, &curx, &cury); 00235 00236 stack[stack_top++] = cury * board_wid + curx; 00237 while (stack_top > 0) 00238 { 00239 stack_top--; 00240 curx = stack[stack_top] % board_wid; 00241 cury = stack[stack_top] / board_wid; 00242 for (i=0; i<8; i++) 00243 { 00244 x = curx + incx[i]; 00245 y = cury + incy[i]; 00246 if (!ISINBOARD (x, y)) continue; 00247 if (board[y * board_wid + x] == KNIGHTS_BN) 00248 return FALSE; 00249 if (board[y * board_wid + x] != KNIGHTS_EMPTY) 00250 continue; 00251 board[y * board_wid + x] = KNIGHTS_CLOSED; 00252 stack[stack_top++] = y * board_wid + x; 00253 } 00254 } 00255 return TRUE; 00256 } 00257 00258 // exhaustive DFS to solve the position exactly 00259 static int eval_max_path_len (byte *theboard, Player player) 00260 { 00261 byte board[KNIGHTS_BOARD_WID * KNIGHTS_BOARD_HEIT]; 00262 int stack [KNIGHTS_BOARD_WID * KNIGHTS_BOARD_HEIT]; 00263 int current [KNIGHTS_BOARD_WID * KNIGHTS_BOARD_HEIT]; 00264 int stack_top = 0; 00265 int i, curx, cury, x, y; 00266 int max_len = 0; 00267 00268 for (i=0; i<board_wid * board_heit; i++) 00269 board[i] = theboard[i]; 00270 00271 get_cur_pos (board, player, &curx, &cury); 00272 00273 current[stack_top] = 0; 00274 stack[stack_top] = cury * board_wid + curx; 00275 00276 while (stack_top >= 0) 00277 { 00278 if (stack_top > max_len) 00279 max_len = stack_top; 00280 i = current[stack_top]++; 00281 if (i == 8) 00282 { 00283 stack_top--; 00284 continue; 00285 } 00286 curx = stack[stack_top] % board_wid; 00287 cury = stack[stack_top] / board_wid; 00288 x = curx + incx[i]; 00289 y = cury + incy[i]; 00290 if (!ISINBOARD (x, y)) continue; 00291 if (board[y * board_wid + x] != KNIGHTS_EMPTY) 00292 continue; 00293 board[y * board_wid + x] = KNIGHTS_CLOSED; 00294 stack_top++; 00295 current[stack_top] = 0; 00296 stack[stack_top] = y * board_wid + x; 00297 } 00298 return max_len; 00299 } 00300 00301 // We may want to continue the game even when a result is apparent. The 00302 // parameter strict is for this. who_won() sets it to TRUE and eval() to FALSE. 00303 static ResultType knights_eval_real (Pos *pos, Player player, float *eval, gboolean strict) 00304 { 00305 int i, j, k; 00306 int wcnt = 0, bcnt = 0; 00307 static int disconn_cnt [2 * KNIGHTS_BOARD_WID * KNIGHTS_BOARD_HEIT] = {0}; 00308 static int total_cnt [2 * KNIGHTS_BOARD_WID * KNIGHTS_BOARD_HEIT] = {0}; 00309 00310 if (pos->state && ((Knights_state *)pos->state)->num_pauses >= 2) 00311 { 00312 *eval = 0; 00313 return RESULT_TIE; 00314 } 00315 00316 if (!strict && eval_disconnected (pos->board)) 00317 { 00318 int wlen = 0, blen = 0; 00319 disconn_cnt [pos->num_moves]++; 00320 total_cnt[pos->num_moves]++; 00321 wlen = eval_max_path_len (pos->board, WHITE); 00322 blen = eval_max_path_len (pos->board, BLACK); 00323 *eval = 2 * (wlen - blen) + (player == WHITE ? -1 : 1); 00324 if (wlen > blen) return RESULT_WHITE; 00325 else if (wlen < blen) return RESULT_BLACK; 00326 else return player == WHITE ? RESULT_BLACK : RESULT_WHITE; 00327 } 00328 00329 total_cnt[pos->num_moves]++; 00330 // if (total_cnt[pos->num_moves] % 10000 == 0) printf ("Ply: %d;\t total: %d;\t disc: %d\n", pos->num_moves, total_cnt[pos->num_moves], disconn_cnt[pos->num_moves]); 00331 00332 get_cur_pos (pos->board, WHITE, &i, &j); 00333 for (k=0; k<8; k++) 00334 { 00335 int x = i + incx[k], y = j + incy[k]; 00336 if (!ISINBOARD (x, y)) continue; 00337 if (pos->board[y * board_wid + x] == KNIGHTS_EMPTY) 00338 wcnt++; 00339 } 00340 00341 get_cur_pos (pos->board, BLACK, &i, &j); 00342 for (k=0; k<8; k++) 00343 { 00344 int x = i + incx[k], y = j + incy[k]; 00345 if (!ISINBOARD (x, y)) continue; 00346 if (pos->board[y * board_wid + x] == KNIGHTS_EMPTY) 00347 bcnt++; 00348 } 00349 *eval = wcnt - bcnt; 00350 if (player == WHITE && wcnt == 0) 00351 { 00352 if (bcnt == 0) *eval -= 1; 00353 *eval *= GAME_EVAL_INFTY; 00354 return RESULT_BLACK; 00355 } 00356 if (player == BLACK && bcnt == 0) 00357 { 00358 if (wcnt == 0) *eval += 1; 00359 *eval *= GAME_EVAL_INFTY; 00360 return RESULT_WHITE; 00361 } 00362 return RESULT_NOTYET; 00363 } 00364 00365 ResultType knights_eval (Pos *pos, Player player, float *eval) 00366 { 00367 return knights_eval_real (pos, player, eval, FALSE); 00368 }