#include <string.h> #include <stdio.h> #include <stdlib.h> #include #include //returns a pair <direction, coordinate> where direction is North, Northeast, etc (clockwise) //and coordinate is in the form x8 + y std::vector< std::pair<int, int> > get_directions(int board[][8], int x, int y, int color) { std::vector< std::pair<int, int> > directions; if(board[x][y]) { return directions; } //north if((y < 6) && (board[x][y+1] == -color)) { for(int i=y+2; i < 8; i++) { if(!board[x][i]) { break; } else if(board[x][i] == color) { directions.push_back(std::make_pair<int, int>(0, x8+i)); break; } } } //northeast if((y < 6) && (x < 6) && (board[x+1][y+1] == -color)) { for(int i=0; (x+i+2 < 8) && (y+i+2 < 8); i++) { if(!board[x+i+2][y+i+2]) { break; } else if(board[x+i+2][y+i+2] == color) { directions.push_back(std::make_pair<int, int>(1, (x+i+2)8+(y+i+2))); break; } } } //east if((x < 6) && (board[x+1][y] == -color)) { for(int i=x+2; i < 8; i++) { if(!board[i][y]) { break; } else if(board[i][y] == color) { directions.push_back(std::make_pair<int, int>(2, i8+y)); break; } } } //southeast if((y > 1) && (x < 6) && (board[x+1][y-1] == -color)) { for(int i=0; (x+i+2 < 8) && (y-i-2 >= 0); i++) { if(!board[x+i+2][y-i-2]) { break; } else if(board[x+i+2][y-i-2] == color) { directions.push_back(std::make_pair<int, int>(3, (x+i+2)8+(y-i-2))); break; } } } //south if((y > 1) && (board[x][y-1] == -color)) { for(int i=y-2; i >= 0; i--) { if(!board[x][i]) { break; } else if(board[x][i] == color) { directions.push_back(std::make_pair<int, int>(4, x8+i)); break; } } } //southwest if((y > 1) && (x > 1) && (board[x-1][y-1] == -color)) { for(int i=0; (x-i-2 >= 0) && (y-i-2 >= 0); i++) { if(!board[x-i-2][y-i-2]) { break; } else if(board[x-i-2][y-i-2] == color) { directions.push_back(std::make_pair<int, int>(5, (x-i-2)8+(y-i-2))); break; } } } //west if((x > 1) && (board[x-1][y] == -color)) { for(int i=x-2; i >= 0; i--) { if(!board[i][y]) { break; } else if(board[i][y] == color) { directions.push_back(std::make_pair<int, int>(6, i8+y)); break; } } } //northwest if((y < 6) && (x > 1) && (board[x-1][y+1] == -color)) { for(int i=0; (x-i-2 >= 0) && (y+i+2 < 8); i++) { if(!board[x-i-2][y+i+2]) { break; } else if(board[x-i-2][y+i+2] == color) { directions.push_back(std::make_pair<int, int>(7, (x-i-2)8+(y+i+2))); break; } } } return directions; } //returns all moves for a players on the current board. Each pair has a coordinate in the form //x8+y, and a vector of pairs, each pair contains a direction and an endpoint in the form x8+y std::vector< std::pair<int, std::vector< std::pair<int, int> > > > get_moves(int board[][8], int color) { std::vector< std::pair<int, std::vector< std::pair<int, int> > > > moves; for(int i=0; i < 8; i++) { for(int j=0; j < 8; j++) { moves.push_back(std::make_pair<int, std::vector< std::pair<int, int> > >(i8+j, get_directions(board, i, j, color))); if(!moves.back().second.size()) { moves.pop_back(); } } } return moves; } //makes a move and flips the appropriate pieces void make_move(int board[][8], int x, int y, int color, std::vector< std::pair<int, int> > directions) { for(auto it=directions.begin(); it != directions.end(); it++) { int i = x; int j = y; while((i != ((*it).second/8)) || (j != ((*it).second&7))) { board[i][j] = color; if(i < ((*it).second/8)) { i++; } else if((i > (*it).second/8)) { i--; } if(j < ((*it).second&7)) { j++; } else if(j > ((*it).second&7)) { j--; } } } }
//undoes a move (needs directions data so it can unflip stuff) void undo_move(int board[][8], int x, int y, int color, std::vector< std::pair<int, int> > directions) { for(auto it=directions.begin(); it != directions.end(); it++) { int i = x; int j = y; while((i != ((*it).second/8)) || (j != ((*it).second&7))) { board[i][j] = -color; if(i < ((*it).second/8)) { i++; } else if((i > (*it).second/8)) { i--; } if(j < ((*it).second&7)) { j++; } else if(j > ((*it).second&7)) { j--; } } board[i][j] = color; } board[x][y] = 0; } void print(int board[][8]) { for(int i=7; i >= 0; i--) { printf("%d ", i); for(int j=0; j < 8; j++) { if(!board[j][i]) { printf("-"); } else if(board[j][i] == 1) { printf("O"); } else { printf("X"); } } printf("\n"); } printf(" "); for(int i=0; i < 8; i++) { printf("%d", i); } printf("\n\n"); } int score(int board[][8], int color) { int sum = 0; for(int i=0; i < 8; i++) { for(int j=0; j < 8; j++) { sum += board[i][j]; } } return sum * color; } //Largely the same pseudocode from the negamax wikipedia article, but adapted for the rules of othello int negamax_aux(int board[][8], int color, int depth, int alpha, int beta) { if(depth == 0) { return score(board, color); } std::vector< std::pair<int, std::vector< std::pair<int, int> > > > moves = get_moves(board, color); if(moves.size() == 0) { if(get_moves(board, -color).size() == 0) { return score(board, color); } int val = -negamax_aux(board, -color, depth-1, -beta, -alpha); if(val >= beta) { return val; } if(val > alpha) { alpha = val; } } else { for(auto it=moves.begin(); it != moves.end(); it++) { make_move(board, (*it).first/8, (*it).first&7, color, (*it).second); int val = -negamax_aux(board, -color, depth-1, -beta, -alpha); undo_move(board, (*it).first/8, (*it).first&7, color, (*it).second); if(val >= beta) { return val; } if(val > alpha) { alpha = val; } } } return alpha; } //parent function to negamax_aux, this function actually maintains the current best move int negamax(int board[][8], int color, int depth) { int alpha = -65; int beta = 65; std::vector< std::pair<int, std::vector< std::pair<int, int> > > > moves = get_moves(board, color); int move = moves[0].first; for(auto it=moves.begin(); it != moves.end(); it++) { make_move(board, (*it).first/8, (*it).first&7, color, (*it).second); int val = -negamax_aux(board, -color, depth-1, -beta, -alpha); undo_move(board, (*it).first/8, (*it).first&7, color, (*it).second); if(val >= beta) { return (*it).first; } if(val > alpha) { alpha = val; move = (*it).first; } } return move; } //run with ./reversi [int] where int is the number of ply the AI searches deep. Default is 3 ply. int main(int argc, char **argv) { int depth = 3; if(argc > 1) { depth = atol(argv[1]); } depth *= 2; int board[8][8]; memset(board, 0, sizeof(board)); board[3][3] = board[4][4] = -1; board[3][4] = board[4][3] = 1; int turn = -1; while(true) { print(board); std::vector< std::pair<int, std::vector< std::pair<int, int> > > > moves= get_moves(board, turn); printf("available moves: "); for(auto it=moves.begin(); it != moves.end(); it++) { printf("(%d, %d) ", (*it).first/8, (it).first%8); } printf("\n"); if(moves.size() == 0) { turn = -turn; moves = get_moves(board, turn); if(moves.size() == 0) { printf("final score: %d\n", score(board, -1)); return 0; } } else { int x, y; if(turn == -1) { scanf("%d %d", &x, &y); for(auto it=moves.begin(); it != moves.end(); it++) { if(x8+y == ((*it).first)) { printf("chose: %d %d\n", x, y); make_move(board, x, y, turn, (*it).second); turn = -turn; break; } } } else { x = negamax(board, turn, depth); for(auto it=moves.begin(); it != moves.end(); it++) { if(x == ((*it).first)) { printf("chose: %d %d\n", x/8, x%8); make_move(board, x/8, x%8, turn, (*it).second); turn = -turn; break; } } } } } return 0; }