체스 AI by Python
이 글은 기존 블로그의 원문에서 가져왔습니다. 원문 작성일: 2022-09-10
1. Set Board
# set board
board = [['R', 'N', 'B', 'K', 'Q', 'B', 'N', 'R'],
['P', 'P', 'P', 'P', 'P', 'P', 'P', 'P']]
for _ in range(4) :
board.append(['.', '.', '.', '.', '.', '.', '.', '.'])
board.append(['p', 'p', 'p', 'p', 'p', 'p', 'p', 'p'])
board.append(['r', 'n', 'b', 'k', 'q', 'b', 'n', 'r'])
U_pieces = []
L_pieces = []
for c in range(C) :
for r in range(R) :
if board[c][r].islower() :
L_pieces.append((c, r))
if board[c][r].isupper() :
U_pieces.append((c, r))
게임 판을 세팅한다.
또한 list에 말들의 좌표값을 저장한다.
2. Movable Tile
# check possible tile
dc_n = [2, 2, -2, -2, 1, 1, -1, -1]
dr_n = [1, -1, 1, -1, 2, -2, 2, -2]
dc_k = [1, 1, 1, 0, 0, -1, -1, -1]
dr_k = [1, 0, -1, 1, -1, 1, 0, -1]
dc_b = [1, 1, -1, -1]
dr_b = [1, -1, 1, -1]
dc_r = [1, -1, 0, 0]
dr_r = [0, 0, 1, -1]
dc_q = dc_k[:]
dr_q = dr_k[:]
def possible_tile(c, r) :
piece_type = board[c][r].lower()
is_lower = board[c][r].islower()
if piece_type == 'p' :
return possible_tile_p(c, r, is_lower)
elif piece_type == 'b' :
return possible_tile_b(c, r, is_lower)
elif piece_type == 'n' :
return possible_tile_n(c, r, is_lower)
elif piece_type == 'r' :
return possible_tile_r(c, r, is_lower)
elif piece_type == 'q' :
return possible_tile_q(c, r, is_lower)
elif piece_type == 'k' :
return possible_tile_k(c, r, is_lower)
def possible_tile_p(c, r, is_lower) :
direction_c = 0
if is_lower :
direction_c = -1
else :
direction_c = 1
result = []
if 0<=c+direction_c<C :
if board[c+direction_c][r] == '.' :
result.append((c+direction_c, r))
if 0<=c+direction_c*2<C and c == int(3.5+direction_c*-1.5) :
if board[c+direction_c*2][r] == '.' :
result.append((c+direction_c*2, r))
if 0<=r+1<R :
if board[c+direction_c][r+1].isalpha() and is_lower != board[c+direction_c][r+1].islower() :
result.append((c+direction_c, r+1))
if 0<=r-1<R :
if board[c+direction_c][r-1].isalpha() and is_lower != board[c+direction_c][r-1].islower() :
result.append((c+direction_c, r-1))
return result
def possible_tile_b(c, r, is_lower) :
result = []
for i in range(4) :
dc = dc_b[i]
dr = dr_b[i]
xc = c + dc
xr = r + dr
while 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
if board[xc][xr].isalpha :
break
xc += dc
xr += dr
return result
def possible_tile_r(c, r, is_lower) :
result = []
for i in range(4) :
dc = dc_r[i]
dr = dr_r[i]
xc = c + dc
xr = r + dr
while 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
if board[xc][xr].isalpha :
break
xc += dc
xr += dr
return result
def possible_tile_k(c, r, is_lower) :
result = []
for i in range(8) :
xc = c + dc_k[i]
xr = r + dr_k[i]
if 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
return result
def possible_tile_n(c, r, is_lower) :
result = []
for i in range(8) :
xc = c + dc_n[i]
xr = r + dr_n[i]
if 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
return result
def possible_tile_q(c, r, is_lower) :
result = []
for i in range(8) :
dc = dc_q[i]
dr = dr_q[i]
xc = c + dc
xr = r + dr
while 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
if board[xc][xr].isalpha :
break
xc += dc
xr += dr
return result
이동가능한 타일을 반환 시켜주는 함수를 정한다.
3. Move piece
# move piece
def move_piece(nc, nr, xc, xr) :
global score
if board[nc][nr].isupper() :
U_pieces.remove((nc, nr))
U_pieces.append((xc, xr))
else :
L_pieces.remove((nc, nr))
L_pieces.append((xc, xr))
temp = board[xc][xr]
board[xc][xr] = board[nc][nr]
board[nc][nr] = '.'
if temp.isalpha() :
if temp.isupper() :
score -= score_a[temp.lower()]
U_pieces.remove((xc, xr))
else :
score += score_a[temp]
L_pieces.remove((xc, xr))
return temp
체스 말을 움직이는 함수를 정의한다.
말을 움직이면서 말 좌표가 담긴 list도 최신화 하고
AI를 위한 score에도 결과를 반영해준다.
4. AI part
# AI part
def make_decision(n, AIturn, return_type) :
global score
global U_pieces
global L_pieces
if n == 0 :
return score
else :
if AIturn :
max_score = -1000000
best_decision = []
for c, r in U_pieces[:] :
possible_tile_list = possible_tile(c, r)
for xc, xr in possible_tile_list :
t_score = score
t_U_pieces = U_pieces[:]
t_L_pieces = L_pieces[:]
temp = move_piece(c, r, xc, xr)
n_score = make_decision(n-1, False, 2)
if max_score < n_score :
max_score = n_score
best_decision = [c, r, xc, xr]
board[c][r] = board[xc][xr]
board[xc][xr] = temp
U_pieces = t_U_pieces[:]
L_pieces = t_L_pieces[:]
score = t_score
if return_type == 1 :
return best_decision
elif return_type == 2 :
return max_score
else :
min_score = 1000000
best_decision = []
for c, r in L_pieces[:] :
possible_tile_list = possible_tile(c, r)
for xc, xr in possible_tile_list :
t_score = score
t_U_pieces = U_pieces[:]
t_L_pieces = L_pieces[:]
temp = move_piece(c, r, xc, xr)
n_score = make_decision(n-1, True, 2)
if min_score > n_score :
min_score = n_score
best_decision = [c, r, xc, xr]
board[c][r] = board[xc][xr]
board[xc][xr] = temp
U_pieces = t_U_pieces[:]
L_pieces = t_L_pieces[:]
score = t_score
return min_score
minimax algorithm을 사용해서 재귀적으로 함수를 짜준다.
또한 alpha-beta pruning을 사용해서 상대적으로 속도를 빠르게 한다.
5. Main part and Show board part
# show board
def print_board() :
print()
print(' 0 1 2 3 4 5 6 7')
for c in range(C) :
sys.stdout.write(' '+str(c))
for r in range(R) :
sys.stdout.write(' '+board[c][r])
print()
# main
print_board()
while (True) :
while (True) :
nc, nr, xc, xr = map(int, sys.stdin.readline().split())
if (xc, xr) in possible_tile(nc, nr) :
move_piece(nc, nr, xc, xr)
print_board()
break
nc, nr, xc, xr = make_decision(5, True, 0)
move_piece(nc, nr, xc, xr)
print_board()
6. 결과
import sys
C = 8
R = 8
# define score
score_a = {'p' : 1, 'n' : 3, 'b' : 3, 'r' : 5, 'q' : 9, 'k' : 10000, '.' : 0}
score = 0
# set board
board = [['R', 'N', 'B', 'K', 'Q', 'B', 'N', 'R'],
['P', 'P', 'P', 'P', 'P', 'P', 'P', 'P']]
for _ in range(4) :
board.append(['.', '.', '.', '.', '.', '.', '.', '.'])
board.append(['p', 'p', 'p', 'p', 'p', 'p', 'p', 'p'])
board.append(['r', 'n', 'b', 'k', 'q', 'b', 'n', 'r'])
# check possible tile
dc_n = [2, 2, -2, -2, 1, 1, -1, -1]
dr_n = [1, -1, 1, -1, 2, -2, 2, -2]
dc_k = [1, 1, 1, 0, 0, -1, -1, -1]
dr_k = [1, 0, -1, 1, -1, 1, 0, -1]
dc_b = [1, 1, -1, -1]
dr_b = [1, -1, 1, -1]
dc_r = [1, -1, 0, 0]
dr_r = [0, 0, 1, -1]
dc_q = dc_k[:]
dr_q = dr_k[:]
def possible_tile(c, r) :
piece_type = board[c][r].lower()
is_lower = board[c][r].islower()
if piece_type == 'p' :
return possible_tile_p(c, r, is_lower)
elif piece_type == 'b' :
return possible_tile_b(c, r, is_lower)
elif piece_type == 'n' :
return possible_tile_n(c, r, is_lower)
elif piece_type == 'r' :
return possible_tile_r(c, r, is_lower)
elif piece_type == 'q' :
return possible_tile_q(c, r, is_lower)
elif piece_type == 'k' :
return possible_tile_k(c, r, is_lower)
def possible_tile_p(c, r, is_lower) :
direction_c = 0
if is_lower :
direction_c = -1
else :
direction_c = 1
result = []
if 0<=c+direction_c<C :
if board[c+direction_c][r] == '.' :
result.append((c+direction_c, r))
if 0<=c+direction_c*2<C and c == int(3.5+direction_c*-1.5) :
if board[c+direction_c*2][r] == '.' :
result.append((c+direction_c*2, r))
if 0<=r+1<R :
if board[c+direction_c][r+1].isalpha() and is_lower != board[c+direction_c][r+1].islower() :
result.append((c+direction_c, r+1))
if 0<=r-1<R :
if board[c+direction_c][r-1].isalpha() and is_lower != board[c+direction_c][r-1].islower() :
result.append((c+direction_c, r-1))
return result
def possible_tile_b(c, r, is_lower) :
result = []
for i in range(4) :
dc = dc_b[i]
dr = dr_b[i]
xc = c + dc
xr = r + dr
while 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
if board[xc][xr].isalpha :
break
xc += dc
xr += dr
return result
def possible_tile_r(c, r, is_lower) :
result = []
for i in range(4) :
dc = dc_r[i]
dr = dr_r[i]
xc = c + dc
xr = r + dr
while 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
if board[xc][xr].isalpha :
break
xc += dc
xr += dr
return result
def possible_tile_k(c, r, is_lower) :
result = []
for i in range(8) :
xc = c + dc_k[i]
xr = r + dr_k[i]
if 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
return result
def possible_tile_n(c, r, is_lower) :
result = []
for i in range(8) :
xc = c + dc_n[i]
xr = r + dr_n[i]
if 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
return result
def possible_tile_q(c, r, is_lower) :
result = []
for i in range(8) :
dc = dc_q[i]
dr = dr_q[i]
xc = c + dc
xr = r + dr
while 0<=xc<C and 0<=xr<R and (board[xc][xr] == '.' or (board[xc][xr].isalpha and is_lower != board[xc][xr].islower())) :
result.append((xc, xr))
if board[xc][xr].isalpha :
break
xc += dc
xr += dr
return result
U_pieces = []
L_pieces = []
for c in range(C) :
for r in range(R) :
if board[c][r].islower() :
L_pieces.append((c, r))
if board[c][r].isupper() :
U_pieces.append((c, r))
# move piece
def move_piece(nc, nr, xc, xr) :
global score
if board[nc][nr].isupper() :
U_pieces.remove((nc, nr))
U_pieces.append((xc, xr))
else :
L_pieces.remove((nc, nr))
L_pieces.append((xc, xr))
temp = board[xc][xr]
board[xc][xr] = board[nc][nr]
board[nc][nr] = '.'
if temp.isalpha() :
if temp.isupper() :
score -= score_a[temp.lower()]
U_pieces.remove((xc, xr))
else :
score += score_a[temp]
L_pieces.remove((xc, xr))
return temp
# show board
def print_board() :
print()
print(' 0 1 2 3 4 5 6 7')
for c in range(C) :
sys.stdout.write(' '+str(c))
for r in range(R) :
sys.stdout.write(' '+board[c][r])
print()
# AI part
def make_decision(n, AIturn, return_type) :
global score
global U_pieces
global L_pieces
if n == 0 :
return score
else :
if AIturn :
max_score = -1000000
best_decision = []
for c, r in U_pieces[:] :
possible_tile_list = possible_tile(c, r)
for xc, xr in possible_tile_list :
t_score = score
t_U_pieces = U_pieces[:]
t_L_pieces = L_pieces[:]
temp = move_piece(c, r, xc, xr)
n_score = make_decision(n-1, False, 2)
if max_score < n_score :
max_score = n_score
best_decision = [c, r, xc, xr]
board[c][r] = board[xc][xr]
board[xc][xr] = temp
U_pieces = t_U_pieces[:]
L_pieces = t_L_pieces[:]
score = t_score
if return_type == 1 :
return best_decision
elif return_type == 2 :
return max_score
else :
min_score = 1000000
best_decision = []
for c, r in L_pieces[:] :
possible_tile_list = possible_tile(c, r)
for xc, xr in possible_tile_list :
t_score = score
t_U_pieces = U_pieces[:]
t_L_pieces = L_pieces[:]
temp = move_piece(c, r, xc, xr)
n_score = make_decision(n-1, True, 2)
if min_score > n_score :
min_score = n_score
best_decision = [c, r, xc, xr]
board[c][r] = board[xc][xr]
board[xc][xr] = temp
U_pieces = t_U_pieces[:]
L_pieces = t_L_pieces[:]
score = t_score
return min_score
# main
print_board()
while (True) :
while (True) :
nc, nr, xc, xr = map(int, sys.stdin.readline().split())
if (xc, xr) in possible_tile(nc, nr) :
move_piece(nc, nr, xc, xr)
print_board()
break
nc, nr, xc, xr = make_decision(5, True, 0)
move_piece(nc, nr, xc, xr)
print_board()
modular programming에 익숙하지가 않아서 그냥 코드를 짰는데 지저분하고 별로다 더 깔끔한 코드를 위해 노력해야할 듯하다.
또한 minimax algorithm에서 깊이를 짝수로 하니 AI가 바보가 되던데 이유를 모르겠다.