[C++] MinMax algorithm with noughts and crosses game (understand min-max heuristic)

Here is an example of min-max algorithm.

The code has been taken from:
Algorithms in a Nutshell, George T. Heineman, Gary Pollice, Stanley Selkow
L’algorithme min-max – SiteDuZeros (French tutorial website)

The Code

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <time.h>

// Board game dimensions
const int BoardWidth  = 4;
const int BoardHeight = 4;
const int OccurencesToWin = 3;
const int AlgorithmDeep = 6;

// Case & Win Types
enum Case {
    Empty = 0,
    Player1,
    Player2,
    Tie,
};

#define PrintScore
//#define PrintScore(X) X

/** Count number of lines
  * This function return the number of lines that are composed
  * by at least nbOccurences
    You can test it with:
    int board[BoardHeight][BoardWidth] = { {0,0,0,0} ,
                                           {0,0,0,0} ,
                                           {0,0,0,0} ,
                                           {1,0,0,0} };
    int player1Series = 0;
    int player2Series = 0;
    countLines(board, &player1Series, &player2Series, 2);
    printf("player1Series %d, player2Series %d \n", player1Series, player2Series);
  */

void countLines(const int board[BoardHeight][BoardWidth],int* const counterPlayer1, int* const counterPlayer2,
                const int nbOccurences){
    // init variables
     *counterPlayer1 = 0;
     *counterPlayer2 = 0;

     int verticalCounter[BoardWidth];
     memset(verticalCounter, 0, BoardWidth * sizeof(int));

     int topLeftBottomRight[BoardWidth];
     memset(topLeftBottomRight, 0, BoardWidth * sizeof(int));
     int topRightBottomLeft[BoardWidth];
     memset(topRightBottomLeft, 0, BoardWidth * sizeof(int));

     int tlbrOffset = 0;
     int trblOffset = 0;

     // go on the board in the height way
     for(int idxHeight = 0 ; idxHeight < BoardHeight ; ++idxHeight){
         if(topLeftBottomRight[tlbrOffset%BoardWidth] >= nbOccurences){
             if(board[idxHeight-1][BoardWidth-1] == Player1){
                 ++(*counterPlayer1);
             }
             else if(board[idxHeight-1][BoardWidth-1] == Player2){
                ++(*counterPlayer2);
             }
         }

         if(topRightBottomLeft[(trblOffset + BoardHeight - 1)%BoardWidth] >= nbOccurences){
             if(board[idxHeight-1][0] == Player1){
                 ++(*counterPlayer1);
             }
             else if(board[idxHeight-1][0] == Player2){
                ++(*counterPlayer2);
             }
         }

        // reset diagonal count
         topLeftBottomRight[(tlbrOffset)%BoardWidth] = 1;
         topRightBottomLeft[(trblOffset + BoardHeight - 1)%BoardWidth] = 1;

         int horizontalCounter = 1;
         // Go on the width way
         for(int idxWidth = 0 ; idxWidth < BoardWidth ; ++idxWidth){
             // Horitontal line
             if(idxWidth && board[idxHeight][idxWidth-1] == board[idxHeight][idxWidth]){
                 ++horizontalCounter;
             }
             else {
                 if(horizontalCounter >= nbOccurences){
                     if(board[idxHeight][idxWidth-1] == Player1){
                         ++(*counterPlayer1);
                     }
                     else if(board[idxHeight][idxWidth-1] == Player2){
                        ++(*counterPlayer2);
                     }
                 }
                 horizontalCounter = 1;
             }
             // Vertical line
             if(idxHeight && board[idxHeight-1][idxWidth] == board[idxHeight][idxWidth]){
                 ++verticalCounter[idxWidth];
             }
             else {
                 if(verticalCounter[idxWidth] >= nbOccurences){
                     if(board[idxHeight-1][idxWidth] == Player1){
                         ++(*counterPlayer1);
                     }
                     else if(board[idxHeight-1][idxWidth] == Player2){
                         ++(*counterPlayer2);
                     }
                 }
                 verticalCounter[idxWidth] = 1;
             }
             // Top Left Bottom Right
             if(idxHeight && idxWidth && board[idxHeight-1][idxWidth-1] == board[idxHeight][idxWidth]){
                 ++topLeftBottomRight[(idxWidth + tlbrOffset)%BoardWidth];
             }
             else {
                 if(topLeftBottomRight[(idxWidth + tlbrOffset)%BoardWidth] >= nbOccurences){
                     if(board[idxHeight-1][idxWidth-1] == Player1){
                         ++(*counterPlayer1);
                     }
                     else if(board[idxHeight-1][idxWidth-1] == Player2){
                        ++(*counterPlayer2);
                     }
                 }
                 topLeftBottomRight[(idxWidth + tlbrOffset)%BoardWidth] = 1;
             }
             // Top Right Bottom Left
             if(idxHeight && idxWidth != BoardWidth -1 && board[idxHeight-1][idxWidth+1] == board[idxHeight][idxWidth]){
                 ++topRightBottomLeft[(idxWidth + trblOffset)%BoardWidth];
             }
             else {
                 if(topRightBottomLeft[(idxWidth + trblOffset)%BoardWidth] >= nbOccurences ){
                     if(board[idxHeight-1][idxWidth+1] == Player1){
                         ++(*counterPlayer1);
                     }
                     else if(board[idxHeight-1][idxWidth+1] == Player2){
                        ++(*counterPlayer2);
                     }
                 }
                 topRightBottomLeft[(idxWidth + trblOffset)%BoardWidth] = 1;
             }
         }

         if(horizontalCounter >= nbOccurences){
             if(board[idxHeight][BoardWidth-1] == Player1){
                 ++(*counterPlayer1);
             }
             else if(board[idxHeight][BoardWidth-1] == Player2){
                ++(*counterPlayer2);
             }
         }

         tlbrOffset = ((tlbrOffset - 1) + BoardWidth) % BoardWidth;
         trblOffset = (trblOffset + 1) % BoardWidth;
     }
     // Count last line
     const int heightLimit = BoardHeight - 1;

     for(int idxWidth = 0 ; idxWidth < BoardWidth ; ++idxWidth){
         if(verticalCounter[idxWidth] >= nbOccurences){
             if(board[heightLimit][idxWidth] == Player1){
                 ++(*counterPlayer1);
             }
             else if(board[heightLimit][idxWidth] == Player2){
                ++(*counterPlayer2);
             }
         }

         if(topLeftBottomRight[(1 + idxWidth + tlbrOffset)%BoardWidth] >= nbOccurences ){
             if(board[heightLimit][idxWidth] == Player1){
                ++(*counterPlayer1);
             }
             else if(board[heightLimit][idxWidth] == Player2){
                ++(*counterPlayer2);
             }
         }

         if(topRightBottomLeft[(idxWidth + trblOffset - 1 + BoardWidth)%BoardWidth] >= nbOccurences ){
             if(board[heightLimit][idxWidth] == Player1){
                ++(*counterPlayer1);
             }
             else if(board[heightLimit][idxWidth] == Player2){
                ++(*counterPlayer2);
             }
         }
     }
}

/** Is the game over (tie or one player won)
  */
Case gameIsOver(const int board[BoardHeight][BoardWidth]){
     int player1Won = 0;
     int player2Won = 0;

     countLines(board, &player1Won, &player2Won, OccurencesToWin);

     if(player1Won){
          return Player1;
     }
     else if(player2Won){
          return Player2;
     }
     else{
          //Si le jeu n'est pas fini et que personne n'a gagné, on renvoie 0
         for(int idxWidth = 0 ; idxWidth < BoardWidth ; ++idxWidth){
              for(int idxHeight = 0 ; idxHeight < BoardHeight ; ++idxHeight){
                    if(board[idxHeight][idxWidth] == Empty){
                         return Empty;
                    }
               }
          }
     }
     //Si le jeu est fini et que personne n'a gagné, on renvoie 3
     return Tie;
}

// Eval a board to give a score (to compare two board for example)
// the higher => the better for the computer
int eval(const Case me, const int board[BoardHeight][BoardWidth]){
     int casesCounterMe = 0;
     int casesCounterOther = 0;
     //Count the number of pions
     for(int idxWidth = 0 ; idxWidth < BoardWidth ; ++idxWidth){
          for(int idxHeight = 0 ; idxHeight < BoardHeight ; ++idxHeight){
               if(board[idxHeight][idxWidth] == me){
                    ++casesCounterMe;
               }
               else if(board[idxHeight][idxWidth] != Empty){
                   ++casesCounterOther;
              }
          }
     }

     const Case winner = gameIsOver(board);
     if( winner == me){
            return 1000 - casesCounterMe;
     }
     if( winner == Tie){
         return 0;
     }
     if( winner != Empty){
            return casesCounterOther - 1000;
     }

     //Small computation to eval the bord
    int player1Series = 0;
    int player2Series = 0;

    countLines(board, &player1Series, &player2Series, 2);

    if( me == Player1){
        return player1Series - player2Series;
    }
    else{
        return player2Series - player1Series;
    }
}

// Max function has to know Min
int Min(const Case me, int board[BoardHeight][BoardWidth],const int deeper);

// Max function, simulates other play
int Max(const Case me, int board[BoardHeight][BoardWidth],const int deeper){
    const Case other = (me == Player1? Player2 : Player1);
     if(deeper == 0 || gameIsOver(board) != Empty ){
          return eval(other, board);
     }

     int maxScore = INT_MIN;

     for(int idxWidth = 0 ; idxWidth < BoardWidth ; ++idxWidth){
          for(int idxHeight = 0 ; idxHeight < BoardHeight ; ++idxHeight){
                if(board[idxHeight][idxWidth] == Empty){
                      board[idxHeight][idxWidth] = other;
                      const int score = Min( me, board, deeper-1 );

                      if(score > maxScore  || ( (score == maxScore) && (rand()%2 == 0) ) ){
                            maxScore = score;
                      }
                      board[idxHeight][idxWidth] = Empty;
                }
          }
     }

     return maxScore;
}

// Min function, simulates computer play
int Min(const Case me, int board[BoardHeight][BoardWidth],const int deeper){
    if(deeper == 0 || gameIsOver(board) != Empty ){
         return eval(me, board);
    }

     int minScore = INT_MAX;

     for(int idxWidth = 0 ; idxWidth < BoardWidth ; ++idxWidth){
          for(int idxHeight = 0 ; idxHeight < BoardHeight ; ++idxHeight){
                if(board[idxHeight][idxWidth] == Empty){
                      board[idxHeight][idxWidth] = me;
                      const int score = Max(me, board, deeper-1 );

                      if(score < minScore  || ( (score == minScore) && (rand()%2 == 0) )  ){
                            minScore = score;
                      }

                      board[idxHeight][idxWidth] = Empty;
                }
          }
     }

     return minScore;

}

// Ask the computer to play
void IAPlays(const Case me, int board[BoardHeight][BoardWidth], const int deeper){
     int maxScore = INT_MIN;
     int maxWidthPosition  = -1;
     int maxHeightPosition = -1;

     //printf("Current Stat:\n");

     for(int idxHeight = 0 ; idxHeight < BoardHeight ; ++idxHeight){
        for(int idxWidth = 0 ; idxWidth < BoardWidth ; ++idxWidth){
                if(board[idxHeight][idxWidth] == Empty){

                      board[idxHeight][idxWidth] = me;
                      const int score = Min( me, board, deeper - 1 );
                      //printf("|%5d", score);

                      if(score > maxScore){
                            maxScore = score;
                            maxWidthPosition = idxWidth;
                            maxHeightPosition = idxHeight;
                      }

                      board[idxHeight][idxWidth] = Empty;
                }
                //else printf("|%5d", 0);
          }
          //printf("|\n");
     }

     board[maxHeightPosition][maxWidthPosition] = me;
}

// Print the board
void PrintBoard(const int board[BoardHeight][BoardWidth]){
    printf("Board:\n");

    for(int idxHeight = 0 ; idxHeight < BoardHeight ; ++idxHeight){
        printf("\t");
        for(int idxWidth = 0 ; idxWidth < BoardWidth ; ++idxWidth){
            switch(board[idxHeight][idxWidth]){
            case Player1: printf("|O");
            break;
            case Player2: printf("|X");
            break;
            case Empty: printf("| ");
            case Tie:;
            }
        }
        printf("|\n");
    }
}

int main(){
    int board[BoardHeight][BoardWidth];
    memset(board, Empty, sizeof(int) * BoardWidth * BoardHeight);

    srand(time(NULL));
    board[int((float(rand())/RAND_MAX)*BoardHeight)][int((float(rand())/RAND_MAX)*BoardWidth)] = Player2;
    Case currentPlayer = Player1;
    while( gameIsOver(board) == Empty ){
        IAPlays(currentPlayer, board, AlgorithmDeep);

        switch(currentPlayer){
        case Player1: currentPlayer = Player2;
        break;
        case Player2: currentPlayer = Player1;
        break;
        case Empty:;
        case Tie:;
        }

        PrintBoard(board);
    }

    switch(gameIsOver(board)){
    case Player1: printf("Player 1 wins\n");
    break;
    case Player2: printf("Player 2 wins\n");
    break;
    case Empty:;
    case Tie: printf("Tie!\n");;
    }

    return 0;
}

Output

Board:
        | | | |
        |X| |O|
        | | | |
Board:
        | |X| |
        |X| |O|
        | | | |
Board:
        |O|X| |
        |X| |O|
        | | | |
Board:
        |O|X|X|
        |X| |O|
        | | | |
Board:
        |O|X|X|
        |X| |O|
        |O| | |
Board:
        |O|X|X|
        |X| |O|
        |O| |X|
Board:
        |O|X|X|
        |X|O|O|
        |O| |X|
Board:
        |O|X|X|
        |X|O|O|
        |O|X|X|
Tie!

Board:
        |O| | | |
        | |X| | |
        | | | | |
        | | | | |
Board:
        |O| | |X|
        | |X| | |
        | | | | |
        | | | | |
Board:
        |O| | |X|
        | |X| |O|
        | | | | |
        | | | | |
Board:
        |O| | |X|
        | |X| |O|
        | | | |X|
        | | | | |
Board:
        |O| | |X|
        | |X|O|O|
        | | | |X|
        | | | | |
Board:
        |O| | |X|
        |X|X|O|O|
        | | | |X|
        | | | | |
Board:
        |O| | |X|
        |X|X|O|O|
        |O| | |X|
        | | | | |
Board:
        |O| | |X|
        |X|X|O|O|
        |O| | |X|
        |X| | | |
Board:
        |O| | |X|
        |X|X|O|O|
        |O| | |X|
        |X| | |O|
Board:
        |O|X| |X|
        |X|X|O|O|
        |O| | |X|
        |X| | |O|
Board:
        |O|X|O|X|
        |X|X|O|O|
        |O| | |X|
        |X| | |O|
Board:
        |O|X|O|X|
        |X|X|O|O|
        |O|X| |X|
        |X| | |O|
Player 2 wins