16 pawn with Minimax

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

#define Max 5
#define computer '*'
#define human 'o'
#define blank '-'
#define infinity (1 << 30)

char board[Max + 1][Max + 1];

int dirX[] = {0, -1, 0, 1};
int dirY[] = {-1, 0, 1, 0};
int diagDirX[] = {0, -1, -1, -1, 0, 1, 1, 1};
int diagDirY[] = {-1, -1, 0, 1, 1, 1, 0, -1};
pair <int, int> dummy = make_pair(-1, -1);

void printGameState() {
    for(int i = 0; i < Max; ++i) {
        for(int j = 0; j < Max; ++j) {
            if(j == 0) printf("%c", board[i][j]);
            else printf("%5c", board[i][j]);
        }
        printf("\n\n");
    }
}

void initializeGame() {
    memset(board, blank, sizeof board);
//    for(int i = 1; i < 2; ++i) {
//        for(int j = 0; j < Max; ++j) {
//            board[i][j] = human;
//        }
//    }
//    for(int i = Max - 1 - 1; i > 2; --i) {
//        for(int j = 0; j < Max; ++j) {
//            board[i][j] = computer;
//        }
//    }
//    board[3][2] = blank;
//    board[2][2] = computer;
//    board[3][0] = blank;

    board[1][0] = human;
    board[2][0] = computer;
    board[3][1] = computer;
    board[3][4] = computer;

    printGameState();
}

bool isEngaged(int x, int y) {
    return board[x][y] == human or board[x][y] == computer;
}

bool isValid(int x, int y) {
    return (x >= 0 and x < Max) and (y >= 0 and y < Max);
}

vector < pair<int ,int> > AvailableMove(int x, int y) {
//    printf("%d %d\n", x, y);
    vector < pair<int ,int> > cells;

    if( (x & 1 and y & 1) or (x & 1 == 0 and y & 1 == 0) ) { // i.e. (1, 1) or (2, 4)

        for(int i = 0, n = sizeof(diagDirX) / sizeof(diagDirX[0]); i < n; ++i) {
            int posX = x + diagDirX[i], posY = y + diagDirY[i];

            if(isValid(posX, posY)) {
                if(!isEngaged(posX, posY))
                    cells.push_back( make_pair(posX, posY) );
            }

            // one step ahead
            int prevX = posX, prevY = posY;
            posX += diagDirX[i], posY += diagDirY[i];
            if(isValid(posX, posY)) {
                if(isEngaged(prevX, prevY) and !isEngaged(posX, posY))
                    cells.push_back( make_pair(posX, posY) );
            }
        }
    } else {
        for(int i = 0, n = sizeof(dirX) / sizeof(dirX[0]); i < n; ++i) {
            int posX = x + dirX[i], posY = y + dirY[i];

            if(isValid(posX, posY)) {
                if(!isEngaged(posX, posY))
                    cells.push_back( make_pair(posX, posY) );
            }

            // one step ahead
            int prevX = posX, prevY = posY;
            posX += dirX[i], posY += dirY[i];
            if(isValid(posX, posY)) {
                if( isEngaged(prevX, prevY) and !isEngaged(posX, posY) )
                    cells.push_back( make_pair(posX, posY) );
            }
        }
    }
    return cells;
}

void printPossibleMoves(vector <pair <int, int> > result) {
    printf("All possible Moves:\n");
    for(vector <pair <int ,int> >:: iterator it = result.begin(); it != result.end(); ++it) {
        printf("(%d, %d)\n", (*it).first, (*it).second);
    }
}

bool isHumanWin() {
    for(int i = 0; i < Max; ++i)
        if(find(board[i], board[i] + Max, computer) != board[i] + Max)
            return false;
    return true;
}

bool isComputerWin() {
    for(int i = 0; i < Max; ++i)
        if(find(board[i], board[i] + Max, human) != board[i] + Max)
            return false;
    return true;
}

bool isTerminateState() {
    if(isHumanWin() or isComputerWin())
        return true;
    return false;
}

bool isAhead(int fromX, int fromY, int toX, int toY) {
    return abs(toX - fromX) > 1 or abs(toY - fromY) > 1;
}

pair <int, int> terminate(int fromX, int fromY, int toX, int toY, char who) {
    int disMissX, disMissY;
    disMissX = abs(toX - fromX) > 1 ? (toX + fromX) / 2 : toX;
    disMissY = abs(toY - fromY) > 1 ? (toY + fromY) / 2 : toY;
    char opposite = (who == human) ? computer : human;
    if(board[disMissX][disMissY] == opposite) {
        return make_pair(disMissX, disMissY);
    } else {
        return dummy;
    }
}

bool takeAction(int fromX, int fromY, int toX, int toY, char who) {
    board[toX][toY] = who;
    board[fromX][fromY] = blank;
    if( isAhead(fromX, fromY, toX, toY) ) {
        pair <int, int> point = terminate(fromX, fromY, toX, toY, who);
        if(point != dummy) {
            board[point.first][point.second] = blank;
            printf("state: \n");
            printGameState();
            return true;
        }
    }
    printf("state: \n");
    printGameState();
    return false;
}

void undoAction(int fromX, int fromY, int toX, int toY, char who, bool removed) {
    board[toX][toY] = blank;
    board[fromX][fromY] = who;
    char player = (who == computer) ? human : computer;
    if(removed) {
        int x = abs(toX - fromX) > 1 ? (toX + fromX) / 2 : toX;
        int y = abs(toY - fromY) > 1 ? (toY + fromY) / 2 : toY;
        board[x][y] = player;
    }
//    printf("state: \n");
//    printGameState();
}

vector < pair <int, int> > availablePawn(char who) {
    vector < pair <int, int> > ret;
    for(int i = 0; i < Max; ++i) {
        for(int j = 0; j < Max; ++j) {
            if(board[i][j] == who)
                ret.push_back( make_pair(i, j) );
        }
    }
    return ret;
}

int utilityValue() {
    if(isComputerWin()) {
        return +1;
    } else if (isHumanWin()) {
        return -1;
    }
    return 0;
}

int minValue();

int maxValue() {
    if(isTerminateState())
        return utilityValue();
    int best = -infinity, localBest;
    bool isRemoved;
    vector < pair <int, int> > availPawns = availablePawn(computer);
    for(vector < pair <int, int> >:: iterator it = availPawns.begin(); it != availPawns.end(); ++it) {
        int fromX = (*it).first, fromY = (*it).second;
        vector < pair <int, int> > allPossibleMoves = AvailableMove(fromX, fromY);
        for(vector < pair <int, int> >:: iterator i = allPossibleMoves.begin(); i != allPossibleMoves.end(); ++i) {
            int toX = (*i).first, toY = (*i).second;
            printf("Max\n");
            isRemoved = takeAction(fromX, fromY, toX, toY, computer);
            localBest = minValue();
            undoAction(fromX, fromY, toX, toY, computer, isRemoved);
            best = max(best, localBest);
        }
    }
    return best;
}


int minValue() {
//    printGameState();
    if(isTerminateState())
        return utilityValue();
    int best = +infinity, localBest;
    bool isRemoved;
    vector < pair <int, int> > availPawns = availablePawn(human);
    for(vector < pair <int, int> >:: iterator it = availPawns.begin(); it != availPawns.end(); ++it) {
        int fromX = (*it).first, fromY = (*it).second;
        vector < pair <int, int> > allPossibleMoves = AvailableMove(fromX, fromY);
        for(vector < pair <int, int> >:: iterator i = allPossibleMoves.begin(); i != allPossibleMoves.end(); ++i) {
            int toX = (*i).first, toY = (*i).second;
            printf("Min\n");
            isRemoved = takeAction(fromX, fromY, toX, toY, human);
            localBest = maxValue();
            undoAction(fromX, fromY, toX, toY, human, isRemoved);
            best = min(best, localBest);
        }
    }
    return best;
}

void miniMax() {
    int best = -infinity, localBest;
    int a, b, x, y;
    bool isRemoved;
    // pick up available computer pawns currently in board
    vector < pair <int, int> > availPawns = availablePawn(computer);
    // for each pawn
    for(vector < pair <int, int> >:: iterator it = availPawns.begin(); it != availPawns.end(); ++it) {
        int fromX = (*it).first, fromY = (*it).second;
        // available move for certain move
        vector < pair <int, int> > allPossibleMoves = AvailableMove(fromX, fromY);
        // trying each available move of certain pawn
        for(vector < pair <int, int> >:: iterator i = allPossibleMoves.begin(); i != allPossibleMoves.end(); ++i) {
            int toX = (*i).first, toY = (*i).second;
            isRemoved = takeAction(fromX, fromY, toX, toY, computer);
            localBest = minValue();
            undoAction(fromX, fromY, toX, toY, computer, isRemoved);
            if(localBest > best) {
                best = localBest;
                a = fromX, b = fromY, x = toX, y = toY;
            }
        }
    }
    takeAction(a, b, x, y, computer);
}

int main(void) {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    initializeGame();
//    startGame();
    int fromX, fromY, toX, toY;
    while(true) {
        // first, human's turn
        printf("Human's turn: x y\n");
        scanf("%d %d", &fromX, &fromY);
        bool end = false;
        while(!end) {
            vector < pair<int, int> > moves = AvailableMove(fromX, fromY);
            printPossibleMoves(moves);
            printf("Choose your move: x y\n");
            scanf("%d %d", &toX, &toY);
            //stop giving input anymore
            if(toX == -1 and toY == -1)
                break;
            //check whether taken move is valid, otherwise ask for a valid one
            while(find(moves.begin(), moves.end(), make_pair(toX, toY)) == moves.end()) {
                printf("Invalid Move!\nChoose your move: x y\n");
                scanf("%d %d", &toX, &toY);
            }
            board[toX][toY] = human;
            board[fromX][fromY] = blank;
            // one step ahead move
            if( isAhead(fromX, fromY, toX, toY) ) {
                pair <int, int> point = terminate(fromX, fromY, toX, toY, human);
                if(point != dummy) {
                    board[point.first][point.second] = blank;
                } else {
                    end = true;
                }
            } else {
                end = true;
            }
            printGameState();
            fromX = toX, fromY = toY;
        }
        if(isHumanWin()) {
            printf("Human win!\n");
            break;
        }
        // computer's turn
        printf("Computer's turn:\n");
        miniMax();
        printGameState();
        if(isComputerWin()) {
            printf("Computer win!\n");
            break;
        }
    }
    return 0;
}