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
