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

   1 /*
   2  *  "Ultimate" AI Algorithm -- ai-ultimate.c
   3  *  Kevin Riggle
   4  *  http://cmancala.sourceforge.net
   5  *  $Source: /cvsroot/cmancala/mancala/src/Attic/ai-ultimate.c,v $
   6  *  $Revision: 1.12.2.1 $
   7  *  $Date: 2003/12/29 05:49:52 $
   8  *
   9  */
  10
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include "mancala.h"
  14 #include "ai.h"
  15 #include "ai-init.h"
  16
  17 static int aiUltimate(int *aiBoard, int *humanBoard, int depth, FILE *log);
  18
  19 /* api function */
  20
  21 int aiMove(int *aiBoard, int *humanBoard) {
  22
  23         return aiInit(aiBoard, humanBoard, "ultimate.log", aiUltimate);
  24
  25 }
  26
  27 int aiUltimate(int *aiBoard, int *humanBoard, int depth, FILE *log) {
  28
  29         int aiBoardTemp[BOARD_MAX+1], humanBoardTemp[BOARD_MAX+1];
  30         int *outcomes[BOARD_MAX+1];
  31         int ai_min[BOARD_MAX+1], human_max[BOARD_MAX+1];
  32         int i, j, k, result, bestmove;
  33
  34         bestmove = result = 0;
  35
  36         /* allocate memory to store the results */
  37         for (i=0; i<=BOARD_MAX; i++)
  38                 if ((outcomes[i] = (int *) calloc(BOARD_MAX+1, sizeof(int)))
  39                         == NULL)
  40                         printf("Cannot allocate memory...\n");
  41
  42         for (i=1; i<=BOARD_MAX; i++) {
  43         for (j=1; j<=BOARD_MAX; j++) {
  44
  45                 /* make another temporary copy of the boards */
  46                 for (k=0; k<=BOARD_MAX; k++) {
  47                         aiBoardTemp[k] = aiBoard[k];
  48                         humanBoardTemp[k] = humanBoard[k];
  49                 }
  50
  51                 /*  RECURSION
  52                 if (move(aiBoardTemp, humanBoardTemp, i) == 0)
  53                         aiUltimate(aiBoardTemp, humanBoardTemp, (depth+1), log);
  54                 if (move(humanBoardTemp, aiBoardTemp, j) == 0)
  55                         aiUltimate(humanBoardTemp, aiBoardTemp, {depth+1), log);
  56                 END RECURSION */
  57
  58                 move(aiBoardTemp, humanBoardTemp, i);
  59                 move(humanBoardTemp, aiBoardTemp, j);
  60
  61                 result = (aiBoardTemp[0] - aiBoard[0])
  62                         - (humanBoardTemp[0] - humanBoard[0]);
  63
  64                 *(outcomes[i] + j) = result;
  65
  66                 printf("%d ", *(outcomes[i] + j));
  67
  68         }
  69         printf("\n");
  70         }
  71
  72         /* find the ai's min move and the human's max move for each row/col */
  73         for (i=1; i<=BOARD_MAX; i++)
  74         for (j=1; j<=BOARD_MAX; j++) {
  75                 ai_min[i] = human_max[j] = 0;
  76                 ai_min[i] = (*(outcomes[i] + j) < ai_min[i])
  77                                 ? *(outcomes[i] + j) : ai_min[i];
  78                 human_max[j] = (*(outcomes[j] + i) > human_max[j])
  79                                 ? *(outcomes[j] + i) : human_max[j];
  80                 printf("A @ %d: %d; H @ %d: %d\n", i, ai_min[i], j,
  81                         human_max[j]);
  82         }
  83
  84         /* free the calloc()s!  free the calloc()s! */
  85         for (i=0; i<=BOARD_MAX; i++)
  86                 free(outcomes[i]);
  87
  88         return bestmove;
  89
  90 }
  91
  92 /*   End ai-ultimate.c   */