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
23
#include <gdk/gdkkeysyms.h>
28
#define OTHELLO_CELL_SIZE 55
29
#define OTHELLO_NUM_PIECES 2
31
char othello_colors[6] = {200, 200, 200, 140, 140, 140};
33
int othello_init_pos [8*8] =
35
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
36
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
37
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
38
0 , 0 , 0 , 2 , 1 , 0 , 0 , 0 ,
39
0 , 0 , 0 , 1 , 2 , 0 , 0 , 0 ,
40
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
41
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
42
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
45
int othello6x6_init_pos [6*6] =
47
0 , 0 , 0 , 0 , 0 , 0 ,
48
0 , 0 , 0 , 0 , 0 , 0 ,
49
0 , 0 , 2 , 1 , 0 , 0 ,
50
0 , 0 , 1 , 2 , 0 , 0 ,
51
0 , 0 , 0 , 0 , 0 , 0 ,
52
0 , 0 , 0 , 0 , 0 , 0 ,
57
#define OTHELLO_EMPTY 0
60
int othello_getmove (Pos *, int, int, GtkboardEventType, Player, byte **, int **);
61
int othello_getmove_kb (Pos *pos, int key, byte **movp, int **rmovp);
63
ResultType othello_who_won (Pos *, Player, char **);
64
ResultType othello_eval (Pos *, Player, float *);
65
ResultType othello_eval_incr (Pos *, byte *, float *);
66
byte * othello_movegen (Pos *);
67
char ** othello_get_pixmap (int, int);
68
guchar *othello_get_rgbmap (int, int);
69
gboolean othello_use_incr_eval (Pos *pos);
71
Game Othello = { OTHELLO_CELL_SIZE, 8, 8,
73
othello_colors, othello_init_pos, NULL, "Othello", "Othello", othello_init};
75
Game Othello6x6 = { OTHELLO_CELL_SIZE, 6, 6,
77
othello_colors, othello6x6_init_pos, NULL, "Othello 6x6", "Othello", othello_init};
80
void othello_init (Game *game)
82
game_getmove = othello_getmove;
83
game_getmove_kb = othello_getmove_kb;
84
game_who_won = othello_who_won;
85
game_eval = othello_eval;
86
game_eval_incr = othello_eval_incr;
87
game_use_incr_eval = othello_use_incr_eval;
88
game_movegen = othello_movegen;
89
game_get_rgbmap = othello_get_rgbmap;
90
game_white_string = "Red";
91
game_black_string = "Blue";
92
game_file_label = FILERANK_LABEL_TYPE_ALPHA;
93
game_rank_label = FILERANK_LABEL_TYPE_NUM | FILERANK_LABEL_DESC;
95
game_doc_about_status = STATUS_COMPLETE;
100
"Status: Fully implemented\n"
101
"URL: "GAME_DEFAULT_URL ("othello");
106
"Status: Fully implemented\n"
107
"URL: "GAME_DEFAULT_URL ("othello6x6");
109
"Two players take turns in placing balls of either color. The objective is to get as many balls of your color as possible.\n"
111
"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"
113
"If you don't have a move, you pass by hitting space or clicking on an empty square."
116
"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"
118
"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"
120
"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";
123
char ** othello_get_pixmap (int idx, int color)
127
static char pixbuf[OTHELLO_CELL_SIZE*(OTHELLO_CELL_SIZE)+1];
128
colors = othello_colors;
129
fg = (idx == OTHELLO_WP ? 0xee << 16 : 0xee);
130
if (color == BLACK) colors += 3;
131
for(i=0, bg=0;i<3;i++)
132
{ int col = colors[i]; if (col<0) col += 256; bg += col * (1 << (16-8*i));}
133
return pixmap_ball_gen(55, pixbuf, fg, bg, 17.0, 30.0);
136
guchar *othello_get_rgbmap (int idx, int color)
138
static guchar rgbbuf[3*OTHELLO_CELL_SIZE*OTHELLO_CELL_SIZE];
141
colors = othello_colors;
142
fg = (idx == OTHELLO_WP ? 0xee << 16 : 0xee);
143
if (color == BLACK) colors += 3;
144
for(i=0, bg=0;i<3;i++)
145
{ int col = colors[i]; if (col<0) col += 256; bg += col * (1 << (16-8*i));}
146
rgbmap_ball_shadow_gen(OTHELLO_CELL_SIZE, rgbbuf, fg, bg, 17.0, 30.0, 3);
150
static int incx[] = { -1, -1, -1, 0, 0, 1, 1, 1};
151
static int incy[] = { -1, 0, 1, -1, 1, -1, 0, 1};
153
static int get_sandwich_len (Pos *pos, int x0, int y0, int dx, int dy, byte player)
155
int x = x0 + dx, y = y0+dy, len=0;
157
for (; x >= 0 && y >= 0 && x < board_wid && y < board_heit;
160
if ((state = pos->board[y * board_wid + x]) == 0)
162
else if (state == player)
168
// does player have a move in this position
169
static gboolean hasmove (Pos *pos, Player player)
171
int i, x, y, found = FALSE;
172
for (x=0; x<board_wid && !found; x++)
173
for (y=0; y<board_heit && !found; y++)
175
if (pos->board [y * board_wid + x] != OTHELLO_EMPTY)
179
if (get_sandwich_len (pos, x, y ,incx[i], incy[i],
180
player == WHITE ? OTHELLO_WP : OTHELLO_BP) > 0)
190
int othello_getmove_kb (Pos *pos, int key, byte **movp, int **rmovp)
193
if (key != GDK_space) return -1;
194
if (hasmove (pos, pos->player)) return -1;
200
int othello_getmove (Pos *pos, int x, int y, GtkboardEventType type, Player to_play,
201
byte **movp, int ** rmovep)
203
int i, j, sw_len, found=0;
204
static byte move[128];
206
byte our = to_play == WHITE ? OTHELLO_WP : OTHELLO_BP;
207
if (type != GTKBOARD_BUTTON_RELEASE)
209
if (pos->board [y * board_wid + x] != OTHELLO_EMPTY)
213
sw_len = get_sandwich_len (pos, x, y ,incx[i], incy[i],
214
to_play == WHITE ? OTHELLO_WP : OTHELLO_BP);
215
if (sw_len > 0) found = 1;
216
for (j=1; j<=sw_len; j++)
218
*temp++ = x + incx[i] * j;
219
*temp++ = y + incy[i] * j;
225
if (hasmove (pos, to_play)) return -1;
237
ResultType othello_who_won (Pos *pos, Player to_play, char **commp)
239
static char comment[32];
240
int i, wscore = 0, bscore = 0, who_idx ,x, y;
241
char *who_str [3] = { "Red won", "Blue won", "its a tie" };
243
for (i=0; i<board_wid * board_heit; i++)
244
if (pos->board[i] == OTHELLO_WP)
246
else if (pos->board[i] == OTHELLO_BP)
248
if (! (wscore == 0 || bscore == 0
249
|| wscore + bscore == board_wid * board_heit))
251
snprintf (comment, 32, "%d : %d", wscore, bscore);
253
return RESULT_NOTYET;
255
if (wscore > bscore) who_idx = 0;
256
else if (wscore < bscore) who_idx = 1;
258
snprintf (comment, 32, "%s (%d : %d)", who_str [who_idx], wscore, bscore);
267
byte * othello_movegen (Pos *pos)
269
int i, j, x, y, sw_len;
271
byte *movlist, *movp = movbuf;
272
Player player = pos->player;
273
byte our = player == WHITE ? OTHELLO_WP : OTHELLO_BP;
274
gboolean game_over = TRUE;
275
for (x=0; x<board_wid; x++)
276
for (y=0; y<board_wid; y++)
278
gboolean found = FALSE;
279
if (pos->board [y * board_wid + x] != OTHELLO_EMPTY)
284
sw_len = get_sandwich_len (pos, x, y ,incx[i], incy[i],
285
player == WHITE ? OTHELLO_WP : OTHELLO_BP);
286
if (sw_len > 0) found = TRUE;
287
for (j=1; j<=sw_len; j++)
289
*movp++ = x + incx[i] * j;
290
*movp++ = y + incy[i] * j;
301
/* if we want to pass, we must return an empty move, NOT no move */
302
if (movp == movbuf && !game_over)
305
movlist = (byte *) (malloc (movp - movbuf));
306
memcpy (movlist, movbuf, (movp - movbuf));
310
static float othello_eval_count (Pos *pos)
313
for (i=0; i<board_wid * board_heit; i++)
314
if (pos->board [i] == OTHELLO_WP)
316
else if (pos->board [i] == OTHELLO_BP)
321
static int othello_eval_mobility_count (Pos *pos, int color)
323
int i, x, y, found, sum = 0;
324
byte our = (color == WHITE ? OTHELLO_WP : OTHELLO_BP);
325
for (x=0; x<board_wid; x++)
326
for (y=0; y<board_heit; y++)
328
if (pos->board [y * board_wid + x] != our)
332
if (get_sandwich_len (pos, x, y ,incx[i], incy[i], our) > 0)
343
static float othello_eval_mobility (Pos *pos)
345
return othello_eval_mobility_count (pos, WHITE) -
346
othello_eval_mobility_count (pos, BLACK);
349
//! Faster approxmiation for mobility
350
static float othello_eval_liberty (Pos *pos)
354
for (i=0; i<board_wid; i++)
355
for (j=0; j<board_heit; j++)
357
if (pos->board [j * board_wid + i] != OTHELLO_EMPTY)
361
int x = i + incx[k], y = j + incy[k];
363
if (!ISINBOARD (x, y)) continue;
364
if ((val = pos->board [y * board_wid + x]) == OTHELLO_EMPTY)
366
liberty += (val == OTHELLO_WP ? -1 : 1);
372
static int othello_eval_num_moves (Pos *pos)
375
for (i=0; i<board_wid * board_heit; i++)
376
if (pos->board [i] != OTHELLO_EMPTY)
381
enum { SAFE, UNSAFE, UNKNOWN };
383
static byte * safe_cached;
386
/* TODO recursion sucks. reimplement this */
387
static int othello_eval_is_safe (Pos *pos, int x, int y, byte our)
389
if (x < 0 || y < 0 || x >= board_wid || y >= board_heit)
391
if (pos->board [y * board_wid + x] != our)
392
{ return (safe_cached [y * board_wid + x] = UNSAFE);}
393
if (safe_cached [y * board_wid + x] != UNKNOWN)
394
return safe_cached [y * board_wid + x];
396
/* crucial to avoid infinite recursion */
397
safe_cached [y * board_wid + x] = UNSAFE;
398
if (othello_eval_is_safe (pos, x - 1, y - 1, our) == UNSAFE
399
&& othello_eval_is_safe (pos, x + 1, y + 1, our) == UNSAFE)
400
{ return (safe_cached [y * board_wid + x] = UNSAFE);}
401
if (othello_eval_is_safe (pos, x + 1, y - 1, our) == UNSAFE
402
&& othello_eval_is_safe (pos, x - 1, y + 1, our) == UNSAFE)
403
{ return (safe_cached [y * board_wid + x] = UNSAFE);}
404
if (othello_eval_is_safe (pos, x - 1, y, our) == UNSAFE
405
&& othello_eval_is_safe (pos, x + 1, y, our) == UNSAFE)
406
{ return (safe_cached [y * board_wid + x] = UNSAFE);}
407
if (othello_eval_is_safe (pos, x, y - 1, our) == UNSAFE
408
&& othello_eval_is_safe (pos, x, y + 1, our) == UNSAFE)
409
{ return (safe_cached [y * board_wid + x] = UNSAFE);}
410
return (safe_cached [y * board_wid + x] = SAFE);
413
static float othello_eval_safe (Pos *pos)
416
if (pos->board [0 * board_wid + 0] == OTHELLO_EMPTY &&
417
pos->board [0 * board_wid + board_wid - 1] == OTHELLO_EMPTY &&
418
pos->board [(board_heit - 1) * board_wid + 0] == OTHELLO_EMPTY &&
419
pos->board [(board_heit - 1) * board_wid + board_wid - 1] == OTHELLO_EMPTY )
421
safe_cached = (byte *) malloc (board_wid * board_heit);
422
assert (safe_cached);
423
for (i=0; i<board_wid * board_heit; i++)
424
safe_cached [i] = UNKNOWN;
426
for (x=0; x<board_wid; x++)
427
for (y=0; y<board_heit; y++)
428
if (pos->board [y * board_wid + x] == OTHELLO_WP &&
429
othello_eval_is_safe (pos, x, y, OTHELLO_WP) == SAFE)
431
else if (pos->board [y * board_wid + x] == OTHELLO_BP &&
432
othello_eval_is_safe (pos, x, y, OTHELLO_BP) == SAFE)
438
/*static float othello_eval_dangerous (Pos *pos)
442
for (i=1; i<=6; i+=5)
443
for (j=1; j<=6; j+=5)
445
if (pos->board[j * board_wid + i] == OTHELLO_WP) danger++;
446
else if (pos->board[j * board_wid + i] == OTHELLO_BP) danger--;
448
for (i=1; i<=6; i+=5)
449
for (j=0; j<=7; j+=7)
451
if (pos->board[j * board_wid + i] == OTHELLO_WP) danger += 0.3;
452
else if (pos->board[j * board_wid + i] == OTHELLO_BP) danger -= 0.3;
454
for (i=0; i<=7; i+=7)
455
for (j=1; j<=6; j+=5)
457
if (pos->board[j * board_wid + i] == OTHELLO_WP) danger += 0.3;
458
else if (pos->board[j * board_wid + i] == OTHELLO_BP) danger -= 0.3;
463
static float othello_eval_material (Pos *pos)
466
for (i=0; i<board_wid * board_heit; i++)
468
if (pos->board[i] == OTHELLO_WP)
470
else if (pos->board[i] == OTHELLO_BP)
476
static float othello_eval_weights (Pos *pos)
478
static int weights8 [4][4] =
480
{ 500, -240, 85, 69 },
481
{ 0 , -130, 49, 23 },
486
// FIXME: find a decent weight set
487
static int weights6 [3][3] =
496
for (i=0; i<board_wid; i++)
497
for (j=0; j<board_heit; j++)
499
int val = pos->board[j * board_wid + i];
501
if (val == OTHELLO_EMPTY)
504
if (pos->game == &Othello)
509
else //if (pos->game == Othello6x6)
515
if (x > y) {int tmp = y; y = x; x = tmp;}
517
wtsum += (pos->game == &Othello ? weights8 [x][y] : weights6[x][y])
518
* (val == OTHELLO_WP ? 1 : -1);
523
ResultType othello_eval (Pos *pos, Player player, float *eval)
528
if (pos->num_moves >= board_wid * board_heit)
530
for (i=0, found=FALSE; i<board_wid*board_heit; i++)
531
if (pos->board [i] == OTHELLO_EMPTY) {found = TRUE; break;}
534
*eval = othello_eval_material (pos);
535
*eval *= GAME_EVAL_INFTY;
536
if (*eval > 0) return RESULT_WHITE;
537
if (*eval < 0) return RESULT_BLACK;
538
return RESULT_NOTYET;
543
10 * othello_eval_liberty (pos)
544
//10 * othello_eval_mobility (pos)
545
+ 100 * othello_eval_safe (pos)
546
+ othello_eval_weights (pos);
547
return RESULT_NOTYET;
550
ResultType othello_eval_incr (Pos *pos, byte *move, float *eval)
553
for (i=0; move[3*i] != -1; i++)
558
*eval = (pos->player == WHITE ? (2 * i - 1) : - (2 * i - 1));
559
return RESULT_NOTYET;
562
gboolean othello_use_incr_eval (Pos *pos)
564
// TODO: use different threshold for Othello6x6
565
return pos->num_moves > 50 ? TRUE : FALSE;
added
removed
.pc/debian-changes-0.11pre0+cvs.2003.11.02-1/src/othello.c
