Skip to content

Instantly share code, notes, and snippets.

@junodeveloper

junodeveloper/main.cpp

Created April 3, 2020 09:04
Show Gist options
  • Save junodeveloper/6618110b8f85748d473469d82d7d5984 to your computer and use it in GitHub Desktop.
Save junodeveloper/6618110b8f85748d473469d82d7d5984 to your computer and use it in GitHub Desktop.
Download ZIP
chess ai (minimax alg. ver.)
Raw
main.cpp
/* 2016.01.20
Chess AI by junodeveloper
Notes:
- Promotion is not implemented.
- Only used minimax algorithm (not alpha-beta prunning).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <time.h>
#define INF 0x7fffffff
#define MAX_DEPTH 4
#define BUFF_OFFSET 999999999
struct Move {
Move() {}
Move(int i1, int j1, int i2, int j2) {fi = i1, fj = j1, ti = i2, tj = j2;}
int fi, fj, ti, tj;
};
/*
Object
B:
0-Pawn, 1-Knight, 2-Bishop, 3-Rook, 4-Queen, 5-King
W:
6-Pawn, 7-Knight, 8-Bishop, 9-Rook, a(10)-Queen, b(11)-King
*/
/*
Type
0-Pawn, 1-Knight, 2-Bishop, 3-Rook, 4-Queen, 5-King
*/
using namespace std;
vector< pair<int, int> > moves[7]; // 0-Pawn(Black), 1-Pawn(White), 2-Knight, 3-Bishop, 4-Rook, 5-Queen, 6-King
unordered_map<string, pair<int, Move> > map[2];
Move bestMove(-1, -1, -1, -1);
int getObject(char ch) {
if(ch=='.') return -1;
if(ch=='a') return 10;
if(ch=='b') return 11;
return ch - '0';
}
int getType(int obj) {
return obj>5 ? obj-6 : obj;
}
char getTypeChar(int type, bool team) {
char ret;
if(type == 0) ret = 'p';
if(type == 1) ret = 'n';
if(type == 2) ret = 'b';
if(type == 3) ret = 'r';
if(type == 4) ret = 'q';
if(type == 5) ret = 'k';
return ret ^ (team ? 32 : 0);
}
/* 0: Black, 1:White */
int getTeam(int obj) {
return obj>5;
}
int getValue(int type) {
if(type == 0) return 1;
if(type == 1 || type==2) return 3;
if(type == 3) return 5;
if(type == 4) return 9;
if(type == 5) return 200;
return 0;
}
void printBoard(string& board) {
printf("board:\n");
for(int i=0;i<8;i++) {
printf("%d|", 8-i);
for(int j=0;j<8;j++) {
int obj = getObject(board[8*i+j]), type = getType(obj), team = getTeam(obj);
if(obj == -1) putchar('.');
else printf("%c", getTypeChar(type, team));
}
puts("");
}
puts(" --------");
printf(" ");
for(int i=0;i<8;i++) printf("%c", 'a'+i);
puts("");
printf("castling: \nBlack - Queen:%d, King:%d\n", board[8*8+1], board[8*8]);
printf("White - Queen:%d, King:%d\n", board[8*8+3], board[8*8+2]);
}
bool isValid(int i, int j) {
return (i>=0 && i<8 && j>=0 && j<8);
}
void moveObj(string& board, int i, int j, int ti, int tj) {
board[8*ti+tj] = board[8*i+j];
board[8*i+j] = '.';
}
string createBoard2() {
string board;
board.resize(8*8+4);
for(int i=0;i<8;i++) {
for(int j=0;j<8;j++)
board[8*i+j]='.';
}
board[5]='5';
board[8*2+5]='0';
board[8*2+4]='a';
board[8*1+3]='b';
board[8*8]=board[8*8+1]=board[8*8+2]=board[8*8+3]=1;
return board;
}
string createBoard() {
string board;
board.resize(8*8+4);
for(int i=0;i<8;i++) {
for(int j=0;j<8;j++) {
if(i==1)
board[8*i+j]='0';
else if(i==6)
board[8*i+j]='6';
else if(i==0 && (j==0 || j==7))
board[8*i+j]='3';
else if(i==7 && (j==0 || j==7))
board[8*i+j]='9';
else if(i==0 && (j==1 || j==6))
board[8*i+j]='1';
else if(i==7 && (j==1 || j==6))
board[8*i+j]='7';
else if(i==0 && (j==2 || j==5))
board[8*i+j]='2';
else if(i==7 && (j==2 || j==5))
board[8*i+j]='8';
else if(i==0 && j==3)
board[8*i+j]='4';
else if(i==7 && j==3)
board[8*i+j]='a';
else if(i==0 && j==4)
board[8*i+j]='5';
else if(i==7 && j==4)
board[8*i+j]='b';
else
board[8*i+j]='.';
}
}
board[8*8]=board[8*8+1]=board[8*8+2]=board[8*8+3]=1;
return board;
}
int updateValue(bool turn, int& current, int value) {
if(turn == 0) {
if(current > value) {
current = value;
return value;
} else if(current == value) return INF-1;
else return INF;
} else {
if(current < value) {
current = value;
return value;
} else if(current == value) return INF-1;
else return INF;
}
}
bool canMove(string& board, bool turn, int i, int j) {
return isValid(i, j) && (getObject(board[8*i+j])!=-1 ? (getTeam(getObject(board[8*i+j]))!=turn) : true);
}
int judgeStatus(string& board) {
int status = 0;
for(int i=0;i<8;i++) {
for(int j=0;j<8;j++) {
int obj = getObject(board[8*i+j]);
if(obj != -1)
status += getValue(getType(obj)) * (getTeam(obj)?1:-1);
}
}
return status;
}
vector<Move> getPossibleMoves(string& board, bool turn) {
vector<Move> ret;
for(int i=0;i<8;i++) {
for(int j=0;j<8;j++) {
int obj = getObject(board[8*i+j]);
if(obj != -1 && getTeam(obj) == turn) {
int type = getType(obj);
int ti, tj;
if(type == 0) { // Pawn
int dir[4][2] = { {1,1}, {1,-1}, {-1,1}, {-1,-1} };
for(int k=0;k<4;k++) {
if((obj == 0 && k>=2) || (obj == 6 && k<2)) continue;
ti = i+dir[k][0], tj = j+dir[k][1];
if(isValid(ti, tj) && getObject(board[8*ti+tj]) != -1 && getTeam(getObject(board[8*ti+tj])) != turn)
ret.push_back(Move(i, j, ti, tj));
}
for(int k=1;k<=2;k++) {
if(k==2 && ((obj==0 && i!=1) || (obj==6 && i!=6))) continue;
ti = i+k*(obj==0 ? 1 : -1), tj = j;
if(isValid(ti, tj) && getObject(board[8*ti+tj]) == -1)
ret.push_back(Move(i, j, ti, tj));
else break;
}
} else if(type == 1) { // Knight
for(int k=0;k<moves[1].size();k++) {
ti = i+moves[1][k].first, tj = j+moves[1][k].second;
if(canMove(board, turn, ti, tj))
ret.push_back(Move(i, j, ti, tj));
}
} else if(type == 2) { // Bishop
for(int k=0;k<moves[2].size();k++) {
for(int l=1;l<=7;l++) {
ti = i+moves[2][k].first * l, tj = j+moves[2][k].second * l;
if(canMove(board, turn, ti, tj)) {
ret.push_back(Move(i, j, ti, tj));
if(getObject(board[8*ti+tj])!=-1 && getTeam(getObject(board[8*ti+tj])) != turn) break;
} else break;
}
}
} else if(type == 3) { // Rook
for(int k=0;k<moves[3].size();k++) {
for(int l=1;l<=7;l++) {
ti = i+moves[3][k].first * l, tj = j+moves[3][k].second * l;
if(canMove(board, turn, ti, tj)) {
ret.push_back(Move(i, j, ti, tj));
if(getObject(board[8*ti+tj])!=-1 && getTeam(getObject(board[8*ti+tj])) != turn) break;
} else break;
}
}
} else if(type == 4) { // Queen
for(int k=0;k<moves[4].size();k++) {
for(int l=1;l<=7;l++) {
ti = i+moves[4][k].first * l, tj = j+moves[4][k].second * l;
if(canMove(board, turn, ti, tj)) {
ret.push_back(Move(i, j, ti, tj));
if(getObject(board[8*ti+tj])!=-1 && getTeam(getObject(board[8*ti+tj])) != turn) break;
} else break;
}
}
} else if(type == 5) { // King
for(int k=0;k<moves[5].size();k++) {
ti = i+moves[5][k].first, tj = j+moves[5][k].second;
if(canMove(board, turn, ti, tj))
ret.push_back(Move(i, j, ti, tj));
}
}
}
}
}
return ret;
}
int play(string& board, bool turn, int depth) {
if(depth == 0) {
bestMove = Move(-1, -1, -1, -1);
map[0].clear(), map[1].clear();
}
if(depth == MAX_DEPTH) return judgeStatus(board);
//printf("depth %d, turn %d\n", depth, turn);
//printBoard(board);
if(map[turn][board].first != 0) {
bestMove = map[turn][board].second;
return map[turn][board].first - BUFF_OFFSET;
}
int local, best = (turn ? -INF : INF);
vector<Move> reserved;
for(int i=0;i<8;i++) {
for(int j=0;j<8;j++) {
int obj = getObject(board[8*i+j]);
if(obj != -1 && getTeam(obj) == turn) {
int type = getType(obj);
int ti, tj;
if(type == 0) { // Pawn
int dir[4][2] = { {1,1}, {1,-1}, {-1,1}, {-1,-1} };
for(int k=0;k<4;k++) {
if((obj == 0 && k>=2) || (obj == 6 && k<2)) continue;
ti = i+dir[k][0], tj = j+dir[k][1];
if(isValid(ti, tj) && getObject(board[8*ti+tj]) != -1 && getTeam(getObject(board[8*ti+tj])) != turn) {
string board2 = board;
moveObj(board2, i, j, ti, tj);
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(i, j, ti, tj));
}
}
}
for(int k=1;k<=2;k++) {
if(k==2 && ((obj==0 && i!=1) || (obj==6 && i!=6))) continue;
ti = i+k*(obj==0 ? 1 : -1), tj = j;
if(isValid(ti, tj) && getObject(board[8*ti+tj]) == -1) {
string board2 = board;
moveObj(board2, i, j, ti, tj);
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(i, j, ti, tj));
}
} else break;
}
} else if(type == 1) { // Knight
for(int k=0;k<moves[1].size();k++) {
ti = i+moves[1][k].first, tj = j+moves[1][k].second;
if(canMove(board, turn, ti, tj)) {
string board2 = board;
moveObj(board2, i, j, ti, tj);
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(i, j, ti, tj));
}
}
}
} else if(type == 2) { // Bishop
for(int k=0;k<moves[2].size();k++) {
for(int l=1;l<=7;l++) {
ti = i+moves[2][k].first * l, tj = j+moves[2][k].second * l;
if(canMove(board, turn, ti, tj)) {
string board2 = board;
moveObj(board2, i, j, ti, tj);
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(i, j, ti, tj));
}
if(getObject(board[8*ti+tj])!=-1 && getTeam(getObject(board[8*ti+tj])) != turn) break;
} else break;
}
}
} else if(type == 3) { // Rook
for(int k=0;k<moves[3].size();k++) {
for(int l=1;l<=7;l++) {
ti = i+moves[3][k].first * l, tj = j+moves[3][k].second * l;
if(canMove(board, turn, ti, tj)) {
string board2 = board;
board2[8*8+turn*2+(j==0)]=0;
moveObj(board2, i, j, ti, tj);
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(i, j, ti, tj));
}
if(getObject(board[8*ti+tj])!=-1 && getTeam(getObject(board[8*ti+tj])) != turn) break;
} else break;
}
}
} else if(type == 4) { // Queen
for(int k=0;k<moves[4].size();k++) {
for(int l=1;l<=7;l++) {
ti = i+moves[4][k].first * l, tj = j+moves[4][k].second * l;
if(canMove(board, turn, ti, tj)) {
string board2 = board;
moveObj(board2, i, j, ti, tj);
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(i, j, ti, tj));
}
if(getObject(board[8*ti+tj])!=-1 && getTeam(getObject(board[8*ti+tj])) != turn) break;
} else break;
}
}
} else if(type == 5) { // King
for(int k=0;k<moves[5].size();k++) {
ti = i+moves[5][k].first, tj = j+moves[5][k].second;
if(canMove(board, turn, ti, tj)) {
string board2 = board;
board2[8*8+turn*2]=board2[8*8+turn*2+1]=0;
moveObj(board2, i, j, ti, tj);
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(i, j, ti, tj));
}
}
int rank = turn ? 7 : 0;
if(board[8*8+turn*2] && board[8*rank+5]=='.' && board[8*rank+6]=='.') {
string board2 = board;
board2[8*rank+6]=board2[8*rank+4];
board2[8*rank+5]=board2[8*rank+7];
board2[8*rank+4]=board2[8*rank+7]='.';
board2[8*8+turn*2]=board2[8*8+turn*2+1]=0;
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(rank, 4, rank, 6));
}
}
if(board[8*8+turn*2+1] && board[8*rank+1]=='.' && board[8*rank+2]=='.' && board[8*rank+3]=='.') {
string board2 = board;
board2[8*rank+2]=board2[8*rank+4];
board2[8*rank+3]=board2[8*rank];
board2[8*rank+4]=board2[8*rank]='.';
board2[8*8+turn*2]=board2[8*8+turn*2+1]=0;
local = updateValue(turn, best, play(board2, 1-turn, depth+1));
if(local != INF) {
// Set best move
if(local != INF - 1)
reserved.clear();
reserved.push_back(Move(rank, 4, rank, 2));
}
}
}
}
}
}
}
if(depth == 0) printf("computer possible moves:%d\n", reserved.size());
if(reserved.size() != 0) {
//if(depth==0) {
//printf("\n\n BEST MOVE(local:%d):\n",best);
//for(int i=0;i<reserved.size();i++)
// printf("(%d,%d) to (%d,%d)\n",1+reserved[i].fj,8-reserved[i].fi,1+reserved[i].tj,8-reserved[i].ti);
//printf("\n\n");
//}
int select = rand()%reserved.size();
bestMove = reserved[select];
}
map[turn][board] = make_pair(BUFF_OFFSET + best, bestMove);
return best;
}
void addMove(int index, int di, int dj) {
moves[index].push_back( make_pair(di, dj) );
}
void initMoves() {
addMove(1, -2, 1);
addMove(1, -2, -1);
addMove(1, -1, 2);
addMove(1, 1, 2);
addMove(1, 2, 1);
addMove(1, 2, -1);
addMove(1, 1, -2);
addMove(1, -1, -2);
addMove(2, 1, 1);
addMove(2, 1, -1);
addMove(2, -1, -1);
addMove(2, -1, 1);
addMove(3, 1, 0);
addMove(3, -1, 0);
addMove(3, 0, 1);
addMove(3, 0, -1);
addMove(4, 1, 1);
addMove(4, 1, -1);
addMove(4, -1, -1);
addMove(4, -1, 1);
addMove(4, 1, 0);
addMove(4, -1, 0);
addMove(4, 0, 1);
addMove(4, 0, -1);
addMove(5, 1, 1);
addMove(5, 1, -1);
addMove(5, -1, -1);
addMove(5, -1, 1);
addMove(5, 1, 0);
addMove(5, -1, 0);
addMove(5, 0, 1);
addMove(5, 0, -1);
}
bool isPossibleMove(vector<Move> moves, int i, int j, int ti, int tj) {
for(int k=0;k<moves.size();k++)
if(moves[k].fi==i && moves[k].fj==j && moves[k].ti==ti && moves[k].tj==tj) return true;
return false;
}
char toLower(char ch) {
return ch<='Z'?ch^32:ch;
}
int main() {
unordered_map<string, int> m;
srand( time(NULL) );
initMoves();
string board = createBoard();
printBoard(board);
Move playerMove(-1,-1,-1,-1);
char input[5];
while(1) {
vector<Move> possible = getPossibleMoves(board, 1);
printf("Enter move : ");
scanf("%s", input);
playerMove.fj = toLower(input[0])-'a';
playerMove.fi = input[1]-'0'-1;
playerMove.tj = toLower(input[2])-'a';
playerMove.ti = input[3]-'0'-1;
playerMove.fi = 7 - playerMove.fi;
playerMove.ti = 7 - playerMove.ti;
bool castling = false;
if(getType(getObject(board[8*playerMove.fi+playerMove.fj]))==5 && abs(playerMove.tj-playerMove.fj)==2) {
if(playerMove.tj<playerMove.fj) {
if(board[8*7+1]=='.' && board[8*7+2]=='.' && board[8*7+3]=='.' && board[8*8+3]) // Queen side castling
board[8*7+2]='b', board[8*7+3]='9', board[8*7]=board[8*7+4]='.', castling = true, board[8*8+2]=board[8*8+3]=0;
} else if(board[8*7+5]=='.' && board[8*7+6]=='.' && board[8*8+2]) // King side castling
board[8*7+6]='b', board[8*7+5]='9', board[8*7+4]=board[8*7+7]='.', castling = true, board[8*8+2]=board[8*8+3]=0;
}
if(!castling && !isPossibleMove(possible, playerMove.fi, playerMove.fj, playerMove.ti, playerMove.tj)) {
printf("Impossible Move. Try again.\n");
continue;
}
if(getType(getObject(board[8*playerMove.fi+playerMove.fj]))==5)
board[8*8+2]=board[8*8+3]=0;
if(getType(getObject(board[8*playerMove.fi+playerMove.fj]))==3)
board[8*8+2+(playerMove.fj==0)]=0;
if(!castling) {
board[8*playerMove.ti+playerMove.tj] = board[8*playerMove.fi+playerMove.fj];
board[8*playerMove.fi+playerMove.fj] = '.';
}
printf("Thinking...\n");
int value = play(board, 0, 0);
printf("value %d, computer moves %d %d to %d %d", value, bestMove.fj+1, (7-bestMove.fi)+1, bestMove.tj+1, (7-bestMove.ti)+1);
printBoard(board);
if(getType(getObject(board[8*bestMove.fi+bestMove.fj]))==3)
board[8*8+(bestMove.fj==0)]=0;
if(getType(getObject(board[8*bestMove.fi+bestMove.fj]))==5)
board[8*8]=board[8*8+1]=0;
if(getType(getObject(board[8*bestMove.fi+bestMove.fj])==5 && abs(bestMove.tj-bestMove.fj))==2) {
if(bestMove.tj<bestMove.fj) // Queen side castling
board[2]='5', board[3]='3', board[0]=board[4]='.';
else // King side castling
board[6]='5', board[5]='3', board[4]=board[7]='.';
board[8*8]=board[8*8+1]=0;
} else {
board[8*bestMove.ti+bestMove.tj] = board[8*bestMove.fi+bestMove.fj];
board[8*bestMove.fi+bestMove.fj] = '.';
}
printBoard(board);
if(value<-100) {
printf("computer win!\n");
break;
}
if(value>100) {
printf("you win!\n");
break;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment