'개발/AI,ML,ALGORITHM'에 해당되는 글 28건

'Hello World!' 라는 문장을 유전자 알고림즘으로 찾아내는 셈플이다.

#ifndef ga_hpp
#define ga_hpp

#include <stdio.h>

#pragma warning(disable:4786) // disable debug warning

#include <iostream> // for cout etc.
#include <vector> // for vector class
#include <string> // for string class
#include <algorithm> // for sort algorithm
#include <time.h> // for random seed
#include <math.h> // for abs()


extern void go();


#endif /* ga_hpp */




//
//  ga.cpp
//  ga
//
//  Created by netcanis on 9/9/16.
//  Copyright © 2016 Netcanis. All rights reserved.
//

#include "ga.hpp"


// 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384

#define TOTAL_POPULATION    2048            // 총 인구     population size
#define MAXIUM_ITERATIONS   16384           // 최대 반복수  maximum iterations
#define ELITISM_RATE        0.10f           // 엘리티즘율   elitism rate
#define MUTATION_RATE       0.25f           // 변이율      mutation rate
#define MUTATION            RAND_MAX * MUTATION_RATE    // 변이 적용 숫자 (MUTATION_RATE에 대한 rand()값)
#define GA_TARGET           std::string("Hello world!") // 타겟 문장


using namespace std; // polluting global namespace, but hey...

struct Citizen
{
    string dna; // 유전자 정보
    unsigned int fitness; // its fitness
};

typedef vector<Citizen> CitizenArray;// 간결하기 위해 for brevity



// 인구 초기화
void initPopulation(CitizenArray &population, CitizenArray &buffer)
{
    for (int i=0; i<TOTAL_POPULATION; i++) {
        Citizen citizen;
        citizen.fitness = 0;
        citizen.dna.erase();
        
        // 문자열 범위안에서 랜덤하게 기본값을 넣어준다. (타겟 사이즈만큼 넣어준다)
        for (int j=0; j<GA_TARGET.size(); j++) {
            citizen.dna += (rand() % 90) + 32;
        }
        
        population.push_back(citizen);
    }
    
    buffer.resize(TOTAL_POPULATION);
}

// 적합도 계산
void calcFitness(CitizenArray &population)
{
    string target = GA_TARGET;
    int targetSize = (int)target.size();
    
    unsigned int fitness;
    for (int i=0; i<TOTAL_POPULATION; i++) {
        fitness = 0;
        for (int j=0; j<targetSize; j++) {
            fitness += abs(int(population[i].dna[j] - target[j]));
        }
        population[i].fitness = fitness;
    }
}

// 적합도 오름차순 정렬
bool sortFitness(Citizen x, Citizen y) {
    return (x.fitness < y.fitness);
}

inline void sortByFitness(CitizenArray &population) {
    sort(population.begin(), population.end(), sortFitness);
}

// 적합도 상위 엘리트를 버퍼에 저장한다.(재사용)
void elitism(CitizenArray &population, CitizenArray &buffer, int esize)
{
    for (int i=0; i<esize; i++) {
        buffer[i].dna = population[i].dna;
        buffer[i].fitness = population[i].fitness;
    }
}

// 두 dna를 반반 랜덤하게 섞는다.
string mixdna(string dna1, string dna2)
{
    string mdna;
    mdna.resize(GA_TARGET.size());
    for (int i=0; i<GA_TARGET.size(); ++i) {
        mdna[i] = (rand() % 2 == 0) ? dna1[i] : dna2[i];
    }
    return mdna;
}

// 변이
void mutate(Citizen &citizen)
{
    // 주어진 위치의 dna를 랜덤하게 바꾼다.
    int pos = rand() % GA_TARGET.size();
    citizen.dna[pos] = (rand() % 90) + 32;
}

// 교차
void mate(CitizenArray &population, CitizenArray &buffer)
{
    // 전체 인구에서 적합도 상위 주어진 퍼센티지만큼 적용했을때 계산된 인원수
    int eSize = TOTAL_POPULATION * ELITISM_RATE;
    
    // 주어진 적합도 상위 엘리트 시민은 교차를 적용하지 않고 그대로 버퍼에 추가한다.
    elitism(population, buffer, eSize);
    
    // Mate the rest
    // 엘리트들을 제외한 너머지 시민은 교차 실행
    for (int i = eSize; i < TOTAL_POPULATION; ++i) {
        // 전체 인구중 절반 상위 시민중 한명 선택 (상위 그룹)
        int index1 = rand() % (TOTAL_POPULATION / 2);
        // 전체 인구중 절반 하위 시민중 한명 선택 (하위 그룹)
        int index2 = rand() % (TOTAL_POPULATION / 2);
        
        string dna1 = population[index1].dna;
        string dna2 = population[index2].dna;
        
        // 50%확률로 랜덤하게 섞는다.
        buffer[i].dna = mixdna(dna1, dna2);
        
        // 변이 적용 - dna인자 한개를 랜덤하게 바꾸어 준다.
        if (rand() < MUTATION) {
            mutate(buffer[i]);
        }
    }
}

// 적합도가 가장 좋은 시민의 dna를 출력해준다.
inline void print_best(CitizenArray &citizen) {
    cout << "Best: " << citizen[0].dna << "  fitness = (" << citizen[0].fitness << ")" << endl;
}

// 대치
inline void swap(CitizenArray *&population, CitizenArray *&buffer) {
    CitizenArray *temp = population; population = buffer; buffer = temp;
}


void go()
{
    srand(unsigned(time(NULL)));
    
    CitizenArray pop_alpha;
    CitizenArray pop_beta;
    
    CitizenArray *population;
    CitizenArray *buffer;
    
    initPopulation(pop_alpha, pop_beta);
    population = &pop_alpha;
    buffer = &pop_beta;
    
    for (int i=0; i<MAXIUM_ITERATIONS; i++) {
        calcFitness(*population); // calculate fitness
        sortByFitness(*population);     // sort them
        print_best(*population); // print the best one
        
        // 적합도가 100%이면 종료처리한다.
        if ((*population)[0].fitness == 0) {
            break;
        }
        
        // 교차
        mate(*population, *buffer); // mate the population together
        
        // 대치
        swap(population, buffer); // swap buffers
    }
}

2020/05/19 - [AI/Algorithm] - neural network

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

2020/05/19 - [AI/Algorithm] - minimax, alpha-beta pruning

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의 구성 요소

신경망 셈플 프로그램입니다.

#include <iostream>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <fstream>
using namespace std;


// 현재 네트워크의 학습률은 2의 제곱근
float learningRate = 1.414213562;

// 운동량
float momentum = 0.25;

// 바이어스(경향, 성향)
int bias = 1;


// 신경망을 통해 전달되는 학습 데이터
double arrTrainingData[4][2] = {
    { 1, 0 },   // target : 1
    { 1, 1 },   // target : 0
    { 0, 1 },   // target : 1
    { 0, 0 }    // target : 0
};

// 신경망 학습 데이터에 대한 값
int arrTargetData[4] = {
    1,
    0,
    1,
    0
};


// 신경망 가중치 값들
float arrWeight[9] = {};
// 신규 업데이트 가중치 값
float arrUpdateWeight[9];
// 이전 업데이트 가중치 값
float arrUpdatePrevWeight[9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

// Hidden Layer
float sumHiddenLayer1;
float sumHiddenLayer2;


// 편미분(도함수) 값
float derivativeOutput;
float derivativeHiddenLayer1;
float derivativeHiddenLayer2;
float sumOutput;

// 기울기(미분 값)
float gradients[9];

// 최종 결과 값
float outputNeuron;

// 현재 학습중인 세대
int epoch = 0;

// 에러
float arrError[4];
float arrRMSE[20000];






////////Prototyping////////
float sigmoid(float x);
void calcHiddenLayers(double input1, double input2);
void calcOutputNeuron();
void calcError(int x);
void calcDerivatives();
void backwardPropagation(double input1, double input2, float error);
void calcUpdates();
void update_new_arrWeight();
float calcRMSE();
void generateWeight();
void trainingNeuralNetwork();
void testInput();
void saveData();
////////Prototyping////////


int main(int argc, const char * argv[]) {
    
    /*
     input neurons : 2
     hidden layers : 2
     output neuron : 1
     
     The learning algorithm i use is the backpropagation algorithm.
     The network has 2 input neurons, 2 hidden layers, and 1 output neuron.
     also the hidden layer and the output layer is supported by a additional bias neuron(a neuron with a constant value of 1)
     */

    
    // 가중치 값 생성
    generateWeight();
    
    // 신경망 학습
    trainingNeuralNetwork();
    
    // 저장파일 생성
    saveData();
    
    // 입력 시작
    testInput();
    
    system("pause");
    
    return 0;
}


////////////////////////////////////////////////////////////////////////////////////////////////
// 가중치 값 랜덤 생성
void generateWeight()
{
    srand((unsigned)time(NULL));
    
    for (int i = 0; i < 9; i++)
    {
        if (1 == rand() % 2) {
            // generate number between -1.0 and 0.0
            arrWeight[i] = -(double(rand()) / (double(RAND_MAX) + 1.0));
        } else {
            // generate number between 1.0 and 0.0
            arrWeight[i] = double(rand()) / (double(RAND_MAX) + 1.0);
        }
        
        cout << "weight " << i << " = " << arrWeight[i] << endl;
    }
    cout << "" << endl;
}

// 신경망 학습
void trainingNeuralNetwork()
{
    // 20000 세대만큼 반복
    while (epoch < 20000)
    {
        for (int i = 0; i < 4; i++)
        {
            double input1 = arrTrainingData[i][0];
            double input2 = arrTrainingData[i][1];
            calcHiddenLayers(input1, input2);   // input
            calcOutputNeuron();                 // output
            
            
            calcError(i); // input!!
            
            calcDerivatives(); // input!!
            
            float error = arrError[i];
            backwardPropagation(input1, input2, error); // input!!
            
            calcUpdates();
            update_new_arrWeight();
        }
        
        // 제곱근 평균 제곱 오차(RMSE;오차(잔차)의 제곱에 대해 평균을 취하고 이를 제곱근한 것)
        // 작을수록 추정의 정확성이 높다.
        // 추정값들이 중심으로부터 얼마나 멀리 떨어져 있는지를 나타낼때 많이 쓰인다.
        float rmse = calcRMSE();
        arrRMSE[epoch] = rmse;
        cout << "epoch: " << epoch << endl;
        
        // 세대수 증가
        epoch = epoch + 1;
        
        
        
        // Adding some motivation so if the neural network is not converging after 4000 epochs it will start over again until it converges
        // 신경망이 4000세대 이후까지 RMSE 에러율이 0.5이하가 안된다면 처음부터 다시 시도한다.(가중치 재설정)
        if (epoch > 4000 && rmse > 0.5)
        {
            for (int i = 0; i < 9; i++)
            {
                arrUpdatePrevWeight[i] = 0;
                arrUpdateWeight[i] = 0;
                gradients[i] = 0;
            }
            for (int i = 0; i < 4; i++) {
                arrError[i] = 0;
            }
            for (int i = 0; i < epoch; i++) {
                arrRMSE[i] = 0;
            }
            epoch = 0;
            generateWeight();
        }
    }
}


// 저장 파일 생성
void saveData()
{
    // 각 세대별 RMSE값 저장
    ofstream dataER;
    dataER.open("errorData1.txt");
    for (int i = 0; i < epoch; i++)
    {
        dataER << i << "   " << arrRMSE[i] << endl;
    }
    dataER.close();
    
    // 최종 가중치 값 저장
    ofstream dataER1;
    dataER1.open("weight_data1.txt");
    for (int i = 0; i < 9; i++)
    {
        dataER1 << i << "   " << arrWeight[i] << endl;
    }
    dataER1.close();
}

// 학습된 신경망 테스트
void testInput()
{
    char choise = 'Y';

    do
    {
        if (choise == 'Y' || choise == 'y')
        {
            float input1;
            float input2;
            cout << "user input 1: "; cin >> input1; cout << endl;
            cout << "user input 2: "; cin >> input2; cout << endl;
            calcHiddenLayers(input1, input2);   // input
            calcOutputNeuron();                 // output
            
            // 반올림 처리로 최종 값을 결정 함
            cout << "output = " << outputNeuron << " => " << floor(outputNeuron+0.5) << endl;
            
            cout << "Again(y/n)? "; cin >> choise;
        }
        else
        {
            break;
        }
    } while ((choise == 'Y' || 'y') && (choise != 'n' || 'N'));
}

////////////////////////////////////////////////////////////////////////////////////////////////

/*
           bias(1)       bias(1)
             | \         |
             |  w4       w8
             |   \       |
 input1 --w0 --- h1      |
        \    |  /  \     |
         \    \/    w6   |
          w1  /\     \   |
            \/  \      outputNeuron
            /\   \    /
          w2  \   w5 w7
          /    \  | /
         /      \ |/
 input2 --w3----- h2
 */

// Hidden Layer 계산
void calcHiddenLayers(double input1, double input2)
{
    sumHiddenLayer1 = (input1 * arrWeight[0]) + (input2 * arrWeight[2]) + (bias * arrWeight[4]);
    sumHiddenLayer2 = (input1 * arrWeight[1]) + (input2 * arrWeight[3]) + (bias * arrWeight[5]);
}

// Output Layer 계산
void calcOutputNeuron()
{
    sumOutput = (sigmoid(sumHiddenLayer1) * arrWeight[6]) + (sigmoid(sumHiddenLayer2) * arrWeight[7]) + (bias * arrWeight[8]);
    outputNeuron = sigmoid(sumOutput);
}


// sigmoid activation function
// 계단형식의 함수를 미분이 가능하도록 곡선화를 해주는 함수이다.
// 주어진 값(x)에 대하여 0 ~ 1사이의 값으로 변환하여 반환해 준다.
// 이 함수를 사용하는 이유는 미분이 용이하기 때문이다. 이 함수의 미분 공식은 sigmoid(x)(1-sigmoid(x)) 이다.
float sigmoid(float x)
{
    float sigmoid = 1.0 / (1.0 + exp(-x));
    return sigmoid;
}

// 타겟값과 얼마나 차이가 나는지 배열에 저장
void calcError(int x)
{
    arrError[x] = outputNeuron - arrTargetData[x];
}



// sigmoid 미분
void calcDerivatives()
{
    /*
    derivativeOutput       = (exp(sumOutput)       / pow((1 + exp(sumOutput)),       2))  * -arrError[x];
    derivativeHiddenLayer1 = (exp(sumHiddenLayer1) / pow((1 + exp(sumHiddenLayer1)), 2))  *  arrWeight[6] * derivativeOutput;
    derivativeHiddenLayer2 = (exp(sumHiddenLayer2) / pow((1 + exp(sumHiddenLayer2)), 2))  *  arrWeight[7] * derivativeOutput;
    */

    // 각 출력값에대한 미분값을 구한다.
    derivativeOutput       = sigmoid(sumOutput)       * (1 - sigmoid(sumOutput));
    derivativeHiddenLayer1 = sigmoid(sumHiddenLayer1) * (1 - sigmoid(sumHiddenLayer1));
    derivativeHiddenLayer2 = sigmoid(sumHiddenLayer2) * (1 - sigmoid(sumHiddenLayer2));
}

// 기울기 계산
// Backward Propagation (역전파)
void backwardPropagation(double input1, double input2, float error)
{
    /*
    gradients[0] = sigmoid(input1) * derivativeHiddenLayer1;
    gradients[1] = sigmoid(input1) * derivativeHiddenLayer2;
    
    gradients[2] = sigmoid(input2) * derivativeHiddenLayer1;
    gradients[3] = sigmoid(input2) * derivativeHiddenLayer2;
    
    gradients[4] = sigmoid(bias)   * derivativeHiddenLayer1;
    gradients[5] = sigmoid(bias)   * derivativeHiddenLayer2;

    gradients[6] = sigmoid(sumHiddenLayer1) * derivativeOutput;
    gradients[7] = sigmoid(sumHiddenLayer2) * derivativeOutput;
    gradients[8] = sigmoid(bias)            * derivativeOutput;
     */

    
    
    // Backward Propagation(역전파)란 Error(오차)가 본래 진행방향과 반대방향으로 전파 된다고 하여 붙여진 이름이다.
    // 역전파 알고리즘은 Supervised Learning(input과 output을 알고있는 상태)에서 신경망을 학습시키는 방법이다.

    double bpOutput = derivativeOutput * -error;
    double bpLayer2 = derivativeHiddenLayer2 * arrWeight[7] * bpOutput;
    double bpLayer1 = derivativeHiddenLayer1 * arrWeight[6] * bpOutput;
    
    // w8,w7,w6
    gradients[8] = sigmoid(bias)            * bpOutput;
    gradients[7] = sigmoid(sumHiddenLayer2) * bpOutput;
    gradients[6] = sigmoid(sumHiddenLayer1) * bpOutput;
    
    // w5, w4
    gradients[5] = sigmoid(bias) * bpLayer2;
    gradients[4] = sigmoid(bias) * bpLayer1;
    
    // w3, w2
    gradients[3] = sigmoid(input2) * bpLayer2;
    gradients[2] = sigmoid(input2) * bpLayer1;
    
    // w1, w0
    gradients[1] = sigmoid(input1) * bpLayer2;
    gradients[0] = sigmoid(input1) * bpLayer1;
}

void calcUpdates()
{
    for (int i = 0; i < 9; i++)
    {
        //arrUpdateWeight[i] = gradients[i];
        arrUpdateWeight[i] = (learningRate * gradients[i]) + (momentum * arrUpdatePrevWeight[i]);
        
        arrUpdatePrevWeight[i] = arrUpdateWeight[i];
    }
}

void update_new_arrWeight()
{
    for (int i = 0; i < 9; i++)
    {
        arrWeight[i] = arrWeight[i] + arrUpdateWeight[i];
    }
}

float calcRMSE()
{
    float rmse = sqrt((pow(arrError[0], 2) + pow(arrError[1], 2) + pow(arrError[2], 2) + pow(arrError[3], 2) / 4));
    cout << "RMSE : " << rmse << endl;
    cout << "" << endl;
    return rmse;
}

//  minimax full search example

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

// 가로 3, 세로 3 바둑판일 경우
// 0~8 총 9개의 자리가 있다. (자리 번호를 0번~8번이라 할경우)
// 내가 처음 놓는 자리를 정했을 때 컴퓨터와 번갈아 놓을 수 있는
// 모든 경우의 수를 minimax full search하여 출력한다.

// 0: empty,  1: human,  2: computer
int board[9] = {0,};
int numberOfCases = 0;


void printLog(int depth, int *log)
{
    for (int i=0; i<depth; ++i) {
        cout<<log[i];
        if (0 == i) {
            cout<<" -> ";
        } else {
            cout<<" ";
        }
    }
    cout<<endl;
}

bool isFull()
{
    for(int i=0; i<9; ++i) {
        if (board[i] == 0) {
            return false;
        }
    }
    return true;
}

int minimax(bool flag, int depth=1, int* log=nullptr)
{
    if(true == isFull()) {
        printLog(depth, log);
        numberOfCases ++;
        return 0;
    }
    
    for (int i = 0; i < 9; ++i) {
        if (board[i] != 0) continue;

        if(true == flag) {  // computer turn
            board[i] = 2;
            log[depth] = i;
            minimax(!flag, depth+1, &log[0]);
        } else {            // human turn
            board[i] = 1;
            log[depth] = i;
            minimax(!flag, depth+1, &log[0]);
        }
        board[i] = 0;
    }
    
    return 0;
}

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

    cout<<"----------- minimax full search example ---------------"<<endl;
    
    int move;
    do {
        cout<<endl<<"Enter the move(0-8):";
        cin>>move;
    } while(move < 0 || move >= 9 || 0 != board[move]);
    
    board[move] = 1;
    
    vector<int> log(9, 0);
    log[0] = move;
    
    minimax(true, 1, &log[0]);

    cout << "number of cases : " << numberOfCases << endl;
    
    return 0;
}

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