MiniMax Algorithm in Game Theory and C implementation

The Minimax Algorithm and it's implementation in C programming

Let us assign the following values for the game: 1 for win by X, 0 for draw, -1 for loss by X.
Given the values of the terminal nodes (win for X (1), loss for X (-1), or draw (0)), the values of the non-terminal nodes are computed as follows:

        1.   the value of a node where it is the turn of player X to move is the maximum of the values of                 its  successors (because X tries to maximize its outcome);

        2.   the value of a node where it is the turn of player O to move is the minimum of the values of                its successors (because O tries to minimize the outcome of X).

Figure below shows how the values of the nodes of the search tree are computed from the values of the leaves of the tree. The values of the leaves of the tree are given by the rules of the game.
         

               if there are three X in a row, column or diagonal

An Example:

    Consider the following game tree (drawn from the point of view of the Maximizing player): 

Show what moves should be chosen by the two players, assuming that both are using the

mini-max procedure.

Solution:

Implementing The minimax Algorithm in c progaram.

// A simple C program to find 

// maximum score that 

// maximizing player can get. 

#include<stdio.h>

#include<string.h>

#include<stdbool.h>  

#include<math.h> 

#define min(a,b) (((a)<(b))?(a):(b))

#define max(a,b) (((a)>(b))?(a):(b))

// depth is current depth in game tree. 

// nodeIndex is index of current node in scores[]. 

// isMax is true if current move is 

// of maximizer, else false 

// scores[] stores leaves of Game tree. 

// h is maximum height of Game tree 

int minimax(int depth, int nodeIndex, bool isMax, 

            int scores[], int h) 

{ 

    // Terminating condition. i.e 

    // leaf node is reached 

    if (depth == h) 

        return scores[nodeIndex]; 

  

    //  If current move is maximizer, 

    // find the maximum attainable 

    // value 

    if (isMax) 

       return max(minimax(depth+1, nodeIndex*2, false, scores, h), 

            minimax(depth+1, nodeIndex*2 + 1, false, scores, h)); 

  

    // Else (If current move is Minimizer), find the minimum 

    // attainable value 

    else

        return min(minimax(depth+1, nodeIndex*2, true, scores, h), 

            minimax(depth+1, nodeIndex*2 + 1, true, scores, h)); 

} 

  

int main() 

{ 

    // The number of elements in scores must be 

    // a power of 2. 

    int scores[16];

    printf("Enter no of leaf nodes   :");

    int x;

    scanf("%d",&x);

    int i;

    printf("\nENter terminal utility\n");

    for(i=0;i<x;i++)

    

    {   

    printf("Utility %d    :" ,i);

    scanf("%d",&scores[i]);

    printf("\n");

}

    

    // x = sizeof(scores)/sizeof(scores[0]); 

    int h = log10(x)/log10(2); 

    int res = minimax(0, 0, true, scores, h); 

    printf("The optimal value is :%d", res);

    return 0; 

}

DOWNLOAD C-program

Lets take an example:

Executing the program the output will be