OpenCores

Subversion Repositories connect-6

[/] [connect-6/] [trunk/] [BUILD_SCC/] [synth_src/] [shared.h] - Blame information for rev 4

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 4 sumanta.chaudhuri
 
2
/*
3
 
4
connectk -- a program to play the connect-k family of games
5
Copyright (C) 2007 Michael Levin
6
 
7
This program is free software; you can redistribute it and/or
8
modify it under the terms of the GNU General Public License
9
as published by the Free Software Foundation; either version 2
10
of the License, or (at your option) any later version.
11
 
12
This program is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with this program; if not, write to the Free Software
19
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
20
 
21
*/
22
/* Some definitions in case glib is not included */
23
//#ifndef TRUE
24
#define TRUE 1
25
#define FALSE 0
26
#define NULL ((void*)0)
27
//#endif
28
//#ifndef __G_TYPES_H__
29
typedef unsigned int gboolean;
30
#pragma bitsize gboolean 1
31
typedef int gsize;
32
//#endif
33
 
34
 
35
/*
36
 *      Options
37
 */
38
 
39
/* These are boolean options the user can toggle through the "Options" menu.
40
   Do not modify them directly as the "Options" menu will not reflect your
41
   changes. You can add more options in connectk.c */
42
extern int opt_pause_ai,        /* Pause AI to inspect the board */
43
//           opt_det_ai,          /* No randomness */
44
           opt_print_u,         /* Print utility after every move */
45
           opt_debug_dfsc,      /* Print out debug messages related to the DFS
46
                                   cache */
47
           opt_debug_thread,    /* Print messages related to thread and mutex function */
48
           opt_mark_log,        /* Take log of weights before marking */
49
           opt_mark_norm,       /* Normalize to the largest weight */
50
           opt_debug_stage,     /* Debug priority stages */
51
           opt_grayscale;       /* Use grayscale rendering for print outs */
52
 
53
/*
54
 *      Utility
55
 */
56
 
57
#ifdef _EFISTDARG_H_
58
char *nvav(int *plen, const char *fmt, va_list va);
59
#endif
60
char *nva(int *plen, const char *fmt, ...);
61
char *va(const char *fmt, ...);
62
/* The va family of functions simplify string processing by allowing
63
   printf-style substitution with any string-accepting function.
64
 
65
   For example:
66
     window_status(va("1 + 2 = %d", 1 + 2));
67
 
68
   nva provides additional functionality by outputting the length of the
69
   formatted string into the integer pointed to by plen. nvav accepts a variable
70
   argument indirectly. */
71
 
72
void window_status(const char *msg);
73
/* Sets the status bar text of the main window */
74
 
75
/*
76
 *      Allocation Chain
77
 */
78
 
79
typedef struct AllocChain {
80
        gboolean free;
81
        /* Is this object unallocated? */
82
 
83
        unsigned int id;
84
        /* Each object has a unique id */
85
 
86
        struct AllocChain *next;
87
        /* Next object in the chain */
88
} AllocChain;
89
 
90
typedef AllocChain *(*AllocFunc)(AllocChain *old_ac);
91
 
92
AllocChain *achain_new(AllocChain **root, AllocFunc af);
93
void achain_free(AllocChain *ac);
94
void achain_copy(const AllocChain *src, AllocChain *dest, gsize mem);
95
 
96
/*
97
 *      Game state
98
 */
99
 
100
/* We limit the maximum values of these variables; note that these are not
101
   arbitrary limits and should be modified with care */
102
#define MAX_BOARD_SIZE  59
103
#define MAX_CONNECT_K   12
104
#define MAX_PLACE_P     12
105
#define MAX_START_Q     6
106
#define MAX_DEPTH       9
107
#define MAX_BRANCH      32
108
 
109
 
110
#define board_size 19
111
#define board_stride 21
112
#define move_no 0
113
#define move_last 0
114
#define connect_k 6
115
#define place_p 2
116
#define start_q 1
117
#define opt_det_ai 1
118
//extern int board_size, board_stride, move_no, connect_k, place_p, start_q;
119
/* Board size (for all boards), moves in the game, connect_k to win, place_p
120
   moves at a time, black has start_q moves on the first move; do NOT modify
121
   these directly! */
122
 
123
enum {
124
        PIECE_ERROR = -1,
125
        /* Error pieces form a one tile deep border around the board */
126
 
127
        PIECE_NONE = 0,
128
        PIECE_BLACK,
129
        PIECE_WHITE,
130
        /* Empty and played pieces */
131
 
132
        PIECES,
133
        /* Total number of normal pieces (2) */
134
 
135
        PIECE_SEARCHED,
136
        PIECE_SEARCHED_MAX = PIECE_SEARCHED + MAX_DEPTH,
137
        /* Markers used by the search system */
138
 
139
        PIECE_THREAT0,
140
        PIECE_MARKER = PIECE_THREAT0,
141
        /* These threat markers are usable by the AIs */
142
};
143
typedef int PIECE;
144
//#pragma bitsize PIECE 16
145
 
146
#define MAX_THREAT (INT_MAX - PIECE_THREAT0)
147
/* Highest value a threat marker can have */
148
 
149
#define PIECE_THREAT(n) (PIECE_THREAT0 + (n))
150
/* This marker represents a threat n-turns (of that player) away */
151
 
152
#define piece_empty(p) ((p) == PIECE_NONE || (p) >= PIECES)
153
/* Checks if a piece is an empty or a marker */
154
 
155
typedef unsigned int PLAYER;
156
/* Type for AIs, this is the index of the AI entry in ai.c */
157
 
158
typedef int BCOORD;
159
#pragma bitsize BCOORD 8
160
/* Type for board coordinates */
161
 
162
typedef struct Board {
163
        int  ac;
164
        /* Allocation chain must be the first member */
165
        #pragma bitsize ac 4
166
        unsigned int moves_left;
167
        /* How many moves the current player has left */
168
        #pragma bitsize  moves_left 8
169
 
170
        //struct Board *parent; //not synthesizable
171
        int parent;
172
        /* The board preceeding this one in history */
173
        #pragma bitsize  parent 4
174
 
175
        gboolean won;
176
        BCOORD win_x1, win_y1, win_x2, win_y2;
177
        /* On won boards, used to indicate where the winning line is */
178
 
179
        PIECE turn;
180
        /* Whose turn it is on this board */
181
 
182
        BCOORD move_x, move_y;
183
        /* The move to the next Board in history */
184
 
185
        PIECE data[board_stride][board_stride];
186
} Board;
187
/* The board structure represents the state of the game board. Do NOT preserve
188
   board pointers across games. */
189
 
190
extern AllocChain *board_root;
191
extern gsize board_mem;
192
/* Variables for the allocation chain */
193
 
194
//extern Board board;
195
/* This is the current board. Do NOT modify it, that's cheating. :) */
196
const char *bcoords_to_string(BCOORD x, BCOORD y);
197
const char *bcoord_to_alpha(BCOORD c);
198
/* Return a static string representing a board coordinate pair */
199
 
200
void string_to_bcoords(const char *string, BCOORD *x, BCOORD *y);
201
/* Attempts to convert a string to board coordinates */
202
 
203
void new_game(Board *board,unsigned int size);
204
 
205
AllocChain *board_alloc(AllocChain *data);
206
#define board_new() ((Board*)achain_new(&board_root, board_alloc))
207
#define board_free(b) achain_free((AllocChain*)b)
208
/* Boards are dynamically allocated and must be free'd */
209
 
210
//#define board_copy(from, to) achain_copy((AllocChain*)from, (AllocChain*)to,\
211
                                         board_mem)
212
void board_copy(const Board *from,  Board *to);
213
/* Overwrite one board with another */
214
 
215
void board_clean(Board *b);
216
/* Remove all threat markers from a board */
217
 
218
int threat_count(const Board *b, PIECE player);
219
/* Gives the number of threats on a board for the current player */
220
 
221
Board *board_at(unsigned int move);
222
/* Returns a static pointer to a board in the history at move */
223
 
224
//int  count_pieces(const Board *b, BCOORD x, BCOORD y, PIECE type,
225
int  count_pieces(const Board *b, BCOORD x, BCOORD y, PIECE type,
226
                      int dx, int dy, PIECE *out);
227
/* Count consecutive pieces of type starting from (x, y) in the direction given
228
   by (dx, dy); includes (x, y) itself in the count and outputs the final
229
   piece to out if it is not NULL */
230
 
231
gboolean check_win_full(const Board *b, BCOORD x, BCOORD y,
232
                        BCOORD *x1, BCOORD *y1, BCOORD *x2, BCOORD *y2);
233
#define check_win(b, x, y) check_win_full(b, x, y, 0, 0, 0, 0)
234
/* Returns non-zero if placing a piece of type at (x, y) on the current board
235
   will result in a win for that player. The start and end coordinates of the
236
   winning line will be placed in (x1, y1) and (x2, y2). */
237
 
238
static inline PIECE piece_at(const Board *b, BCOORD x, BCOORD y)
239
{
240
        //return b->data[(y + 1) * board_stride + x + 1];
241
        return b->data[y+1][x+1];
242
}
243
/* Returns the piece at (x, y) on board b. If the coordinates are out of range,
244
   this function will return PIECE_ERROR. */
245
 
246
char piece_to_char(PIECE piece);
247
/* Returns a one character representation of a piece (e.g. 'W', 'B', etc) */
248
 
249
const char *piece_to_string(PIECE piece);
250
/* Returns a static string representation of a piece (e.g. "White" etc) */
251
 
252
static inline void place_piece_type(Board *b, BCOORD x, BCOORD y, PIECE type)
253
{
254
        //b->data[(y + 1) * board_stride + x + 1] = type;
255
        b->data[y+1][x+1]=type;
256
}
257
#define place_piece(b, x, y) place_piece_type(b, x, y, (b)->turn)
258
#define place_threat(b, x, y, n) place_piece_type(b, x, y, PIECE_THREAT(n))
259
/* Places a piece on board b, overwriting any piece that was previously in that
260
   place */
261
 
262
#define other_player(p) ((p) == PIECE_BLACK ? PIECE_WHITE : PIECE_BLACK)
263
/* Invert a player piece */
264
 
265
/*
266
 *      Move arrays
267
 */
268
 
269
/* Some guideline values for move weights: */
270
#define AIW_MAX         INT_MAX         /* largest weight value */
271
#define AIW_MIN         INT_MIN         /* smallest weight value */
272
#define AIW_WIN         AIW_MAX         /* this move wins the game */
273
#define AIW_DEFEND      (AIW_WIN - 2)   /* defends from an opponent win */
274
#define AIW_NONE        0               /* does nothing */
275
#define AIW_DRAW        AIW_NONE        /* draw game */
276
#define AIW_LOSE        (-AIW_WIN)      /* this move loses the game */
277
#define AIW_THREAT_MAX  262144          /* value of an immediate threat */
278
 
279
typedef int AIWEIGHT;
280
/* Type for AI move weights (utilities) */
281
#pragma bitsize AIWEIGHT 32
282
 
283
typedef struct {
284
        AIWEIGHT weight;
285
        BCOORD x, y;
286
} AIMove;
287
/* AIs return an array filled with these */
288
 
289
typedef struct AIMoves {
290
        int ac;
291
        /* Allocation chain must be the first member */
292
        #pragma bitsize ac 4
293
 
294
        unsigned int len;
295
        /* Number of members in data */
296
        #pragma bitsize len 8
297
 
298
        AIWEIGHT utility;
299
        /* A composite utility value set by some AIs when producing a moves
300
           list */
301
 
302
        AIMove data[361];
303
        /* Array of AIMove structures */
304
} AIMoves;
305
/* An array type for holding move lists */
306
 
307
AllocChain *aimoves_alloc(AllocChain *data);
308
#define aimoves_new() ((AIMoves*)achain_new(&aimoves_root, aimoves_alloc))
309
//#define aimoves_free(m) achain_free((AllocChain*)(m))
310
static inline void aimoves_free(AIMoves *m) {
311
        m->len=0;
312
}
313
///////////* Move arrays are dynamically allocated and must be free'd */
314
//////////
315
//////////#define aimoves_copy(from, to) achain_copy((AllocChain*)(from),\
316
//////////                                           (AllocChain*)(to), aimoves_mem)
317
///////////* Overwrite one array with another */
318
//////////
319
//////////void aimoves_add(AIMoves *moves, const AIMove *aim);
320
///////////* Add an AIMove to an AIMoves array; move weights will be added to existing
321
//////////   weights */
322
//////////
323
void aimoves_append(AIMoves *moves, const AIMove *aim);
324
#define aimoves_set aimoves_append
325
///////////* Add an AIMove to an AIMoves array; existing moves weights will be
326
//////////   overwritten */
327
//////////
328
int aimoves_choose(AIMoves *moves, AIMove *move);
329
/* Will choose one of the best moves from a GArray of AIMove structures at
330
   random. Returns non-zero if a move was chosen or zero if a move could not
331
   be chosen for some reason. */
332
//////////
333
int aimoves_compare(const void *a, const void *b);
334
/* A comparison function for sorting move lists by weight */
335
//////////
336
//////////void aimoves_crop(AIMoves *moves, unsigned int n);
337
///////////* Reduce a moves list to the top-n by weight */
338
//////////
339
//////////void aimoves_concat(AIMoves *m1, const AIMoves *m2);
340
///////////* Concatenates m2 to m1 without checking for duplicates */
341
//////////
342
//////////AIMoves *aimoves_dup(const AIMoves *moves);
343
///////////* Duplicate a GArray of moves */
344
//////////
345
int aimoves_find(const AIMoves *moves, BCOORD x, BCOORD y);
346
///////////* Returns the index of (x, y) if it is in moves or -1 otherwise */
347
//////////
348
//////////void aimoves_range(AIMoves *moves, AIWEIGHT *min, AIWEIGHT *max);
349
///////////* Find the smallest and largest weight in the move array */
350
//////////
351
//////////void aimoves_merge(AIMoves *m1, const AIMoves *m2);
352
///////////* Merges m2 into m1, the highest weight is used for duplicates */
353
//////////
354
//////////void aimoves_print(const AIMoves *moves);
355
///////////* Prints out an array of moves */
356
//////////
357
//////////void aimoves_remove(AIMoves *moves, BCOORD x, BCOORD y);
358
///////////* Remove an AIMove from a GArray of AIMoves */
359
//////////
360
//////////void aimoves_remove_index_fast(AIMoves *moves, int i);
361
///////////* Remove a move from the list by overwriting it by the last move and
362
//////////   decrementing the length */
363
//////////
364
void aimoves_shuffle(AIMoves *moves,unsigned int current_random);
365
/* Shuffle a list of moves */
366
 
367
void aimoves_sort(AIMoves *moves);
368
/* Sort a list of moves by descending weight */
369
 
370
//////////void aimoves_subtract(AIMoves *m1, const AIMoves *m2);
371
///////////* Subtracts members of m2 from m1; O(n^2) */
372
//////////
373
extern AllocChain *aimoves_root;
374
//////////extern gsize aimoves_mem;
375
///////////* Allocation chain variables */
376
//////////
377
//////////const char *aiw_to_string(AIWEIGHT w);
378
///////////* Convert a weight to a string representation */
379
//////////
380
//////////char *aimove_to_string(const AIMove *move);
381
///////////* Convert a move to a string representation */
382
//////////
383
///////////*
384
////////// *      AI helper functions
385
////////// */
386
//////////
387
//////////extern int ai_stop;
388
///////////* If this variable is non-zero, the system is trying to stop the AI thread
389
//////////   and your AI should exit. Do not set this yourself. */
390
//////////
391
//////////typedef AIMoves *(*AIFunc)(const Board *b);
392
///////////* AIs are defined as functions that output an unsorted, weighted list of board
393
//////////   coordinates for an arbitrary board. To create an AI in a file other than
394
//////////   ai.c, add a prototype of the function here and in ai.c. */
395
//////////
396
//////////AIMoves *enum_top_n(const Board *b, int n);
397
///////////* Returns an array containing the top n moves according to the utility
398
//////////   function */
399
//////////
400
/*AIMoves **/ void enum_adjacent(Board *b, int dist,AIMoves *moves,unsigned int current_random);
401
/* Enumerate empty tiles at most dist away from some other piece on the board */
402
 
403
/*AIMoves **/void ai_marks(Board *b, PIECE min,AIMoves *moves);
404
/* Fills a moves list with tiles marked at least PIECE_THREAT(min) */
405
 
406
/*
407
 *      AI
408
 */
409
 
410
/* This table holds the information about all of the AIs in the program. Each
411
   has a short and long description. The short description will be used for
412
   the command line interface and the long description appears in the UI menu.
413
   Each AI has an associated AIFunc which outputs a move for the current
414
   board. */
415
///////////typedef struct AI {
416
///////////        char *s_desc, *l_desc;
417
///////////        AIFunc func;
418
///////////} AI;
419
///////////
420
///////////AIMoves *ai_sequences(const Board *b);
421
////////////* The square of the number of pieces in a window */
422
///////////
423
///////////AIMoves *ai_mesh(const Board *b);
424
////////////* The board as a mesh weighed down by the pieces */
425
///////////
426
///////////AIMoves *ai_monte_carlo(const Board *b);
427
////////////* Chooses the best move based on which one wins the most random games */
428
///////////
429
///////////AIMoves *ai_random(const Board *b);
430
////////////* Plays in a random tile */
431
///////////
432
/*AIMoves */ void ai_adjacent(Board *b,AIMove *move,unsigned int current_random);
433
/* Plays in a random tile adjacent to any piece on the board */
434
 
435
///////////AIMoves *ai_windows(const Board *b);
436
////////////* Plays in the best defensive position */
437
///////////
438
///////////AIMoves *ai_utility(const Board *b);
439
///////////AIMoves *ai_dfs_utility(const Board *b);
440
////////////* Utility function */
441
///////////
442
/*AIMoves **/int ai_threats(Board *board,AIMove *move);
443
AIMoves *ai_priority(const Board *b);
444
/* Multi-level threats */
445
 
446
 
447
 
448
void my_srandom(int seed,unsigned int *current_random);
449
int my_irand(int imax,unsigned int current_random);
450
//void backup_move(Board *board, AIMoves *moves,AIMove *move);
451
AIWEIGHT threat_line(int x, int y, int dx, int dy,Board *b,Board *bwrite,AIMoves *moves,int k);
452
int threat_window(int x, int y, int dx, int dy,
453
                         PIECE *ptype, int *pdouble,Board *b);
454
int connect6ai_synth(int firstmove,char movein[8], char colour, char moveout[8]);

powered by: WebSVN 2.1.0

© copyright 1999-2014 OpenCores.org, equivalent to ORSoC AB, all rights reserved. OpenCores®, registered trademark.