[알고리즘] 동적계획법 - Tic-Tae-Toe

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

Tic-Tae-Toe

Tic-Tac-Toe게임은 두 명이 번갈아가며 O와 X를 3×3 판에 써서 같은 글자를 가로, 세로, 혹은 대각선 상에 놓이도록 하는 놀이이다. 

[ .  ][ .  ][ .  ]
[ .  ][ o ][ x ]
[ .  ][ .  ][ o ]

---

해결 전략

 

해결 전략

• 보드 만들기      :  vector<vector<char>> board
• 캐시 설정         :  int cache[19683]     (안 두거나 o이거나 x거나 3가지 경우의 수. 따라서 3^9칸 = 19683 경우의 수)
• 게임 상태 설정 :  enum { DEFAULT, WIN, DRAW, LOSE}
• 이긴 경우 확인 :  bool IsFinished
• 경기 알고리즘  :  CanWin(vector<vector<char>>& board, char turn)

[  o  ][  x  ][  .  ][  .  ][  o  ][  x  ][ 012 ][ 012 ][ 012 ]  => 3^9 = 19683

                                        27       9       3       0           3진법

                      

 

---

 

코드

 

#include <iostream>
#include <vector>
using namespace std;
 
// 0 ~ 3^9(=19683)
int HashKey(const vector<vector<char>>& board)
{
    int ret = 0;
 
    for (int y = 0; y < 3; y++)
    {
        for (int x = 0; x < 3; x++)
        {
            ret = ret * 3;
 
            if (board[y][x] == 'o')
                ret += 1;
            else if (board[y][x] == 'x')
                ret += 2;
        }
    }
 
    return ret;
}
 
vector<vector<char>> board;
int cache[19683];
 
enum
{
    DEFAULT = 2,
    WIN = 1,
    DRAW = 0,
    LOSE = -1
};
 
bool IsFinished(const vector<vector<char>>& board, char turn)
{
    // 좌우
    for (int i = 0; i < 3; i++)
        if (board[i][0] == turn && board[i][1] == turn && board[i][2] == turn)
            return true;    
    // 상하
    for (int i = 0; i < 3; i++)
        if (board[0][i] == turn && board[1][i] == turn && board[2][i] == turn)
            return true;
    // 대각선
    if (board[0][0] == turn && board[1][1] == turn && board[2][2] == turn)
        return true;
    if (board[0][2] == turn && board[1][1] == turn && board[2][0] == turn)
        return true;
 
    return false;
}
 
int CanWin(vector<vector<char>>& board, char turn)
{
    // 기저 사례
    if (IsFinished(board, 'o' + 'x' - turn))
        return LOSE;
 
    // 캐시 확인
    int key = HashKey(board);
    int& ret = cache[key];
    if (ret != DEFAULT)
        return ret;
 
    // 풀기
    int minValue = DEFAULT;
 
    for (int y = 0; y < 3; y++)
    {
        for (int x = 0; x < 3; x++)
        {
            if (board[y][x] != '.')
                continue;
 
            // 착수
            board[y][x] = turn;
 
            // 확인
            minValue = min(minValue, CanWin(board, 'o' + 'x' - turn)); // 상대방이 패배하는게 제일 좋은 케이스 
 
            // 취소
            board[y][x] = '.';
        }
    }
 
    if (minValue == DRAW || minValue == DEFAULT)
        return ret = DRAW;
 
    return ret = -minValue;
}
 
int main()
{
    board = vector<vector<char>>
    {
        {'.', '.', '.'},
        {'.', '.', '.'},
        {'.', '.', '.'}
    };
 
    for (int i = 0; i < 19683; i++)
        cache[i] = DEFAULT;
 
    int win = CanWin(board, 'o');
 
    switch (win)
    {
    case WIN:
        cout << "Win" << endl;
        break;
    case DRAW:
        cout << "Draw" << endl;
        break;
    case LOSE:
        cout << "Lose" << endl;
        break;
    }
}

 

---

 

주의사항 

 

// 1 byte
memset(cache, -2, sizeof(cache));  // 사용불가능
memset(cache, 0, sizeof(cache));   // 0 0 0 0 0000
memset(cache, -1, sizeof(cache));  // 0b111111111

chache를 설정할 때 -1, 0, 1이 아닌 값을 memset을 사용할 수 없다. memset 설정 시 1 byte로 설정해야 하기 때문에 -1, 0, 1이 아닌 값은 사용할 수 없다. 

 

 

 

---

 

마무리

마무리