틱택토 AI - minimax

#include <iostream>
#include <vector>
 
 
using namespace std;
 
// 말을 놓았는지 안놓았는지 상황을 알려주는 enum 클래스
enum class Pawn
{
    None,
    O,
    X
};
 
// Game 클래스 선언
class Game
{
 
public:
    Game()    // Game 생성자 선언
        : m_turn(Pawn::None)    // m_turn이라는 private한 배열 initialize - None으로 initialize
                            // 처음에 선언되었을때는 무조건 None으로 시작한다. m_turn은 말의 종류를 의미함
    {
        for (int y = 0; y < 3; ++y)
        {
            for (int x = 0; x < 3; ++x)
            {
                m_board[y][x] = Pawn::None;    // 모든 3*3 배열에 None이라는 말을 채운다
            }
        }
    }
 
 
public:
    void move(int x, int y)    // Move라는 함수 선언
    {
        m_board[y][x] = m_turn;    //m_turn값을 대입한다.
 
        if (m_turn == Pawn::O)
        {
            m_turn = Pawn::X;    // 말의 순서를 전환해준다
        }
        else
        {
            m_turn = Pawn::O;    //마찬가지. 말의 순서 전환.
        }
    }
 
    bool canMove(int x, int y) const
    {
        return (m_board[y][x] == Pawn::None);    //말을 놓을 수 있는지 확인한다. None으로 채워진 경우에 가능.
    }
 
    Pawn turn() const
    {
        return m_turn;    //turn을 반환한다. 누구 turn인가?
    }
 
    bool isFull() const
    {
        for (int y = 0; y < 3; ++y)
        {
            for (int x = 0; x < 3; ++x)
            {
                if (m_board[y][x] == Pawn::None)    //단 하나라도 None이 보일 경우, Full이 아니다. False 반환
                {
                    return false;
                }
            }
        }
 
        return true;
    }
 
    Pawn whoWin() const
    {
        for (int i = 0; i < 3; ++i)    //행 기준
        {
            if (m_board[i][0] == m_board[i][1] && m_board[i][1] == m_board[i][2])    //가로 1줄
            {
                return m_board[i][0];    //이긴 player 상태를 반환한다
            }
 
            if (m_board[0][i] == m_board[1][i] && m_board[1][i] == m_board[2][i])    // 세로 1줄
            {
                return m_board[0][i];    //이긴 player 상태를 반환한다
            }
        }
 
        if (m_board[0][0] == m_board[1][1] && m_board[1][1] == m_board[2][2])
        {
            return m_board[0][0];    // 우하향 대각선 체크
        }
 
        if (m_board[2][0] == m_board[1][1] && m_board[1][1] == m_board[0][2])
        {
            return m_board[2][0];    //우상향 대각선 체크
        }
 
        return Pawn::None;    //승자가 없을 경우, None 리턴
    }
 
    void autoAI()
    {
        minimax(0);    //minmax 알고리즘을 이용한 컴퓨터 다음 수 확인
    }
 
 
public:    //화면 출력
    void print() const
    {
        cout << "-----" << endl;
 
        for (int y = 0; y < 3; ++y)
        {
            for (int x = 0; x < 3; ++x)
            {
                switch (m_board[y][x])    //출력하기 위한 스위치문
                {
                case Pawn::O:
                    cout << "O";
                    break;
 
                case Pawn::X:
                    cout << "X";
                    break;
 
                default:
                    cout << " ";
                    break;
                }
            }
 
            cout << endl;
        }
 
        cout << "-----" << endl;
    }
 
 
private:
    Pawn m_board[3][3];    // 말을 담기 위한 배열
    Pawn m_turn;    // 말의 종류
 
 
private:    //핵심 알고리즘 - minimax 알고리즘
    int minimax(int depth)
    {
        Pawn winner = whoWin();    //재귀 함수로 처리할 것이므로, 탈출 조건을 설정하기 위한 장치
 
        if (winner == Pawn::O)    // 승자가 정해지면 return 한다
        {
            return depth - 10;    // O 는 사용자. 더 작은 값이 나올수록 AI에겐 유리하므로, depth를 더해준다
                                // 그래야 깊은 탐색을 하기 전에 탐색을 그만둘 수 있다. depth가 작을수록 유리함
        }
        else if (winner == Pawn::X)
        {
            return 10 - depth;    // X 는 AI. 더 큰 값이 나올수록 AI에게 유리하므로, depth를 빼준다
                                // 그래야 깊은 탐색을 하기 전에 탐색을 그만둘 수 있다. depth가 작을수록 유리함
        }
        else if (isFull())
        {
            return 0;
        }
 
 
        int maxScore = -10000000;    //매 턴마다 Max값을 갱신해준다 - 각 단계별로 필요함
        int maxX = -1, maxY = -1;    // Max값을 가질 때의 좌표를 기억해주기 위함
 
        int minScore = 10000000;    // 매 턴마다 min값을 갱신해준다 - 각 단계별로 필요
        int minX = -1, minY = -1;    // min값을 가질 때 좌표를 기억해주기 위함.
 
 
        // 가장 중요한 파트 -> DFS 방식을 이용한듯
        for (int y = 0; y < 3; ++y)
        {
            for (int x = 0; x < 3; ++x)    //원칙적으로는, 모든 칸들에 대한 탐색을 다 해줘야 한다.
            {                            // 일종의 for문 + 재귀호출 버전.
                if (canMove(x, y))    // 해당 칸이 비어있을 경우
                {
                    Game newGame = *this;    // 가장 최근의 말을 저장한 뒤 newGame이라는 새로운 객체에 전달함
                    newGame.move(x, y);    // newGame이라는 객체 안에 (x,y)의 말을 추가한다.
 
                    int score = newGame.minimax(depth + 1);    //재귀함수 호출. 가장 중요한 부분. depth를 증가시킨 뒤 수행
                                                            // 클래스 선언을 하지 않을 시, 여러 함수들 각각에 파라미터를 
                                                            // 계속해서 넣어줘야 하는데, 번거롭다!! 어쩔 수 없이 클래스가 최선!!
                    if (score > maxScore)    // maxScore를 갱신해준다
                    {
                        maxScore = score;
                        maxX = x;
                        maxY = y;    // max일때의 X,Y값도 갱신해준다
                    }
 
                    if (score < minScore)    // minScore를 갱신해준다
                    {
                        minScore = score;
                        minX = x;
                        minY = y;    // min일때의 X,Y값도 갱신해준다
                    }
                }
            }
        }
 
 
        if (turn() == Pawn::X)    // 해당 턴이 X일 경우, Max 방향으로 이동 + maxScore 출력
        {
            move(maxX, maxY);
            return maxScore;
        }
        else      // 해당 턴이 X일 경우, min 방향으로 이동 + minScore 출력
        {
            move(minX, minY);
            return minScore;
        }
 
 
        return 0;
    }
};
 
 
int main()
{
    Game game;    // Game을 선언한다
 
    while (game.isFull() == false)    //모든 칸이 다 채워지기 전까지, Game을 계속 실행한다
    {
        game.print();    //출력 먼저하기
 
 
        int x = 0, y = 0;
        cin >> x >> y;    //입력을 받는다
 
        if (game.canMove(x, y))    //비어있는 칸이라면, 다음을 수행한다
        {
            game.move(x, y);    // 움직인다  - 내 턴
 
            game.autoAI();    // 움직인다 - 컴퓨터 턴
 
            Pawn winner = game.whoWin();    //누가 이겼는가 - 이긴 사람이 없을경우, None으로 채워짐
            if (winner == Pawn::O)    //O 플레이어가 이겼을때 : Win
            {
                cout << "Win!" << endl;
                break;
            }
            else if (winner == Pawn::X)    //X 플레이어가 이겼을때 : Lose
            {
                cout << "Lose!" << endl;
                break;
            }
        }
    }
 
    cout << "Game Over!" << endl;    // 게임오버!
 
    return 0;
}