前回

今回の目標

評価値算出のための遺伝的アルゴリズムを改善する。

ここから本編

これまで出ていた改善案は以下の通り。

進化方法を変える
突然変異の確率を変える

なお、「srand関数の引数を変える」、「思考方法を、それぞれが何手先まで読むか？　まで変えながら実験」はすでに検証しているので今回は注視しません。

また、これまでの実験で得られた評価値が左右対称でなかった原因として、osero_geneticクラス内の関数nhandに原因があると考えました。
そこで新たな改善案として、ソースファイルのnhand関数を以下のように変更しました。

osero_gengetic.cpp

void osero_genetic::nhand(int * line, int * col){
    int i = 0, j = 0;
    double score = 0, max_score = -(this -> SIZE << 3);
    int line_ans[this -> SIZE << 1] = 0, col_ans[this -> SIZE << 1] = 0;
    int num = 0;
    BOARD place = 1;
    BOARD board_leaf[2];

    while (place){
        if (check(this -> bw, i, j)){
            board_leaf[0] = this -> bw[0];
            board_leaf[1] = this -> bw[1];
            put(board_leaf, i, j, this -> turn);
            score = this -> board_add(board_leaf, 1, !(this -> turn));
            if (score == -100.0) score = count(board_leaf);
            if (score > max_score){
                max_score = score;
                line_ans[0] = i;
                col_ans[0] = j;
                num = 0;

            // 追加部分
            }else if (score == max_score){
                num++;
                line_ans[num] = i;
                col_ans[num] = j;
            }
        }
        i++;
        if (i == 8) i = 0, j++;
        place = place << 1;
    }

    // 追加部分
    if (num) {
        int place = rand() % (num + 1);
        line_ans[0] = line_ans[place];
        col_ans[0] = col_ans[place];
    }

    *line = line_ans[0];
    *col = col_ans[0];
}

line_ans及びcol_ansを配列にし、追加部分とコメントしてあるif文を追加しました。
どういうことかというと、先読みした際のスコアがもし同じだった場合の処理を追加したということです。これまではそれがなく、同じスコアの際は最初に見つけた場所に置いていました。
今までこの部分がなかったのは、普通の1handなら評価値がすべて1なので先読みした際のスコアが同じになることもあったのですが、今扱っているdouble型評価値ではそうそうないだろうという理由でした。
しかしプレイヤー役は相変わらず評価値すべて1(正しくは1.0)で先読みしていたので左上ばかりに置くアルゴリズムとなっていたため修正しました。
これで学習結果が左右非対称になることはなくなるはずです。

count_lastも今回仕様で変更しました。
これまでの戻り値は「my > opp」でbool値でした。

osero_genetic.cpp

int osero_genetic::count_last(void){
    int my, opp;

    my = this -> computer;
    opp = this -> player;

    my = popcount(this -> bw[my]);
    opp = popcount(this -> bw[opp]);

    return my - opp;
}

また、今までのプログラムでは学習した評価値のファイル保存順が間違ってたので修正しました。

また今回、下に示す5つのメンバ変数は学習時のパラメータで変更しないので静的メンバに変更しました。

osero_genetic.h

// 今まで
int read_goal = 1;
int mode = 0;
int player, computer;
bool print = false;

// 今回
static int mode;
static int player, computer;
static int srand_num;
static bool print;

進化方法と突然変異の確率を総当たりで変える

これまでは複数のテーマを別に検証していましたが、機械学習の時の反省を活かし、進化方法と突然変異の確率を総当たりで変えながら実験していきたいと思います。
機械学習の時と違い、pandasの扱いにも慣れてきたので当時よりも複雑なデータ処理が可能になったことも理由の一つです。

つまり今回、

データ選択方法
交叉方法
突然変異の確率
コンピュータの思考方法
プレイヤー役の思考方法
世代
一世代の人数

の七重ループになります。
なお今回、srand関数の引数は前回の「per srand_num」及び「per srand_num and random」のグラフで平均的な値をとっていた99を採用します。

今回の実行プログラムは長く複雑なので、分割しながら説明します。

実行プログラム

mainの上に書くやつ

run.cpp

#include "osero_genetic.h"

// 静的メンバの初期化
int osero_genetic::mode = 1;
int osero_genetic::computer = 0;
int osero_genetic::player = 1;
int osero_genetic::srand_num = 99;
bool osero_genetic::print = false;

// 一世代の数と親の数、世代数
const int child = 32;
const int parent = 16;
const int entire = 100;

const int proba_arr[parent] = {
    99, 89, 81, 74, 67, 61, 55, 50, 46, 41,
    38, 34, 31, 28, 26, 23//, 21, 19, 17, 16
};

enum class sele_method{
    all,
    ranking,
    tournament,
    roulette,
    sentinel
};

enum class evol_method{
    random,
    one_crossing,
    two_crossing,
    mask,
    sentinel
};

inline double first_eva(void){
    return DOUBLE(rand()) / (RAND_MAX >> 1) - 1;
}

// sele_func member
void all(double ** eva, double ** new_eva, double * score);
void ranking(double ** eva, double ** new_eva, double * score);
void tournament(double ** eva, double ** new_eva, double * score);
void roulette(double ** eva, double ** new_eva, double * score);

// evol_func member
void random(double ** par_eva, double ** chi_eva);
void one_crossing(double ** par_eva, double ** chi_eva);
void two_crossing(double ** par_eva, double ** chi_eva);
void mask(double ** par_eva, double ** chi_eva);

// run mutation in specified probability
void mutation(double ** eva, int proba);

まず静的メンバを初期化し世代数なども設定します。
前回、親の数は不定でしたが、様々な方法を試すにあたり不具合が生じたので今回は子供の半数である16で固定します。

proba_arrは、ランキング選択の際に用いる各順位の評価値の選択確率です。
数字は以下のプログラムで作りました、正直適当です。
一度は親の人数20人でプログラムを作りましたが、少しでも実行時間を減らすことと今までの実験と似た条件で実験するため子供32人、親16人に変更しました。

test.cpp

#include <stdio.h>

int main(void){
    double proba = 99;

    for (int i = 0; i < 20; i++){
        printf("%3d,", static_cast<int>(proba));
        proba /= 1.1;
        if (i == 9) printf("\n");
    }

    printf("\n");

    return 0;
}

次に二つの列挙体クラスについて。
これらは、選択及び進化の方法でそれぞれ四つずつです。
選択については

全て(前回の方法と少し異なる)
ランキング
トーナメント
ルーレット

進化については

ランダム(前回の方法と全く同じ)
一点交叉
二点交叉
マスク

「全て」の選択方法が前回と少し異なるのは、親の数が限定されるためです。

インライン関数は評価値初期化のためのものです。

次に実際に選択や進化を行う関数の宣言と突然変異関数の宣言です。

選択関数

四つある選択関数それぞれについて説明します。
なお使用変数は以下の通り。

eva　現在の評価値。child x 64の二次元配列。
new_eva　次世代の親となる評価値。parent x 64の二次元配列。
score　現在の評価値がもつスコア。対戦後の駒数の差(自分の駒-相手の駒数で、マイナスになることもある)。childこの要素を持つ一次元配列。

全て

非常に雑なプログラムですが、正直この方法は今までにもやってきているのであまりデータを欲しているわけではないです。
疑似的な比較のため選択方法に追加しました。
勝利した際に使っていた評価値を親に選び、20人選んだ時点で動作を打ち切ります。
20人に満たなかった場合、強引に20人の親を用意するため先頭から順番にコピーします。

run.cpp

void all(double ** eva, double ** new_eva, double * score){
    int num = 0;

    for (int i = 0; i < child; i++){
        if (score[i] > 0){
            for (int j = 0; j < 64; j++){
                new_eva[num][j] = eva[i][j];
            }
            num++;
        }
        if (num == parent) break;
    }

    if (num < parent){
        int times = parent - num;
        for (int i = 0; i < times; i++){
            for (int j = 0; j < 64; j++){
                new_eva[num][j] = eva[i][j];
            }
            num++;
        }
    }
}

ランキング

まず、全員のランキングを作成するため以下の動作をchild回繰り返します。

cnt変数を0にする。
他の人のスコアを見て回り、自分より大きなスコアを得ている人がいたらcntをインクリメントする。
上の動作が終わった時のcnt変数の値をインクリメントすればそのまま順位となるので、その値をrank配列に格納する。

なお、同順位となる可能性もありますが、数字がかぶっても問題ないため無視します。

その後、親選びを行います。
こちらは乱数/100 の余りがproba_arrで指定した値以下であれば親として選び、親が16人集まるまで繰り返します。
また、一度選ばれた人の順位を0にすることで同一人物が複数回親になることを禁止しています。
プログラム内でcnt変数を使いまわしていますが、前半では順位、後半ではすでに選んだ親の人数として使っています。

run.cpp

void ranking(double ** eva, double ** new_eva, int * score){
    int i, j;
    int rank[child];
    int cnt;

    for (i = 0; i < child; i++){
        cnt = 0;
        for (j = 0; j < child; j++){
            if (score[j] > score[i]) cnt++;
        }
        rank[i] = cnt + 1;
    }

    cnt = 0;
    i = 0;
    do{
        if (rank[i] && rand() % 100 < proba_arr[rank[i] - 1]){
            for (j = 0; j < 64; j++){
                new_eva[cnt][j] = eva[i][j];
            }
            rank[i] = 0;
            cnt++;
        }
        i++;
        if (i == child) i = 0;
    }while (cnt != parent);
}

トーナメント

40人いる子供を番号順に二列に並べ、よりスコアの高かったほうを親として採用しています。

run.cpp

void tournament(double ** eva, double ** new_eva, double * score){
    int i, j;
    int place;

    for (i = 0; i < parent; i++){
        place = i << 1;
        if (score[place] > score[place + 1]){
            ;
        }else{
            place++;
        }
        for (j = 0; j < 64; j++){
            new_eva[i][j] = eva[place][j];
        }
    }
}

ルーレット

ルーレット選択を実現するため、以下のアルゴリズムを作成しました。

最小スコアを探す。
スコア値すべてから最小スコアを引く(スコア値をすべて0または正の数にする)。
スコア値すべてに5を足す(最下位のデータが選ばれる可能性を確保するため)
以下の動作を、16人の親が確保できるまで繰り返す。
now_place変数を0に初期化する。
now_placeが、設定したplace変数を超えるまで各人のスコアを足す。
超えたタイミングで、その時のスコアを持っていた評価値がまだ親になったことがなければ、親として選ぶ(一度親になった人のスコアを0にし、次に選ばれる可能性を0にする)。

run.cpp

void roulette(double ** eva, double ** new_eva, int * score){
    int i, j;
    int min_score = 100;

    for (i = 0; i < child; i++){
        if (score[i] < min_score){
            min_score = score[i];
        }
    }

    for (i = 0; i < child; i++){
        score[i] = score[i] - min_score + 5;
    }

    int cnt;
    int place = 100, now_place;

    i = 0;
    for (cnt = 0; cnt < parent; cnt++){
        now_place = 0;
        do{
            i++;
            if (i == child) i = 0;
            now_place += score[i];
        }while (now_place < place);

        for (j = 0; j < 64; j++){
            new_eva[cnt][j] = eva[i][j];
        }
        score[i] = 0;
    }
}

進化関数

四つある進化関数についても同様に解説します。
なお、使用する変数は以下の通り。

par_eva　先ほど16人選びだした親。
chi_eva　32人の子供で、親から作る。

ランダム

以前のものと全く同じです。

run.cpp

void random(double ** par_eva, double ** chi_eva){
    for (int i = 0; i < child; i++){
        for (int j = 0; j < 64; j++){
            chi_eva[i][j] = par_eva[rand() % parent][j];
        }
    }
}

一点交叉

被らないよう両親を選び、交叉を行います。

run.cpp

void one_crossing(double ** par_eva, double ** chi_eva){
    int i, j;
    int mama, papa;
    int cut_place;

    for (i = 0; i < child; i++){
        cut_place = rand() % 64;
        mama = rand() % parent;
        do{
            papa = rand() % parent;
        }while (mama == papa);

        for (j = 0; j < cut_place; j++){
            chi_eva[i][j] = par_eva[mama][j];
        }
        for (; j < 64; j++){
            chi_eva[i][j] = par_eva[papa][j];
        }
    }
}

二点交叉

一点交叉とほぼ同じですが、ひとつめの交叉箇所がふたつめよりも必ず先に来るようにしています。

run.cpp

void two_crossing(double ** par_eva, double ** chi_eva){
    int i, j;
    int mama, papa;
    int cut_place1, cut_place2;

    for (i = 0; i < child; i++){
        do{
            cut_place1 = rand() % 64;
            cut_place2 = rand() % 64;
        }while (cut_place1 >= cut_place2);
        mama = rand() % parent;
        do{
            papa = rand() % parent;
        }while (mama == papa);

        for (j = 0; j < cut_place1; j++){
            chi_eva[i][j] = par_eva[mama][j];
        }
        for (; j < cut_place2; j++){
            chi_eva[i][j] = par_eva[papa][j];
        }
        for (; j < 64; j++){
            chi_eva[i][j] = par_eva[mama][j];
        }
    }
}

マスク

ランダムにマスクを作り、両親からその位置の評価値を受け取ります。
rand関数の返り値はintなので、32ビットシフトさせたものと足すことで盤面サイズである64ビット分確保しています。

run.cpp

void mask(double ** par_eva, double ** chi_eva){
    int i, j;
    int mama, papa;
    BOARD mask_b, place;

    for (i = 0; i < child; i++){
        mask_b = (static_cast<BOARD>(rand()) << 32) + rand();
        mama = rand() % parent;
        do{
            papa = rand() % parent;
        }while (mama == papa);

        j = 0;
        place = 1;
        while (place){
            if (place & mask_b){
                chi_eva[i][j] = par_eva[mama][j];
            }else{
                chi_eva[i][j] = par_eva[papa][j];
            }
            j++;
            place = place << 1;
        }
    }
}

突然変異

突然変異関数です。
見ての通り評価値と突然変異の確率を受け取ってその通りに突然変異させます。

run.cpp

void mutation(double ** eva, int proba){
    for (int i = 0; i < child; i++){
        for (int j = 0; j < 64; j++){
            if (rand() % 100 < proba){
                eva[i][j] = first_eva();
            }
        }
    }
}

main

いよいよmain関数ですが、やはり長いため分割しながら説明します。

宣言部分

run.cpp

    int win_sum;
    int score[child];
    double ** eva = new double *[child], ** par_eva = new double *[parent];
    double eva_p[64], eva_my[64], eva_f[child][64];
    void (* sele_func[INT(sele_method::sentinel)])(double **, double **, int *) = {
        all,
        ranking,
        tournament,
        roulette
    };
    void (* evol_func[INT(evol_method::sentinel)])(double **, double **) = {
        random,
        one_crossing,
        two_crossing,
        mask
    };

    osero_genetic * run;
    FILE * dataf = fopen("data.csv", "w");
    FILE * evaf = fopen("eva.csv", "w");

各変数の説明をします。

数字

win_sum　一世代の勝利数。
score　各人の対戦後のスコア。自分の駒数-相手の駒数。
eva　対戦の際に従う評価値。
par_eva　次世代の親評価値。
eva_p　値全て1の評価値。
eva_my　プレイヤー役が従う強そうな評価値。詳細は後述。
eva_f　評価値の初期値。どの方法であっても初期値はこれを使う。

関数ポインタ

sele_func　選択関数。
evol_func　進化関数。

インスタンス

run　オセロの試合実行用。

ファイルハンドル

dataf　各世代での勝利数を記録するファイル。
evaf　最終評価値を記録するファイル。

初期設定

run.cpp

    fprintf(
        dataf,
       "evolution_method,select_method,per_mutation,computer,player,generation,win_per\n"
    );
    fprintf(evaf, "evolution_method,select_method,per_mutation,computer,player,indi");
    for (int i = 0; i < 64; i++) fprintf(evaf, ",%d", i);
    fprintf(evaf, "\n");

    srand(99);

    // setup eva and par_eva
    for (int i = 0; i < child; i++){
        eva[i] = new double[64];
    }
    for (int i = 0; i < parent; i++){
        par_eva[i] = new double[64];
    }

    // setup eva_p and eva_my
    for (int i = 0; i < 64; i++){
        eva_p[i] = 1.0;

        if (i == 0 || i == 7 || i == 56 || i == 63){
            eva_my[i] = 1.0;
        }else if (i == 1 || i == 6 || i == 8 || i == 9 || i == 14 ||i == 15 ||
                  i == 48 || i == 49|| i == 54 || i == 55 || i == 57 || i == 62){
            eva_my[i] = -1.0;
        }else if (i == 2 || i == 5 || i == 58 || i == 61 ||
                  i == 16 || i == 23 || i == 40 || i == 47 ||
                  i == 18 || i == 21 || i == 42 || i == 45){
            eva_my[i] = 0.5;
        }else{
            eva_my[i] = 0.1;
        }
    }

    // setup eva
    for (int i = 0; i < child; i++){
        for (int j = 0; j < 64; j++){
            eva_f[i][j] = first_eva();
        }
    }

まずデータ保存ファイル及び評価値保存ファイルに各パラメータを書きます。
今までの評価値保存は人間に分かりやすい形で行っていましたが今回は機械に分かりやすい形に変更しました。

その後srand関数を呼びます。

evaとper_evaはポインタ配列の先頭ポインタなので、その先の配列を作ることで二次元配列にします。

また、eva_pはすべて1で、eva_myは以下の表を見ながら強そうな評価値にしました。具体的に、端っこの青色部分を1.0点、そのすぐ隣の赤色部分を-1.0点、さらに隣の水色部分を0.5点、その他白い場所を0.1点としました。

その後、評価値の初期値であるeva_fを初期化します。

学習実行部分

怒涛のfor文です。
少しでも見やすいよう、字下げを一つ解除しています。main関数内にあるので、本来は最初のfor文も字下げされています。

動作説明は以下の通り。

以下の動作を進化方法の数だけ繰り返す(4通り)。
進行状況をプリントする。
以下の動作を選択方法の数だけ繰り返す(4通り)。
進行状況をプリントする。
以下の動作を突然変異の確率の数だけ繰り返す(3通り)。
進行状況をプリントする。
以下の動作をコンピュータの思考方法の数だけ繰り返す(2通り)。
以下の動作をプレイヤー役の思考方法の数だけ繰り返す(5通り)。
全ての評価値を初期化する。
学習を始める。評価値に従い、9～10の動作を繰り返す(32通り)。
まず思考方法などに合わせインスタンスを作成する。
試合を行い、対戦後のスコアをscore配列に保存する。
選択方法に従い、次世代の親の選択を行う。
進化方法に従い、次世代の評価値を作成する。
突然変異の確率に従い、突然変異を行う。
各条件と結果を記録する。
8～14の動作を世代数だけ繰り返す(100世代)。
最終的な評価値を記録する。

4x4x3x2x5x32x100の1,536,000試合、つまり約150万試合行います。

run.cpp

// evolution_method
for (int evol = 0; evol < INT(evol_method::sentinel); evol++){
    // print progress
    printf("[");
    for (int i = 0; i < evol + 1; i++) printf("#");
    for (int i = 0; i < INT(evol_method::sentinel) - evol - 1; i++) printf(" ");
    printf("]\n");

    // select_method
    for (int sele = 0; sele < INT(sele_method::sentinel); sele++){
        // print progress
        printf("    [");
        for (int i = 0; i < sele + 1; i++) printf("#");
        for (int i = 0; i < INT(sele_method::sentinel) - sele - 1; i++) printf(" ");
        printf("]\n");

        // per_mutation
        for (int muta = 0; muta <= 10; muta += 5){
            // print progress
            printf("        [");
            for (int i = 0; i < muta / 5 + 1; i++) printf("#");
            for (int i = 0; i < 3 - muta / 5 - 1; i++) printf(" ");
            printf("]\n");

            // computer
            for (int computer = 1; computer <= 2; computer++){
                // player
                for (int player = 0; player <= 4; player++){
                    // setup eva
                    for (int i = 0; i < child; i++){
                        for (int j = 0; j < 64; j++){
                            eva[j][i] = eva_f[i][j];
                        }
                    }

                    // start learning
                    for (int gene = 0; gene < entire; gene++){
                        for (int indi = 0; indi < child; indi++){
                            if (player == 0){
                                run = new osero_genetic(0, eva[indi], 1);
                            }else if (player == 1 || player == 2){
                                run = new osero_genetic(0, eva[indi], 0, eva_p);
                                run -> read_goal[1] = player;
                            }else{
                                run = new osero_genetic(0, eva[indi], 0, eva_my);
                                run -> read_goal[1] = player - 2;
                            }

                            run -> read_goal[0] = computer;

                            score[indi] = run -> play();

                            delete run;
                        }

                        sele_func[sele](eva, par_eva, score);

                        evol_func[evol](par_eva, eva);

                        if (muta) mutation(eva, muta);

                        // data output
                        fprintf(
                            dataf,
                            "%d,%d,%d,%d,%d,%d,%d\n",
                            evol,
                            sele,
                            muta,
                            computer,
                            player,
                            gene,
                            win_sum
                        );
                    }

                    // final eva output
                    for (int i = 0; i < child; i++){
                        fprintf(
                            evaf,
                            "%d,%d,%d,%d,%d,%d",
                            evol,
                            sele,
                            muta,
                            computer,
                            player,
                            i
                        );
                        for (int j = 0; j < 64; j++){
                            fprintf(evaf, ",%2.4f", eva[i][j]);
                        }
                        fprintf(evaf, "\n");
                    }
                }
            }
        }
    }
}

〆部分

特筆することはないです。
ファイルを閉じ、ひたすらdeleteしています。

run.cpp

    // tidying up
    fclose(evaf);
    fclose(dataf);
    for (int i = 0; i < child; i++){
        delete[] eva[i];
    }
    for (int i = 0; i < parent; i++){
        delete[] par_eva[i];
    }
    delete[] eva;
    delete[] par_eva;

    return 0;

実行結果

なんとなく奇麗なので載せます。

[#   ]
    [#   ]
        [#  ]
        [## ]
        [###]
    [##  ]
        [#  ]
        [## ]
        [###]
    [### ]
        [#  ]
        [## ]
        [###]
    [####]
        [#  ]
        [## ]
        [###]
[##  ]
    [#   ]
        [#  ]
        [## ]
        [###]
    [##  ]
        [#  ]
        [## ]
        [###]
    [### ]
        [#  ]
        [## ]
        [###]
    [####]
        [#  ]
        [## ]
        [###]
[### ]
    [#   ]
        [#  ]
        [## ]
        [###]
    [##  ]
        [#  ]
        [## ]
        [###]
    [### ]
        [#  ]
        [## ]
        [###]
    [####]
        [#  ]
        [## ]
        [###]
[####]
    [#   ]
        [#  ]
        [## ]
        [###]
    [##  ]
        [#  ]
        [## ]
        [###]
    [### ]
        [#  ]
        [## ]
        [###]
    [####]
        [#  ]
        [## ]
        [###]

記事が長くなりそうなので考察は次回行います。

フルバージョン

genetic_kaizenフォルダ内に入っています。

次回は

今回のデータ分析と考察を行います。

次回