minimax, alpha-beta pruning

minimax, alpha-beta pruning

 

알고리즘 공부하면서 만들어봤던 tic tac toe 입니다.

 

 

// tic tac toe sample (minimax, alpha-beta pruning)

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;


//#define TEST_MODE


// 0: 빈자리, 1:user, 2:computer
int board[9] = {0,};
// 화면에 출력할 문자
char shape[3] = {'*','O','X'};
// 컴퓨터가 놓은 수(배열 인덱스)
int target_index;
// 순서에 대한 인덱스
int sequence_index = 0;

#ifdef TEST_MODE
// 로그
int log[9] = {0,};
// 경우의 수
int numberOfCases = 0;
#endif//TEST_MODE


bool isFull();
int checkVictory(int index);
void printBoard();
#ifdef TEST_MODE
int minimax(bool flag, int index, int depth=1, int* log=nullptr);
#else
int minimax(bool flag, int index);
#endif//TEST_MODE
int alphaBetaPruning(bool flag, int* score);


#ifdef TEST_MODE
int fact_recursion(int n)
{
    if(n <= 1)
        return 1;
    else
        return n * fact_recursion(n-1);
}
#endif//TEST_MODE


// 놓을 곳이 있다면 0, 없다면 1을 리턴.
bool isFull()// Board is full
{
    for(int i=0; i<9; ++i ) {
        if (board[i] == 0) {
            return false;
        }
    }
    return true;
}

// 승리했을 경우 1, 그렇지 않으면 0 리턴
int checkVictory(int index)
{
//     0 1 2
//     3 4 5
//     6 7 8

    int x = index % 3;
    int y = index / 3;
    int r = board[y*3+x];
    
    // 가로
    if (board[y*3+0]==r && board[y*3+1]==r && board[y*3+2]==r)  return r;

    // 세로
    if (board[0*3+x]==r && board[1*3+x]==r && board[2*3+x]==r)  return r;

    // 대각선
    // 0,4,8 : 가로,세로,대각선\
    // 2,4,6 : 가로,세로,대각선/
    if(0 == index%4 && (board[0]==r && board[4]==r && board[8]==r))   return r;   /* 대각선 \ */
    if(0 == index%2 && (board[2]==r && board[4]==r && board[6]==r))   return r;   /* 대각선 / */
    
    return 0;
}

// 보드 상태 출력
void printBoard()
{
    cout<<endl;
    cout<<shape[board[0]]<<"|"<<shape[board[1]]<<"|"<<shape[board[2]]<<endl;
    cout<<"-----"<<endl;
    cout<<shape[board[3]]<<"|"<<shape[board[4]]<<"|"<<shape[board[5]]<<endl;
    cout<<"-----"<<endl;
    cout<<shape[board[6]]<<"|"<<shape[board[7]]<<"|"<<shape[board[8]]<<endl;
}


// 유저 수 두기
int doPlayer()
{
    int move;
    do {
        cout<<endl<<"Enter the move(0-8):";
        cin>>move;
    } while(move < 0 || move >= 9 || 0 != board[move]);
    
    
    // 순서 인덱스 증가
    sequence_index += 1;
    board[move] = 1;
    printBoard();
    
    
#ifdef TEST_MODE
    // 경우의 수 초기화
    numberOfCases = 0;
    
    // 로그 기록
    memset(&log[0], 0, sizeof(log));
    log[0] = move;
    
    cout<<endl<<sequence_index << "+ 유저의 선택 :" << move << endl;
#endif//TEST_MODE
    
    
    if (1 == checkVictory(move)) {
        cout<<endl<<"You Won......"<<endl<<endl;
        return 1;
    }
    
    if(true == isFull()) {
        cout<<endl<<"Draw...."<<endl<<endl;
        return 2;
    }
    
    return 0;
}

// 컴퓨터 수 두기
int doComputer() {
    
    cout<<endl<<"Computer Thinking..."<<endl;
    
    if (0 == sequence_index) {
        // 첫번째 두는 경우는 랜덤위치에 두도록 한다.
        target_index = rand() % 9;
    } else {
#ifdef TEST_MODE
        minimax(true, target_index, 1, &log[0]);
#else
        minimax(true, target_index);
#endif//TEST_MODE
    }
    
    cout<<endl<<"CPU MOVE...."<<endl;
    sequence_index += 1; // 순서 인덱스 증가
    board[target_index] = 2;
    printBoard();
    cout<<endl<< sequence_index << " + 컴퓨터의 선택 :" << target_index << endl;
    
#ifdef TEST_MODE
    int count = 0;
    for (int i=0; i<9; ++i) {
        if (0 == board[i]) count++;
    }
    int fact = fact_recursion(count+1);
    cout<<endl<< "number of cases : " << numberOfCases << endl;
    int cutoff = fact - numberOfCases;
    float per = (float)cutoff / (float)fact * 100.0;
    cout<<"total : "<<fact << ",   cutoff : "<< cutoff << " ("<< per << " %)"<<endl;
#endif//TEST_MODE
    
    if(2 == checkVictory(target_index)) {
        cout<<"CPU WON....."<<endl<<endl;
        return 1;
    }
    
    if(true == isFull()) {
        cout<<"Draw...."<<endl<<endl;
        return 2;
    }
    return 0;
}


#ifdef TEST_MODE

void printLog(int depth, int type)
{
    for (int i=0; i<depth; ++i) {
        cout<<log[i];
        if (0 == i) {
            cout<<" -> ";
        } else {
            cout<<" ";
        }
    }
    
    if (type == 10) {// 컴퓨터 승리
        cout << "\t\t depth : "<< depth <<" com won";
    } else if (type == -10) {// 인간 승리
        cout << "\t\t depth : "<< depth <<" human won";
    } else {// 무승부
        cout << "\t\t depth : "<< depth <<" draw";
    }
    cout<<endl;
    numberOfCases ++;
}

// minimax and alpha-beta pruning 알고리즘 구현
// flag가 true일경우 컴퓨터가 둘 차례, false이면 유저 차례
int minimax(bool flag, int index, int depth, int* log)
{
    int state = checkVictory(index);
    if(2 == state) {                // 컴퓨터가 이겻을 경우 10 리턴
        printLog(depth, 10);
        return 10;
    } else if(1 == state) {         // 유저가 이겼을 경우 -10 리턴
        printLog(depth, -10);
        return -10;
    } else if(true == isFull()) {   // 더이상 둘 자리가 없을 경우 0 리턴.
        printLog(depth, 0);
        return 0;
    }
    
    
    //if score[i]=1 then it is empty
    // 스코어 값이 1이면 빈자리를 의미한다.
    int score[9] = {1,1,1,1,1,1,1,1,1};
    
    for (int i = 0; i < 9; ++i) {
        // 빈 자리가 아니라면 스킵
        if (board[i] != 0) continue;
        
        int scoreValue = 1;
        
        if(true == flag) {
            // 컴퓨터가 가상으로 둔 수
            board[i] = 2;
            // 로그 기록
            log[depth] = i;
            // 유저가 둘 차례
            scoreValue = minimax(false, i, depth+1, &log[0]);
        } else {
            // 유저가 가상으로 둔 수
            board[i] = 1;
            // 로그 기록
            log[depth] = i;
            // 컴퓨터가 둘 차례
            scoreValue = minimax(true, i, depth+1, &log[0]);
        }
        
        // 가상으로 둔 수 초기화
        board[i] = 0;
        // 가상으로 둔 수에 대한 점수 기록.
        score[i] = scoreValue;
    }
    
    
    return alphaBetaPruning(flag, &score[0]);
}

#else

// minimax and alpha-beta pruning 알고리즘 구현
// flag가 true일경우 컴퓨터가 둘 차례, false이면 유저 차례
int minimax(bool flag, int index)
{
    //int checkVictory(int index)
    int state = checkVictory(index);
    if(2 == state) {                // 컴퓨터가 이겼을 경우 10 리턴
        return 10;
    } else if(1 == state) {         // 유저가 이겼을 경우 -10 리턴
        return -10;
    } else if(true == isFull()) {   // 더이상 둘 자리가 없을 경우 0 리턴.
        return 0;
    }
    
    
    //if score[i]=1 then it is empty
    // 스코어 값이 1이면 빈자리를 의미한다.
    int score[9] = {1,1,1,1,1,1,1,1,1};
    
    for (int i = 0; i < 9; ++i) {
        // 빈 자리가 아니라면 스킵
        if (board[i] != 0) continue;
        
        int scoreValue = 1;

        if(true == flag) {
            // 컴퓨터가 가상으로 둔 수
            board[i] = 2;
            // 유저가 둘 차례
            scoreValue = minimax(false, i);
        } else {
            // 유저가 가상으로 둔 수
            board[i] = 1;
            // 컴퓨터가 둘 차례
            scoreValue = minimax(true, i);
        }
        
        // 가상으로 둔 수 초기화
        board[i] = 0;
        // 가상으로 둔 수에 대한 점수 기록.
        score[i] = scoreValue;
    }
    
    return alphaBetaPruning(flag, &score[0]);
}
#endif//TEST_MODE


int alphaBetaPruning(bool flag, int* score)
{
    if (true == flag) {
        int maxValue = -1000;
        for (int j=0; j<9; ++j) {
            if(score[j] > maxValue && score[j] != 1) {
                maxValue = score[j];
                target_index = j;
            }
        }
        return maxValue;
    } else {
        int minValue = 1000;
        for(int j=0; j<9; ++j) {
            if(score[j] < minValue && score[j] != 1) {
                minValue = score[j];
                target_index = j;
            }
        }
        return minValue;
    }
}


int main(int argc, const char * argv[]) {

    srand((unsigned)time(0));
    
    cout<<"---------- TIC TAC TOE ----------";
    cout<<endl<<"Human : O,  Com : X";
    cout<<endl<<"Human first(1),  Com first(2) : ";
    int selectFirst;
    cin>>selectFirst;
    
    if(1 == selectFirst) {
        doPlayer();
    }
    
    while( true ) {
        if (doComputer() > 0) break;
        if (doPlayer() > 0) break;
    }
    
    return 0;
}

 

2020/05/19 - [AI/Algorithm] - minimax full search example

2020/05/19 - [iOS/Tips] - Bitbucket Carthage 사용

2020/05/19 - [iOS/Jailbreak] - Fridump 사용법 (3/3) - 메모리 덤프

2020/05/19 - [iOS/Jailbreak] - Fridump 사용법 (2/3) - Mac OS X 환경 구축

2020/05/19 - [iOS/Jailbreak] - Fridump 사용법 (1/3) - iOS디바이스 환경 구축

2020/05/19 - [iOS/Jailbreak] - Fridump, Tcpdump, OpenSSL Quick Guide

2020/05/19 - [OS/Mac OS X] - gdb 사용

2020/05/19 - [iOS/Jailbreak] - Frida 설치 및 사용법

2020/05/19 - [OS/Mac OS X] - gdb 설치

2020/05/19 - [OS/Mac OS X] - Mac에서 Node.js 설치

2020/05/19 - [iOS/Jailbreak] - Tcpdump 사용법

2020/05/19 - [개발노트] - UUID의 구성 요소

2020/05/18 - [iOS/Tips] - APNs

2020/05/18 - [iOS/Swift] - Multiple font colors in a single UILabel