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

#define TRUE 1
#define FALSE 0

#define EMPTY 0
#define BLACK 1
#define WHITE 2

#define WIN 1000
#define LOSS (-WIN)

#define DEPTH 3

#define MAX 16
#define VALID(x, y) (0 <= (x) && (x) < MAX && 0 <= (y) && (y) < MAX)

int board[MAX][MAX];

#define MAXSTONE 19

int stone[MAXSTONE][2][2];

void board_init() {
    int x, y;
    int b, w;
    b = w = 0;
    for (x = 0; x < MAX; x++) {
        for (y = 0; y < MAX; y++) {
            if (x == 0 && y == 5 ||
                x == 5 && y == 0 ||
                x == MAX-6 && y == MAX-1 ||
                x == MAX-1 && y == MAX-6)
                board[x][y] = EMPTY;
            else if (x + y < 6) {
                board[x][y] = BLACK;
                stone[b][0][0] = x;
                stone[b][0][1] = y;
                b++;
            }
            else if (x + y > MAX+MAX-8) {
                board[x][y] = WHITE;
                stone[w][1][0] = x;
                stone[w][1][1] = y;
                w++;
            }
            else
                board[x][y] = EMPTY;
        }
    }
}

int board_done(int player) {
    int black, white, value;
    int x, y;
    black = TRUE;
    white = TRUE;
    for (x = 0; x < 16; x++) {
        for (y = 0; y < 16; y++) {
            if (x == 0 && y == 5 ||
                x == 5 && y == 0 ||
                x == MAX-6 && y == MAX-1 ||
                x == MAX-1 && y == MAX-6)
                continue;
            else if (x + y < 6 && board[x][y] != WHITE)
                white = FALSE;
            else if (x + y > MAX+MAX-8 && board[x][y] != BLACK)
                black = FALSE;
        }
    }
    if (player == BLACK)
        value = black;
    else if (player == WHITE)
        value = white;
    return value;
}

int move[MAX*MAX*20*DEPTH*5];
int move_sp;
int move_s, from_x, from_y, to_x, to_y;

static void move_push(int s, int x1, int y1, int x2, int y2) {
    move[move_sp++] = s;
    move[move_sp++] = x1;
    move[move_sp++] = y1;
    move[move_sp++] = x2;
    move[move_sp++] = y2;
    if (move_sp > MAX*MAX*20*DEPTH*5) {
        printf("Stack overflow\n");
        getchar();
        exit(1);
    }
}

static void move_pop() {
    to_y = move[--move_sp];
    to_x = move[--move_sp];
    from_y = move[--move_sp];
    from_x = move[--move_sp];
    move_s = move[--move_sp];
}

int jump[MAX*MAX*2];
int jump_fp, jump_rp;
int jump_x, jump_y;

static void jump_push(int x, int y) {
    jump[jump_rp++] = x;
    jump[jump_rp++] = y;
}

static void jump_pop() {
    jump_x = jump[jump_fp++];
    jump_y = jump[jump_fp++];
}

int path[MAX][MAX];
int path_mark;

void path_init() {
    int x, y;
    for (x = 0; x < MAX; x++)
        for (y = 0; y < MAX; y++)
            path[x][y] = 0;
    path_mark = 0;
}

int dir_table[8][2] = {
    {-1, -1}, {-1, 0}, {-1, 1},
    {0, -1}, {0, 1},
    {1, -1}, {1, 0}, {1, 1},
};

void move_gen_one(int s, int x, int y) {
    int dir, dx, dy;
    int ax, ay, bx, by;
    jump_fp = jump_rp = 0;
    path_mark++;
    for (dir = 0; dir < 8; dir++) {
        dx = dir_table[dir][0];
        dy = dir_table[dir][1];
        ax = x + dx;
        ay = y + dy;
        if (VALID(ax, ay)) {
            if (board[ax][ay] == EMPTY)
                move_push(s, x, y, ax, ay);
            else {
                bx = ax + dx;
                by = ay + dy;
                if (VALID(bx, by) && board[bx][by] == EMPTY)
                    jump_push(bx, by);
            }
        }
    }
    while (jump_rp > jump_fp) {
        jump_pop();
        move_push(s, x, y, jump_x, jump_y);
        path[jump_x][jump_y] = path_mark;
        for (dir = 0; dir < 8; dir++) {
            dx = dir_table[dir][0];
            dy = dir_table[dir][1];
            ax = jump_x + dx;
            ay = jump_y + dy;
            if (VALID(ax, ay) && board[ax][ay] != EMPTY) {
                bx = ax + dx;
                by = ay + dy;
                if (VALID(bx, by) && board[bx][by] == EMPTY &&
                    path[bx][by] != path_mark)
                    jump_push(bx, by);
            }
        }
    }
}

void move_gen(int player) {
    int p, s, x, y;
    p = player - 1;
    for (s = 0; s < MAXSTONE; s++) {
        x = stone[s][p][0];
        y = stone[s][p][1];
        move_gen_one(s, x, y);
    }
}

int board_eval(int player) {
    int black, white, value;
    int s, x, y;
    black = 0;
    white = 0;
    for (s = 0; s < MAXSTONE; s++) {
        x = stone[s][0][0];
        y = stone[s][0][1];
        black += MAX+MAX-7 - x - y;
        if (x == MAX-1 || y == MAX-1)
            black++;
        x = stone[s][1][0];
        y = stone[s][1][1];
        white += x + y - 5;
        if (x == 0 || y == 0)
            white++;
    }
    if (player == BLACK)
        value = white - black;
    else if (player == WHITE)
        value = black - white;
    return value;
}

static int player_next(int player) {
    int next;
    if (player == BLACK)
        next = WHITE;
    else if (player == WHITE)
        next = BLACK;
    return next;
}

int play[DEPTH*5];
int play_sp;

static void move_play(int p) {
    board[to_x][to_y] = board[from_x][from_y];
    board[from_x][from_y] = EMPTY;
    stone[move_s][p][0] = to_x;
    stone[move_s][p][1] = to_y;
    play[play_sp++] = move_s;
    play[play_sp++] = from_x;
    play[play_sp++] = from_y;
    play[play_sp++] = to_x;
    play[play_sp++] = to_y;
}

static void move_undo(int p) {
    to_y = play[--play_sp];
    to_x = play[--play_sp];
    from_y = play[--play_sp];
    from_x = play[--play_sp];
    move_s = play[--play_sp];
    board[from_x][from_y] = board[to_x][to_y];
    board[to_x][to_y] = EMPTY;
    stone[move_s][p][0] = from_x;
    stone[move_s][p][1] = from_y;
}

int alphabeta(int player, int alpha, int beta, int depth) {
    int next, value;
    int sp;
    int p;
    if (depth == 0)
        return board_eval(player);
    if (board_done(player))
        return WIN;
    next = player_next(player);
    sp = move_sp;
    p = player - 1;
    move_gen(player);
    while (move_sp > sp) {
        move_pop();
        move_play(p);
        value = -alphabeta(next, -beta, -alpha, depth-1);
        move_undo(p);
        if (value > alpha)
            alpha = value;
        if (alpha >= beta)
            break;
    }
    move_sp = sp;
    return alpha;
}

void ai_play(int player) {
    int next, alpha, beta, depth, value;
    int s, x1, y1, x2, y2;
    int p;
    next = player_next(player);
    alpha = LOSS;
    beta = WIN;
    depth = DEPTH;
    move_sp = 0;
    play_sp = 0;
    path_init();
    p = player - 1;
    move_gen(player);
    while (move_sp > 0) {
        move_pop();
        move_play(p);
        value = -alphabeta(next, -beta, -alpha, depth-1);
        move_undo(p);
        if (value > alpha) {
            s = move_s;
            x1 = from_x;
            y1 = from_y;
            x2 = to_x;
            y2 = to_y;
            alpha = value;
        }
    }
    move_s = s;
    from_x = x1;
    from_y = y1;
    to_x = x2;
    to_y = y2;
    printf("%2d %2d -> %2d %2d (%+2d)\n", x1, y1, x2, y2, alpha);
    move_play(p);
}

int main() {
    int player;
    board_init();
#ifdef GUI
    ui_init();
    board_draw();
#endif
    player = BLACK;
    while (1) {
        ai_play(player);
#ifdef GUI
        board_draw();
#endif
        if (board_done(player))
            break;
        player = player_next(player);
    }
#ifdef GUI
    ui_fini();
#endif
    return 0;
}