This is the doxygen documentation for gtkboard.

.
Main Page   Data Structures   File List   Data Fields   Globals  

pentaline.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 
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 }