File: mancala.c

package info (click to toggle)
mancala 1.0.3-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, jessie, jessie-kfreebsd, sid, stretch
  • size: 196 kB
  • ctags: 104
  • sloc: ansic: 710; makefile: 67; sh: 6
file content (451 lines) | stat: -rw-r--r-- 13,620 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
/* $Id: mancala.c,v 1.2 2007-06-13 18:29:52 sverrehu Exp $ */
/**************************************************************************
 *
 *  FILE            mancala.c
 *  MODULE OF       The board game Mancala.
 *
 *  DESCRIPTION     An implementation of the simple game called Mancala.
 *                  This is the backend.
 *
 *  WRITTEN BY      Sverre H. Huseby
 *
 **************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

#include "minimax.h"
#include "mancala.h"

/**************************************************************************
 *                                                                        *
 *                       P R I V A T E    D A T A                         *
 *                                                                        *
 **************************************************************************/

/*
 *  Define this if you want a more timeconsuming evaluation function.
 *  We're not sure it makes it any better -- it may even make it worse.
 */
#define FULL_EVAL

/*
 *  The board state stack, and the current stacklevel.
 */
static Board boardStack[STACK_LEVELS];
static int   idx = 0;

/*
 *  The game logic function requests an array of pointers to possible
 *  moves for a level of it's recursion. We need one array for each
 *  possible recursion level, so we don't mess things up. possibleMoveTable
 *  contains the real move variables, while possibleMove contains the
 *  pointers into the variable table.
 */
static Move  possibleMoveTable[STACK_LEVELS][MAX_HOLES];
static PMove possibleMove[STACK_LEVELS][MAX_HOLES];



/**************************************************************************
 *                                                                        *
 *                   P R I V A T E    F U N C T I O N S                   *
 *                                                                        *
 **************************************************************************/

/*------------------------------------------------------------------------*
 |                 Callbacks for the game logic function                  |
 *------------------------------------------------------------------------*/

/*-------------------------------------------------------------------------
 *
 *  NAME          pushBoard
 *
 *  FUNCTION      Save the current board state on a stack.
 *
 *  DESCRIPTION   This callback is called at the start of each recursion
 *                level. We use it to save the current board setup, and
 *                to make sure requests for new moves (getMoves()) don't
 *                mess up the array of moves currently being explored.
 */
static void pushBoard(void)
{
    ++idx;
    memcpy(&boardStack[idx], &boardStack[idx - 1], sizeof(Board));
}



/*-------------------------------------------------------------------------
 *
 *  NAME          popBoard
 *
 *  FUNCTION      Restore the current board stat from the stack.
 *
 *  DESCRIPTION   This callback is called at the end of each recursion
 *                level. We restore the board state (remove the
 *                `experimental' moves), and open for reuse of the array
 *                of possible moves.
 */
static void popBoard(void)
{
    --idx;
}



/*-------------------------------------------------------------------------
 *
 *  NAME          getMoves
 *
 *  FUNCTION      Make list of possible moves for the given player.
 *
 *  INPUT         player  the player to make movelist for.
 *
 *  OUTPUT        numMoves
 *                        number of moves in the returned array.
 *
 *  RETURNS       An array of pointers to legal moves, or NULL if no
 *                legal moves for this player.
 *
 *  DESCRIPTION   This callback is called for each recursion level to
 *                get a list of possible following moves. A legal move is
 *                the number of a non-empty hole for the player in question.
 *
 *                The current stacklevel is used to find a `free' array
 *                that we can fill with legal moves. We couldn't use the
 *                same array all the time, since the array we returned in
 *                the previous call is not fully examined (yeah, recursion
 *                gives some interresting problems...).
 */
static PMove *getMoves(Player player, int *numMoves)
{
    int        q, n = 0;
    StoneCount *hole;
    PMove      *m, *ret;

    m = ret = possibleMove[idx];
    hole = boardStack[idx].hole[player];
    for (q = 0; q < MAX_HOLES; q++) {
	if (*hole)
	    m[n++]->hole = q;
	++hole;
    }
    if ((*numMoves = n) == 0)
	ret = NULL;
    return ret;
}



/*-------------------------------------------------------------------------
 *
 *  NAME          undoMove
 *
 *  FUNCTION      Update the board to the state before the given move.
 *
 *  INPUT         player  the player that did the move.
 *                move    pointer to the move to undo.
 *
 *  DESCRIPTION   This callback is called at the end of each recursion
 *                level. Since we really change the board in popBoard(),
 *                we don't need to do anything here.
 */
static void undoMove(Player player, PMove move)
{
    /* memcpy(&boardStack[idx], &boardStack[idx - 1], sizeof(Board)); */
}



/*-------------------------------------------------------------------------
 *
 *  NAME          evalBoard
 *
 *  FUNCTION      Evaluate the board after a player has moved.
 *
 *  INPUT         player  the player to evaluate the board for.
 *
 *  RETURNS       A measure indicating how good the current board is for
 *                the given player. Larger values are better. A positive
 *                value indicates that the given player is in the lead,
 *                while a negative value indicates the opposite.
 *
 *  DESCRIPTION   We do it simple; just see which player has captured
 *                most stones.
 */
static Score evalBoard(Player player)
{
    Board  *b;

#ifdef FULL_EVAL
    Player winner;
    /*
     *  The next thing that happens after the evaluation, is that the
     *  previous board is popped from the stack, so we can let the
     *  evaluation function mess the board up like this:
     */
    checkAndFixWin(&winner);
#endif
    b = &boardStack[idx];
    return b->mancala[player] - b->mancala[player ^ 1];
}



/**************************************************************************
 *                                                                        *
 *                    P U B L I C    F U N C T I O N S                    *
 *                                                                        *
 **************************************************************************/

/*-------------------------------------------------------------------------
 *
 *  NAME          initGame
 *
 *  FUNCTION      Set up variables for a new game.
 */
void initGame(int stones_pr_hole)
{
    int    q, w;
    Board  *b;
    Player player;
    
    /*
     *  The game logic function uses random numbers to choose between
     *  moves that gives equal score, so we initiate the generator.
     */
    srand(time(NULL));

    /*
     *  An important step: Set up the possible move -pointers that the
     *  caller of getMoves() want. We make pointers into the table
     *  containing the real values.
     */
    for (q = 0; q < STACK_LEVELS; q++)
	for (w = 0; w < MAX_HOLES; w++)
	    possibleMove[q][w] = &possibleMoveTable[q][w];

    /*
     *  Clear the game stack, and set up the board to initial state.
     *  The `real' board is actually at position 0 of the stack array.
     */
    idx = 0;
    b = &boardStack[idx];
    for (player = 0; player < 2; player++) {
	b->mancala[player] = 0;
	for (w = 0; w < MAX_HOLES; w++)
	    b->hole[player][w] = stones_pr_hole;
    }
}



/*-------------------------------------------------------------------------
 *
 *  NAME          getHole
 *
 *  FUNCTION      Get number of stones in a hole on the board.
 *
 *  INPUT         player  the player to get number of stones for.
 *                hole    the hole number. 0 is the hole closest to
 *                        the mancala.
 *
 *  RETURNS       The number of stones in the given hole.
 */
StoneCount getHole(Player player, int hole)
{
    return boardStack[0].hole[player][hole];
}



/*-------------------------------------------------------------------------
 *
 *  NAME          getMancala
 *
 *  FUNCTION      Get number of stones in the mancala of a player.
 *
 *  INPUT         player  the player to get number of stones for.
 *
 *  RETURNS       The number of stones in the given player's mancala.
 */
StoneCount getMancala(Player player)
{
    return boardStack[0].mancala[player];
}



/*-------------------------------------------------------------------------
 *
 *  NAME          legalMove
 *
 *  FUNCTION      Check if a human's move is legal.
 *
 *  INPUT         player  the player that wants to move.
 *                move    pointer to the move to check.
 *
 *  RETURNS       1 if legal move, 0 if illegal.
 *
 *  DESCRIPTION   This is used to check if a human player has chosen to
 *                do a legal move. The computer player will only do moves
 *                returned by getMoves(), and those are (or should) all be
 *                legal.
 */
int legalMove(Player player, PMove move)
{
    int   q;
    PMove *legalmove;     /* array of pointerts to legal moves */
    int   numMoves;       /* number of moves in this array */

    legalmove = getMoves(player, &numMoves);
    for (q = 0; q < numMoves; q++) {
	if ((*legalmove)->hole == move->hole)
	    return 1;
	++legalmove;
    }
    return 0;
}



/*-------------------------------------------------------------------------
 *
 *  NAME          checkAndFixWin
 *
 *  FUNCTION      Check if the game is ended, and in that case fix scores.
 *
 *  OUTPUT        winner  the player that won.
 *
 *  RETURNS       0 if game not finished, 1 if one winner, 2 if draw.
 *
 *  DESCRIPTION   The game is over if any of the players have no stones
 *                left to move. In that case, all remaining stones for the
 *                opposite player is moved to that player's mancala, and
 *                the winner is the one with more stones.
 */
int checkAndFixWin(Player *winner)
{
    int        q, ret = 0, sum[2];
    Board      *b;
    StoneCount *hole;
    Player     player;

    b = &boardStack[idx];
    for (player = 0; player < 2; player++) {
	hole = b->hole[player];
	sum[player] = 0;
	for (q = 0; q < MAX_HOLES; q++)
	    sum[player] += hole[q];
    }
    if (sum[0] == 0 || sum[1] == 0) {
	ret = 1;
	for (player = 0; player < 2; player++) {
	    b->mancala[player] += sum[player];
	    hole = b->hole[player];
	    for (q = 0; q < MAX_HOLES; q++)
		hole[q] = 0;
	}
	if (b->mancala[0] > b->mancala[1])
	    *winner = 0;
	else if (b->mancala[0] < b->mancala[1])
	    *winner = 1;
	else
	    ret = 2;
    }
    return ret;
}



/*-------------------------------------------------------------------------
 *
 *  NAME          getBestMove
 *
 *  FUNCTION      Calculate best move for player.
 *
 *  INPUT         player  the player to evaluate.
 *                maxPly  max recursion depth.
 *
 *  RETURNS       Pointer to the best move to make, or NULL if no move
 *                available.
 *
 *  DESCRIPTION   This is just a frontend to the real game logic function,
 *                hiding the static functions found in this file.
 */
PMove getBestMove(Player player, int maxPly)
{
    return miniMax(pushBoard, popBoard,
		   getMoves, doMove, undoMove,
		   evalBoard, player, maxPly);
}



/*------------------------------------------------------------------------*
 |   The following function is a callback, but it's used for moving too.  |
 *------------------------------------------------------------------------*/

/*-------------------------------------------------------------------------
 *
 *  NAME          doMove
 *
 *  FUNCTION      Update the board with the given move.
 *
 *  INPUT         player  the player that does the move.
 *                move    pointer to the move to make.
 *
 *  RETURNS       The next player to move. For Mancala, this is the same
 *                player once again if the last stone ends in the mancala.
 *
 *  DESCRIPTION   This function is used both as a callback for finding the
 *                best moves, and as a `normal' function to update the
 *                board when a move is chosen.
 */
Player doMove(Player player, PMove move)
{
    int        seeds, holeNum, oppositeHoleNum;
    StoneCount *hole, *oppositeHole;
    Board      *b;
    Player     nextPlayer, holeOwner;

    nextPlayer = player ^ 1;
    b = &boardStack[idx];
    holeOwner = player;
    hole = b->hole[holeOwner];
    holeNum = move->hole;
    seeds = hole[holeNum];
    hole[holeNum] = 0;
    for (;;) {
	if (--holeNum < 0) {
	    if (holeOwner == player) {
		++b->mancala[player];
		if (!--seeds) {
		    nextPlayer = player;
		    break;
		}
	    }
	    holeOwner ^= 1;
	    hole = b->hole[holeOwner];
	    holeNum = MAX_HOLES - 1;
	} 
	++hole[holeNum];
	if (!--seeds) {
	    if (holeOwner == player) {
		oppositeHoleNum = MAX_HOLES - 1 - holeNum;
		oppositeHole = b->hole[player ^ 1];
		if (hole[holeNum] == 1 && oppositeHole[oppositeHoleNum]) {
		    b->mancala[player] += 1 + oppositeHole[oppositeHoleNum];
		    oppositeHole[oppositeHoleNum] = 0;
		    hole[holeNum] = 0;
		}
	    }
	    break;
	}
    }
    return nextPlayer;
}