コンピュータとオセロ対戦22 ～遺伝的アルゴリズム、改善～

前回

今回の目標

前回の反省を活かして遺伝的アルゴリズムを改良し、最適な評価値を求めます。

ここから本編

ヘッダファイル

いままでいちいちソースファイルを変更していましたが、よく考えればせっかくクラスを使っているので継承を使いたいと思います。

親クラスがこちら、普通のオセロです。
普通に盤面を表示したり、試合結果を表示したりします。

osero.h

#ifndef osero_h
#define osero_h

#include <stdio.h>
#include <stdlib.h>

#define INT(num) (static_cast<int>(num))
#define DOUBLE(num) (static_cast<double>(num))

typedef unsigned long BOARD;

enum class TURN{
    black,
    white
};

enum class PLAY_WAY{
    nhand,
    nhand_custom,
    nleast,
    nmost,
    random,
    human,
    sentinel
};

class osero{
    protected:
        // other
        const int SIZE = 8;
        bool turn = false;
        int bmethod, wmethod;
        void (osero:: * play_method[INT(PLAY_WAY::sentinel)]) (int *, int *) = {
            &osero::nhand,
            &osero::nhand_custom,
            &osero::nleast,
            &osero::nmost,
            &osero::random,
            &osero::human
        };

        // board
        BOARD bw[2];
        double eva[2][64];

        // function
        bool check(BOARD * now, int line, int col, bool turn);
        bool check_all(void);
        int check_place(BOARD * now, int num, bool turn, bool tar_turn);
        void put(BOARD * now, int line, int col, bool turn);
        void printb(void);
        void nhand(int * line, int * col);
        void nhand_custom(int * line, int * col);
        void nleast(int * line, int * col);
        void nmost(int * line, int * col);
        void random(int * line, int * col);
        void human(int * line, int * col);
        int popcount(BOARD now);
        double count(BOARD * now);
        double board_add(BOARD * now, int num, bool turn, bool iscustom);
        void count_last(void);
        void reset(void);

    public:
        osero();
        osero(int player_b, int player_w);
        osero(int player_b, double * eva, int player_w);
        osero(int player_b, int player_w, double * eva);
        osero(int player_b, double * eva1, int player_w, double * eva2);
        virtual ~osero();

        int player, computer;
        int srand_num = 99;
        int read_goal[2] = {1, 1};

        void play(void);
};

#endif

そして今回使うクラスがこちら。
playとcount_lastのみ上書きし、学習用に盤面のプリントなし・count_lastは結果のプリントなしでスコアを返す関数に変更しました。

osero_genetic.h

#ifndef osero_genetic_h
#define osero_genetic_h

#include "osero.h"

class osero_genetic : public osero{
    private:
        int count_last(void);

    public:
        osero_genetic(int player_b, int player_w):
            osero(player_b, player_w){};
        osero_genetic(int player_b, double * eva, int player_w):
            osero(player_b, eva, player_w){};
        osero_genetic(int player_b, int player_w, double * eva):
            osero(player_b, player_w, eva){};
        osero_genetic(int player_b, double * eva1, int player_w, double * eva2):
            osero(player_b, eva1, player_w, eva2){};
        ~osero_genetic();

        virtual int play(void);
};

#endif

ソースファイル

nhand, nhand_custom

まず、nhand関数にミスがあることを見つけました。
check関数にターンを与えていなかったため、数手先まで読む際に正確に相手のターンで置ける場所を調べられませんでした。
ついでに、普通のnhandをする際にわざわざ値全て1の評価値を作るのが面倒だったのでnhand関数とnhand_custom関数に分けました。
詳しくは以下。
board_add関数のiscustomにカスタムかどうかのブール値を入れ、それによって処理を変えています。

osero.cpp

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

    while (place){
        if (this -> check(this -> bw, i, j, this -> turn)){printf("%d, %d: ", i + 1, j + 1);
            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), false);
            if (score == -100){
                int my, opp;
                my = popcount(board_leaf[INT(this -> turn)]);
                opp = popcount(board_leaf[INT(!(this -> turn))]);
                score = my - opp;
            }
            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;
            }printf("%d\n", score);
        }
        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];
}

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

    while (place){
        if (this -> check(this -> bw, i, j, this -> turn)){
            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), true);
            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];
}

double osero::board_add(BOARD * now, int num, bool turn, bool iscustom){
    if (num == this -> read_goal[INT(this -> turn)]){
        if (iscustom){
            return count(now);
        }else{
            int my, opp;
            my = popcount(now[INT(this -> turn)]);
            opp = popcount(now[INT(!(this -> turn))]);
            return my - opp;
        }
    }

    int i = 0, j = 0, put_num = 0;
    double score_ele, score = 1.0;
    BOARD place = 1;
    BOARD board_leaf[2];

    while (place){
        if (check(now, i, j, turn)){
            board_leaf[0] = now[0];
            board_leaf[1] = now[1];
            put(board_leaf, i, j, turn);
            score_ele = this -> board_add(board_leaf, num + 1, !turn, iscustom);
            if (score_ele == -100.0){
                if (iscustom){
                    score_ele = count(now);
                }else{
                    int my, opp;
                    my = popcount(now[INT(this -> turn)]);
                    opp = popcount(now[INT(!(this -> turn))]);
                    score_ele = my - opp;
                }
            }
            score += score_ele;
            put_num++;
        }
        i++;
        if (i == 8) i = 0, j++;
        place = place << 1;
    }

    if (put_num) return score / put_num;
    else return -100.0;
}

nleast

プレイヤー役の思考方法として、ランダムとnhandだけではバリエーション不足と思ったので増やします。
nleastは、n回先の相手のターンで相手が置ける場所が最小になる場所に置く関数です。n手先ではなくn回先の相手のターンです。
1leastの場合単純に次のターンで相手の置ける手数が最小になることを目指しますが、2leastの場合、相手が次のターンで置いた後さらに自分が置き、その先の相手のターンで相手がとれる手数が最小になるようにしています。

具体的にプログラムの説明をします。
といってもnhandとあまり変わらないですが以下の通りです。なお、ここでcheck_place関数は、n回先の 相手の ターンでの相手の手数が返ってくる関数です(のちほど中身を解説します)。

1. 盤面上の場所を調べ、その位置が置ける場所だった場合、board_leafに現在の盤面をコピペしそこに置く。
2. n回先の相手のターンで相手がとれる手数を受け取る。
3. 得られた手数が最小の場合、最小手数とその時の位置を記録する。
4. 得られた手数が最小と等しい場合、候補としてその時の位置を記録する。
5. 1～4の動作を盤面上のすべての位置において繰り返す。
6. 最小手数になる位置が複数ある場合、その中からランダムに置く位置を決定する。
7. line変数及びcol変数に演算結果を渡す。

片方(例えば黒)はどこにも置けないがもう片方(例えば白)は置ける、という状況になることもあると思いますが、nhand同様その場合は「置けない」となった地点で処理を止めたいと思います。
なぜならそんな状況になるのはよっぽど一方的な戦いとなっているか終盤であるかのどちらかで、そのような時に正確に考える必要性は薄いと考えたためです。

実際の中身がこちら。

osero.cpp

void osero::nleast(int * line, int * col){
    int i = 0, j = 0;
    int place_num, min_place_num = 100;
    int line_ans[this -> SIZE << 1], col_ans[this -> SIZE << 1];
    int num = 0;
    BOARD place = 1;
    BOARD board_leaf[2];

    while (place){
        if (check(this -> bw, i, j, this -> turn)){
            board_leaf[0] = this -> bw[0];
            board_leaf[1] = this -> bw[1];
            this -> put(board_leaf, i, j, this -> turn);
            place_num = this -> check_place(board_leaf, 1, !(this -> turn), !(this -> turn));
            if (place_num < min_place_num){
                min_place_num = place_num;
                line_ans[0] = i;
                col_ans[0] = j;
                num = 0;
            }else if (place_num == min_place_num){
                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];
}

nmost

nleastに続く追加関数としてnmostがあります。
こちらは逆に、n回先の自分のターンでとれる手数が最大になるような位置に置く関数です。
1mostの場合、自分が置いた後に相手が置いたその盤面で自分のとれる手数が最大になるよう置きます。2mostの場合は自分が置いた後に相手が置いた後に自分が置いた後に相手が置いた後の盤面を見ます。

具体的にプログラムを説明します。
なお、ここでcheck_place関数は、n回先の 自分の ターンでの相手の手数が返ってくる関数です。

1. 盤面上の場所を調べ、その位置が置ける場所だった場合、board_leafに現在の盤面をコピペしそこに置く。
2. n回先の自分のターンで自分がとれる手数を受け取る。
3. 得られた手数が最大の場合、最大手数とその時の位置を記録する。
4. 得られた手数が最大と等しい場合、候補としてその時の位置を記録する。
5. 1～4の動作を盤面上のすべての位置において繰り返す。
6. 最大手数になる位置が複数ある場合、その中からランダムに置く位置を決定する。
7. line変数及びcol変数に演算結果を渡す。

osero.cpp

void osero::nmost(int * line, int * col){
    int i = 0, j = 0;
    int place_num, max_place_num = -1;
    int line_ans[this -> SIZE << 1], col_ans[this -> SIZE << 1];
    int num = 0;
    BOARD place = 1;
    BOARD board_leaf[2];

    while (place){
        if (check(this -> bw, i, j, this -> turn)){
            board_leaf[0] = this -> bw[0];
            board_leaf[1] = this -> bw[1];
            this -> put(board_leaf, i, j, turn);
            place_num = this -> check_place(board_leaf, 1, !(this -> turn), this -> turn);
            if (place_num > max_place_num){
                max_place_num = place_num;
                line_ans[0] = i;
                col_ans[0] = j;
                num = 0;
            }else if (place_num == max_place_num){
                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];
}

check_place

ここで、ブラックボックスとして扱っていたcheck_place関数について説明します。
この関数はn回先の 相手または自分 のとれる手数を返す関数です。相手の手数を調べるか、それとも自分の手数を調べるかをtar_turn引数で指定します。
基本的な動作としては以下の通りです。

1. 盤面(now)、数字(num)、ターン(turn)、ターゲットターン(tar_turn)の四つの引数を受け取る。
2. もしturnがtar_turnと等しく(つまり与えられたターンがターゲットとするターンであれば)、かつnumが設定しておいたread_goalの値と等しければ(つまりそれがn回先のターゲットターンであれば)、とれる手数を返す。
3. もしturnがtar_turnと等しく(つまり与えられたターンがターゲットとするターンであれば)、かつnumが設定しておいたread_goalの値と等しくなけれれば(つまりそれがn回先のターゲットターンに達していなければ)、置ける場所を調べ再帰。帰ってきた値の平均を返す。
4. もしturnがtar_turnと等しくなければ(つまり与えられたターンがターゲットとするターンでなければ)、置ける場所を調べ再帰。

ここで、3と4の違いは、再起する際に与える引数numをインクリメントするかしないかです。調べたいのはn回先の自分または相手の手数であり、n手先のものではありません。そのため、調べたいターンでない場合はnumをインクリメントしないことで対応します。

nleastからこの関数を呼び出す場合は相手の手数を調べたいのでtar_turnに!(this -> turn)を与え、nmostから呼び出す際は自分の手数を調べたいので(this -> turn)を与えます。
1leastの場合、(turn == tar_turn)および(num == this -> read_goal[INT(this -> turn)])を早速満たすのでそこでとれる手数を数え返します。
1mostの場合、(num == this -> read_goal[INT(this -> turn)])は満たしますが(turn == tar_turn)を満たさないので再帰します。再帰先で(turn == tar_turn)および(num == this -> read_goal[INT(this -> turn)])を満たすので、そこで自分がとれる手数を数え、返します。

osero.cpp

int osero::check_place(BOARD * now, int num, bool turn, bool tar_turn){
    int i = 0, j = 0;
    int put_num = 0;
    BOARD place = 1;

    if (turn == tar_turn){
        if (num == this -> read_goal[INT(this -> turn)]){
            while (place){
                if (this -> check(now, i, j, turn)){
                    put_num++;
                }
                i++;
                if (i == 8) i = 0, j++;
                place = place << 1;
            }

            return put_num;
        }else{
            int place_sum = 0;
            BOARD board_leaf[2];

            while (place){
                if (this -> check(now, i, j, turn)){
                    board_leaf[0] = now[0];
                    board_leaf[1] = now[1];
                    put(board_leaf, i, j, turn);
                    place_sum += this -> check_place(board_leaf, num + 1, !turn, tar_turn);
                    put_num++;
                }
                i++;
                if (i == 8) i = 0, j++;
                place = place << 1;
            }

            if (put_num)
                return place_sum / put_num;
            else
                return 0;
        }
    }else{
        int place_sum;
        BOARD board_leaf[2];

        while (place){
            if (this -> check(now, i, j, turn)){
                board_leaf[0] = now[0];
                board_leaf[1] = now[1];
                put(now, i, j, turn);
                place_sum = this -> check_place(board_leaf, num, !turn, tar_turn);
            }
            i++;
            if (i == 8) i = 0, j++;
            place = place << 1;
        }

        return place_sum;
    }
}

実行ファイル

前回までの実験から、

進化方法はトーナメントを
交叉方法は一点交叉を
コンピュータの思考方法は1handを
プレイヤー役の思考方法はランダム、1hand、2hand、1least、1mostからランダム
突然変異の確率は3%

という条件で学習を行います。
また、前回の学習では100世代でも十分に学習できていましたが、今回対戦相手の思考方法が毎回変わるので一応1000世代までさせることにしました。

mainの上に書くやつ

今回から64ではなくboard_sizeと書くことにしました。
変更の予定はありませんが、名前を付けた方が分かりやすいと考えたためです。
あとはプレイヤー役の思考方法をまとめたenum classを作ったくらいで、特筆すべきことはありません。

run.cpp

#include "osero_genetic.h"

const int child = 32;
const int parent = 16;
const int entire = 1000;
const int board_size = 64;
const int mutation = 3;

enum class player{
    random,
    one_hand,
    two_hand,
    one_least,
    one_most,
    sentinel
};

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

void tournament(double ** eva, double ** new_eva, int * score);
void one_crossing(double ** par_eva, double ** chi_eva);

tournament

前回と同じですので割愛します。

one_crossing

突然変異もこの関数の中で行いました。

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() % board_size;
        mama = rand() % parent;
        do{
            papa = rand() % parent;
        }while (mama == papa);

        for (j = 0; j < board_size; j++){
            if (rand() % 100 > mutation){
                if (j < cut_place)
                    chi_eva[i][j] = par_eva[mama][j];
                else
                    chi_eva[i][j] = par_eva[papa][j];
            }else{
                chi_eva[i][j] = first_eva();
            }
        }
    }
}

main

各変数の宣言と評価値の初期化、学習、そしてもろもろのデータの出力を行っています。
前回のプログラムからかなり簡単になりました。
今回は32x1000の約3万試合ですので実行はすぐ終わります。

run.cpp

int main(void){
    int i, j;
    int computer = INT(PLAY_WAY::nhand_custom);
    int play_method;
    int score[child];
    int win_sum;
    double ** eva = new double *[child], ** par_eva = new double *[parent];
    osero_genetic * run;

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

    // setup eva
    for (i = 0; i < child; i++){
        eva[i] = new double[board_size];
        for (j = 0; j < board_size; j++){
            eva[i][j] = first_eva();
        }
    }
    for (i = 0; i < parent; i++){
        par_eva[i] = new double[board_size];
    }

    // file print
    fprintf(dataf, "generation,player,win_per\n");
    for (i = 0; i < board_size - 1; i++){
        fprintf(evaf, "%d,", i);    
    }
    fprintf(evaf, "%d\n", i);

    srand(99);
    for (int gene = 0; gene < entire; gene++){
        printf("[%4d/%4d]", gene + 1, entire);
        win_sum = 0;
        for (int indi = 0; indi < child; indi++){
            printf(".");
            play_method = rand() % INT(player::sentinel);
            switch (play_method){
                case INT(player::random):
                    run = new osero_genetic(
                        computer,
                        eva[indi],
                        INT(PLAY_WAY::random)
                    );
                    break;
                case INT(player::one_hand):
                    run = new osero_genetic(
                        computer,
                        eva[indi],
                        INT(PLAY_WAY::nhand)
                    );
                    break;
                case INT(player::two_hand):
                    run = new osero_genetic(
                        computer,
                        eva[indi],
                        INT(PLAY_WAY::nhand)
                    );
                    run -> read_goal[1] = 2;
                    break;
                case INT(player::one_least):
                    run = new osero_genetic(
                        computer,
                        eva[indi],
                        INT(PLAY_WAY::nleast)
                    );
                    break;
                case INT(player::one_most):
                    run = new osero_genetic(
                        computer,
                        eva[indi],
                        INT(PLAY_WAY::nmost)
                    );
                    break;
                default:
                    printf("program miss\n");
            }

            run -> computer = 0;
            run -> player = 1;

            score[indi] = run -> play();
            if (score[indi] > 0) win_sum++;

            delete run;
        }

        tournament(eva, par_eva, score);

        one_crossing(par_eva, eva);

        fprintf(dataf, "%d,%d,%d\n", gene, play_method, win_sum);

        printf("\n");
    }

    // output eva
    for (i = 0; i < child; i++){
        for (j = 0; j < board_size - 1; j++){
            fprintf(evaf, "%f,", eva[i][j]);
        }
        fprintf(evaf, "%f\n", eva[i][j]);
    }

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

    return 0;
}

実行結果

まず以下のプログラムを書きました。
拡張子が「.py」になっていますが、ipynbを使っています。

data.py

import pandas as pd
import matplotlib.pyplot as plt

df = pd.read_csv("data.csv")
df_eva = pd.read_csv("eva.csv")

generation = 1000
child = 32
board_size = 64
player = df["player"].nunique()
player_arr = [
    "random",
    "one_hand",
    "two_hand",
    "one_least",
    "one_most"
]

def plot(fig_name, xlabel, ylabel, directory):
    global x, y
    fig = plt.figure(figsize=(10, 10))
    plt.plot(x, y)
    plt.xlabel(xlabel)
    plt.ylabel(ylabel)
    plt.title(fig_name)
    plt.savefig(directory + fig_name)
    plt.clf()
    plt.close()

まず世代が進むごとに勝率がどれだけ変化したかを見ます。

data.py

x = [i for i in range(generation)]
y = df["win_per"] / child * 100

title = "win rate in generation"

plot(title, "generation", "win rate [%]", "fig/")

結果がこちら。

勝率はあまり上がっていないように見えます。
では、プレイヤー役の思考方法ごとの勝率の変化はどうなっているかを見てみます。

data.py

for i in range(player):
    df_ele = df.query("player == %d" % i)
    print("%s data" % player_arr[i])
    print("num: %d" % len(df_ele), end="\n\n")

    title = "win rate in generation and %s" % player_arr[i]
    x = df_ele["generation"]
    y = df_ele["win_per"]
    plot(title, "generation", "win rate [%]", "fig/")

random data
num: 82

one_hand data
num: 216

two_hand data
num: 210

one_least data
num: 240

one_most data
num: 252

なぜかrandomの回数が少ないですね。
グラフは以下の通り。

どの結果も大して勝率は向上していません。
ついでに各思考方法相手の平均勝率を見てみました。

data.py

y = []

for i in range(player):
    df_ele = df.query("player == %d" % i)
    y.append(df_ele["win_per"].mean() / child * 100)

title = "win rate in player"
x = player_arr
fig = plt.figure(figsize=(10, 10))
plt.bar(x, y)
plt.xlabel("player")
plt.ylabel("win rate [%]")
plt.title(title)
plt.savefig("fig/%s" % title)
plt.clf()
plt.close()

出来上がった評価値を見てみます。

data.py

eva_mean = open("eva_mean.csv", "w")

for i in range(board_size):
    eva_mean.write(str(df_eva[str(i)].mean()))
    if (i % 8 == 7):
        eva_mean.write("\n")
    else:
        eva_mean.write(",")

eva_mean.close()

絶対値が1に近いものもありますので、何かしらの特徴は出ていますね。
しかし予想していた形とは全く異なります。

フルバージョン

genetic_variety内に入っています。

次回は

今まで行ってきた方法は評価値を求めるうえではあまり有効ではない気がしてきました。
そもそも評価値を求めることはこのシリーズの最終目標ではないので、潔く撤退し次回は別の方法で有用な評価値を考えます。

次回