コンピュータとオセロ対戦３ ～一手先まで読む～

前回の記事(ランダムに返す)

今回の目標

前回までで、ランダムに返してくるコンピュータとオセロ対戦ができるようになりました。
今回からはランダムではなく、勝てるように考えながら打ち返してくるプログラムを作ります。

かなり効率の悪いプログラムなので、完成版ではここで紹介する方法は使っていません。
参考程度にご覧ください。

ここから本編

方法は？

まず考えるのはこれです。
「一手先まで読んで返す」ということは、

1. 今自分が置ける場所をすべて探す
2. 1で見つけたそれぞれの場所に実際に置いてみて彼我の枚数差を数える、またはひっくりかえせる数を数える
3. 2で得た数字が最も大きい場所に置く

という動作が必要になります。
2についてですが、将来的に「n手先まで読んで返す」というプログラムが作りたいことから「実際においてみて、その後それぞれの枚数を数える」という方式で行きたいと思います。
「絶対に一手先までしか読まない！」という場合は後者のほうがいいと思います。その場合はcheck関数をうまく使えば行けるのかな。

プログラムでどう実現する？

次に考えるのはこれです。
将来的に「n手先まで読んで返す」をやりたいことから、構造体によるグラフを考えます。
つまり、下の写真のように、今の盤面状態から一手先、二手先を連結させてシミュレーションできるようにします。ひとつひとつの四角が構造体です。

完成版では構造体は使っていません。
参考程度に読んでください。

mainの上に書くやつ

増えました。
「Board_state」が構造体、その中の「score」が自分の駒の数-相手の駒の数、「board」がシミュレーションした盤面状態です。
今まで「board」と言っていた配列は「board_global」になりました。
あとは、シミュレーション用の関数がいくつか増えました。

1hand.c

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

#define NONE 0
#define WHITE 1
#define BLACK 2
#define SIZE 8

typedef struct BOARD{
    int score;
    char board[SIZE][SIZE];
} Board_state;

char board_global[SIZE][SIZE] = {NONE};
bool turn;

void setup(void);
void print(void);
void que(int * line, int * col);
void put(int line, int col, Board_state * now);
void put_global(int line, int col);
void stop(void);
bool check(int line, int col, Board_state * now);
bool check_global(int line, int col);
bool check_all(void);
bool all_none(void);
void count(Board_state * now);
void count_last(void);
void think(void);
int board_add(int line, int col);

stop

簡単な奴から行きます。
大丈夫だとは思いますが、何手先までも読もうとするとまあまあメモリを消費すると思うので一応非常停止関数を作っておきます。
決して「負けそうになった時に動かそう」だなんて考えてません（笑）。

1hand.c

void stop(void){
    printf("メモリ確保に失敗しました\n");
    exit(-1);
}

count

今までcount関数は、最後に勝敗を決めるために使っていましたが、今回は「自分の駒の数-相手の駒の数」を計算するために使います。
今までのcount関数はcount_lastに改名しました。

1hand.c

void count(Board_state * now){
    int i, j;
    int my = 0, opp = 0;

    for (i = 0; i < SIZE; i++){
        for (j = 0; j < SIZE; j++){
            if (now -> board[i][j] == WHITE) my++;
            else if (now -> board[i][j]  == BLACK) opp++;
        }
    }
    now -> score =  my - opp;
}

check

簡単な奴終わりました。
こちらもcountと同様、構造体用の関数です。今までのcheckはcheck_globalに改名しました。

1hand.c

bool check(int line, int col, Board_state * now){
    // 置ける　 true
    // 置けない false
    if (line >= SIZE || col >= SIZE){
        // printf("その位置には置けません\n");
        return false;
    }
    if (now -> board[line][col] != NONE){
        // printf("その位置には置けません\n");
        return false;
    }

    int my, opp;
    int i = 2;
    if (turn) my = BLACK, opp = WHITE;
    else my = WHITE, opp = BLACK;

    // 縦
    if (line - 1 >= 0 && now -> board[line - 1][col] == opp){
        while (line - i >= 0){
            if (now -> board[line - i][col] == NONE) break;
            if (now -> board[line - i][col] == my) return true;
            i++;
        }
        i = 2;
    }
    if (line + 1 < SIZE && now -> board[line + 1][col] == opp){
        while (line + i < SIZE){
            if (now -> board[line + i][col] == NONE) break;
            if (now -> board[line + i][col] == my) return true;
            i++;
        }
        i = 2;
    }
    /* 横と斜めも同様 */
    return false;
}

put

構造体用のput。今までのputはput_globalに改名しました。

1hand.c

void put(int line, int col, Board_state * now){
    int i, j;
    int my, opp;
    int pos1, pos2;

    if (turn){
        my = BLACK, opp = WHITE;
        now -> board[line][col] = BLACK;
    }else{
        my = WHITE, opp = BLACK;
        now -> board[line][col] = WHITE;
    }

    // 縦
    pos1 = -1;
    pos2 = -1;
    i = 2;
    if (line - 1 >= 0 && now -> board[line - 1][col] == opp){
        while (line - i >= 0){
            if (now -> board[line - i][col] == NONE) break;
            if (now -> board[line - i][col] == my){
                pos1 = i;
                break;
            }
            i++;
        }
        i = 2;
    }
    if (line + 1 < SIZE && now -> board[line + 1][col] == opp){
        while (line + i < SIZE){
            if (now -> board[line + i][col] == NONE) break;
            if (now -> board[line + i][col] == my){
                pos2 = i;
                break;
            }
            i++;
        }
        i = 2;
    }
    if (pos1 != -1){
        for (i = 1; i < pos1; i++){
            now -> board[line - i][col] = my;
        }
    }
    if (pos2 != -1){
        for (i = 1; i < pos2; i++){
            now -> board[line + i][col] = my;
        }
    }
    /* 横と斜めも同様 */
}

board_add

新たに一手先を考えるための関数です。
今の盤面状態をコピペし、駒を置き、その時のスコアを数え、そのスコアを返す動きをします。

1hand.c

int board_add(int line, int col){
    int i, j;
    char * line_array;
    Board_state leaf;

    if (&leaf == NULL) stop();

    for (i = 0; i < SIZE; i++){
        line_array = (&leaf) -> board[i];
        for (j = 0; j < SIZE; j++){
            line_array[j] = board_global[i][j];
        }
    }
    put(line, col, &leaf);
    count(&leaf);
    return (&leaf) -> score;
}

think

ついに思考部分です。
一手先までしか考えないなら影響はほとんどないと思いますが、重たい処理になることを恐れ、「* 2」などはすべて「>> 1」にしています。
流れとしては、

1. 置ける場所をすべてlineとcolにメモする。
2. 置ける場所すべてについて、以下の処理を行う。
3. 置ける場所に置くシミュレーションをし、board_addからスコアを返してもらう。
4. もし端っこを取れたら莫大なスコアを得られる。
5. もし今までの最大スコアだった場合、最大スコアを更新し、line_putとcol_putにそれぞれ記録する。
6. もし最大スコアと同じスコアを得られた場合、line_putとcol_putに候補として追加する。
7. もし候補が複数あった場合（subnumで判断）、ランダムで置く場所を選ぶ。
8. 置く。

です。説明では分からないと思うのでプログラム読んでください。

1hand.c

void think(void){
    int i, j, num = 0, subnum = 0;
    int score, max_score = -SIZE * SIZE;
    int line[SIZE >> 1] = {-1}, col[SIZE >> 1] = {-1};
    int line_put[SIZE], col_put[SIZE];

    for (i = 0; i < SIZE; i++){
        for (j = 0; j < SIZE; j++){
            if (check_global(i + 1, j + 1)){
                line[num] = i;
                col[num] = j;
                num++;
            }
        }
    }

    if (num == 0){
        printf("置ける場所がありません\n");
        return;
    }

    for (i = 0; i < num; i++){
        score = board_add(line[i], col[i]);
        if ((line[i] == 0 && col[i] == 0)
             || (line[i] == 0 && col[i] == SIZE - 1)
             || (line[i] == SIZE - 1 && col[i] == 0)
             || (line[i] == SIZE - 1 && col[i] == SIZE - 1))
            score = SIZE * SIZE;
        if (max_score < score){
            max_score = score;
            subnum = 0;
            line_put[0] = line[i];
            col_put[0] = col[i];
        }else if (max_score == score){
            subnum++;
            line_put[subnum] = line[i];
            col_put[subnum] = col[i];
        }
    }

    if (subnum){
        subnum = rand() % (subnum + 1);
        line_put[0] = line_put[subnum];
        col_put[0] = col_put[subnum];
    }

    printf("行: %d\n列: %d\n", line_put[0] + 1, col_put[0] + 1);

    put_global(line_put[0] + 1, col_put[0] + 1);

    return;
}

main

1hand.c

int main(){
    int line, col;
    bool my_check = true, old_check = true;
    srand((unsigned int)time(NULL));

    // check_allで反転させられるので
    turn = false;
    setup();

    long now = time(NULL);
    while ((my_check = check_all()) || all_none()){
        if (turn) printf("\nあなたのターンです\n");
        else printf("\nわたしのターンです\n");
        if (my_check){
            if (turn){
                que(&line, &col);
                while (!check_global(line, col)){
                    printf("その位置には置けません\n");
                    que(&line, &col);
                }
                put_global(line, col);
            }else{
                think();
            }
        }else{
            printf("置ける場所がありません\n");
        }
        if (!my_check && !old_check) break;
        old_check = my_check;
    }

    printf("\n試合時間: %ld秒\n", time(NULL) - now);
    count_last();

    return 0;
}

フルバージョン

この中の「1hand.c」です。

実際にやってみる

置いてくる場所が予想できるのであまり強くないですね。
ただプログラムなので、人間が考えないような予想外のところに置いてくることがたまにあります。

次回は

ランクアップして二手先まで読んで返すプログラムを考えます。
次回