vcs.maemo.org Git - mancala/blob - src/ai-recurse.c

   1 /*
   2  *  Recursive AI Algorithm -- ai-recurse.c
   3  *  Kevin Riggle
   4  *  http://cmancala.sourceforge.net
   5  *  $Source: /cvsroot/cmancala/mancala/src/Attic/ai-recurse.c,v $
   6  *  $Revision: 1.22.2.1 $
   7  *  $Date: 2003/12/29 05:49:52 $
   8  *
   9  */
  10
  11 #include <stdlib.h>
  12 #include <stdio.h>
  13 #include "mancala.h"
  14 #include "ai.h"
  15 #include "ai-init.h"
  16
  17 /* How far should I go? */
  18 #define MAX_DEPTH 20
  19
  20 /* keep the actual mechanics of the recursive algorithm internal */
  21 static int aiRecurse (int *aiBoard, int *humanBoard, int depth, FILE *log);
  22
  23 /* new stub api function using init routine */
  24
  25 int aiMove(int *aiBoard, int *humanBoard) {
  26
  27         return aiInit(aiBoard, humanBoard, "recurse.log", aiRecurse);
  28
  29 }
  30
  31 /* actual recursive function, accept no imitations */
  32 int aiRecurse (int *aiBoard, int *humanBoard, int depth, FILE *log) {
  33
  34         int aiBoardTemp[BOARD_MAX+1], humanBoardTemp[BOARD_MAX+1];
  35         int i, j, bestmove, pts, endpos;
  36
  37         bestmove = pts = endpos = 0;
  38
  39         /*printf("AI at depth %d\n", depth);*/
  40         fprintf(log, "AI at depth %d\n", depth);
  41
  42         /* Keep us from recursing infinitely */
  43         if (depth > MAX_DEPTH)
  44                 return bestmove;
  45
  46         /* iterate through each board position */
  47         for (i=1; i<=BOARD_MAX; i++) {
  48
  49                 /* copy boards to temp. location */
  50                 for(j=0; j<=BOARD_MAX; j++) {
  51                         aiBoardTemp[j] = aiBoard[j];
  52                         humanBoardTemp[j] = humanBoard[j];
  53                 }
  54
  55                 /* test the current move */
  56                 endpos = move(aiBoardTemp, humanBoardTemp, i);
  57
  58                 /* if we get another turn, recurse */
  59                 if (endpos == 0)
  60                         aiRecurse(aiBoardTemp, humanBoardTemp,
  61                                 (depth+1), log);
  62
  63                 /* log it */
  64                 fprintf(log, "Moving from %d at depth %d\n", i, depth);
  65                 fprintf(log, "Ends at %d and nets %d points.\n", endpos,
  66                         (aiBoardTemp[0] - aiBoard[0]));
  67
  68                 /* if this move is better, record it */
  69                 if ((aiBoardTemp[0] - aiBoard[0]) > pts) {
  70                         pts = (aiBoardTemp[0] - aiBoard[0]);
  71                         bestmove = i;
  72                 }
  73         }
  74
  75         /* if no move is best and some still exist, pick one at random */
  76         if ((bestmove == 0) && (!gameWon(aiBoard, humanBoard)))
  77                 while (aiBoard[(bestmove
  78                         = rand_btw(1,BOARD_MAX+1))] == 0)
  79                         ;
  80
  81         /* make the final move and return */
  82         move(aiBoard, humanBoard, bestmove);
  83
  84         return bestmove;
  85
  86 }
  87
  88 /*  End ai-recurse.c  */