틱택토AI - AlphaBetaPrunning (미완)

#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int INF = 10000000000;
 
class point {    //point 구조체라고 보면 됨
public:    
    int x, y;
 
public:
    point() {}
 
    point(int x, int y) {
        this->x = x;
        this->y = y;
    }
};
 
class PointAndScore {    // 점수랑 포인트가 결합된 클래스. 하나의 노드라고 보면 됨
 
public:
    point p;
    int score;
 
public :
    PointAndScore() {}
 
public:
    PointAndScore(point p, int score) {
 
        this->p = p;
        this->score = score;
    }
};
 
class Board {    // 전체 클래스. 핵심 내용들 모두 들어있음
    vector<point> availPoint;    // 가능한 모든 점들을 담아놓는 벡터
    int board[4][4] = { 0 };    // 생성자같은 것 없이 바로 board 배열 호출
 
    vector<PointAndScore> rootChildScore;    // 자식 노드들의 점수와 좌푯값을 저장하는 벡터
 
    public:
    int evaluateBoard() {    // 가중치를 부여하는 함수
        int score = 0;
 
        for (int i = 1; i <= 3; i++) {    // 모든 행을 점검
            int blank = 0;
            int o = 0;
            int x = 0;
 
            for (int j = 1; j <= 3; j++) {    //각 행별로, 말의 갯수를 세서 함수로 전달
                if (board[i][j] == 0) {
                    blank++;
                }
                if (board[i][j] == 1) {
                    o++;
                }
                if (board[i][j] == 2) {
                    x++;
                }
            }
            score += weightMake(o, x);
        }
 
        for (int j = 1; j <= 3; j++) {    // 모든 열을 점검
            int blank = 0;
            int o = 0;
            int x = 0;
 
            for (int i = 1; i <= 3; i++) {    //각 열별로, 말의 갯수를 세서 함수로 전달
                if (board[i][j] == 0) {
                    blank++;
                }
                if (board[i][j] == 1) {
                    o++;
                }
                if (board[i][j] == 2) {
                    x++;
                }
            }
            score += weightMake(o, x);
        }
 
        // 모든 대각선을 점검 (1)
        int blank = 0;
        int o = 0;
        int x = 0;
        for (int i = 1; i <= 3; i++) {    // 모든 대각선을 점검
            if (board[i][i] == 0) {
                blank++;
            }
            if (board[i][i] == 1) {
                o++;
            }
            if (board[i][i] == 2) {
                x++;
            }
            score += weightMake(o, x);
        }
 
        //모든 대각선을 점검 (2)
        blank = 0;
        o = 0;
        x = 0;
        for (int i = 1; i <= 3; i++) {    // 모든 대각선을 점검
            if (board[4-i][i] == 0) {
                blank++;
            }
            if (board[4-i][i] == 1) {
                o++;
            }
            if (board[4-i][i] == 2) {
                x++;
            }
            score += weightMake(o, x);
        }
        return score;
    }
 
public:
    int weightMake(int o, int x) {
        if (x == 3) {    //컴퓨터에게 유리 (상)
            return 100;
        }
        else if (x == 2 && o == 0) {    //컴퓨터에게 유리 (중)
            return 50;
        }
        else if (x == 1 && o == 0) {    //컴퓨터에게 유리 (하)
            return 10;
        }
        else if (x == 0 && o == 1) {    // 인간에게 유리 (하)
            return -10;
        }
        else if (x == 0 && o == 2) {    // 인간에게 유리 (중)
            return -50;
        } else if (o == 3) {    //인간에게 유리
            return -100;
        }
        else {    // 모든  칸이 가득 차있으며, 결론이 지어지지 않는 경우
            return 0;
        }
    }
 
public:
    // 알파베타 적용
    int uptoDepth = -1;    //깊이 제한을 둘 때 사용한다. 그러나 여기에선 아직 깊이 제한을 두지 않음. 추후에 사용
 
public:
    int AlphaBeta(int alpha, int beta, int depth, int player) {    //알파, 베타, 깊이, 사용자 를 받는다. 재귀호출
                                                                //리턴하는 값 : 각 state에서의 가중치    
        //탈출조건 설정 (1) : 알파값이 베타값보다 클 때
        if (alpha > beta) {
            if (player == 1) {    //컴퓨터 차례인 경우, 무조건 해당 턴을 가져야 하므로 큰 수 리턴
                return INF;
            }
            if (player == 2) {    //컴퓨터 차례인 경우, 무조건 해당 턴을 가져야 하므로 작은 수 리턴
                return -INF;
            }
        }
        //탈출조건 (2) - 깊이 제한을 넘은 경우 또는 게임이 끝날 경우
        if (depth == uptoDepth || gameOver() == true) {
            return evaluateBoard();
        }
        //탈출조건 (3) - 더 이상 자식 노드가 없는 경우
        vector<point> childNode = getAvailablePoint();
 
        if (childNode.empty() == true) {
            return 0;
        }
        
        if (depth == 0)
            rootChildScore.clear();    // 깊이가 0이 되었을때, 더 이상 사용하지 않을 것이므로 초기화해준다
 
        //알고리즘 핵심부분
        int maxScore = -INF;
        int minScore = INF;    // 해당 노드에서의 최종 score값이 되는 것.
        for (int i = 0; i < childNode.size(); i++) {
            int currentScore;    //현재 노드에서의 score. 따로 저장하지 않음. 일종의 tmp
 
            if (player == 1) {//컴퓨터 턴인 경우 - 최댓값을 산출하는 게 가장 좋음 + 알파만 변한다
                move(childNode[i], 1);    //일단 말을 옮긴다
                currentScore = AlphaBeta(alpha, beta, depth + 1, 2);    //score를 처리하기 위해 무책임하게 재귀호출을 해버렸다
 
                maxScore = max(maxScore, currentScore);    // max알파값은 currentScore랑 비교해서 그때그때 갱신해줌
                alpha = max(alpha, currentScore);    // 자식노드에게 바뀐 alpha를 전달해주기 위함
 
                if (depth == 0) {    // 결국엔 여기서 선택할 것임. rootChildScore에 해당되는 여러 후보군들 중 최적의 선택을 함
                    rootChildScore.push_back(PointAndScore(childNode[i], currentScore));
                }
            }
            else {
                move(childNode[i], 2);
                currentScore = AlphaBeta(alpha, beta, depth + 1, 1);
 
                minScore = min(minScore, currentScore);
                beta = min(currentScore, beta);
 
                if (depth == 0) {    
                    rootChildScore.push_back(PointAndScore(childNode[i], currentScore));
                }
            }
            board[childNode[i].y][childNode[i].x] = 0;    //다시 원상복구시킴 (DFS의 중요한 기법)
 
            if (currentScore == INF || currentScore == -INF) {    // alpha > beta 일때, 더 이상의 childNode를 탐색하지 않음
                break;
            }
        }
 
        if (player == 1) {    //컴퓨터 차례일 때
            return maxScore;
        }
        else {    // 사용자 차례일 때
            return minScore;
        }
    }
 
    public:
    void move(point p, int player) {
        board[p.y][p.x] = player;
    }
 
    public:
    bool gameOver() {    // 게임이 끝난는지를 확인해주는 함수
        if (winMan() == true || winAI() == true || getAvailablePoint().empty() == true) {
            return true;
        }
    }
 
    public:
    bool winMan() {    //사용자가 이겼는지 확인해주는 함수
        for (int i = 1; i <= 3; i++) {    //행
            if (board[i][1] == 1 && board[i][2] == 1 && board[i][3] == 1) {
                return true;
            }
        }
        for (int i = 1; i <= 3; i++) {    //행
            if (board[1][i] == 1 && board[2][i] == 1 && board[3][i] == 1) {
                return true;
            }
        }
        if (board[1][1] == 1 && board[2][2] == 1 && board[3][3] == 1) {    //우하향 대각
            return true;
        }
        if (board[3][1] == 1 && board[2][2] == 1 && board[1][3] == 1) {    //우상향 대각
            return true;
        }
 
        return false;
    }
 
    public:
    bool winAI() {    //AI가 이겼는지 확인해주는 함수
        for (int i = 1; i <= 3; i++) {    //행
            if (board[i][1] == 2 && board[i][2] == 2 && board[i][3] == 2) {
                return true;
            }
        }
        for (int i = 1; i <= 3; i++) {    //행
            if (board[1][i] == 2 && board[2][i] == 2 && board[3][i] == 2) {
                return true;
            }
        }
        if (board[1][1] == 2 && board[2][2] == 2 && board[3][3] == 2) {    //우하향 대각
            return true;
        }
        if (board[3][1] == 2 && board[2][2] == 2 && board[1][3] == 2) {    //우상향 대각
            return true;
        }
 
        return false;
    }
 
    public:
    vector<point> getAvailablePoint() {    //가능한 모든 말들을 다 저장해서 반환하는 함수
        vector<point> availablePoint;
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                if (board[i][j] == 0) {
                    availablePoint.push_back(point(i, j));
                }
            }
        }
        return availablePoint;
    }
 
    public:
    point returnBestMove() {    //내가 찾고자 하는 가장 중요한 내용. 현재 루트의 자손들 중 가장 좋은 선택은?
        int maxN = -INF;
 
        int rstIdx;
        for (int i = 0; i < rootChildScore.size(); i++) {
            if (maxN < rootChildScore[i].score) {
                rstIdx = i;
                maxN = rootChildScore[i].score;
            }
        }
        
        return rootChildScore[rstIdx].p;
    }
 
    public:
    void takeHumanInput() {        //인간의 이동 좌표를 입력받는다
        int y, x;
        scanf("%d %d", &y, &x);
 
        move(point(x, y), 2);
    }
 
    public:
    void display() {        // 게임 화면을 출력함
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                if (board[i][j] == 1)
                    printf("X ");
                else if (board[i][j] == 2)
                    printf("O ");
                else
                    printf("  ");
            }
            printf("\n");
        }
    }
 
    public:
    void resetBoard() {        // 게임 화면을 초기화시킴
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                board[i][j] = 0;
            }
        }
    }
};
 
int main() {    //메인 함수
    Board b = Board();
 
    b.display();
 
    while (b.gameOver() == false) {
        printf("좌표를 입력하세요 : (행,렬)\n");
        b.takeHumanInput();
        b.display();
 
        if (b.gameOver() == true)
            break;
 
        b.AlphaBeta(-INF, INF, 0, 1);
        b.move(b.returnBestMove(), 1);
        b.display();
    }
 
    if (b.winMan() == true)
        printf("You Win!!\n");
    else if (b.winAI() == true)
        printf("AI Win!!\n");
    else
        printf("Draw!!\n");
}