본문으로 건너뛰기

python-implementation

체스 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가 바보가 되던데 이유를 모르겠다.