rendered paste body#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 19int 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;}