1
/* This file is a part of gtkboard, a board games system.
2
Copyright (C) 2003, Arvind Narayanan <arvindn@users.sourceforge.net>
4
This program is free software; you can redistribute it and/or modify
5
it under the terms of the GNU General Public License as published by
6
the Free Software Foundation; either version 2 of the License, or
7
(at your option) any later version.
9
This program is distributed in the hope that it will be useful,
10
but WITHOUT ANY WARRANTY; without even the implied warranty of
11
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
GNU General Public License for more details.
14
You should have received a copy of the GNU General Public License
15
along with this program; if not, write to the Free Software
16
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA
20
/** \file pentaline.c */
31
#define PENTALINE_CELL_SIZE 40
32
#define PENTALINE_NUM_PIECES 2
34
#define PENTALINE_BOARD_WID 12
35
#define PENTALINE_BOARD_HEIT 12
37
#define PENTALINE_RP 1
38
#define PENTALINE_BP 2
39
#define PENTALINE_EMPTY 0
41
char pentaline_colors[9] = {200, 220, 200, 200, 220, 200, 0, 0, 0};
44
void pentaline_init ();
46
Game Pentaline = { PENTALINE_CELL_SIZE, PENTALINE_BOARD_WID, PENTALINE_BOARD_HEIT,
48
pentaline_colors, NULL, NULL, "Pentaline", "k-in-a-row", pentaline_init};
51
static int pentaline_getmove (Pos *, int, int, GtkboardEventType, Player, byte **, int **);
52
static ResultType pentaline_who_won (Pos *, Player , char **);
53
static void pentaline_set_init_pos (Pos *pos);
54
unsigned char * pentaline_get_rgbmap (int idx, int color);
55
ResultType pentaline_eval_incr (Pos *, Player, byte *, float *);
56
byte * pentaline_movegen (Pos *);
57
ResultType pentaline_eval (Pos *, Player, float *);
58
void *pentaline_newstate (Pos *pos, byte *move);
62
// length, open/closed, white/black
67
void pentaline_init ()
69
game_eval = pentaline_eval;
70
game_movegen = pentaline_movegen;
71
game_getmove = pentaline_getmove;
72
game_who_won = pentaline_who_won;
73
game_get_rgbmap = pentaline_get_rgbmap;
74
game_draw_cell_boundaries = TRUE;
75
// game_eval_incr = pentaline_eval_incr;
76
game_white_string = "Red";
77
game_black_string = "Blue";
79
game_state_size = sizeof (Pentaline_state);
80
game_newstate = pentaline_newstate;
81
game_allow_flip = TRUE;
82
game_doc_about_status = STATUS_COMPLETE;
86
"Status: Fully implemented (But AI needs improvement)\n"
87
"URL: "GAME_DEFAULT_URL("pentaline");
89
"Two players take turns in placing balls of either color. The first to get 5 balls in a row wins.\n\n"
90
"This game is the same as the free-style variant of GoMoku.\n";
93
byte * pentaline_movegen (Pos *pos)
97
byte *movlist, *movp = movbuf;
99
int incx[4] = { 0, 1, 1, -1};
100
int incy[4] = { 1, 0, 1, 1};
101
int nbrx[] = { -1, -1, -1, 0, 0, 1, 1, 1};
102
int nbry[] = { -1, 0, 1, -1, 1, -1, 0, 1};
103
byte *board = pos->board;
104
Player player = pos->player;
105
for (i=0; i<board_wid; i++)
106
for (j=0; j<board_heit; j++)
108
if (board [j * board_heit + i] == PENTALINE_EMPTY)
115
if (j + l * incy[k] >= board_heit || i + l * incx[k] >= board_wid)
116
{ found = 0; break; }
117
val = board [(j + l * incy[k]) * board_wid + i + l * incx[k]];
118
if (val == PENTALINE_EMPTY) {found = 0; break;}
119
if (val != board [j * board_wid + i]) { found = 0; break; }
121
if (found) { break; }
126
for (i=0; i<board_wid; i++)
127
for (j=0; j<board_heit; j++)
129
if (board[j * board_wid + i] != PENTALINE_EMPTY) continue;
134
if (x >= 0 && y >= 0 && x < board_wid && y < board_heit
135
&& board [y * board_wid + x] != PENTALINE_EMPTY)
139
*movp++ = (player == WHITE ? PENTALINE_RP : PENTALINE_BP);
145
if (movp == movbuf) // empty board
147
*movp++ = board_wid / 2 - random() % 2;
148
*movp++ = board_heit / 2 - random() % 2;
149
*movp++ = (player == WHITE ? PENTALINE_RP : PENTALINE_BP);
153
movlist = (byte *) (malloc (movp - movbuf));
154
memcpy (movlist, movbuf, (movp - movbuf));
158
ResultType pentaline_who_won (Pos *pos, Player to_play, char **commp)
161
int incx[4] = { 0, 1, 1, -1};
162
int incy[4] = { 1, 0, 1, 1};
163
for (i=0; i<board_wid; i++)
164
for (j=0; j<board_heit; j++)
170
if (j + l * incy[k] >= board_heit || i + l * incx[k] >= board_wid)
171
{ found = 0; break; }
172
val = pos->board [(j + l * incy[k]) * board_wid + i + l * incx[k]];
173
if (val == PENTALINE_EMPTY) {found = 0; break; }
174
if (val != pos->board [j * board_wid + i]) { found = 0; break; }
176
if (found) {*commp = (to_play == WHITE ? "Blue won" : "Red won");
177
return (to_play == WHITE ? RESULT_BLACK : RESULT_WHITE);}
181
int len, open, color;
182
for (color = 0; color < 2 && pos->state; color++)
184
printf ("player = %s: ", color==0?"Red ":"Blue");
185
for (open = 0; open < 2; open++)
187
printf ("open=%d: ", open+1);
188
for (len = 0; len < 5; len++)
190
((Pentaline_state *)pos->state)->chains[len][open][color]);
198
return RESULT_NOTYET;
201
int pentaline_getmove (Pos *pos, int x, int y, GtkboardEventType type, Player to_play, byte **movp, int ** rmovep)
205
if (type != GTKBOARD_BUTTON_RELEASE)
207
if (pos->board [y * board_wid + x] != PENTALINE_EMPTY)
211
move[2] = to_play == WHITE ? PENTALINE_RP : PENTALINE_BP;
218
unsigned char * pentaline_get_rgbmap (int idx, int color)
222
static char rgbbuf[3 * PENTALINE_CELL_SIZE * PENTALINE_CELL_SIZE];
223
colors = pentaline_colors;
224
fg = (idx == PENTALINE_RP ? 0xee << 16 : 0xee);
225
if (color == BLACK) colors += 3;
226
for(i=0, bg=0;i<3;i++)
227
{ int col = colors[i]; if (col<0) col += 256; bg += col * (1 << (16-8*i));}
228
rgbmap_ball_shadow_gen(PENTALINE_CELL_SIZE, rgbbuf, fg, bg, 13.0, 30.0, 2);
232
static float eval_line (byte *board, int x, int y, int incx, int incy)
237
newx = x - incx, newy = y - incy;
238
val = board [y * board_wid + x];
239
if (val == PENTALINE_EMPTY) return 0;
240
sgn = (val == PENTALINE_RP ? 1 : -1);
241
if (newx >= 0 && newy >= 0 && newx < board_wid && newy < board_heit)
243
if(board [newy * board_wid + newx] == val)
245
if(board [newy * board_wid + newx] == PENTALINE_EMPTY)
248
for (len = 0; ; x+= incx, y+=incy, len++)
250
if (x < 0 || y < 0 || x >= board_wid || y >= board_heit) break;
251
if (board [y * board_wid + x] != val) break;
253
if (!(x < 0 || y < 0 || x >= board_wid || y >= board_heit)
254
&& board [y * board_wid + x] == PENTALINE_EMPTY)
256
if (len >= 5) return GAME_EVAL_INFTY * sgn;
257
return open * open * (1 << len) * sgn;
260
static float eval_line_bidir (byte *board, int x, int y, int incx, int incy)
262
int val = board[y * board_wid + x];
268
while (x >= 0 && y >= 0 && x < board_wid && y < board_heit
269
&& board [y * board_wid + x] == val);
272
return eval_line (board, x, y, incx, incy);
275
static float eval_runs (byte *board)
278
int incx[4] = { 0, 1, 1, -1 };
279
int incy[4] = { 1, 0, 1, 1 };
281
for (i=0; i<board_wid; i++)
282
for (j=0; j<board_heit; j++)
284
if (board [j * board_wid + i] == PENTALINE_EMPTY)
287
eval += eval_line (board, i, j, incx[k], incy[k]);
292
static int incx[4] = { 0, 1, 1, -1 };
293
static int incy[4] = { 1, 0, 1, 1 };
295
ResultType pentaline_eval_incr (Pos *pos, Player to_play, byte *move, float *eval)
299
pos->board [move[1] * board_wid + move[0]] = move[2];
301
val += eval_line_bidir (pos->board, move[0], move[1], incx[k], incy[k]);
302
pos->board [move[1] * board_wid + move[0]] = 0;
304
return RESULT_NOTYET;
307
ResultType pentaline_eval (Pos *pos, Player player, float *eval)
309
#define FIRST_WON { *eval = player == WHITE ? (1 << 20) : - (1 << 20); return player == WHITE ? RESULT_WHITE : RESULT_BLACK; }
310
#define SECOND_WON { *eval = player == WHITE ? - (1 << 20) : (1 << 20); return player == WHITE ? RESULT_BLACK : RESULT_WHITE; }
311
int color = player == WHITE ? 0 : 1;
313
Pentaline_state *state;
315
state = ((Pentaline_state *)pos->state);
318
if (state->chains[4][1][color] > 0 || state->chains[4][0][color] > 0)
320
*eval = player == WHITE ? (1 << 20) : - (1 << 20);
321
return player == WHITE ? RESULT_WHITE : RESULT_BLACK;
324
// opponent: 5-in-a-row
325
if (state->chains[4][1][1-color] > 0 || state->chains[4][0][1-color] > 0)
327
*eval = player == WHITE ? - (1 << 20) : (1 << 20);
328
return player == WHITE ? RESULT_BLACK : RESULT_WHITE;
332
if (state->chains[3][1][color] > 0 || state->chains[3][0][color] > 0)
334
*eval = player == WHITE ? (1 << 20) : - (1 << 20);
335
return player == WHITE ? RESULT_WHITE : RESULT_BLACK;
338
// opponent: 4-in-a-row, both sides open
339
if (state->chains[3][1][1-color] > 0)
340
*eval += (player == WHITE ? -(1 << 18) : (1 << 18));
342
// opponent: 2 4-in-a-row's
343
if (state->chains[3][0][1-color] > 1)
344
*eval += (player == WHITE ? -(1 << 18) : (1 << 18));
346
// 3-in-a-row, both sides open; opponent doesn't have 4-in-a-row
347
if (state->chains[2][1][color] > 0 && state->chains[3][0][1-color] == 0)
348
*eval += (player == WHITE ? (1 << 16) : - (1 << 16));
350
// opponent: 2 3-in-a-row's, both sides open
351
if (state->chains[2][1][1-color] > 1)
352
*eval += (player == WHITE ? -(1 << 14) : (1 << 14));
354
// opponent: a 4 and a doubly open 3
355
if (state->chains[3][0][1-color] > 0 && state->chains[2][1][1-color] > 0)
356
*eval += (player == WHITE ? - (1 << 12) : (1 << 12));
358
// These seem to be all the winning patterns. Can't find any more.
361
for (len = 0; len < 4; len++)
362
for (open = 0; open < 2; open++)
364
*eval += state->chains[len][open][0] * (1 + open) * (1 + open) * (1 << len);
365
*eval -= state->chains[len][open][1] * (1 + open) * (1 + open) * (1 << len);
367
return RESULT_NOTYET;
371
// 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}
372
static void get_chain_info (byte *board, int x, int y, int dx, int dy,
373
int *len, int *open, int *color)
376
int val = board [y * board_wid + x];
379
if (!ISINBOARD (x, y))
381
if (val == PENTALINE_EMPTY)
383
*color = (val == PENTALINE_RP ? 0 : 1);
390
while (ISINBOARD (x, y) && board [y * board_wid + x] == val);
391
if (ISINBOARD (x, y) && board [y * board_wid + x] == PENTALINE_EMPTY) (*open)++;
399
while (ISINBOARD (x, y) && board [y * board_wid + x] == val);
400
if (ISINBOARD (x, y) && board [y * board_wid + x] == PENTALINE_EMPTY) (*open)++;
404
static void update_state (byte chains[5][2][2], int len, int open, int color, int inc)
406
if (len == 0) return;
412
if (open == 0) return;
413
if (inc == -1) assert (chains[len-1][open-1][color] > 0);
414
chains[len-1][open-1][color] += inc;
417
void *pentaline_newstate (Pos *pos, byte *move)
420
static Pentaline_state state;
421
Pentaline_state def_state =
422
{{{{0, 0},{0, 0}},{{0, 0},{0, 0}},{{0, 0},{0, 0}},{{0, 0},{0, 0}},
425
int newcolor, oldcolor;
428
memcpy (&state, pos->state, sizeof (Pentaline_state));
430
memcpy (&state, &def_state, sizeof (Pentaline_state));
433
get_chain_info (pos->board, move[0] + incx[k], move[1] + incy[k],
434
incx[k], incy[k], &len, &open, &oldcolor);
435
/* if (len != 0 && len <= 5 && open != 0)
437
if (len > 5) len = 5;
438
assert (state.chains[len-1][open-1][oldcolor] > 0);
439
state.chains[len-1][open-1][oldcolor]--;
442
update_state (state.chains, len, open, oldcolor, -1);
443
get_chain_info (pos->board, move[0] - incx[k], move[1] - incy[k],
444
-incx[k], -incy[k], &len, &open, &oldcolor);
445
/* if (len != 0 && len <= 5 && open != 0)
447
if (len > 5) len = 5;
448
assert (state.chains[len-1][open-1][oldcolor] > 0);
449
state.chains[len-1][open-1][oldcolor]--;
452
update_state (state.chains, len, open, oldcolor, -1);
455
pos->board [move[1] * board_wid + move[0]] = move[2];
458
int x = move[0], y = move[1];
459
if (ISINBOARD (x + incx[k], y + incy[k])
460
&& pos->board [(y + incy[k]) * board_wid + (x + incx[k])] != val)
462
get_chain_info (pos->board, move[0] + incx[k], move[1] + incy[k],
463
incx[k], incy[k], &len, &open, &oldcolor);
464
/* if (len != 0 && len <= 5 && open != 0)
466
if (len > 5) len = 5;
467
state.chains[len-1][open-1][oldcolor]++;
470
update_state (state.chains, len, open, oldcolor, +1);
472
if (ISINBOARD (x - incx[k], y - incy[k])
473
&& pos->board [(y - incy[k]) * board_wid + (x - incx[k])] != val)
475
get_chain_info (pos->board, move[0] - incx[k], move[1] - incy[k],
476
-incx[k], -incy[k], &len, &open, &oldcolor);
477
/* if (len != 0 && len <= 5 && open != 0)
479
if (len > 5) len = 5;
480
state.chains[len-1][open-1][oldcolor]++;
483
update_state (state.chains, len, open, oldcolor, +1);
485
get_chain_info (pos->board, move[0], move[1],
486
incx[k], incy[k], &len, &open, &newcolor);
487
/* if (len != 0 && len <= 5 && open != 0)
489
if (len > 5) len = 5;
490
state.chains[len-1][open-1][newcolor]++;
493
update_state (state.chains, len, open, newcolor, +1);
495
pos->board [move[1] * board_wid + move[0]] = 0;
added
removed
.pc/debian-changes-0.11pre0+cvs.2003.11.02-1/src/pentaline.c
