This is the doxygen documentation for gtkboard.

.
Main Page   Data Structures   File List   Data Fields   Globals  

breakthrough.c

Go to the documentation of this file.
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 "../pixmaps/chess.xpm"
00026 
00027 #define BREAKTHROUGH_CELL_SIZE 54
00028 #define BREAKTHROUGH_NUM_PIECES 2
00029 
00030 #define BREAKTHROUGH_BOARD_WID 8
00031 #define BREAKTHROUGH_BOARD_HEIT 8
00032 
00033 #define BREAKTHROUGH_EMPTY 0
00034 #define BREAKTHROUGH_WP 1
00035 #define BREAKTHROUGH_BP 2
00036 
00037 int breakthrough_initpos [BREAKTHROUGH_BOARD_WID*BREAKTHROUGH_BOARD_HEIT] = 
00038 {
00039         2 , 2 , 2 , 2 , 2 , 2 , 2 , 2 ,
00040         2 , 2 , 2 , 2 , 2 , 2 , 2 , 2 ,
00041         0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
00042         0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
00043         0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
00044         0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
00045         1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
00046         1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
00047 };
00048 
00049 
00050 char ** breakthrough_pixmaps [] = 
00051 {
00052         chess_wp_54_xpm,
00053         chess_bp_54_xpm,
00054 };
00055 
00056 int breakthrough_curx = -1, breakthrough_cury = -1;
00057 
00058 static char breakthrough_colors[] = 
00059         {200, 200, 130, 
00060         0, 140, 0};
00061 static int breakthrough_getmove (Pos *, int, int, GtkboardEventType, Player, byte **, int **);
00062 static int breakthrough_getmove_kb (Pos *, int, Player, byte ** , int **);
00063 void breakthrough_init ();
00064 static ResultType breakthrough_who_won (Pos *, Player, char **);
00065 static ResultType breakthrough_eval (Pos *, Player, float *eval);
00066 static ResultType breakthrough_eval_incr (Pos *, Player, byte *, float *);
00067 static byte * breakthrough_movegen (Pos *);
00068 static void *breakthrough_newstate (Pos *, byte *);
00069 
00070 Game Breakthrough = { BREAKTHROUGH_CELL_SIZE, BREAKTHROUGH_BOARD_WID, BREAKTHROUGH_BOARD_HEIT, 
00071         BREAKTHROUGH_NUM_PIECES, 
00072         breakthrough_colors, breakthrough_initpos, breakthrough_pixmaps, "Breakthrough", breakthrough_init};
00073 
00074 void breakthrough_init ()
00075 {
00076         game_getmove = breakthrough_getmove;
00077 //      game_who_won = breakthrough_who_won;
00078         game_eval = breakthrough_eval;
00079 //      game_eval_incr = breakthrough_eval_incr;
00080         game_movegen = breakthrough_movegen;
00081         game_file_label = FILERANK_LABEL_TYPE_ALPHA;
00082         game_rank_label = FILERANK_LABEL_TYPE_NUM | FILERANK_LABEL_DESC;
00083         game_allow_flip = TRUE;
00084         game_doc_about = 
00085                 "Breakthrough\n"
00086                 "Two player game\n"
00087                 "Status: Partially implemented\n"
00088                 "URL: "GAME_DEFAULT_URL ("breakthrough");
00089 }
00090 
00091 static gboolean eval_is_backward (byte *board, int x, int y)
00092 {
00093         int incy, other, j;
00094         int val = board[y * board_wid + x];
00095         assert (val != BREAKTHROUGH_EMPTY);
00096         incy = val == BREAKTHROUGH_WP ? 1 : -1;
00097         other = val == BREAKTHROUGH_WP ? BREAKTHROUGH_BP : BREAKTHROUGH_WP;
00098 
00099         for (j = y; j < board_heit && j >= 0; j -= incy)
00100         {
00101                 if (x - 1 >= 0 && board[j * board_wid + x - 1] == val) return FALSE;
00102                 if (x + 1 < board_wid && board[j * board_wid + x + 1] == val) return FALSE;
00103         }
00104         
00105         for (j = y + incy; j < board_heit && j >= 0; j += incy)
00106         {
00107                 if (board[j * board_wid + x] != BREAKTHROUGH_EMPTY) return FALSE;
00108                 if (x - 1 >= 0 && j + incy >= 0 && j + incy < board_heit &&
00109                                 board[j * board_wid + x - 1] == val &&
00110                                 board[(j + incy) * board_wid + x - 1] == other) return TRUE;
00111                 if (x + 1 >= 0 && j + incy >= 0 && j + incy < board_heit &&
00112                                 board[j * board_wid + x + 1] == val &&
00113                                 board[(j + incy) * board_wid + x + 1] == other) return TRUE;
00114         }
00115         return FALSE;
00116 }
00117 
00118 // Is this pawn a passer?
00119 static gboolean eval_is_passer (byte *board, int x, int y)
00120 {
00121         int incy, other;
00122         int val = board[y * board_wid + x];
00123         assert (val != BREAKTHROUGH_EMPTY);
00124         incy = val == BREAKTHROUGH_WP ? 1 : -1;
00125         other = val == BREAKTHROUGH_WP ? BREAKTHROUGH_BP : BREAKTHROUGH_WP;
00126         for (y += incy; y < board_heit && y >= 0; y += incy)
00127         {
00128                 if (board[y * board_wid + x] != BREAKTHROUGH_EMPTY) return FALSE;
00129                 if (x - 1 >= 0 && board[y * board_wid + x - 1] == other) return FALSE;
00130                 if (x + 1 < board_wid && board[y * board_wid + x + 1] == other) return FALSE;
00131         }
00132         return TRUE;
00133 }
00134 
00135 static gboolean eval_is_blocked (byte *board, int x, int y)
00136 {
00137         // TODO
00138         return FALSE;
00139 }
00140 
00141 static ResultType breakthrough_eval (Pos *pos, Player player, float *eval)
00142 {
00143         float wtsum = 0;
00144         int i, j;
00145         int wcount[BREAKTHROUGH_BOARD_WID], bcount[BREAKTHROUGH_BOARD_WID];
00146         float doubled_pawn_penalty = 0.2;
00147         float edge_pawn_bonus = 0.1;
00148         float backward_pawn_penalty = 0.5;
00149         float blocked_pawn_penalty = 0.1;
00150 
00151         int passer_min_white = board_heit, passer_min_black = board_heit;
00152         
00153         for (i=0; i<board_wid; i++)
00154         {
00155                 // cheap optimization trick 
00156                 if (pos->board [0 * board_wid + i] == BREAKTHROUGH_WP && 
00157                                 pos->board [(board_heit - 1) * board_wid + i] == BREAKTHROUGH_BP)
00158                         continue;
00159                 for (j=0; j<board_heit; j++)
00160                 {
00161                         int val = pos->board[j * board_wid + i];
00162                         if (val == BREAKTHROUGH_EMPTY) continue;
00163                         if (eval_is_passer (pos->board, i, j))
00164                         {
00165                                 if (val == BREAKTHROUGH_WP && (board_wid -1 - j < passer_min_white))
00166                                         passer_min_white = board_wid -1 - j;
00167                                 if (val == BREAKTHROUGH_BP && (j < passer_min_black))
00168                                         passer_min_black = j;
00169                         }
00170                 }
00171         }
00172         if (passer_min_white < board_heit || passer_min_black < board_heit)
00173         {
00174                 int diff = passer_min_white - passer_min_black;
00175                 if (diff < 0 || (diff == 0 && player == WHITE))
00176                 {
00177                         *eval = -diff + 1;
00178                         return RESULT_WHITE;
00179                 }
00180                 if (diff > 0 || (diff == 0 && player == BLACK))
00181                 {
00182                         *eval = -diff - 1;
00183                         return RESULT_BLACK;
00184                 }
00185         }
00186         
00187         for (i=0; i<board_wid; i++)
00188                 wcount[i] = bcount[i] = 0;
00189 
00190         for (i=0; i<board_wid; i++)
00191         for (j=0; j<board_heit; j++)
00192         {
00193                 int val = pos->board [j * board_wid + i];
00194                 if (val == BREAKTHROUGH_EMPTY) continue;
00195                 if (val == BREAKTHROUGH_WP)
00196                 {
00197                         wtsum += (1 + 0.1 * j);
00198                         if (i == 0 || i == board_wid - 1)
00199                                 wtsum += edge_pawn_bonus;
00200                         if (eval_is_backward (pos->board, i, j))
00201                                 wtsum -= backward_pawn_penalty;
00202                         wcount[i]++;
00203                 }
00204                 else if (val == BREAKTHROUGH_BP)
00205                 {
00206                         wtsum -= (1 + 0.1 * (board_wid - 1 - j));
00207                         if (i == 0 || i == board_wid - 1)
00208                                 wtsum -= edge_pawn_bonus;
00209                         if (eval_is_backward (pos->board, i, j))
00210                                 wtsum += backward_pawn_penalty;
00211                         bcount[i]++;
00212                 }
00213         }
00214         
00215         for (i=0; i<board_wid; i++)
00216         {
00217                 wtsum -= (wcount[i] > 1 ? wcount[i] - 1 : 0);
00218                 wtsum += (bcount[i] > 1 ? bcount[i] - 1 : 0);
00219         }
00220         
00221         *eval = wtsum;
00222         return RESULT_NOTYET;
00223 }
00224 
00225 static ResultType breakthrough_eval_incr (Pos *pos, Player player, byte *move, float *eval)
00226 {
00227         byte *board = pos->board;
00228         if (move[0] == move[3]) *eval = 0;
00229         else *eval = (player == WHITE ? 1 : -1);
00230         *eval += 0.01 * random() / RAND_MAX;
00231         return RESULT_NOTYET;
00232 }
00233 
00234 static byte * breakthrough_movegen (Pos *pos)
00235 {
00236         int i, j, m, n, xoff, yoff;
00237         byte movbuf [256];
00238         byte *movlist, *movp = movbuf;
00239         byte *board = pos->board;
00240 
00241         // generate a random permutation of the moves
00242         xoff = random() % board_wid;
00243         yoff = random() % board_heit;
00244         for (m=0; m<board_wid; m++)
00245         for (n=0; n<board_heit; n++)
00246         {
00247                 int incx, incy;
00248                 i = (m + xoff) % board_wid;
00249                 j = (n + yoff) % board_heit;
00250                 if (board [j * board_wid + i] != 
00251                                 (pos->player == WHITE ? BREAKTHROUGH_WP : BREAKTHROUGH_BP))
00252                         continue;
00253                 incy = board [j * board_wid + i] == BREAKTHROUGH_WP ? 1 : -1;
00254                 for (incx = -1; incx <= 1; incx += 1)
00255                 {
00256                         int val;
00257                         if (!ISINBOARD (i + incx, j + incy))
00258                                 continue;
00259                         val = board [(j+incy) * board_wid + (i+incx)];
00260                         if ((val == BREAKTHROUGH_EMPTY || val == board [j * board_wid + i]) 
00261                                         && incx != 0)
00262                                 continue;
00263                         if (val != BREAKTHROUGH_EMPTY && incx == 0) continue;
00264                         *movp++ = i + incx;
00265                         *movp++ = j + incy;
00266                         *movp++ = (pos->player == WHITE ? BREAKTHROUGH_WP : BREAKTHROUGH_BP);
00267                         *movp++ = i;
00268                         *movp++ = j;
00269                         *movp++ = 0;
00270                         *movp++ = -1;
00271                 }               
00272         }
00273         *movp++ = -2;
00274         movlist = (byte *) (malloc (movp - movbuf));
00275         memcpy (movlist, movbuf, (movp - movbuf));
00276         return movlist;
00277 }
00278 
00279 int breakthrough_getmove (Pos *pos, int x, int y, GtkboardEventType type, Player player, 
00280                 byte **movp, int **rmovp)
00281 {
00282         static byte move[128];
00283         byte *mp = move;
00284         int diffx, diffy;
00285         if (type != GTKBOARD_BUTTON_RELEASE)
00286                 return 0;
00287         if (breakthrough_curx < 0)
00288         {
00289                 if ((player == WHITE && pos->board [y * board_wid + x] == BREAKTHROUGH_WP)
00290                                 || (player == BLACK && pos->board [y * board_wid + x] == BREAKTHROUGH_BP))
00291                 {
00292                         int incy = player == WHITE ? 1 : -1;
00293                         int other = player == WHITE ? BREAKTHROUGH_BP : BREAKTHROUGH_WP;
00294                         if ((x == 0 || pos->board [(y + incy) * board_wid + x - 1] != other) &&
00295                                 (x == board_wid - 1 || 
00296                                  pos->board [(y + incy) * board_wid + x + 1] != other))
00297                         {
00298                                 if (pos->board [(y + incy) * board_wid + x] != BREAKTHROUGH_EMPTY)
00299                                         return -1;
00300                                 else
00301                                 {
00302                                         *mp++ = x;
00303                                         *mp++ = y;
00304                                         *mp++ = 0;
00305                                         *mp++ = x;
00306                                         *mp++ = y + incy;
00307                                         *mp++ = pos->board [y * board_wid + x];
00308                                         *mp++ = -1;
00309                                         *movp = move;
00310                                         return 1;
00311                                 }
00312                         }
00313                         else
00314                         {
00315                                 breakthrough_curx = x;
00316                                 breakthrough_cury = y;
00317                         }
00318                         return 0;
00319                 }
00320                 return -1;
00321         }
00322         diffx = x - breakthrough_curx;
00323         diffy = y - breakthrough_cury;
00324         if ((player == WHITE && pos->board [y * board_wid + x] == BREAKTHROUGH_WP)
00325                 || (player == BLACK && pos->board [y * board_wid + x] == BREAKTHROUGH_BP))
00326         {
00327                 breakthrough_curx = breakthrough_cury = -1;
00328                 return -1;
00329         }
00330         else if (pos->board[y * board_wid + x] == BREAKTHROUGH_EMPTY 
00331                         && 
00332                         (
00333                                 (player == WHITE && (diffy != 1 || diffx != 0))
00334                                         ||
00335                                 (player == BLACK && (diffy != -1 || diffx != 0))
00336                         )
00337            )
00338         {
00339                 breakthrough_curx = breakthrough_cury = -1;
00340                 return -1;
00341         }
00342         else if (((player == WHITE && pos->board [y * board_wid + x] == BREAKTHROUGH_BP)
00343                 || (player == BLACK && pos->board [y * board_wid + x] == BREAKTHROUGH_WP))
00344                 && 
00345                         ((player == WHITE && (diffy != 1 || abs (diffx) != 1))
00346                 ||(player == BLACK && (diffy != -1 || abs(diffx) != 1))))
00347         {
00348                 breakthrough_curx = breakthrough_cury = -1;
00349                 return -1;
00350         }
00351         *mp++ = x;
00352         *mp++ = y;
00353         *mp++ = (player == WHITE ? BREAKTHROUGH_WP : BREAKTHROUGH_BP);
00354         *mp++ = breakthrough_curx;
00355         *mp++ = breakthrough_cury;
00356         *mp++ = 0;
00357         *mp++ = -1;
00358         *movp = move;
00359         breakthrough_curx = breakthrough_cury = -1;
00360         return 1;
00361 }
00362