← Back to branch summary

~ubuntu-branches/ubuntu/natty/gtkboard/natty

« back to all changes in this revision

Viewing changes to .pc/debian-changes-0.11pre0+cvs.2003.11.02-2/src/breakthrough.c

  • Committer: Bazaar Package Importer
  • Author(s): Barak A. Pearlmutter
  • Date: 2011-02-28 11:25:02 UTC
  • mto: This revision was merged to the branch mainline in revision 10.
  • Revision ID: james.westby@ubuntu.com-20110228112502-e9aah248wxelm7ao
Tags: 0.11pre0+cvs.2003.11.02-2
autotools tweaks, most notably -lSDL to supplement -lSDL_mixer

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/debian-changes-0.11pre0+cvs.2003.11.02-2/src/breakthrough.c
 
1
/*  This file is a part of gtkboard, a board games system.
 
2
    Copyright (C) 2003, Arvind Narayanan <arvindn@users.sourceforge.net>
 
3
 
 
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.
 
8
 
 
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.
 
13
 
 
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
 
17
 
 
18
*/
 
19
#include <stdio.h>
 
20
#include <stdlib.h>
 
21
#include <string.h>
 
22
#include <assert.h>
 
23
 
 
24
#include "game.h"
 
25
#include "../pixmaps/chess.xpm"
 
26
 
 
27
#define BREAKTHROUGH_CELL_SIZE 54
 
28
#define BREAKTHROUGH_NUM_PIECES 2
 
29
 
 
30
#define BREAKTHROUGH_BOARD_WID 8
 
31
#define BREAKTHROUGH_BOARD_HEIT 8
 
32
 
 
33
#define BREAKTHROUGH_EMPTY 0
 
34
#define BREAKTHROUGH_WP 1
 
35
#define BREAKTHROUGH_BP 2
 
36
 
 
37
int breakthrough_initpos [BREAKTHROUGH_BOARD_WID*BREAKTHROUGH_BOARD_HEIT] = 
 
38
{
 
39
        2 , 2 , 2 , 2 , 2 , 2 , 2 , 2 ,
 
40
        2 , 2 , 2 , 2 , 2 , 2 , 2 , 2 ,
 
41
        0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
 
42
        0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
 
43
        0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
 
44
        0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
 
45
        1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
 
46
        1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
 
47
};
 
48
 
 
49
 
 
50
char ** breakthrough_pixmaps [] = 
 
51
{
 
52
        chess_wp_54_xpm,
 
53
        chess_bp_54_xpm,
 
54
};
 
55
 
 
56
int breakthrough_curx = -1, breakthrough_cury = -1;
 
57
 
 
58
static char breakthrough_colors[] = 
 
59
        {200, 200, 130, 
 
60
        0, 140, 0};
 
61
static int breakthrough_getmove (Pos *, int, int, GtkboardEventType, Player, byte **, int **);
 
62
static int breakthrough_getmove_kb (Pos *, int, Player, byte ** , int **);
 
63
void breakthrough_init ();
 
64
static ResultType breakthrough_who_won (Pos *, Player, char **);
 
65
static ResultType breakthrough_eval (Pos *, Player, float *eval);
 
66
static ResultType breakthrough_eval_incr (Pos *, byte *, float *);
 
67
static byte * breakthrough_movegen (Pos *);
 
68
static void *breakthrough_newstate (Pos *, byte *);
 
69
 
 
70
Game Breakthrough = { BREAKTHROUGH_CELL_SIZE, BREAKTHROUGH_BOARD_WID, BREAKTHROUGH_BOARD_HEIT, 
 
71
        BREAKTHROUGH_NUM_PIECES, 
 
72
        breakthrough_colors, breakthrough_initpos, breakthrough_pixmaps, 
 
73
        "Breakthrough", "Chess variants", breakthrough_init};
 
74
 
 
75
void breakthrough_init ()
 
76
{
 
77
        game_getmove = breakthrough_getmove;
 
78
//      game_who_won = breakthrough_who_won;
 
79
        game_eval = breakthrough_eval;
 
80
//      game_eval_incr = breakthrough_eval_incr;
 
81
        game_movegen = breakthrough_movegen;
 
82
        game_file_label = FILERANK_LABEL_TYPE_ALPHA;
 
83
        game_rank_label = FILERANK_LABEL_TYPE_NUM | FILERANK_LABEL_DESC;
 
84
        game_allow_flip = TRUE;
 
85
        game_doc_about_status = STATUS_UNPLAYABLE;
 
86
        game_doc_about = 
 
87
                "Breakthrough\n"
 
88
                "Two player game\n"
 
89
                "Status: Partially implemented\n"
 
90
                "URL: "GAME_DEFAULT_URL ("breakthrough");
 
91
}
 
92
 
 
93
static gboolean eval_is_backward (byte *board, int x, int y)
 
94
{
 
95
        int incy, other, j;
 
96
        int val = board[y * board_wid + x];
 
97
        assert (val != BREAKTHROUGH_EMPTY);
 
98
        incy = val == BREAKTHROUGH_WP ? 1 : -1;
 
99
        other = val == BREAKTHROUGH_WP ? BREAKTHROUGH_BP : BREAKTHROUGH_WP;
 
100
 
 
101
        for (j = y; j < board_heit && j >= 0; j -= incy)
 
102
        {
 
103
                if (x - 1 >= 0 && board[j * board_wid + x - 1] == val) return FALSE;
 
104
                if (x + 1 < board_wid && board[j * board_wid + x + 1] == val) return FALSE;
 
105
        }
 
106
        
 
107
        for (j = y + incy; j < board_heit && j >= 0; j += incy)
 
108
        {
 
109
                if (board[j * board_wid + x] != BREAKTHROUGH_EMPTY) return FALSE;
 
110
                if (x - 1 >= 0 && j + incy >= 0 && j + incy < board_heit &&
 
111
                                board[j * board_wid + x - 1] == val &&
 
112
                                board[(j + incy) * board_wid + x - 1] == other) return TRUE;
 
113
                if (x + 1 >= 0 && j + incy >= 0 && j + incy < board_heit &&
 
114
                                board[j * board_wid + x + 1] == val &&
 
115
                                board[(j + incy) * board_wid + x + 1] == other) return TRUE;
 
116
        }
 
117
        return FALSE;
 
118
}
 
119
 
 
120
// Is this pawn a passer?
 
121
static gboolean eval_is_passer (byte *board, int x, int y)
 
122
{
 
123
        int incy, other;
 
124
        int val = board[y * board_wid + x];
 
125
        assert (val != BREAKTHROUGH_EMPTY);
 
126
        incy = val == BREAKTHROUGH_WP ? 1 : -1;
 
127
        other = val == BREAKTHROUGH_WP ? BREAKTHROUGH_BP : BREAKTHROUGH_WP;
 
128
        for (y += incy; y < board_heit && y >= 0; y += incy)
 
129
        {
 
130
                if (board[y * board_wid + x] != BREAKTHROUGH_EMPTY) return FALSE;
 
131
                if (x - 1 >= 0 && board[y * board_wid + x - 1] == other) return FALSE;
 
132
                if (x + 1 < board_wid && board[y * board_wid + x + 1] == other) return FALSE;
 
133
        }
 
134
        return TRUE;
 
135
}
 
136
 
 
137
static gboolean eval_is_blocked (byte *board, int x, int y)
 
138
{
 
139
        // TODO
 
140
        return FALSE;
 
141
}
 
142
 
 
143
static ResultType breakthrough_eval (Pos *pos, Player player, float *eval)
 
144
{
 
145
        float wtsum = 0;
 
146
        int i, j;
 
147
        int wcount[BREAKTHROUGH_BOARD_WID], bcount[BREAKTHROUGH_BOARD_WID];
 
148
        float doubled_pawn_penalty = 0.2;
 
149
        float edge_pawn_bonus = 0.1;
 
150
        float backward_pawn_penalty = 0.5;
 
151
        float blocked_pawn_penalty = 0.1;
 
152
 
 
153
        int passer_min_white = board_heit, passer_min_black = board_heit;
 
154
        
 
155
        for (i=0; i<board_wid; i++)
 
156
        {
 
157
                // cheap optimization trick 
 
158
                if (pos->board [0 * board_wid + i] == BREAKTHROUGH_WP && 
 
159
                                pos->board [(board_heit - 1) * board_wid + i] == BREAKTHROUGH_BP)
 
160
                        continue;
 
161
                for (j=0; j<board_heit; j++)
 
162
                {
 
163
                        int val = pos->board[j * board_wid + i];
 
164
                        if (val == BREAKTHROUGH_EMPTY) continue;
 
165
                        if (eval_is_passer (pos->board, i, j))
 
166
                        {
 
167
                                if (val == BREAKTHROUGH_WP && (board_wid -1 - j < passer_min_white))
 
168
                                        passer_min_white = board_wid -1 - j;
 
169
                                if (val == BREAKTHROUGH_BP && (j < passer_min_black))
 
170
                                        passer_min_black = j;
 
171
                        }
 
172
                }
 
173
        }
 
174
        if (passer_min_white < board_heit || passer_min_black < board_heit)
 
175
        {
 
176
                int diff = passer_min_white - passer_min_black;
 
177
                if (diff < 0 || (diff == 0 && player == WHITE))
 
178
                {
 
179
                        *eval = -diff + 1;
 
180
                        return RESULT_WHITE;
 
181
                }
 
182
                if (diff > 0 || (diff == 0 && player == BLACK))
 
183
                {
 
184
                        *eval = -diff - 1;
 
185
                        return RESULT_BLACK;
 
186
                }
 
187
        }
 
188
        
 
189
        for (i=0; i<board_wid; i++)
 
190
                wcount[i] = bcount[i] = 0;
 
191
 
 
192
        for (i=0; i<board_wid; i++)
 
193
        for (j=0; j<board_heit; j++)
 
194
        {
 
195
                int val = pos->board [j * board_wid + i];
 
196
                if (val == BREAKTHROUGH_EMPTY) continue;
 
197
                if (val == BREAKTHROUGH_WP)
 
198
                {
 
199
                        wtsum += (1 + 0.1 * j);
 
200
                        if (i == 0 || i == board_wid - 1)
 
201
                                wtsum += edge_pawn_bonus;
 
202
                        if (eval_is_backward (pos->board, i, j))
 
203
                                wtsum -= backward_pawn_penalty;
 
204
                        wcount[i]++;
 
205
                }
 
206
                else if (val == BREAKTHROUGH_BP)
 
207
                {
 
208
                        wtsum -= (1 + 0.1 * (board_wid - 1 - j));
 
209
                        if (i == 0 || i == board_wid - 1)
 
210
                                wtsum -= edge_pawn_bonus;
 
211
                        if (eval_is_backward (pos->board, i, j))
 
212
                                wtsum += backward_pawn_penalty;
 
213
                        bcount[i]++;
 
214
                }
 
215
        }
 
216
        
 
217
        for (i=0; i<board_wid; i++)
 
218
        {
 
219
                wtsum -= (wcount[i] > 1 ? wcount[i] - 1 : 0);
 
220
                wtsum += (bcount[i] > 1 ? bcount[i] - 1 : 0);
 
221
        }
 
222
        
 
223
        *eval = wtsum;
 
224
        return RESULT_NOTYET;
 
225
}
 
226
 
 
227
static ResultType breakthrough_eval_incr (Pos *pos, byte *move, float *eval)
 
228
{
 
229
        byte *board = pos->board;
 
230
        if (move[0] == move[3]) *eval = 0;
 
231
        else *eval = (pos->player == WHITE ? 1 : -1);
 
232
        *eval += 0.01 * random() / RAND_MAX;
 
233
        return RESULT_NOTYET;
 
234
}
 
235
 
 
236
static byte * breakthrough_movegen (Pos *pos)
 
237
{
 
238
        int i, j, m, n, xoff, yoff;
 
239
        byte movbuf [256];
 
240
        byte *movlist, *movp = movbuf;
 
241
        byte *board = pos->board;
 
242
 
 
243
        // generate a random permutation of the moves
 
244
        xoff = random() % board_wid;
 
245
        yoff = random() % board_heit;
 
246
        for (m=0; m<board_wid; m++)
 
247
        for (n=0; n<board_heit; n++)
 
248
        {
 
249
                int incx, incy;
 
250
                i = (m + xoff) % board_wid;
 
251
                j = (n + yoff) % board_heit;
 
252
                if (board [j * board_wid + i] != 
 
253
                                (pos->player == WHITE ? BREAKTHROUGH_WP : BREAKTHROUGH_BP))
 
254
                        continue;
 
255
                incy = board [j * board_wid + i] == BREAKTHROUGH_WP ? 1 : -1;
 
256
                for (incx = -1; incx <= 1; incx += 1)
 
257
                {
 
258
                        int val;
 
259
                        if (!ISINBOARD (i + incx, j + incy))
 
260
                                continue;
 
261
                        val = board [(j+incy) * board_wid + (i+incx)];
 
262
                        if ((val == BREAKTHROUGH_EMPTY || val == board [j * board_wid + i]) 
 
263
                                        && incx != 0)
 
264
                                continue;
 
265
                        if (val != BREAKTHROUGH_EMPTY && incx == 0) continue;
 
266
                        *movp++ = i + incx;
 
267
                        *movp++ = j + incy;
 
268
                        *movp++ = (pos->player == WHITE ? BREAKTHROUGH_WP : BREAKTHROUGH_BP);
 
269
                        *movp++ = i;
 
270
                        *movp++ = j;
 
271
                        *movp++ = 0;
 
272
                        *movp++ = -1;
 
273
                }               
 
274
        }
 
275
        *movp++ = -2;
 
276
        movlist = (byte *) (malloc (movp - movbuf));
 
277
        memcpy (movlist, movbuf, (movp - movbuf));
 
278
        return movlist;
 
279
}
 
280
 
 
281
int breakthrough_getmove (Pos *pos, int x, int y, GtkboardEventType type, Player player, 
 
282
                byte **movp, int **rmovp)
 
283
{
 
284
        static byte move[128];
 
285
        byte *mp = move;
 
286
        int diffx, diffy;
 
287
        if (type != GTKBOARD_BUTTON_RELEASE)
 
288
                return 0;
 
289
        if (breakthrough_curx < 0)
 
290
        {
 
291
                if ((player == WHITE && pos->board [y * board_wid + x] == BREAKTHROUGH_WP)
 
292
                                || (player == BLACK && pos->board [y * board_wid + x] == BREAKTHROUGH_BP))
 
293
                {
 
294
                        int incy = player == WHITE ? 1 : -1;
 
295
                        int other = player == WHITE ? BREAKTHROUGH_BP : BREAKTHROUGH_WP;
 
296
                        if ((x == 0 || pos->board [(y + incy) * board_wid + x - 1] != other) &&
 
297
                                (x == board_wid - 1 || 
 
298
                                 pos->board [(y + incy) * board_wid + x + 1] != other))
 
299
                        {
 
300
                                if (pos->board [(y + incy) * board_wid + x] != BREAKTHROUGH_EMPTY)
 
301
                                        return -1;
 
302
                                else
 
303
                                {
 
304
                                        *mp++ = x;
 
305
                                        *mp++ = y;
 
306
                                        *mp++ = 0;
 
307
                                        *mp++ = x;
 
308
                                        *mp++ = y + incy;
 
309
                                        *mp++ = pos->board [y * board_wid + x];
 
310
                                        *mp++ = -1;
 
311
                                        *movp = move;
 
312
                                        return 1;
 
313
                                }
 
314
                        }
 
315
                        else
 
316
                        {
 
317
                                breakthrough_curx = x;
 
318
                                breakthrough_cury = y;
 
319
                        }
 
320
                        return 0;
 
321
                }
 
322
                return -1;
 
323
        }
 
324
        diffx = x - breakthrough_curx;
 
325
        diffy = y - breakthrough_cury;
 
326
        if ((player == WHITE && pos->board [y * board_wid + x] == BREAKTHROUGH_WP)
 
327
                || (player == BLACK && pos->board [y * board_wid + x] == BREAKTHROUGH_BP))
 
328
        {
 
329
                breakthrough_curx = breakthrough_cury = -1;
 
330
                return -1;
 
331
        }
 
332
        else if (pos->board[y * board_wid + x] == BREAKTHROUGH_EMPTY 
 
333
                        && 
 
334
                        (
 
335
                                (player == WHITE && (diffy != 1 || diffx != 0))
 
336
                                        ||
 
337
                                (player == BLACK && (diffy != -1 || diffx != 0))
 
338
                        )
 
339
           )
 
340
        {
 
341
                breakthrough_curx = breakthrough_cury = -1;
 
342
                return -1;
 
343
        }
 
344
        else if (((player == WHITE && pos->board [y * board_wid + x] == BREAKTHROUGH_BP)
 
345
                || (player == BLACK && pos->board [y * board_wid + x] == BREAKTHROUGH_WP))
 
346
                && 
 
347
                        ((player == WHITE && (diffy != 1 || abs (diffx) != 1))
 
348
                ||(player == BLACK && (diffy != -1 || abs(diffx) != 1))))
 
349
        {
 
350
                breakthrough_curx = breakthrough_cury = -1;
 
351
                return -1;
 
352
        }
 
353
        *mp++ = x;
 
354
        *mp++ = y;
 
355
        *mp++ = (player == WHITE ? BREAKTHROUGH_WP : BREAKTHROUGH_BP);
 
356
        *mp++ = breakthrough_curx;
 
357
        *mp++ = breakthrough_cury;
 
358
        *mp++ = 0;
 
359
        *mp++ = -1;
 
360
        *movp = move;
 
361
        breakthrough_curx = breakthrough_cury = -1;
 
362
        return 1;
 
363
}
 
364