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;
}

ACM-ICPC 2007年 国内予選 問題A ICPC 得点集計ソフトウェア

問題A:ICPC 得点集計ソフトウェア

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while (cin >> n, n) {
        int buf, sum, sz;
        vector<int> s;

        while(n--) {
            cin >> buf;
               s.push_back(buf);
        }
        sort(s.begin(), s.end());

        sum = 0;
        sz = s.size();
        for (int i = 1; i < sz-1; i++)
            sum += s[i];
        cout << sum/(sz-2) << endl;
    }
    return 0;
}

Project Euler Problem 10

Problem 10

エラトステネスの篩を使って、総和の計算をするだけ。

Schemeのコードは、Scheme:数遊び:素数列に載せられているgemmaさんのコードを参考、もとい、パクらせていただいた。

Scheme

(use srfi-1)
(use srfi-42)
(use numbers)

(define (primes n)
  (let loop ((l (unfold (lambda (x) (> x n)) values (lambda (x) (+ x 2)) 3))
             (primes-list '(2)))
    (let ((m (car l)))
      (if (> (* m m) n)
          (append primes-list l)
          (loop (remove (lambda (x) (zero? (modulo x m))) l)
                (cons m primes-list))))))

(define (p010)
  ;リストが長すぎて、applyを呼び出すとエラーが起きる……
  ;(print (apply + (primes 2000000)))
  (print (sum-ec (: i (primes 2000000)) i)))

(p010)

C++

#include <cstdio>
#include <cstring>

#define LIM 2000000
char primes[LIM+1];

void e()
{
    memset(primes, 1, sizeof(primes));
    primes[1] = 0;
    for (int i = 2; i <= LIM; i++)
        for (int j = 2*i; j <= LIM; j += i)
            primes[j] = 0;
}

int main()
{
    long long ans;

    e();
    ans = 0;
    for (int i = 1; i <= LIM; i++)
        if (primes[i])
            ans += i;

    printf("%lld\n", ans);
    return 0;
}

EGGXを用いたマンデルブロ集合の色付き描画

前回の記事のプログラムを少々変更してマンデルブロ集合の図を色付けした。

数列の発散、収束を計算していた関数と、それに関連する部分を少しだけ変えたプログラムを次に示す。発散する点においては、発散するまでに計算した回数を利用して色付けした。

#include <complex>
#include <eggx.h>
using namespace std;

#define BASE_SCALE 300

#define RE_START -2
#define RE_END 1
#define RE_LENGTH (RE_END - RE_START)
#define RE_STEP ((double)RE_LENGTH/WIDTH)
#define RE2X(r) (int)((r-RE_START)*BASE_SCALE)

#define IM_START -1
#define IM_END 1
#define IM_LENGTH (IM_END - IM_START)
#define IM_STEP ((double)IM_LENGTH/HEIGHT)
#define IM2Y(i) (int)((i-IM_START)*BASE_SCALE)

#define WIDTH (BASE_SCALE * RE_LENGTH)
#define HEIGHT (BASE_SCALE * IM_LENGTH)

#define INF 2
#define MAX_ITER 1000

#define EGGX_BLACK 0

int calc(complex<double> c)
{
    int n;
    complex<double> z;
    for (n = 0; n < MAX_ITER; n++) {
        z = z*z + c;
        if (abs(z) >= INF)
            return n%15+1;
    }
    return EGGX_BLACK;
}

void draw(int win)
{
    double re, im;
    for (re = RE_START; re <= RE_END; re += RE_STEP) {
        for (im = IM_START; im <= IM_END; im += IM_STEP) {
            int color = calc(complex<double>(re, im));
            newpen(win, color);
            pset(win, RE2X(re), IM2Y(im));
        }
    }
}

int main()
{
    int win;

    gsetinitialbgcolor("gray");
    win = gopen(WIDTH, HEIGHT);

    draw(win);

    ggetch();
    gclose(win);
    return 0;
} 

EGGXを用いたマンデルブロ集合の描画

EGGXを使ってマンデルブロ集合を描く。

結論から示す。マンデルブロ集合を描いたとき、次のような図となる。

以下、どのようにこの図を描いていくのかを説明する。

まず、複素数列{Zn}を次のように定義する。
Zn+1 = (Zn)ˆ2 + C
Z0 = 0
ただし、Z0は初項であり、Zn+1におけるCは複素平面上の一点を意味する。

このときマンデルブロ集合は、「数列{Zn}においてn->∞としたとき、その数列が発散しないような複素数C全体の集合」と定義される。

では、マンデルブロ集合を図として描くときの手順を示す。
(1) 実部の区間を[-2, 1]、虚部の区間を[-1, 1]とし、その区間を描画領域とする。
(2) (1)の区間内にある全ての点を、上述の数列{Zn}のCとして与える。
(3) (2)で決めた数列{Zn}においてn->∞としたとき、{Zn}が発散するならば白、収束するならば黒で複素平面上の点であるCの位置に、点を描く。

以上が、基本的な手順となる。ただ、マンデルブロ集合は{Zn}が収束するような点全体として定義されるので、発散する点はマンデルブロ集合に含まれない。けれども、手順(3)からも判るように、ここでは発散する点を白で描いている。

マンデルブロ集合を描く、EGGXを用いたC++のソースコードを次に示す。実際にEGGXを用いてコンパイルする場合は、拡張子を.ccにすること。

#include <complex>
#include <eggx.h>
using namespace std;

#define BASE_SCALE 300

#define RE_START -2
#define RE_END 1
#define RE_LENGTH (RE_END - RE_START)
#define RE_STEP ((double)RE_LENGTH/WIDTH)
#define RE2X(r) (int)((r-RE_START)*BASE_SCALE)

#define IM_START -1
#define IM_END 1
#define IM_LENGTH (IM_END - IM_START)
#define IM_STEP ((double)IM_LENGTH/HEIGHT)
#define IM2Y(i) (int)((i-IM_START)*BASE_SCALE)

#define WIDTH (BASE_SCALE * RE_LENGTH)
#define HEIGHT (BASE_SCALE * IM_LENGTH)

#define INF 2
#define MAX_ITER 1000

#define EGGX_BLACK 0
#define EGGX_WHITE 1

bool not_inf(complex<double> c)
{
    complex<double> z;

    /*
        数列{Zn}を実際にn->∞として計算することは無理なので、
        n->MAX_ITERとして計算している。
    */
    for (int n = 0; n < MAX_ITER; n++) {
        z = z*z + c;

        /*
            |Zn|が2以上に達したら|Zn+1| > |Zn|なので、
            数列は必ず発散する。
        */
        if (abs(z) >= INF)
            return false;
    }
    return true;
}

/*
//C版(複素数を使わず書く)
//引数のa,bはC++版の
//複素数cをc = a + i*bと表したときのa, b。
int not_inf(double a, double b)
{
    int n;
    double re, im;
    re = im = 0;
    for (n = 0; n < MAX_ITER; n++) {
        double tr = re, ti = im;
        re = tr*tr - ti*ti + a;
        im = 2*tr*ti + b;

        if (sqrt(re*re+im*im) >= INF)
            return 0;
        //また、上のif文は以下と同値
        //if (re*re+im*im >= INF*INF)
        //  return 0;
    }
    return 1;
}
*/

void draw(int win)
{
    double re, im;
    for (re = RE_START; re <= RE_END; re += RE_STEP) {
        for (im = IM_START; im <= IM_END; im += IM_STEP) {
            bool f = not_inf(complex<double>(re, im));
            newpen(win, f?EGGX_BLACK:EGGX_WHITE);

            /*
                RE2X,IM2Yを呼び出し、複素平面内の点を
                ウィンドウの座標に変換して描いている。
            */
            pset(win, RE2X(re), IM2Y(im));
        }
    }
}

int main()
{
    int win;

    gsetinitialbgcolor("gray");
    win = gopen(WIDTH, HEIGHT);

    draw(win);

    ggetch();
    gclose(win);
    return 0;
}

なお、ウェブ上に載せられているマンデルブロ集合の図は、たいてい、周囲が色付けされている。通常は、数列が無限大に発散するまでに計算された回数を用いて色付けする。上述のプログラムに色付けの機能を加えるためには、上に示した手順(3)において「{Zn}が発散するならば白」としている部分の処理を変えればよい。

Project Euler Problem 9

Problem 9

a, b, cは全て自然数で、a < b < cかつa + b + c = 1000であるから、
0 < a < 1000/3, a < b < (1000-a)/2, c = 1000 - (a+b)という条件の下で調べれば良い。

証明:
a + b + c = 1000より、c = 1000 - (a+b)となり、b < cに代入すると、
b < 1000 - (a+b)
<=> b < (1000-a)/2
よって、a < b < (1000-a)/2となる。
またこれより、
a < (1000-a)/2
<=> a < 1000/3
よって、0 < a < 1000/3となる。

Scheme

(use srfi-42)

(define n 1000)
(define (p009)
  (print (car (list-ec (: a (floor (/ n 3)))
                       (: b a (floor (/ (- n a) 2)))
                       (:let c (- n a b))
                (if (eq? (+ (* a a) (* b b)) (* c c)))
                (* a b c)))))

(p009)

C++

#include <cstdio>

int main()
{
    for (int a = 1; a < 1000/3; a++)
    for (int b = a; b < (1000-a)/2; b++)
    {
        int c = 1000-(a+b);
        if (a*a+b*b==c*c) {
            printf("%d\n", a*b*c);
            goto end;
        }
    }
end:
    return 0;
}

Project Euler Problem 8

Problem 8

Schemeのコードが、すこぶる醜い。入力数値のリストを作り、先頭から5つ、二番目から5つ、,,,、(リストの要素数-4)番目から5つ、と数値を取って全ての並びを求めている。そうして求めた各リストに対して積を計算し、最大を得た。けれども並びの求め方が、醜い。もっとうまく書けそうだ。

Scheme

(use srfi-1)

(define (p008)
  (define (integer->digit c) (- c (char->integer #\0)))
  (define (input-digits)
    (let ((c (read-char)))
      (cond ((eof-object? c) '())
            ((char-numeric? c)
              (cons (integer->digit (char->integer c)) (input-digits)))
            (else (input-digits)))))
  (define (split-list ls)
    (map (lambda (x) 
           (receive (_ t) (split-at ls x)
             (take t 5)))
         (iota (- (length ls) 4))))
  (print (apply max (map (lambda (x) (apply * x)) (split-list (input-digits))))))

(p008)

C++

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int main()
{
    char c;
    int xs[5], ma;

    ma = 0;
    memset(xs, 0, sizeof(xs));
    while ((c = getchar()) != EOF) {
        if (!isdigit(c))
            continue;
        xs[4] = c-'0';

        int p = 1;
        for (int i = 0; i < 5; i++)
            p *= xs[i];
        ma = max(ma, p);

        for (int i = 0; i < 4; i++)
            xs[i] = xs[i+1];
    }
    printf("%d\n", ma);

    return 0;
}