EGGXを用いたリバーシプログラムの作成

ひょんなことからαβ法を実装する機会を得て、いろいろな種類の題材で試してみたいなと思い、とりあえずリバーシプログラムをEGGXで作った。EGGXは使いやすいので、最近特に大好きなライブラリになってきた。

次なる題材としては機械学習かモンテカルロ法を用いて何らかのプログラムを作るつもり。

ちなみに、大富豪的にプログラムを作ったので計算量は考えていない。無駄な処理もある。適当に作ったオセロプログラムなので、ビットボードなどの技術は使っていない。本格的に作るならば真面目に設計を考えるべきだろう。

なお、プログラム中で使用した盤面の評価値はオセロの評価値を作ってみよう！ 羊の人工知能研究 ～将棋AI開発の日々～に載せられている値を使わせて頂きました。

#include 
#include 
#include 
#include 
#include 
#include 

#define HEIGHT 8
#define WIDTH 8

#define CELL_SIZE 40
#define WINDOW_HEIGHT (CELL_SIZE*HEIGHT)
#define WINDOW_WIDTH (CELL_SIZE*WIDTH)
#define EGGX_BLACK 0
#define EGGX_WHITE 1
#define EGGX_GRAY 9
#define EGGX_LEFT_CLICK 1
#define EGGX_RIGHT_CLICK 3

int win;

typedef enum {
    EMPTY = 0,
    BLACK = 1,
    WHITE = -1
} stone;

#define OPPONENT_STONE(s) (-s)

#define INFINITY 0xFFFF
#define MAX_DEPTH 5

int board[HEIGHT][WIDTH];

int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

int cost_board[HEIGHT][WIDTH] = {
    { 120, -20, 20,  5,  5, 20, -20, 120 },
    { -20, -40, -5, -5, -5, -5, -40, -20 },
    {  20,  -5, 15,  3,  3, 15,  -5,  20 },
    {   5,  -5,  3,  3,  3,  3,  -5,   5 },
    {   5,  -5,  3,  3,  3,  3,  -5,   5 },
    {  20,  -5, 15,  3,  3, 15,  -5,  20 },
    { -20, -40, -5, -5, -5, -5, -40, -20 },
    { 120, -20, 20,  5,  5, 20, -20, 120 }
};

void show_board(stone player);
void input_click(int *y, int *x);

void initialize_board(void);
//void print_board(void);
int evaluate(stone player);
bool is_in_board(int y, int x);
bool can_move(stone player, int y, int x);
bool move(stone player, int y, int x);
bool change_line(stone player, int y, int x, int diff);
void input(void);
bool opponent_input(void);
int solve(int *ans_y, int *ans_x, stone player, int depth, int alpha, int beta);

int count_stones(stone s);
bool is_end(void);
void output_winnner(void);

void show_board(stone player)
{
    int i, y, x;

    eggx_gclr(win);
    eggx_newpen(win, EGGX_BLACK);
    for (i = 0; i < WINDOW_WIDTH; i += CELL_SIZE)
        eggx_drawline(win, i, 0, i, WINDOW_HEIGHT);
    for (i = 0; i < WINDOW_HEIGHT; i += CELL_SIZE)
        eggx_drawline(win, 0, i, WINDOW_WIDTH, i);

    for (y = 0; y < WINDOW_HEIGHT; y += CELL_SIZE) {
        for (x = 0; x < WINDOW_WIDTH; x += CELL_SIZE) {
            int c = CELL_SIZE/2;

            if (player == BLACK && can_move(player, y/CELL_SIZE, x/CELL_SIZE)) {
                eggx_newpen(win, EGGX_GRAY);
                eggx_fillrect(win, x+1, y+1, CELL_SIZE-1, CELL_SIZE-1);
            }

            switch (board[y/CELL_SIZE][x/CELL_SIZE]) {
            case BLACK: eggx_newpen(win, EGGX_BLACK); break;
            case WHITE: eggx_newpen(win, EGGX_WHITE); break;
            case EMPTY: continue;
            }
            eggx_fillcirc(win, x+c, y+c, c-2, c-2);
        }
    }

    eggx_winname(win, "Black=%d,White=%d", count_stones(BLACK), count_stones(WHITE));
}

void input_click(int *y, int *x)
{
    int type, button;
    double dbl_x, dbl_y;

    for (;;) {
        eggx_ggetevent(&type, &button, &dbl_x, &dbl_y);
        if (type == ButtonPress && button == EGGX_LEFT_CLICK) {
            *x = (int)dbl_x/CELL_SIZE;
            *y = (int)dbl_y/CELL_SIZE;
            break;
        } else if (type == ButtonPress && button == EGGX_RIGHT_CLICK) {
            *x = -1;
            *y = -1;
            break;
        }
    }
}

void initialize_board(void)
{
    memset(board, EMPTY, sizeof(board));
    board[3][3] = WHITE;
    board[3][4] = BLACK;
    board[4][3] = BLACK;
    board[4][4] = WHITE;
}

/*
void print_board(void)
{
    int y, x;
    printf("  0 1 2 3 4 5 6 7\n");
    for (y = 0; y < HEIGHT; y++) {
        printf("%d", y);
        for (x = 0; x < WIDTH; x++) {
            switch (board[y][x]) {
            case EMPTY: printf(" -"); break;
            case WHITE: printf(" W"); break;
            case BLACK: printf(" B"); break;
            }
        }
        putchar('\n');
    }
    putchar('\n');
}
*/

int evaluate(stone player)
{
    int y, x;
    int sum = 0;
    for (y = 0; y < HEIGHT; y++)
        for (x = 0; x < WIDTH; x++)
            sum += board[y][x]*cost_board[y][x];
    return player*sum;
}

bool is_in_board(int y, int x)
{
    return (0 <= x) && (x < WIDTH) && (0 <= y) && (y < HEIGHT);
}

bool can_move(stone player, int y, int x)
{
    bool mov;
    int buf[HEIGHT][WIDTH];

    memcpy(buf, board, sizeof(buf));
    mov = move(player, y, x);
    memcpy(board, buf, sizeof(board));
    return mov;
}

bool move(stone player, int y, int x)
{
    int d;
    bool mov = false;

    for (d = 0; d < 8; d++)
        mov |= change_line(player, y, x, d);
    if (mov)
        board[y][x] = player;

    return mov;
}

bool change_line(stone player, int y, int x, int diff)
{
    int i;
    if (board[y][x] != EMPTY)
        return false;
    for (i = 1;; i++) {
        int ny = y + dy[diff]*i;
        int nx = x + dx[diff]*i;

        if (!is_in_board(ny, nx))
            return false;
        else if (board[ny][nx] == OPPONENT_STONE(player))
            continue;
        else if (board[ny][nx] == EMPTY)
            return false;
        else if (board[ny][nx] == player && i == 1)
            return false;
        else if (board[ny][nx] == player)
            break;
    }
    while (--i > 0)
        board[y+dy[diff]*i][x+dx[diff]*i] = player;
    return true;
}

void input(void)
{
    int y, x;
    input_click(&y, &x);
    if (y == -1 && x == -1)// pass
        return;
    else if (!move(BLACK, y, x))
        input();
    //printf("own:%d, %d\n", x, y);
}

bool opponent_input(void)
{
    int y, x;

    eggx_winname(win, "...");
    y = x = -1;
    solve(&y, &x, WHITE, 0, -INFINITY, INFINITY);
    if (y == -1 && x == -1) {
        //printf("opp:pass\n");
        return false;
    }
    move(WHITE, y, x);

    //printf("opp:%d, %d\n", x, y);
    return true;
}

int solve(int *ans_y, int *ans_x, stone player, int depth, int alpha, int beta)
{
    int y, x;
    int buf_y, buf_x;
    int buf[HEIGHT][WIDTH];
    if (depth == MAX_DEPTH)
        return evaluate(player);
    
    buf_y = buf_x = -1;
    memcpy(buf, board, sizeof(board));
    for (y = 0; y < HEIGHT; y++) {
        for (x = 0; x < WIDTH; x++) {
            if (can_move(player, y, x)) {
                int eval_value;
               
                move(player, y, x);
                eval_value = -solve(ans_y, ans_x, OPPONENT_STONE(player), depth+1, -beta, -alpha);
                memcpy(board, buf, sizeof(buf));

                if (alpha < eval_value) {
                    alpha = eval_value;
                    buf_y = y;
                    buf_x = x;
                    if (alpha >= beta)
                        goto END;
                }
            }
        }
    }

    if (buf_y == -1 && buf_x == -1)//pass
        return -solve(ans_y, ans_x, OPPONENT_STONE(player), depth+1, -beta, -alpha);

END:
    *ans_y = buf_y;
    *ans_x = buf_x;
    return alpha;
}

int count_stones(stone s)
{
    int y, x, c;
    c = 0;
    for (y = 0; y < HEIGHT; y++)
        for (x = 0; x < WIDTH; x++)
            if (board[y][x] == s)
                c++;
    return c;
}

bool is_end(void)
{
    return count_stones(EMPTY)==0;
}

void output_winnner(void)
{
    int b, w;
    b = count_stones(BLACK);
    w = count_stones(WHITE);

    if (b == w)
        eggx_winname(win, "Draw! Black=%d,White=%d", b, w);
    else
        eggx_winname(win, "%sWin! Black=%d,White=%d", (b>w?"Black":"White"), b, w);
}

int main(void)
{
    eggx_gsetinitialattributes(DISABLE, BOTTOM_LEFT_ORIGIN);
    eggx_gsetinitialbgcolor("#008000");
    win = eggx_gopen(WINDOW_WIDTH, WINDOW_HEIGHT);
    eggx_gclr(win);

    stone turn = BLACK;
    initialize_board();
    for (;;) {
        //print_board();
        show_board(turn);

        if (is_end())
            break;

        if (turn == BLACK)
            input();
        else
            opponent_input();
        turn = OPPONENT_STONE(turn);
    }

    output_winnner();
    eggx_ggetch();
    eggx_gclose(win);
    return 0;
}