'개발'에 해당되는 글 185건

'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

Private일 경우 비번 입력한다.

git "https://[아이디]:[비밀번호]@bitbucket.org/netcanis/otp.git"

로컬일 경우

git "file:///directory/to/project" "branch"

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/etc] - APNs

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

2020/05/18 - [개발툴/Xcode] - Storyboard References (스토리보드 분리)

2020/05/18 - [iOS/Jailbreak] - OpenSSL Mac 연동

2020/05/18 - [iOS/Objective-C] - NSLog 출력 크기 제한 풀기

[ Mac OS X ] 메모리 덤프

테스트할 디바이스를 연결한 뒤 Fridump를 통해 메모리 덤프를 해보록 하겠습니다.

USB에 연결된 디바이스내 프로세스 이름과 PID목록 출력

frida-ps -U

만약 테스트하려는 앱이름이 한글일 경우

fridump.py파일을 열어 73번 라인 코드를 이름대신 PID값으로 처리되도록 다음과 같이 수정한 다.

아래와 같이 변경하면 입력한 앱이름대신 PID로 입력했을경우 입력된 PID문자열을 int형 변환을 통해 PID로 인식되어 처리되도록 한다.

session = frida.get_usb_device().attach(int(APP_NAME))

프로세스 이름으로 메모리 덤프 실행 ( 중요 : 관리자 권한 실행을 위해 -H옵션 추가)

sudo -H python fridump.py -U -s -r [앱이름] 

Finder에서 fridump폴더 아래 dump폴더가 생성된 것을 확인할 수 있다.

덤프 데이터파일 맨 아래 strings.txt파일을 볼 수 있다. 이것은 메모리내 문자열로 처리되어 검출된 데이터들을 모아놓은 텍스트 파일이다. 

(대부분 heap메모리 상에서 문자열 처리한 부분은 이곳에서 검출된다.)

strings.txt을 얼어보면 다음과같이 메모리에서 검출된 문자열정보들을 확인할 수 있다.

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

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

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

2020/06/12 - [iOS/Jailbreak] - Fridump 사용법 (4/4) - 결과물 바이너리 검색

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (1/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (2/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (3/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (4/4)

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/etc] - APNs

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

2020/05/18 - [개발툴/Xcode] - Storyboard References (스토리보드 분리)

2020/05/18 - [iOS/Jailbreak] - OpenSSL Mac 연동

2020/05/18 - [iOS/Objective-C] - NSLog 출력 크기 제한 풀기

[ Mac OS X ] 환경 구축

Fridump를 사용한 메모리 덤프는 Mac OS X 환경에서 Fridump를 콘솔환경에서 실행하여 USB로 연결된 iOS디바이스에 실행중인 앱의 메모리를 덤프하게 됩니다.

이제 맥 환경구축을 해보도록 하겠습니다.

Homebrew 설치

https://brew.sh

/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/ master/install)"

python 설치 (2.7.x버전이 설치되어 있음) - 아래 명령 실행시 python3 설치됨.(선택사항)

brew install python 

python —version

wget 설치

brew install wget

usbmuxd 설치

brew install usbmuxd rm get-pip.py

Xcode Command Line Tool 설치

xcode-select --install

MacPorts 다운로드 및 인스톨

https://www.macports.org/install.php

콘솔창 종료후 재실행

MacPort 설치

sudo port -v selfupdate

Putty 설치

sudo port install putty

pip설치

wget https://bootstrap.pypa.io/get-pip.py sudo python get-pip.py

Frida-tools 설치

sudo pip install frida-tools

'Cannot uninstall six' 에러 발생시 아래와 같이 처리한다.

sudo pip install frida-tools —ignore-installed six

버전문제로 인한 에러 처리

frida-tools 버전과 frida버전이 업데이트 되면서 서로 버전 지원 문제로

실행시 에러가 출력되며 실행되지 않는 경우가 있다.

탈옥 iPhone이 12.4버전일 경우 아래 버전으로 설치하기 바란다.

pip install frida==12.6.11

pip install frida-tools==2.0.2

실행중인 프로세스 이름과 PID 목록 출력

frida-ps

frada-ps 옵션을 확인

frida-ps -h

기기에서 실행중인 프로세스 목록 출력

frida-ps -U

-U : USB로 연결된 기기에 접속.

-D : Device ID로 기기에 접속.

-R : Remote Server(원격서버)에 접속

-H : Host의 Remote Server(원격서버)에 접속

USB에 연결된 디바이스 목록 출력

frida-ls-devices

기타 Frida관련 명령 및 사용법은 아래 사이트에서 참고하도록 한다.

https://www.frida.re/docs/ios/#with-jailbreak

fridump 설치

cd ~ 

git clone https://github.com/Nightbringer21/fridump

설치확인

cd fridump 

ls

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

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

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

2020/06/12 - [iOS/Jailbreak] - Fridump 사용법 (4/4) - 결과물 바이너리 검색

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (1/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (2/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (3/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (4/4)

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/etc] - APNs

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

2020/05/18 - [개발툴/Xcode] - Storyboard References (스토리보드 분리)

2020/05/18 - [iOS/Jailbreak] - OpenSSL Mac 연동

2020/05/18 - [iOS/Objective-C] - NSLog 출력 크기 제한 풀기

[ iOS ] 환경 구축

iOS앱 메모리 덤프 Fridump 사용 방법에 대해 알아보겠습니다.

처음 해보는 경우 약간 복잡해 보일 수 있지만 최대한 쉽게 설명하도록 하겠습니다.

준비사항 :

⁃ jailbreak된 iOS Device (iPhone, iPad, iPod touch) 

⁃ Mac OS or Windows OS에 fridump, python, brew, pip, frida, frida-tools 등.

[ iOS Device ]

Cydia에서 OpenSSL, OpenSSH 설치

Cydia / Srouces 텝에서 다음 주소 추가 https://build.frida.re/

추가된 소스를 텝한다.

디바이스 비트수에 맞게 Frida 설치 (64bit일 경우 상단 Frida설치)

같은 방법으로 OpenSSL도 설치

OpenSSH, iFile, MobileTerminal등도 설치

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

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

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

2020/06/12 - [iOS/Jailbreak] - Fridump 사용법 (4/4) - 결과물 바이너리 검색

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (1/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (2/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (3/4)

2020/07/11 - [Android/Rooting] - 안드로이드 Fridump 사용하기 (4/4)

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/etc] - APNs

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

2020/05/18 - [개발툴/Xcode] - Storyboard References (스토리보드 분리)

2020/05/18 - [iOS/Jailbreak] - OpenSSL Mac 연동

2020/05/18 - [iOS/Objective-C] - NSLog 출력 크기 제한 풀기