コンピュータとオセロ対戦14 ～BitBoard～

前回

今回の目標

前回、「次回は勉強会だ」と書きましたが、勉強していると知らないことが多すぎて一回ではまとめきれないと分かったので、今回から何回かに分けて機械学習の準備を行っていきます。

今回はBitBoardに挑戦していきます。今までのボード情報はchar型二次元配列に保存していたためデータ集めに時間がかかっていましたが、これでたぶん早くなるはずです。
また、今までのデータ集めはすべてC言語で行っていましたが、条件替えのたびにプログラムを変えるのも面倒だったのでc++で作っていきたいと思います。

今回はひとまず普通にオセロができるようになることを目標とし、データ集め用のカスタムは必要な時に行います。

また、盤面は8x8で固定することにしました。
どうせ6x6や4x4の学習はしないと思いますし。
たまにプログラムの中に「数字 << 3」とありますが、これは行番号を8倍しているだけです。

ここから本編

最終目標は関数ポインタを用いて、一つのクラスで様々な状況に対応してもらうこと！　です。
そのために

ヘッダファイル

unsigned long(64bit)をボード情報に使うため、BOARDという名前を付けておきました。BOARDの二次元配列で黒と白の情報をそれぞれ保存します。
white_num、black_num、score、PLAYERは今回使ってないですがいずれ使うかもしれないので入れてあります。
play_methodは、思考方法を書いた関数のポインタをあらかじめ入れておく配列です。main関数などでPLAY_WAYのなかから指定を行い、その番号をplay_methodの添え字に入れることで思考方法を特定します。

osero.h

#ifndef osero_h
#define osero_h

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

const bool BLACK = false;
const bool WHITE = true;

typedef unsigned long BOARD;

enum class TURN{
    black,
    white
};

enum class PLAY_WAY{
    human,
    random,
    sentinel
};

class osero{
    private:
        // board
        BOARD bw[2];         // 盤面情報
        int black_num = 0;   // 今回は使わない
        int white_num = 0;   // 今回は使わない
        char score[8][8];    // 今回は使わない

        // other
        const int SIZE = 8;
        bool PLAYER;
        bool turn = BLACK;
        int bmethod, wmethod;
        void (osero:: * play_method[static_cast<int>(PLAY_WAY::sentinel)]) (int *, int *) = {
            &osero::que,
            &osero::random
        };

        // function
        bool check(int line, int col);
        bool check_all(void);
        void put(int line, int col);
        void setup(void);
        void printb(void);
        void count(void);
        void que(int * line, int * col);
        void random(int * line, int * col);
        int popcount(BOARD now);

    public:
        osero(int player_b, int player_w);
        ~osero();
        void play(void);
};

#endif

ソースファイル

上に書くやつ

ほぼないですが。

osero.cpp

#include <time.h>

#include "osero.h"

extern const bool BLACK;
extern const bool WHITE;

コンストラクタ

ボードの初期位置に石を置いています。
また、黒と白それぞれがどの打ち方をするのかを保存しておきます。
このクラスをmain関数などで呼び出す際は、PLAY_WAYを使って指定します。

osero.cpp

osero::osero(int player_b, int player_w){
    this -> bw[static_cast<int>(TURN::black)] = 0x810000000;
    this -> bw[static_cast<int>(TURN::white)] = 0x1008000000;
    this -> bmethod = player_b;
    this -> wmethod = player_w;

    return;
}

デストラクタ

特に何もしません。

osero.cpp

osero:: ~osero(){
    return;
}

printb

プリントしないと、とにかくすべてのプログラムにおいてデバッグができないのでまずこれ作ります。

osero.cpp

void osero::printb(void){
    int i, j;

    printf("\n  ");
    for (i = 0; i < this -> SIZE; i++) printf(" %d ", i + 1);

    printf("\n -------------------------\n");
    for (i = 0; i < this -> SIZE << 3; i++){
        if (i % this -> SIZE == 0) printf("%d", (i + this -> SIZE) >> 3);
        if (this -> bw[static_cast<int>(TURN::black)] & static_cast<BOARD>(1) << i) printf("|○");
        else if (this -> bw[static_cast<int>(TURN::white)] & static_cast<BOARD>(1) << i) printf("|●");
        else printf("|  ");
        if (i % this -> SIZE == 7) printf("|\n -------------------------\n");
    }

    return;
}

que

人が入力してプレイするための関数です。

osero.cpp

void osero::que(int * line, int * col){
    printf("行: ");
    scanf("%d", line);
    printf("列: ");
    scanf("%d", col);
    *line -= 1;
    *col -= 1;
    if (!(this -> check(*line, *col))){
        printf("その場所には置けません\n");
        this -> que(line, col);
    }
}

check_all

置ける場所があるかどうか調べる関数。

osero.cpp

bool osero::check_all(void){
    int i, j;

    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            if (this -> check(i, j)) return true;

    return false;
}

count

今回はそんなに必要ないですがカウント関数。

osero.cpp

void osero::count(void){
    int black, white;

    this -> black_num = this -> popcount(this -> bw[static_cast<int>(TURN::black)]);
    this -> white_num = this -> popcount(this -> bw[static_cast<int>(TURN::white)]);

    printf("%d\n", this -> black_num);
    printf("%d\n", this -> white_num);
}

popcount

アルゴリズムはこちらをパクりました。

osero.cpp

int osero::popcount(BOARD now){
    now = now - ((now >> 1) & 0x5555555555555555);
    now = (now & 0x3333333333333333) + ((now >> 2) & 0x3333333333333333);
    now = (now + (now >> 4)) & 0x0f0f0f0f0f0f0f0f;
    now = now + (now >> 8);
    now = now + (now >> 16);
    now = now + (now >> 32);

    return now & 0x7f;
}

check

指定した場所に置けるかどうか調べる関数。
前とあまり変わっていません。

osero.cpp

bool osero::check(int line, int col){
    if (this -> bw[static_cast<int>(TURN::black)] & static_cast<BOARD>(1) << ((line << 3) + col)) return false;
    if (this -> bw[static_cast<int>(TURN::white)] & static_cast<BOARD>(1) << ((line << 3) + col)) return false;

    int x, y;
    int line_x, col_y;
    bool my = this -> turn, opp = !(this -> turn);

    for (x = -1; x <= 1; x++){
        for (y = -1; y <= 1; y++){
            if (x != 0 || y != 0){
                line_x = line + x;
                col_y = col + y;
                while ((this -> bw[opp] & static_cast<BOARD>(1) << ((line_x << 3) + col_y))
                       && 0 <= x + line_x && x + line_x < this -> SIZE
                       && 0 <= y + col_y && y + col_y < this -> SIZE){
                    if (this -> bw[my] & static_cast<BOARD>(1) << ((line_x + x << 3) + col_y + y))
                        return true;
                    line_x += x;
                    col_y += y;
                }
            }
        }
    }

    return false;
}

put

置く関数。
ひっくりかえす場所をinver変数に保存しておき、あとで足したり引いたりしています。

osero.cpp

void osero::put(int line, int col){
    int x, y;
    int line_x, col_y, num;
    bool my = this -> turn, opp = !(this -> turn);
    BOARD inver;

    this -> bw[my] = this -> bw[my] | static_cast<BOARD>(1) << ((line << 3) + col); 

    for (x = -1; x <= 1; x++){
        for (y = -1; y <= 1; y++){
            if (x != 0 || y != 0){
                inver = 0;
                line_x = line + x;
                col_y = col + y;
                place = static_cast<BOARD>(1) << ((line_x << 3) + col_y);
                while ((this -> bw[opp] & place)
                       && 0 <= x + line_x && x + line_x < this -> SIZE
                       && 0 <= y + col_y && y + col_y < this -> SIZE){
                    inver = inver | place;
                    line_x += x;
                    col_y += y;
                    place = static_cast<BOARD>(1) << ((line_x << 3) + col_y);
                }
                if (this -> bw[my] & place){
                    this -> bw[my] = this -> bw[my] + inver;
                    this -> bw[opp] = this -> bw[opp] - inver;
                }
            }
        }
    }
}

play

ここで関数ポインタを作り、play_methodから指定した関数を入れています。
あとは今までのmain関数と大して変わりません。

osero.cpp

void osero::play(void){
    double start = clock();

    srand((unsigned int)time(NULL));
    bool can = true, old_can = true;
    int line, col;
    void (osero:: * player[2]) (int *, int *) = {
        play_method[this -> bmethod],
        play_method[this -> wmethod]
    };

    printf("黒: ○\n白: ●\n\n");

    this -> printb();

    while((can = check_all()) || old_can){
        if (this -> turn == static_cast<bool>(TURN::black))
            printf("黒のターンです\n");
        else
            printf("白のターンです\n");
        
        if (can){
            (this->*player[static_cast<int>(this -> turn)])(&line, &col);
            this -> put(line, col);
            this -> printb();
        }else{
            printf("置ける場所がありません\n");
        }
        this -> turn = !(this -> turn);
        old_can = can;
    }

    printf("\n試合時間: %.4lf秒\n", (clock() - start) / 1000000);
    count();
}

実行ファイル

ここで黒と白がそれぞれどんな打ち方をするか指定します。
下のプログラムでは黒が人、白がランダムに打ち返します。
コメントアウトしている例ではランダム同士の対戦です。
もちろん人同士や、黒がランダムで白が人もできます。関数を追加すれば簡単に「ランダム VS nhand」「1hand VS 2hand」も可能になります。・・・なるはずです。

run.cpp

#include "osero.h"

int main(void){
    osero * run = new osero(
        static_cast<int>(PLAY_WAY::human),
        static_cast<int>(PLAY_WAY::random)
        // static_cast<int>(PLAY_WAY::random),
        // static_cast<int>(PLAY_WAY::random)
    );
    run -> play();
    delete run;

    return 0;
}

フルバージョン

実際にやってみた

ふつうにできました。

次回は

評価値について考えます。

次回