GameDev

FSM     GameState;

int LARGE_INT = 1000;
int LARGE_NEGATIVE_INT = -1000;

DecisionTree::DecisionTree(){


}

//Check for win/loss/draw
int DecisionTree::EvaluateBoard(Grid GridTemp){

    //Vertical Win State
    if(GridTemp.Locations[0][0].state == GridTemp.Locations[0][1].state &&  GridTemp.Locations[0][1].state == GridTemp.Locations[0][2].state && GridTemp.Locations[0][2].state != 0 ){
        if(GridTemp.Locations[0][0].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[0][0].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations[1][0].state == GridTemp.Locations[1][1].state &&  GridTemp.Locations[1][1].state ==  GridTemp.Locations[1][2].state && GridTemp.Locations[1][2].state != 0){
        if(GridTemp.Locations[1][0].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[1][0].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations[2][0].state == GridTemp.Locations[2][1].state &&  GridTemp.Locations[2][1].state ==  GridTemp.Locations[2][2].state && GridTemp.Locations[2][2].state != 0){
        if(GridTemp.Locations[2][0].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[2][0].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    //Vertical Win State REVERSE
    if(GridTemp.Locations[0][2].state == GridTemp.Locations[0][1].state &&  GridTemp.Locations[0][1].state == GridTemp.Locations[0][0].state && GridTemp.Locations[0][1].state != 0 ){
        if(GridTemp.Locations[0][2].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[0][2].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations[1][2].state == GridTemp.Locations[1][1].state &&  GridTemp.Locations[1][1].state ==  GridTemp.Locations[1][0].state && GridTemp.Locations[1][0].state != 0){
        if(GridTemp.Locations[1][2].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[1][2].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations[2][2].state == GridTemp.Locations[2][1].state &&  GridTemp.Locations[2][1].state ==  GridTemp.Locations[2][0].state && GridTemp.Locations[2][0].state != 0){
        if(GridTemp.Locations[2][2].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[2][2].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    //Horizontal Win State
    if(GridTemp.Locations[0][0].state == GridTemp.Locations[1][0].state &&  GridTemp.Locations[1][0].state ==  GridTemp.Locations[2][0].state && GridTemp.Locations[2][0].state != 0){
        if(GridTemp.Locations[0][0].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[0][0].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations[0][1].state == GridTemp.Locations[1][1].state &&  GridTemp.Locations[1][1].state ==  GridTemp.Locations[2][1].state && GridTemp.Locations[2][1].state != 0){
        if(GridTemp.Locations[0][1].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[0][1].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations[0][2].state == GridTemp.Locations[1][2].state &&  GridTemp.Locations[1][2].state ==  GridTemp.Locations[2][2].state && GridTemp.Locations[2][2].state != 0){
        if(GridTemp.Locations[0][2].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[0][2].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    //Horizontal Win State
    if(GridTemp.Locations[2][0].state == GridTemp.Locations[1][0].state &&  GridTemp.Locations[1][0].state ==  GridTemp.Locations[0][0].state && GridTemp.Locations[0][0].state != 0){
        if(GridTemp.Locations[2][0].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[2][0].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations[2][1].state == GridTemp.Locations[1][1].state &&  GridTemp.Locations[1][1].state ==  GridTemp.Locations[0][1].state && GridTemp.Locations[0][1].state != 0){
        if(GridTemp.Locations[2][1].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[2][1].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations[2][2].state == GridTemp.Locations[1][2].state &&  GridTemp.Locations[1][2].state ==  GridTemp.Locations[0][2].state && GridTemp.Locations[0][2].state != 0){
        if(GridTemp.Locations[2][2].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[2][2].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }


    //Diagonal Win State
    if(GridTemp.Locations[0][0].state == GridTemp.Locations[1][1].state &&  GridTemp.Locations[1][1].state ==  GridTemp.Locations[2][2].state && GridTemp.Locations[2][2].state != 0){
        if(GridTemp.Locations[0][0].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[0][0].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    //Diagonal Win State reverse
    if(GridTemp.Locations[0][2].state == GridTemp.Locations[1][1].state &&  GridTemp.Locations[2][0].state ==  GridTemp.Locations[1][1].state && GridTemp.Locations[0][2].state != 0){
        if(GridTemp.Locations[0][2].state == 2){
            return LARGE_INT;
        }
        else if (GridTemp.Locations[0][2].state == 1){
            return LARGE_NEGATIVE_INT;
        }
    }

    if(GridTemp.Locations [0][0].state != 0 &&
        GridTemp.Locations[0][1].state != 0 &&
        GridTemp.Locations[0][2].state != 0 &&
        GridTemp.Locations[1][0].state != 0 &&
        GridTemp.Locations[2][0].state != 0 &&
        GridTemp.Locations[1][1].state != 0 &&
        GridTemp.Locations[2][2].state != 0 &&
        GridTemp.Locations[1][2].state != 0 &&
        GridTemp.Locations[2][1].state != 0 ){
            return 0;
    }

    return -1;

}

//Returns container of all valid moves
vector<int> DecisionTree::GetValidMoves(Grid Temp){

    //Container of valid move
    vector<int> ValidMoves;

    //Check for Empty Locations
    for(int i = 0; i != 3; i++){
        for(int j = 0; j != 3; j++){
            if(Temp.Locations[i][j].state == 0){
                ValidMoves.push_back(i);                //x Position
                ValidMoves.push_back(j);                //Y Position
            }
        }}

    return ValidMoves;
}

//Calls Min/max Functions
vector<int> DecisionTree::MiniMax(Grid Temp){

    int nBestScore = LARGE_NEGATIVE_INT;
    vector<int> nBestMoves;

    //--Get Valid Moves--//
    vector<int> nValidMoves;
    nValidMoves = GetValidMoves(Temp);

    //While ValidMoves list is not empty
    while(nValidMoves.size() > 0){

        //Set First valid move to Computers
        Temp.Locations[nValidMoves[0]][nValidMoves[1]].state = 2;

        //Call min (Which calls max) - Recursive calls
        int nScore = Min(Temp);

        //Add Best Moves
        if(nScore > nBestScore){
            nBestScore = nScore;
            nBestMoves.clear();
            nBestMoves.push_back(nValidMoves[0]);           //x Position
            nBestMoves.push_back(nValidMoves[1]);           //Y Position
        }

        //Add Best Moves
        else if( nScore == nBestScore){
            nBestMoves.push_back(nValidMoves[0]);
            nBestMoves.push_back(nValidMoves[1]);
        }

        //Reset Grid to previous state
        Temp.Locations[nValidMoves[0]][nValidMoves[1]].state = 0;
        nValidMoves.erase(nValidMoves.begin());
        nValidMoves.erase(nValidMoves.begin());

    }

    //return random move from BestMoves Container
    return nBestMoves;
}

//Checks Player One moves
int DecisionTree::Min(Grid Temp){

    //Check for win/loss/draw/continue
    int nMoveScore = EvaluateBoard(Temp);
    if(nMoveScore !=-1) {return nMoveScore;}        //Game is over

    //Winning Score
    int nBestScore = LARGE_INT;

    //Create list of valid moves
    vector<int> nValidMoves;
    nValidMoves = GetValidMoves(Temp);

    //While there are valid moves:
    while(nValidMoves.size() > 0){

        //Set First Valid move to Player, Call 'MAX'
        Temp.Locations[nValidMoves[0]][nValidMoves[1]].state = 1;
        int nScore = Max(Temp);

        if(nScore < nBestScore){
            nBestScore = nScore;
        }

        Temp.Locations[nValidMoves[0]][nValidMoves[1]].state = 0;
        nValidMoves.erase(nValidMoves.begin() + 0);
        nValidMoves.erase(nValidMoves.begin() + 0);

    }

    //return best result
    return nBestScore;
}

//Checks Player Two Moves
int DecisionTree::Max(Grid Temp){

    int nMoveScore = EvaluateBoard(Temp);
    if(nMoveScore !=-1) {return nMoveScore;}        //Game is over

    int nBestScore = LARGE_NEGATIVE_INT;

    vector<int> nValidMoves;
    nValidMoves = GetValidMoves(Temp);

    while(nValidMoves.size() > 0){
        Temp.Locations[nValidMoves[0]][nValidMoves[1]].state = 2;
        int nScore = Min(Temp);

        if(nScore > nBestScore){
            nBestScore = nScore;
        }

        Temp.Locations[nValidMoves[0]][nValidMoves[1]].state = 0;
        nValidMoves.erase(nValidMoves.begin() + 0);
        nValidMoves.erase(nValidMoves.begin() + 0);

    }

    return nBestScore;
}