Sunday, March 29, 2015

MiniMax with alpha-beta pruning

// minimax.cpp : Defines the entry point for the console application.
//

// MIT licence ... you may do whatever you want with this source code
// last updated on 2015.03.29
// version 0.1

#include <stdio.h>
#include <stdlib.h>

#define infinity 10000

//-------------------------------------------------------------------------
struct node{
 int score;         // score for leaves
 int num_children;  // number of children
 int *children;     // index of children 
};

//-------------------------------------------------------------------------
bool read_tree(node*& tree, int &num_nodes)
{
 // each node has an index.
 // root has index 0
 // the indexes of other nodes are obtained by traversing the tree level by level.

 // file structure: on each line we have information about one node:
 // node_index num_children
 // if num_children is 0 then the next value is the score of that leaf
 // if num_children > 0 then we have a list of indexes for each children

 FILE *f = fopen("tree1.txt", "r"); // full path to the input file
 if (!f)
  return false;

 fscanf(f, "%d", &num_nodes);
 tree = (node*)malloc(num_nodes * sizeof(node));

 for (int i = 0; i < num_nodes; i++){
  int node_index;
  fscanf(f, "%d", &node_index);
  fscanf(f, "%d", &tree[node_index].num_children);

  if (!tree[node_index].num_children){
   fscanf(f, "%d", &tree[node_index].score);
   tree[node_index].children = NULL;
  }
  else{
   tree[node_index].children = (int*)malloc (tree[node_index].num_children * sizeof(int));
   tree[node_index].score = 0; // it is not used anyway
   for (int j = 0; j < tree[node_index].num_children; j++)
    fscanf(f, "%d", &tree[node_index].children[j]);
  }
 }
 return true;
}
//-------------------------------------------------------------------------
int minimax_ab(node* tree, int node_index, int level, int a, int b, int *visited, int &num_visited)
{
 if (!tree[node_index].num_children){
  visited[num_visited++] = node_index;
  return tree[node_index].score;
 }
 else
  if (level % 2){// min level
   int min_score = infinity;
   visited[num_visited++] = node_index;

   for (int i = 0; i < tree[node_index].num_children; i++){
    int child_score = minimax_ab(tree, tree[node_index].children[i], level + 1, a, b, visited, num_visited);
    if (min_score > child_score)
     min_score = child_score;
    if (b > min_score)
     b = min_score;
    if (b <= a)
     break;
   }
   return min_score;
  }
  else{// max level;
   int max_score = -infinity;
   visited[num_visited++] = node_index;
   for (int i = 0; i < tree[node_index].num_children; i++){
    int child_score = minimax_ab(tree, tree[node_index].children[i], level + 1, a, b, visited, num_visited);
    if (max_score < child_score)
     max_score = child_score;
    if (a < max_score)
     a = max_score;
    if (b <= a)
     break;
   }
   return max_score;
  }
}
//-------------------------------------------------------------------------
int main(void)
{
 int num_nodes;
 node *tree;

 if (read_tree(tree, num_nodes)){

  int a = -infinity;
  int b = infinity;

  int *visited = (int*)malloc (num_nodes * sizeof(int));
  int num_visited = 0;

  int alpha = minimax_ab(tree, 0, 0, a, b, visited, num_visited);

  printf("Alpha = %d\n", alpha);

  printf("Number of visited nodes = %d\n", num_visited);
  printf("Visited nodes: ");
  for (int i = 0; i < num_visited; i++)
   printf("%d ", visited[i]);

  free(visited);
// free memory allocated by tree
  for (int i = 0; i < num_nodes; i++)
   if (tree[i].children)
     free(tree[i].children);
  free(tree);
 }
 else
  printf("Cannot read/find file!");

 printf("\n\nPress enter.");
 getchar();

 return 0;
}
//-------------------------------------------------------------------------
Example of input (from: https://en.wikipedia.org/wiki/Alpha-beta_pruning (accessed on 2015.03.22)). Just copy the lines below in a file and specify the correct location in the read_tree function:
33
0 3 1 2 3
1 2 4 5
2 2 6 7
3 2 8 9
4 2 10 11
5 1 12
6 2 13 14
7 1 15
8 1 16
9 2 17 18
10 2 19 20
11 3 21 22 23
12 1 24
13 1 25
14 2 26 27
15 1 28
16 1 29
17 2 30 31
18 1 32
19 0 5
20 0 6
21 0 7
22 0 4
23 0 5
24 0 3
25 0 6
26 0 6
27 0 9
28 0 7
29 0 5
30 0 9
31 0 8
32 0 6

No comments:

Post a Comment