//
//  main.cpp
//  Tic-Tac-Toe
//
//  Created by mac on 2017/4/2.
//  Copyright ? 2017年 mac. All rights reserved.
//

#include <iostream>
#include <vector>
#include <math.h>
#include <cctype>

using namespace::std;
vector<vector <int> > board(4 ,vector<int>(4,0));
vector<vector <int> > boardvalues(4 ,vector<int>(4,0));
int seatchDepth = 6;
bool isCutoffOccured = false;
int maxDepthReached = 0;
int totalNodesGenerated = 0;
int pruningMax = 0;
int pruningMin = 0;
bool drawGame = false;
int winner = -1;
int alpha =-1000;
int beta = 1000;
struct Move{
    int i;
    int j;
    int value;
};
Move MaxValue(vector<vector <int> > board,int alpha,int beta,int depth);
Move MinValue(vector<vector <int> > board,int alpha,int beta,int depth);

//calculaye 3 pieces in a line
int get3PieceEval(vector<vector <int> > board){
    int PlayerScore = 0;
    int AIScore = 0;
    //row  score
    for(int i=0; i<4; i++){
        if ((board[i][0]==board[i][1])&&(board[i][0]==board[i][2]))//
        {
            if((board[i][0]==2)&&(board[i][3] == 0))
                AIScore += 6;
            if((board[i][0]==1)&&(board[i][3] == 0))
                PlayerScore += 6;
        }
        if((board[i][0]==board[i][2])&&(board[i][0]==board[i][3]))
        {
            if((board[i][0]==2)&&(board[i][1] == 0))
                AIScore += 6;
            if((board[i][0]==1)&&(board[i][1] == 0))
                PlayerScore += 6;
        }
        if((board[i][0]==board[i][1])&&(board[i][0]==board[i][3]))
        {
            if((board[i][0]==2)&&(board[i][2] ==0))
                AIScore += 6;
            if((board[i][0]==1)&&(board[i][2] ==0))
                PlayerScore += 6;
        }
        if((board[i][1]==board[i][2])&&(board[i][1]==board[i][3]))
        {
            if((board[i][1]==2)&&(board[i][0] ==0))
                AIScore += 6;
            if((board[i][1]==1)&&(board[i][0] ==0))
                PlayerScore += 6;
        }
        
    }
    //col  score
    for(int i=0; i<4; i++){
        if ((board[0][i]==board[1][i])&&(board[0][i]==board[2][i]))//
        {
            if((board[0][i]==2)&&(board[3][i] ==0))
                AIScore += 6;
            if((board[0][i]==1)&&(board[3][i] ==0))
                PlayerScore += 6;
        }
        if((board[0][i]==board[2][i])&&(board[0][i]==board[3][i]))
        {
            if((board[0][i]==2)&&(board[1][i] ==0))
                AIScore += 6;
            if((board[0][i]==1)&&(board[1][i] ==0))
                PlayerScore += 6;
        }
        if((board[0][i]==board[1][i])&&(board[0][i]==board[3][i]))
        {
            if((board[0][i]==2)&&(board[2][i] ==0))
                AIScore += 6;
            if((board[0][i]==1)&&(board[2][i] ==0))
                PlayerScore += 6;
        }
        if((board[1][i]==board[2][i])&&(board[1][i]==board[3][i]))
        {
            if((board[1][i]==2)&&(board[0][i] ==0))
                AIScore += 6;
            if((board[1][i]==1)&&(board[0][i] ==0))
                PlayerScore += 6;
        }
        
    }
    //45 Diagnal  score
    {
        if((board[0][0]==board[1][1])&&(board[1][1]==board[2][2]))//
        {
            if((board[0][0]==2)&&(board[3][3] ==0))
                AIScore += 6;
            if((board[0][0]==1)&&(board[3][3] ==0))
                PlayerScore += 6;
        }
        if((board[0][0]==board[2][2])&&(board[2][2]==board[3][3]))//
        {
            if((board[0][0]==2)&&(board[1][1] ==0))
                AIScore += 6;
            if((board[0][0]==1)&&(board[1][1] ==0))
                PlayerScore += 6;
        }
        if((board[0][0]==board[1][1])&&(board[1][1]==board[3][3]))//
        {
            if((board[0][0]==2)&&(board[2][2] ==0))
                AIScore += 6;
            if((board[0][0]==1)&&(board[2][2] ==0))
                PlayerScore += 6;
        }
        if((board[1][1]==board[2][2])&&(board[2][2]==board[3][3]))//
        {
            if((board[1][1]==2)&&(board[0][0] ==0))
                AIScore += 6;
            if((board[1][1]==1)&&(board[0][0] ==0))
                PlayerScore += 6;
        }
        
    }
    //135 Diagnal  score
    {
        if((board[0][3]==board[1][2])&&(board[1][2]==board[2][1]))//
        {
            if((board[0][3]==2)&&(board[3][0] ==0))
                AIScore += 6;
            if((board[0][3]==1)&&(board[3][0] ==0))
                PlayerScore += 6;
        }
        if((board[0][3]==board[1][2])&&(board[1][2]==board[3][0]))//
        {
            if((board[0][3]==2)&&(board[2][1] ==0))
                AIScore += 6;
            if((board[0][3]==1)&&(board[2][1] ==0))
                PlayerScore += 6;
        }
        if((board[0][3]==board[2][1])&&(board[2][1]==board[3][0]))//
        {
            if((board[0][3]==2)&&(board[1][2] ==0))
                AIScore += 6;
            if((board[0][3]==1)&&(board[1][2] ==0))
                PlayerScore += 6;
        }
        if((board[1][2]==board[2][1])&&(board[2][1]==board[3][0]))//
        {
            if((board[1][2]==2)&&(board[0][3] ==0))
                AIScore += 6;
            if((board[1][2]==1)&&(board[0][3] ==0))
                PlayerScore += 6;
        }
        
    }
    //cout<<"get1PieceEval"<<AIScore-PlayerScore<<endl;
    return AIScore-PlayerScore;
   
}
//calculaye 2 pieces in a line
int get2PieceEval(vector<vector <int> > board){
    int PlayerScore = 0;
    int AIScore = 0;
    //row score
    for(int i=0; i<4; i++){
        if (board[i][0]==board[i][1])//
        {
            if((board[i][0]==2)&&(board[i][3]==0)&&(board[i][2]==0))
                AIScore += 3;
            if((board[i][0]==1)&&(board[i][3]==0)&&(board[i][2]==0))
                PlayerScore += 3;
        }
        if(board[i][0]==board[i][2])
        {
            if((board[i][0]==2)&&(board[i][1]==0)&&(board[i][3]==0))
                AIScore += 3;
            if((board[i][0]==1)&&(board[i][1]==0)&&(board[i][3]==0))
                PlayerScore += 3;
        }
        if(board[i][0]==board[i][3])
        {
            if((board[i][0]==2)&&(board[i][1]==0)&&(board[i][2]==0))
                AIScore += 3;
            if((board[i][0]==1)&&(board[i][1]==0)&&(board[i][2]==0))
                PlayerScore += 3;
        }
        if(board[i][1]==board[i][2])
        {
            if((board[i][1]==2)&&(board[i][0]==0)&&(board[i][3]==0))
                AIScore += 3;
            if((board[i][1]==1)&&(board[i][0]==0)&&(board[i][3]==0))
                PlayerScore += 3;
        }
        if(board[i][1]==board[i][3])
        {
            if((board[i][1]==2)&&(board[i][0]==0)&&(board[i][2]==0))
                AIScore += 3;
            if((board[i][1]==1)&&(board[i][0]==0)&&(board[i][2]==0))
                PlayerScore += 3;
        }
        if(board[i][2]==board[i][3])
        {
            if((board[i][2]==2)&&(board[i][0]==0)&&(board[i][1]==0))
                AIScore += 3;
            if((board[i][2]==1)&&(board[i][0]==0)&&(board[i][1]==0))
                PlayerScore += 3;
        }

        
    }
    //col  score
    for(int i=0; i<4; i++){
        if (board[0][i]==board[1][i])//
        {
            if((board[0][i]==2)&&(board[2][i]==0)&&(board[3][i]==0))
                AIScore += 3;
            if((board[0][i]==1)&&(board[2][i]==0)&&(board[3][i]==0))
                PlayerScore += 3;
        }
        if(board[0][i]==board[2][i])
        {
            if((board[0][i]==2)&&(board[1][i]==0)&&(board[3][i]==0))
                AIScore += 3;
            if((board[0][i]==1)&&(board[1][i]==0)&&(board[3][i]==0))
                PlayerScore += 3;
        }
        if(board[0][i]==board[3][i])
        {
            if((board[0][i]==2)&&(board[1][i]==0)&&(board[2][i]==0))
                AIScore += 3;
            if((board[0][i]==1)&&(board[1][i]==0)&&(board[2][i]==0))
                PlayerScore += 3;
        }
        if(board[1][i]==board[2][i])
        {
            if((board[1][i]==2)&&(board[0][i]==0)&&(board[3][i]==0))
                AIScore += 3;
            if((board[1][i]==1)&&(board[0][i]==0)&&(board[3][i]==0))
                PlayerScore += 3;
        }
        if(board[1][i]==board[3][i])
        {
            if((board[1][i]==2)&&(board[0][i]==0)&&(board[2][i]==0))
                AIScore += 3;
            if((board[1][i]==1)&&(board[0][i]==0)&&(board[2][i]==0))
                PlayerScore += 3;
        }
        if(board[2][i]==board[3][i])
        {
            if((board[2][i]==2)&&(board[0][i]==0)&&(board[1][i]==0))
                AIScore += 3;
            if((board[2][i]==1)&&(board[0][i]==0)&&(board[1][i]==0))
                PlayerScore += 3;
        }

        
    }
    //45 Diagnal  score
    {
        if(board[0][0]==board[1][1])//
        {
            if((board[0][0]==2)&&(board[2][2]==0)&&(board[3][3]==0))
                AIScore += 3;
            if((board[0][0]==1)&&(board[2][2]==0)&&(board[3][3]==0))
                PlayerScore += 3;
        }
        if(board[0][0]==board[2][2])//
        {
            if((board[0][0]==2)&&(board[1][1]==0)&&(board[3][3]==0))
                AIScore += 3;
            if((board[0][0]==1)&&(board[1][1]==0)&&(board[3][3]==0))
                PlayerScore += 3;
        }
        if(board[0][0]==board[3][3])//
        {
            if((board[0][0]==2)&&(board[1][1]==0)&&(board[2][2]==0))
                AIScore += 3;
            if((board[0][0]==1)&&(board[1][1]==0)&&(board[2][2]==0))
                PlayerScore += 3;
        }
        if(board[1][1]==board[2][2])//
        {
            if((board[1][1]==2)&&(board[0][0]==0)&&(board[3][3]==0))
                AIScore += 3;
            if((board[1][1]==1)&&(board[0][0]==0)&&(board[3][3]==0))
                PlayerScore += 3;
        }
        if(board[1][1]==board[3][3])//
        {
            if((board[1][1]==2)&&(board[0][0]==0)&&(board[2][2]==0))
                AIScore += 3;
            if((board[1][1]==1)&&(board[0][0]==0)&&(board[2][2]==0))
                PlayerScore += 3;
        }
        if(board[2][2]==board[3][3])//
        {
            if((board[2][2]==2)&&(board[0][0]==0)&&(board[1][1]==0))
                AIScore += 3;
            if((board[2][2]==1)&&(board[0][0]==0)&&(board[1][1]==0))
                PlayerScore += 3;
        }
        
    }
    //135 Diagnal  score
    {
        if(board[0][3]==board[1][2])//
        {
            if((board[0][3]==2)&&(board[2][1]==0)&&(board[3][0]==0))
                AIScore += 3;
            if((board[0][3]==1)&&(board[2][1]==0)&&(board[3][0]==0))
                PlayerScore += 3;
        }
        if(board[0][3]==board[2][1])//
        {
            if((board[0][3]==2)&&(board[1][2]==0)&&(board[3][0]==0))
                AIScore += 3;
            if((board[0][3]==1)&&(board[1][2]==0)&&(board[3][0]==0))
                PlayerScore += 3;
        }
        if(board[0][3]==board[3][0])//
        {
            if((board[0][3]==2)&&(board[1][2]==0)&&(board[2][1]==0))
                AIScore += 3;
            if((board[0][3]==1)&&(board[1][2]==0)&&(board[2][1]==0))
                PlayerScore += 3;
        }
        if(board[1][2]==board[2][1])//
        {
            if((board[1][2]==2)&&(board[0][3]==0)&&(board[3][0]==0))
                AIScore += 3;
            if((board[1][2]==1)&&(board[0][3]==0)&&(board[3][0]==0))
                PlayerScore += 3;
        }
        if(board[1][2]==board[3][0])//
        {
            if((board[1][2]==2)&&(board[0][3]==0)&&(board[2][1]==0))
                AIScore += 3;
            if((board[1][2]==1)&&(board[0][3]==0)&&(board[2][1]==0))
                PlayerScore += 3;
        }
        if(board[2][1]==board[3][0])//
        {
            if((board[1][2]==2)&&(board[0][3]==0)&&(board[1][2]==0))
                AIScore += 3;
            if((board[1][2]==1)&&(board[0][3]==0)&&(board[1][2]==0))
                PlayerScore += 3;
        }
        
    }
    //cout<<"get1PieceEval"<<AIScore-PlayerScore<<endl;
    return AIScore-PlayerScore;
}
//calculaye 1 piece score in a line
int get1PieceEval(vector<vector <int> > board){
    int PlayerScore = 0;
    int AIScore = 0;
     for(int i=0; i<4; i++){
         if (board[i][1]==0 && board[i][2]==0 && board[i][3]==0 )//
         {
             if(board[i][0]==1){
                 PlayerScore++;
                 //cout<<"player add score row at"<<i<<" 0"<<endl;
             }
             if(board[i][0]==2){
                 AIScore++;
                 //cout<<"AI add score row at"<<i<<" 0"<<endl;
             }
         }
         if (board[i][0]==0 && board[i][2]==0 && board[i][3]==0 )//
         {
             if(board[i][1]==1){
                 PlayerScore++;
                 //cout<<"player add score at"<<i<<" 1"<<endl;
             }
             if(board[i][1]==2){
                 AIScore++;
                 //cout<<"AI add score row at"<<i<<" 1"<<endl;
             }
         }
         if (board[i][0]==0 && board[i][1]==0 && board[i][2]==0 )//
         {
             if(board[i][3]==1){
                 PlayerScore++;
                 //cout<<"player add score at"<<i<<" 2"<<endl;
             }
             if(board[i][3]==2){
                 AIScore++;
                 //cout<<"AI add score row at"<<i<<" 2"<<endl;
             }
         }
         if (board[i][0]==0 && board[i][1]==0 && board[i][3]==0 )//
         {
             if(board[i][2]==1){
                 PlayerScore++;
                 //cout<<"player add score at"<<i<<" 3"<<endl;
             }
             if(board[i][2]==2){
                 AIScore++;
                 //cout<<"AI add score row at"<<i<<" 3"<<endl;
             }
         }
     }
    
     for(int i=0; i<4; i++){
        if (board[1][i]==0 && board[2][i]==0 && board[3][i]==0 )//
        {
            if(board[0][i]==1){
                PlayerScore++;
                //cout<<"player add score col at"<<"0 "<<i<<endl;
            }
            if(board[0][i]==2){
                AIScore++;
                //cout<<"AI add score col at"<<"0 "<<i<<endl;
            }
        }
        if (board[0][i]==0 && board[2][i]==0 && board[3][i]==0 )//
        {
            if(board[1][i]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"1 "<<i<<endl;
            }
            if(board[1][i]==2){
                AIScore++;
                //cout<<"AI add score col at"<<"1 "<<i<<endl;
            }
        }
        if (board[0][i]==0 && board[1][i]==0 && board[2][i]==0 )//
        {
            if(board[3][i]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"3 "<<i<<endl;
            }
            if(board[3][i]==2){
                AIScore++;
                //cout<<"AI add score col at"<<"3 "<<i<<endl;
            }
        }
        if (board[0][i]==0 && board[1][i]==0 && board[3][i]==0 )//
        {
            if(board[2][i]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"2 "<<i<<endl;
            }
            if(board[2][i]==2){
                AIScore++;
                //cout<<"AI add score col at"<<"2 "<<i<<endl;
            }
        }
    }
    //diagnal 45
    {
        if (board[0][0]==0 && board[1][1]==0 && board[2][2]==0 )//
        {
            if(board[3][3]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"3 "<<"3"<<endl;
            }
            if(board[3][3]==2){
                AIScore++;
                //cout<<"AI add score 45 at"<<"3 "<<"3"<<endl;
            }
        }
        if (board[0][0]==0 && board[2][2]==0 && board[3][3]==0 )//
        {
            if(board[1][1]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"1 "<<"1"<<endl;

            }
            if(board[1][1]==2){
                AIScore++;
                //cout<<"AI add score 45 at"<<"1 "<<"1"<<endl;
            }
        }
        if (board[0][0]==0 && board[1][1]==0 && board[3][3]==0 )//
        {
            if(board[2][2]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"2 "<<"2"<<endl;

            }
            if(board[2][2]==2){
                AIScore++;
                //cout<<"AI add score 45 at"<<"2 "<<"2"<<endl;
            }
        }
        if (board[1][1]==0 && board[2][2]==0 && board[3][3]==0 )//
        {
            if(board[0][0]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"0 "<<"0"<<endl;

            }
            if(board[0][0]==2){
                AIScore++;
                //cout<<"AI add score 45 at"<<"0 "<<"0"<<endl;
            }
        }
 
    }
    
    {
        if (board[0][3]==0 && board[1][2]==0 && board[2][1]==0 )//
        {
            if(board[3][0]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"3 "<<"0"<<endl;

            }
            if(board[3][0]==2){
                AIScore++;
                //cout<<"AI add score 135 at"<<"3 "<<"0"<<endl;
            }
        }
        if (board[0][3]==0 && board[1][2]==0 && board[3][0]==0 )//
        {
            if(board[2][1]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"2 "<<"1"<<endl;

            }
            if(board[2][1]==2){
                AIScore++;
                //cout<<"AI add score 135 at"<<"2 "<<"1"<<endl;
            }
        }
        if (board[0][3]==0 && board[2][1]==0 && board[3][0]==0 )//
        {
            if(board[1][2]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"1 "<<"2"<<endl;

            }
            if(board[1][2]==2){
                AIScore++;
                //cout<<"AI add score 135 at"<<"1 "<<"2"<<endl;
            }
        }
        if (board[1][2]==0 && board[2][1]==0 && board[3][0]==0 )//
        {
            if(board[0][3]==1){
                PlayerScore++;
                //cout<<"player add score at"<<"0 "<<"3"<<endl;

            }
            if(board[0][3]==2){
                AIScore++;
                //cout<<"AI add score 135 at"<<"0 "<<"3"<<endl;
            }
        }
   
    }
     //cout<<"get1PieceEval"<<AIScore-PlayerScore<<endl;
     return AIScore-PlayerScore;
}
//get evaluate score
int GetEvals(vector<vector <int> > board){
    int result = 0;
    result = get3PieceEval(board) + get2PieceEval(board) + get1PieceEval(board);
    return result;
}
//print current board
void print_board(vector<vector <int> > board){
    cout<<"-----------------"<<endl;
    for(int i = 0; i<4 ;i++){
        cout<<"|";
        for(int j = 0; j<4 ;j++){
            cout<<" "<<board[i][j]<<" ";
            cout<<"|";
        }
        cout<<endl;
        cout<<"-----------------"<<endl;
    }
}
//check if game end
bool Terminal_Test(vector<vector <int> > board){
    //row check
    for(int i=0; i<4; i++){
        if ((board[i][0]!=0)&&(board[i][0]==board[i][1])&&(board[i][1]==board[i][2])&&(board[i][2]==board[i][3]))//
        {
            winner = board[i][0];
            //cout<<"row winnner:"<<winner<<endl;
            return true;
        }
    }
    //col check
    for(int j=0; j<4; j++){
        if ((board[0][j]!=0)&&(board[0][j]==board[1][j])&&(board[1][j]==board[2][j])&&(board[2][j]==board[3][j]))//
        {
            winner = board[0][j];
            //cout<<"col winnner:"<<winner<<endl;
            return true;
        }
    }
    //diagnal check
    if((board[0][0]!=0)&&(board[0][0]==board[1][1])&&(board[1][1]==board[2][2])&&(board[2][2]==board[3][3]))//
    {
        winner = board[0][0];
        //cout<<"diagnal winnner:"<<winner<<endl;
        return true;
    }
    if((board[0][3]!=0)&&(board[0][3]==board[1][2])&&(board[1][2]==board[2][1])&&(board[2][1]==board[3][0]))//
    {
        winner = board[0][3];
        //cout<<"diagnal winnner:"<<winner<<endl;
        return true;
    }
    for(int m = 0 ;m< 4 ;m++){
        for(int n =0; n< 4; n++){
            if(board[m][n]==0){ //is there an empty position?
                winner = -1;
                return false;
            }
        }
    }
    winner = 0;
    //cout<<"full board no winner"<<endl;
    return true;;
}

Move MaxValue(vector<vector <int> > board,int alpha,int beta,int depth){
    //if game end, assigne 1000,-1000,0 to board score
    if(Terminal_Test(board))
    {
        
        Move tmpMove {-1,-1,0};
        if (winner == 0){
            //cout<<"No winner set value to 0"<<endl;
            tmpMove.value = http://www.mamicode.com/0;
            drawGame = true;
            maxDepthReached = maxDepthReached>(seatchDepth-depth) ? maxDepthReached:(seatchDepth-depth);
            return tmpMove;
        }
        else if (winner == 1){
            //cout<<"You win set value to -1000"<<endl;
            tmpMove.value = http://www.mamicode.com/-1000;
            drawGame = false;
            maxDepthReached = maxDepthReached>(seatchDepth-depth) ? maxDepthReached:(seatchDepth-depth);
            return tmpMove;
        }
        else{//winner = 2
            //cout<<"Computer win set value to 1000"<<endl;
            tmpMove.value = http://www.mamicode.com/1000;
            drawGame = false;
            maxDepthReached = maxDepthReached>(seatchDepth-depth) ? maxDepthReached:(seatchDepth-depth);
            return tmpMove;
        }
    }
    else if(depth==0)
    { //if game not end and reach search depth, get current board score
        Move tmpMove {-1,-1,0};
        tmpMove.value = GetEvals(board);
        //cout<<"eval get value: "<<tmpMove.value<<endl;
        maxDepthReached = seatchDepth;
        isCutoffOccured = true;
        return tmpMove;
    }
    else
    { //can search further
         drawGame = false;
        //cout<<"current no winner"<<endl;
        int v=-999999;
        Move nextMove = {-1,-1,v};
        int i = 0;
        int j = 0;
        int tmpi = 0;
        int tmpj = 0;
        //seach array board one by one, if position is empty, try place piece on that posistion
        for(i=0; i< 4;i++){
            for(j=0; j<4;j++){
                if(board[i][j]==0){
                    //cout<<"try Max Move: "<<i<<" "<<j<<endl;
                    totalNodesGenerated++;
                    board[i][j] = 2;
                    //print_board(board);
                    Move tmpMove = MinValue(board,alpha,beta,depth-1);
                    if(depth==seatchDepth)
                    {
                        boardvalues[i][j] = tmpMove.value;
                        //cout<<"boardvalue for"<<"i:"<<i<<" j:"<<j<<"is "<<tmpMove.value<<endl;
                    }
                   // cout<<"back to MaxValue func"<<endl;
                    board[i][j] = 0;
                    //remember the position have higher score
                    if(tmpMove.value>v)
                    {
                        tmpi = i;
                        tmpj = j;
                        //cout<<"current v is:"<<v;
                       // cout<<"value >= v set new v :"<<tmpMove.value<<" remember ij to tmpij: "<<tmpi<<" "<<tmpj<<endl;
                    }
                    v =max(tmpMove.value,v);
                    //if score >= beta, pruning happened
                    if (v>=beta){
                        nextMove.i = i;
                        nextMove.j = j;
                        nextMove.value =v;
                        //cout<<"current v is:"<<v<<" beta is:"<<beta;
                       // cout<<"v >= beta, purning happen set nextmove to ijv and return"<<endl;
                        
                        pruningMax++;
                        return nextMove;
                    }
                    //cout<<"set new alpha value from "<<myalpha;
                    //get new alpha value
                    alpha = max(alpha, v);
                   // cout<<" to "<<myalpha<<endl;
                }
            }
        }
        // loop done, set best move and score
        nextMove.i = tmpi;
        nextMove.j = tmpj;
        nextMove.value = v;
       // cout<<"set nextmove to tmpij v and return"<<endl;
        return nextMove;
    }
}

Move MinValue(vector<vector <int> > board,int alpha,int beta ,int depth){
    //if game end, assigne 1000,-1000,0 to board score
    if(Terminal_Test(board))
    {
        Move tmpMove {-1,-1,0};
        if (winner == 0){
            //cout<<"draw set value to 0"<<endl;
            tmpMove.value = http://www.mamicode.com/0;
            drawGame = true;
            maxDepthReached = maxDepthReached>(seatchDepth-depth) ? maxDepthReached:(seatchDepth-depth);
            return tmpMove;
        }
        else if (winner == 1){
            //cout<<"I win set value to -1000"<<endl;
            tmpMove.value = http://www.mamicode.com/-1000;
            drawGame = false;
            maxDepthReached = maxDepthReached>(seatchDepth-depth) ? maxDepthReached:(seatchDepth-depth);
            return tmpMove;
        }
        else{
            //cout<<"Computer win set value to 1000"<<endl;
            tmpMove.value = http://www.mamicode.com/1000;
            drawGame = false;
            maxDepthReached = maxDepthReached>(seatchDepth-depth) ? maxDepthReached:(seatchDepth-depth);
            return tmpMove;
        }
    }
    else if (depth==0)
    {//if game not end and reach search depth, get current board score
        Move tmpMove {-1,-1,0};
        tmpMove.value = GetEvals(board);
        //cout<<"eval get value: "<<tmpMove.value<<endl;
        maxDepthReached = seatchDepth;
        isCutoffOccured = true;
        return tmpMove;
    }
    else
    { //can search further
        //cout<<"current no winner"<<endl;
        int v=999999;
        Move nextMove = {-1,-1,v};
        int i = 0;
        int j = 0;
        int tmpi = 0;
        int tmpj = 0;
        //seach array board one by one, if position is empty, try place piece on that posistion
        for(i=0; i< 4;i++){
            for(j=0; j<4;j++){
                if(board[i][j]==0){
                    totalNodesGenerated++;
                    //cout<<"try Min Move: "<<i<<" "<<j<<endl;
                    board[i][j] = 1;
                    //print_board(board);
                    Move tmpMove = MaxValue(board,alpha,beta,depth-1);
                    //cout<<"back to MinValue func"<<endl;

                    board[i][j] = 0;
                    //remember the position have higher score
                    if(tmpMove.value<v)
                    {
                        tmpi = i;
                        tmpj = j;
                       // cout<<"current v is:"<<v;
                        //cout<<"value <= v set new v :"<<tmpMove.value<<" remember ij to tmpij:"<<tmpi<<" "<<tmpj<<endl;
                    }
                    v =min(tmpMove.value,v);
                    //if score >= beta, pruning happened
                    if (v<=alpha){
                        nextMove.i = i;
                        nextMove.j = j;
                        nextMove.value =v;
                       
                        pruningMin++;
                        //cout<<"current v is:"<<v<<" alpha is:"<<alpha;
                        //cout<<"v <= alpha, pruning happen set nextmove to ijv and return"<<endl;
                        return nextMove;
                    }
                    //cout<<"set new beta value from "<<mybeta;
                    //get new alpha value
                    beta = min(beta, v);
                    //cout<<" to "<<mybeta<<endl;
                }
            }
        }
        // loop done, set best move and score
        nextMove.i = tmpi;
        nextMove.j = tmpj;
        nextMove.value = v;
        //cout<<"set nextmove to tmpij v and return"<<endl;
        return nextMove;
    }
}

//start search
Move Alpha_Beta_Search(){
    Move nextmove = MaxValue(board,alpha,beta,seatchDepth);
    return nextmove;
}

//check if input valid
bool passValidMoveCheck(int row,int col)
{
    if(row>=0 && row<4 && col>=0 && col<4 && board[row][col]==0){
        return true;
    }
    else{
        return false;
    }
}

int main(int argc, const char * argv[]) {
    //board[3][0] = 1;
    //board[2][1] = 1;
    //board[0][2] = 2;
    //board[0][1] = 2;
    //print_board(board);
    cout<<"**************************************"<<endl;
    cout<<"        Welcome To Tic-Tac-Toe        "<<endl;
    cout<<"**************************************"<<endl;
    cout<<endl;
    cout<<endl;
    cout<<endl;
    int difficulty;
    
    cout<<"Please select difficulty:(1.easy 2.intermediate 3.difficult)"<<endl;
    cout<<"------------------------------------------------------------"<<endl;
    cin >> difficulty;

    bool firstMove=true;
    int firstmove=0;
    cout<<"Do you want to move first:(1.yes 2.no)"<<endl;
    cout<<"------------------------------------------------------------"<<endl;
    cin >> firstmove;
        //3 levels difficulty matches 3 search depth;
    switch (difficulty){
        case 1:
            seatchDepth = 3;
            break;
        case 2:
            seatchDepth = 5;
            break;
        case 3:
            seatchDepth = 7;
            break;

    }
    //determine if player want to move first
    switch (firstmove){
        case 1:
            firstMove = true;
            break;
        case 2:
            firstMove = false;
            break;
        
    }
    //print_board(board);
    if(firstMove){
    while(1){
        int row,col;
        cout<<"Enter your Move:(format: a b, a is row b is col)"<<endl;
        cout<<"------------------------------------------------------------"<<endl;
        cin>>row>>col;
        if(passValidMoveCheck(row,col))
            {
                cout<<"your move is row: "<<row<<" and col: "<<col<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                board[row][col] = 1;
                //print_board(board);
                if(Terminal_Test(board))
                {
                    if(winner == 1){
                        cout<< "You Win!"<<endl;
                        break;
                    }
                    else{
                        cout<< "Draw Game!"<<endl;
                        break;
                    }
                }
                Move AIMove = Alpha_Beta_Search();
                cout<<"AI move is row: "<<AIMove.i<<" and col: "<<AIMove.j<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                {
                    if(isCutoffOccured)
                        cout<<"Cutoff Occured: "<< "true"<<endl;
                    else
                        cout<<"Cutoff Occured: "<< "false"<<endl;
                    cout<<"max Depth Reached: "<< maxDepthReached<<endl;
                    cout<<"------------------------------------------------------------"<<endl;
                    cout<<"total Nodes Generated: "<< totalNodesGenerated<<endl;
                    cout<<"------------------------------------------------------------"<<endl;
                    cout<<"pruning in Max func: "<< pruningMax<<endl;
                    cout<<"------------------------------------------------------------"<<endl;
                    cout<<"pruning in Min func: "<< pruningMin<<endl;
                    cout<<"------------------------------------------------------------"<<endl;
                    cout<<"Max Search Depth: "<< seatchDepth<<endl;
                    cout<<"------------------------------------------------------------"<<endl;
                    isCutoffOccured = false;
                    maxDepthReached = 0;
                    totalNodesGenerated = 0;
                    pruningMax = 0;
                    pruningMin = 0;
                }
                
                board[AIMove.i][AIMove.j] = 2;
                print_board(board);
                //cout<<"score board is:"<<endl;
                //print_board(boardvalues);
                for(int i =0;i<4;i++){
                    for(int j=0;j<4;j++){
                        boardvalues[i][j]=0;
                    }
                }
                if(Terminal_Test(board))
                {
                    if(!drawGame){
                        cout<< "Computer Win!"<<endl;
                        break;
                    }
                    else{
                        cout<< "Draw Game!"<<endl;
                        break;
                    }
                }
                alpha = -1000;
                beta = 1000;
            }
        else{
            cout<<"illeagal input, please try again"<<endl;
            cout<<"------------------------------------------------------------"<<endl;
        }
    }
    }
    else{
        while(1)
        {
            int row,col;
            //AI move
            Move AIMove = Alpha_Beta_Search();
            cout<<"AI move is row: "<<AIMove.i<<" and col: "<<AIMove.j<<endl;
            cout<<"------------------------------------------------------------"<<endl;
            {
                if(isCutoffOccured)
                    cout<<"Cutoff Occured: "<< "true"<<endl;
                else
                    cout<<"Cutoff Occured: "<< "false"<<endl;
                cout<<"max Depth Reached: "<< maxDepthReached<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                cout<<"total Nodes Generated: "<< totalNodesGenerated<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                cout<<"pruning in Max func: "<< pruningMax<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                cout<<"pruning in Min func: "<< pruningMin<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                cout<<"Max Search Depth: "<< seatchDepth<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                isCutoffOccured = false;
                maxDepthReached = 0;
                totalNodesGenerated = 0;
                pruningMax = 0;
                pruningMin = 0;
            }
            board[AIMove.i][AIMove.j] = 2;
            print_board(board);
            if(Terminal_Test(board))
            {
                if(!drawGame){
                    cout<< "Computer Win!"<<endl;
                    break;
                }
                else{
                    cout<< "Draw Game!"<<endl;
                    break;
                }
            }
            //Player Move
            cout<<"Enter your Move:(format: a b, a is row b is col)"<<endl;
            cout<<"------------------------------------------------------------"<<endl;
            cin>>row>>col;
            while(!passValidMoveCheck(row,col))
            {
                cout<<"illeagal input, please try again"<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                cin>>row>>col;
            }
            if(passValidMoveCheck(row,col))
            {
                cout<<"your move is row: "<<row<<" and col: "<<col<<endl;
                cout<<"------------------------------------------------------------"<<endl;
                board[row][col] = 1;
                print_board(board);
                if(Terminal_Test(board))
                {
                    if(winner == 1){
                        cout<< "You Win!"<<endl;
                        break;
                    }
                    else{
                        cout<< "Draw Game!"<<endl;
                        break;
                    }
                }
                alpha = -1000;
                beta = 1000;
            }
        }
    }
    return 0;
}