DSA-알고리즘 스터디

Feb 10, 2022

개요
제네릭
적용: 틱택토
적용: 커넥트포
연습문제
- 📝 8-1
- 📝 8-2
- 📝 8-3
- 📝 8-4
- 📝 8-5
- 📝 8-6

개요

틱택토, 커넥트포, 체스 등의 게임에서 플레이어는 상대와 적대적인 관계를 가지고 있다. 한 사람이 유리하다는 것은 다시 말해서 다른 사람이 불리하다는 것을 의미한다. 게임에서 승리하기 위해서는 수를 예측하고 최적의 이동을 선택해 이점을 살려야 하며, 이 과정에서 적대적 탐색 알고리즘을 사용한다.

제네릭

보드게임 구성 요소

board.py

# 보드게임 구성 요소

from __future__ import annotations
from typing import NewType, List
from abc import ABC, abstractmethod

# 게임에서의 이동을 나타내는 정수 타입
# 타입 엘리어스의 두 타입은 동등하지만, NewType은 한 타입을 다른 타입의 서브 타입으로 선언한다.
Move = NewType("Move", int)


class Piece:
    @property
    def opposite(self) -> Piece:
        raise NotImplementedError("서브클래스로 구현해야 합니다.")


class Board(ABC):
    # 누구 차례인가?
    @property
    @abstractmethod
    def turn(self) -> Piece:
        ...

    # 현재 위치에서 새 위치로 이동한다.
    @abstractmethod
    def move(self, location:Move) -> Board:
        ...

    # 말은 현재 위치에서 어디로 움직일 수 있는가?
    @property
    @abstractmethod
    def legal_moves(self) -> List[Move]:
        ...

    # 이겼는가?
    @property
    @abstractmethod
    def is_win(self) -> bool:
        ...

    # 무승부인가?
    @property
    def is_draw(self) -> bool:
        return (not self.is_win) and (len(self.legal_moves) == 0)

    # 플레이어의 말 위치를 평가하여 어느 쪽이 유리한지 확인한다.
    @abstractmethod
    def evaluate(self, player:Piece) -> float:
        ...

각 플레이어는 자신의 턴이 되면 현재 상황을 바탕으로 최적의 수를 계산한 후 새로운 위치에 말을 놓는다. 이미 말이 위치한 곳에는 말을 놓을 수 없다. 턴이 끝나면 승리 또는 무승부를 확인한 후 상대방의 턴으로 넘어간다.

게임의 개념과 진행을 Piece 및 Board 클래스에 작성한다. 두 클래스는 각각 플레이어와 게임 판을 의미한다.

최소최대 알고리즘

minmax.py

from __future__ import annotations
from board import Piece, Board, Move


def minmax(board:Board, 
           maximizing:bool, 
           original_player:Piece, 
           max_depth:int = 8) -> float:
    # 기저 조건 - 종료 위치 또는 최대 깊이에 도달한다.
    if board.is_win or board.is_draw or max_depth == 0:
        return board.evaluate(original_player)

    # 재귀 조건 - 자신의 이익을 극대화하거나 상대의 이익을 최소화한다.
    # 최대화 - 가장 높은 평가를 받는 움직임을 찾는다.
    if maximizing:  
        best_eval:float = float("-inf") # 가장 낮은 점수로 시작
        for move in board.legal_moves:
            result:float = minmax(board.move(move), 
                                  False, 
                                  original_player, 
                                  max_depth - 1)
            best_eval = max(result, best_eval)
        return best_eval
    # 최소화 - 가장 낮은 평가를 받는 움직임을 찾는다.
    else:
        worst_eval:float = float("inf") # 가장 높은 점수로 시작
        for move in board.legal_moves:
            result = minmax(board.move(move), 
                            True, 
                            original_player, 
                            max_depth - 1)
            worst_eval = min(result, worst_eval)
        return worst_eval

자신의 이득은 최대화하고, 상대의 이득은 최소화하는 수를 찾아야 한다. 최소최대 알고리즘은 탐색 깊이만큼 재귀 호출을 사용하며, 각 깊이는 Board 클래스의 evaluate() 메서드에서 선언한 점수를 가지고 있다. 기저 조건에 도달할 때까지 합산된 총 점수가 가장 높은 경우를 반환한다.

알파베타 가지치기

minmax.py

def alphabeta(board:Board, 
              maximizing:bool, 
              original_player:Piece, 
              max_depth:int = 8, 
              alpha:float = float("-inf"), 
              beta:float = float("inf")) -> float:
    if board.is_win or board.is_draw or max_depth == 0:
        return board.evaluate(original_player)

    if maximizing:
        for move in board.legal_moves:
            result: float = alphabeta(board.move(move), 
                                      False, 
                                      original_player, 
                                      max_depth - 1, 
                                      alpha, 
                                      beta)
            alpha = max(result, alpha)
            if beta <= alpha:
                break
        return alpha
    else:
        for move in board.legal_moves:
            result = alphabeta(board.move(move), 
                               True, 
                               original_player, 
                               max_depth - 1, 
                               alpha, 
                               beta)
            beta = min(result, beta)
            if beta <= alpha:
                break
        return beta

최소최대 알고리즘에서는 탐색 깊이가 깊어질수록 불필요한 탐색이 발생한다. 이미 탐색한 위치보다 낮은 점수를 가진 탐색 위치를 제거(가지치기)한다면, 보다 효율적인 탐색 과정을 수행할 수 있다.

알파는 현재까지 발견된 자신의 최고의 최대화 움직임 평가를 나타내며, 베타는 현재까지 발견된 상대의 최고의 최소화 움직임 평가를 나타낸다. 베타가 알파보다 크지 않다면 해당 탐색은 무의미하므로 탐색 트리에서 제외시킨다.

최적의 수 찾기

minmax.py

def find_best_move(board:Board, max_depth:int = 8) -> Move:
    best_eval:float = float("-inf")
    best_move:Move = Move(-1)
    for move in board.legal_moves:
        result:float = alphabeta(board.move(move), False, board.turn, max_depth)
        if result > best_eval:
            best_eval = result
            best_move = move
    return best_move

보다 효율적인 알파베타 가지치기를 사용한다.

적용: 틱택토

tictactoe.py

#   0 | 1 | 2
# ----+---+----
#   3 | 4 | 5
# ----+---+----
#   6 | 7 | 8

from __future__ import annotations
from typing import List
from enum import Enum
from board import Piece, Board, Move


class TTTPiece(Piece, Enum):
    X = "X"
    O = "O"
    E = " "

    @property
    def opposite(self) -> TTTPiece:
        if self == TTTPiece.X:
            return TTTPiece.O
        elif self == TTTPiece.O:
            return TTTPiece.X
        else:
            return TTTPiece.E

    def __str__(self) -> str:   # repr 사용 X
        return self.value


class TTTBoard(Board):
    def __init__(self, 
                 position:List[TTTPiece] = [TTTPiece.E] * 9,
                 turn:TTTPiece = TTTPiece.X) -> None:
        self.position:List[TTTPiece] = position
        self._turn:TTTPiece = turn

    @property
    def turn(self) -> Piece:
        return self._turn

    def move(self, location:Move) -> Board:
        temp_position:List[TTTPiece] = self.position.copy()
        temp_position[location] = self._turn
        return TTTBoard(temp_position, self._turn.opposite)

    @property
    def legal_moves(self) -> List[Move]:
        return [Move(l) for l in range(len(self.position)) if self.position[l] == TTTPiece.E]

    @property
    def is_win(self) -> bool:
        return self.position[0] == self.position[1] and self.position[0] == self.position[2] and self.position[0] != TTTPiece.E or\
               self.position[3] == self.position[4] and self.position[3] == self.position[5] and self.position[3] != TTTPiece.E or\
               self.position[6] == self.position[7] and self.position[6] == self.position[8] and self.position[6] != TTTPiece.E or\
               self.position[0] == self.position[3] and self.position[0] == self.position[6] and self.position[0] != TTTPiece.E or\
               self.position[1] == self.position[4] and self.position[1] == self.position[7] and self.position[1] != TTTPiece.E or\
               self.position[2] == self.position[5] and self.position[2] == self.position[8] and self.position[2] != TTTPiece.E or\
               self.position[0] == self.position[4] and self.position[0] == self.position[8] and self.position[0] != TTTPiece.E or\
               self.position[2] == self.position[4] and self.position[2] == self.position[6] and self.position[2] != TTTPiece.E

    def evaluate(self, player:Piece) -> float:
        if self.is_win and self.turn == player:
            return -1
        elif self.is_win and self.turn != player:
            return 1
        else:
            return 0

    def __repr__(self) -> str:
        return f"""
        {self.position[0]}|{self.position[1]}|{self.position[2]}
        -----
        {self.position[3]}|{self.position[4]}|{self.position[5]}
        -----
        {self.position[6]}|{self.position[7]}|{self.position[8]}
        """

틱택토 게임에서 플레이어는 X 또는 O의 말을 가지고 시작한다. 3 x 3 크기의 게임 판에서 가로, 세로, 대각선 관계 없이 한 줄을 만들면 승리하며, 비어 있는 위치라면 어디든 말을 놓을 수 있을 수 있다.

tictactoe_ai.py

from minmax import find_best_move
from tictactoe import TTTBoard
from board import Move, Board

board:Board = TTTBoard()


def get_player_move() -> Move:
    player_move:Move = Move(-1)
    while player_move not in board.legal_moves:
        play:int = int(input("이동할 위치를 입력하세요 (0-8): "))
        player_move = Move(play)
    return player_move


if __name__ == "__main__":
    while True:
        human_move:Move = get_player_move()
        board = board.move(human_move)
        if board.is_win:
            print("당신이 이겼습니다!")
            break
        elif board.is_draw:
            print("비겼습니다!")
            break
        computer_move:Move = find_best_move(board)
        print(f"컴퓨터가 {computer_move}(으)로 이동했습니다.")
        board = board.move(computer_move)
        print(board)
        if board.is_win:
            print("컴퓨터가 이겼습니다!")
            break
        elif board.is_draw:
            print("비겼습니다!")
            break

적용: 커넥트포

connectfour.py

# □ □ □ □ □ □ □
# □ □ □ □ □ □ □
# □ □ □ □ □ □ □
# □ □ □ □ □ □ □
# □ □ □ □ □ □ □
# □ □ □ □ □ □ □

from __future__ import annotations
from typing import List, Optional, Tuple
from enum import Enum
from board import Piece, Board, Move


class C4Piece(Piece, Enum):
    B = "B"
    R = "R"
    E = " "

    @property
    def opposite(self) -> C4Piece:
        if self == C4Piece.B:
            return C4Piece.R
        elif self == C4Piece.R:
            return C4Piece.B
        else:
            return C4Piece.E
    
    def __str__(self) -> str:
        return self.value


def generate_segments(num_columns:int,
                      num_rows:int,
                      segment_length:int) -> List[List[Tuple[int, int]]]:

    # 세그먼트 - 네 개의 격자 위치 리스트
    # 세그먼트가 모두 같은 색이면 해당 색의 플레이어가 승리
    # 수직 세그먼트 생성
    segments:List[List[Tuple[int, int]]] = []
    for c in range(num_columns):
        for r in range(num_rows - segment_length + 1):
            segment:List[Tuple[int, int]] = []
            for t in range(segment_length):
                segment.append((c, r + t))
            segments.append(segment)
    
    # 수평 세그먼트 생성
    for c in range(num_columns - segment_length + 1):
        for r in range(num_rows):
            segment = []
            for t in range(segment_length):
                segment.append((c + t, r))
            segments.append(segment)

    # 대각선 세그먼트 생성 (왼쪽 아래 -> 오른쪽 위)
    for c in range(num_columns - segment_length + 1):
        for r in range(num_rows - segment_length + 1):
            segment = []
            for t in range(segment_length):
                segment.append((c + t, r + t))
            segments.append(segment)
    
    # 대각선 세그먼트 생성 (왼쪽 위 -> 오른쪽 아래)
    for c in range(num_columns - segment_length + 1):
        for r in range(segment_length - 1, num_rows):
            segment = []
            for t in range(segment_length):
                segment.append((c + t, r - t))
            segments.append(segment)

    return segments


class C4Board(Board):
    NUM_ROWS:int = 6
    NUM_COLUMNS:int = 7
    SEGMENT_LENGTH:int = 4
    SEGMENTS:List[List[Tuple[int, int]]] = generate_segments(NUM_COLUMNS, NUM_ROWS, SEGMENT_LENGTH)

    class Column:
        def __init__(self) -> None:
            self._container:List[C4Piece] = []

        @property
        def full(self) -> bool:
            return len(self._container) == C4Board.NUM_ROWS

        def push(self, item:C4Piece) -> None:
            if self.full:
                raise OverflowError("격자 열 범위에 벗어날 수 없습니다.")
            self._container.append(item)

        def __getitem__(self, index:int) -> C4Piece:
            if index > len(self._container) - 1:
                return C4Piece.E
            return self._container[index]

        def __repr__(self) -> str:
            return repr(self._container)

        def copy(self) -> C4Board.Column:
            temp: C4Board.Column = C4Board.Column()
            temp._container = self._container.copy()
            return temp

    def __init__(self, 
                 position:Optional[List[C4Board.Column]] = None,
                 turn:C4Piece = C4Piece.B) -> None:
        if position is None:
            self.position:List[C4Board.Column] = [C4Board.Column() for _ in range(C4Board.NUM_COLUMNS)]
        else:
            self.position = position
        self._turn:C4Piece = turn

    @property
    def turn(self) -> Piece:
        return self._turn

    def move(self, location:Move) -> Board:
        temp_position:List[C4Board.Column] = self.position.copy()
        for c in range(C4Board.NUM_COLUMNS):
            temp_position[c] = self.position[c].copy()
        temp_position[location].push(self._turn)
        return C4Board(temp_position, self._turn.opposite)

    @property
    def legal_moves(self) -> List[Move]:
        return [Move(c) for c in range(C4Board.NUM_COLUMNS) if not self.position[c].full]

    def _count_segment(self, segment:List[Tuple[int, int]]) -> Tuple[int, int]:
        black_count:int = 0
        red_count:int = 0
        for column, row in segment:
            if self.position[column][row] == C4Piece.B:
                black_count += 1
            elif self.position[column][row] == C4Piece.R:
                red_count += 1
        return black_count, red_count

    @property
    def is_win(self) -> bool:
        for segment in C4Board.SEGMENTS:
            black_count, red_count = self._count_segment(segment)
            if black_count == 4 or red_count == 4:
                return True
        return False

    def _evaluate_segment(self, 
                          segment:List[Tuple[int, int]], 
                          player:Piece) -> float:
        black_count, red_count = self._count_segment(segment)
        if red_count > 0 and black_count > 0:
            return 0
        count:int = max(red_count, black_count)
        score:float = 0
        if count == 2:
            score = 1
        elif count == 3:
            score = 100
        elif count == 4:
            score = 1_000_000

        color:C4Piece = C4Piece.B
        if red_count > black_count:
            color = C4Piece.R

        if color != player:
            return -score
        return score

    def evaluate(self, player:Piece) -> float:
        total:float = 0
        for segment in C4Board.SEGMENTS:
            total += self._evaluate_segment(segment, player)
        return total

    def __repr__(self) -> str:
        display:str = ""
        for r in reversed(range(C4Board.NUM_ROWS)):
            display += "|"
            for c in range(C4Board.NUM_COLUMNS):
                display += f"{self.position[c][r]}" + "|"
            display += "\n"
        return display

틱택토 게임에서 게임 판의 크기가 7 x 6로 증가했으며, 4줄(segment)을 완성해야 승리한다. 또한 모든 빈 공간이 적합한 것은 아니다. 각 열은 바닥부터 채워야 한다. Move의 적합성을 검사하기 위해 내부에 Column 클래스를 작성한다.

connectfour_ai.py

from minmax import find_best_move
from connectfour import C4Board
from board import Move, Board

board:Board = C4Board()


def get_player_move() -> Move:
    player_move:Move = Move(-1)
    while player_move not in board.legal_moves:
        play:int = int(input("이동할 위치를 입력하세요 (0-6): "))
        player_move = Move(play)
    return player_move


if __name__ == "__main__":
    while True:
        human_move:Move = get_player_move()
        board = board.move(human_move)
        if board.is_win:
            print("당신이 이겼습니다!")
            break
        elif board.is_draw:
            print("비겼습니다!")
            break
        computer_move:Move = find_best_move(board, 3)
        print(f"컴퓨터가 {computer_move}열을 선택했습니다.")
        board = board.move(computer_move)
        print(board)
        if board.is_win:
            print("컴퓨터가 이겼습니다!")
            break
        elif board.is_draw:
            print("비겼습니다!")
            break

연습문제

📝 8-1

틱택토에 단위 테스트를 추가하여 legal_moves, is_win, is_draw 속성이 잘 작동하는지 확인하라.

알고리즘 수업 시간에 assert문(가정 설정문)을 사용한 적 있다. 조건을 만족하지 못하면 에러를 발생시키는 성질을 이용하면 주어진 알고리즘이 잘 작동하는지 테스트할 수 있다. 단위 테스트 프레임워크인 unittest 모듈은 테스트를 구성하고 실행하는 데 풍부한 도구 모음을 제공하고 있다. 앞서 작성한 틱택토 게임에서 3가지 상황을 테스트하여, 그때마다 알고리즘이 이상적인 수를 찾는지 확인할 수 있다.

https://docs.python.org/ko/3/library/unittest.html

tictactoe_tests.py

import unittest
from typing import List
from minmax import find_best_move
from tictactoe import TTTPiece, TTTBoard
from board import Move


class TTTMINmaxTestCase(unittest.TestCase):
    # X가 승리하는 이동
    def test_easy_position(self):
        to_win_easy_position:List[TTTPiece] = [TTTPiece.X, TTTPiece.O, TTTPiece.X,
                                               TTTPiece.X, TTTPiece.E, TTTPiece.O,
                                               TTTPiece.E, TTTPiece.E, TTTPiece.O]
        test_board1:TTTBoard = TTTBoard(to_win_easy_position, TTTPiece.X)
        answer1:Move = find_best_move(test_board1)
        self.assertEqual(answer1, 6)

    # O의 승리를 방해하는 이동
    def test_block_position(self):
        to_block_position:List[TTTPiece] = [TTTPiece.X, TTTPiece.E, TTTPiece.E,
                                            TTTPiece.E, TTTPiece.E, TTTPiece.O,
                                            TTTPiece.E, TTTPiece.X, TTTPiece.O]
        test_board2:TTTBoard = TTTBoard(to_block_position, TTTPiece.X)
        answer2:Move = find_best_move(test_board2)
        self.assertEqual(answer2, 2)

    # 남은 두 턴을 고려한 최선의 이동
    def test_hard_position(self):
        to_win_hard_position:List[TTTPiece] = [TTTPiece.X, TTTPiece.E, TTTPiece.E,
                                               TTTPiece.E, TTTPiece.E, TTTPiece.O,
                                               TTTPiece.O, TTTPiece.X, TTTPiece.E]
        test_board3:TTTBoard = TTTBoard(to_win_hard_position, TTTPiece.X)
        answer3:Move = find_best_move(test_board3)
        self.assertEqual(answer3, 1)


if __name__ == "__main__":
    unittest.main()

위 코드는 책에 나온 틱택토 게임에서의 단위 테스트이다. 이 테스트에서는 세 가지의 특정한 상황(보드 판)이 주어진다. 이번 턴에 승리할 수 있다면 승리하는 수를 두어야 한다. 다음 턴에 상대가 승리할 수 있을 때, 이를 방해하는 수를 두어야 한다. 어떤 상황도 아니라면, 최소최대 알고리즘(또는 알파베타 가지치기)를 통해 탐색 깊이 내에서 가장 승리 가능성이 높은 수를 두어야 한다. 펜을 꺼내 종이에 몇 번 끄적여 본다면, 우리는 세 경우의 답을 알 수 있다. 이제 남은 건 구한 답을 assertEqual 메서드에 지정하는 일 뿐이다.

테스트 대상이 되는 메서드의 이름은 무조건 test로 시작해야 한다. 그렇지 않으면 대상에서 제외된다.

실행 결과

...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK

모든 조건을 만족해 테스트가 성공적으로 끝났다면 위와 같은 결과가 출력된다. 이제 문제로 돌아가 테스트를 위한 메서드를 추가한다(필자는 파일을 분리하였음).

_practice_question_8_1.py

import unittest
from typing import List
from tictactoe import TTTPiece, TTTBoard
from board import Move


class TTTMoreTest(unittest.TestCase):
    # legal_moves
    def test_legal_moves(self):
        position1:List[TTTPiece] = [
            TTTPiece.X, TTTPiece.O, TTTPiece.X,
            TTTPiece.X, TTTPiece.E, TTTPiece.O,
            TTTPiece.E, TTTPiece.E, TTTPiece.O
        ]
        test_board1:TTTBoard = TTTBoard(position1, TTTPiece.X)
        answer1:List[Move] = test_board1.legal_moves
        self.assertEqual(answer1, [4, 6, 7])

    # is_win
    def test_is_win(self):
        position2:List[TTTPiece] = [
            TTTPiece.E, TTTPiece.X, TTTPiece.E,
            TTTPiece.E, TTTPiece.X, TTTPiece.O,
            TTTPiece.E, TTTPiece.X, TTTPiece.O
        ]
        test_board2:TTTBoard = TTTBoard(position2, TTTPiece.X)
        answer2:Move = test_board2.is_win
        self.assertEqual(answer2, True)

    # is_draw
    def test_is_draw(self):
        position3:List[TTTPiece] = [
            TTTPiece.X, TTTPiece.O, TTTPiece.O,
            TTTPiece.O, TTTPiece.X, TTTPiece.X,
            TTTPiece.X, TTTPiece.X, TTTPiece.O
        ]
        test_board3:TTTBoard = TTTBoard(position3, TTTPiece.X)
        answer3:Move = test_board3.is_draw
        self.assertEqual(answer3, True)


if __name__ == "__main__":
    unittest.main()

실행 결과

...
----------------------------------------------------------------------
Ran 3 tests in 0.001s

OK

세 속성 모두 잘 작동한다.

📝 8-2

커넥트포에 대한 최소최대 알고리즘의 단위 테스트를 작성하라.

import unittest
from typing import List
from minmax import find_best_move
from connectfour import C4Piece, C4Board
from board import Move


class C4MINmaxTestCase(unittest.TestCase):
    # B가 승리하는 이동
    def test_easy_position(self):
        to_win_easy_position:List[C4Board.Column] = [
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column()
        ]
        to_win_easy_position[0].push(C4Piece.B)
        to_win_easy_position[1].push(C4Piece.R)
        to_win_easy_position[0].push(C4Piece.B)
        to_win_easy_position[1].push(C4Piece.R)
        to_win_easy_position[0].push(C4Piece.B)
        to_win_easy_position[1].push(C4Piece.R)
        test_board1:C4Board = C4Board(to_win_easy_position, C4Piece.B)
        answer1:Move = find_best_move(test_board1, 3)
        self.assertEqual(answer1, 0)

    # R의 승리를 방해하는 이동
    def test_block_position(self):
        to_block_position:List[C4Board.Column] = [
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column(),
            C4Board.Column()
        ]
        to_block_position[0].push(C4Piece.B)
        to_block_position[1].push(C4Piece.R)
        to_block_position[0].push(C4Piece.B)
        to_block_position[1].push(C4Piece.R)
        to_block_position[2].push(C4Piece.B)
        to_block_position[1].push(C4Piece.R)
        test_board2:C4Board = C4Board(to_block_position, C4Piece.B)
        answer2:Move = find_best_move(test_board2, 3)
        self.assertEqual(answer2, 1)


if __name__ == "__main__":
    unittest.main()

커넥트포 게임에서는 position의 기본 단위로 Column 컨테이너를 사용하므로 이에 맞게 수정한다. 틱택토 게임처럼 한꺼번에 말을 배치하는 것은 구조적으로 불가능하므로 push를 통해서 하나씩 배치한다. 탐색 깊이는 3으로 지정한다.

주어진 상황을 시각화하면 다음과 같다.

B가 승리하는 이동	R의 승리를 방해하는 이동

B가 승리하기 위해서는 0열에 두어야 하며, R의 승리를 방해하기 위해서는 1열에 두어야 한다.

실행 결과

..
----------------------------------------------------------------------
Ran 2 tests in 0.554s

OK

두 속성 모두 잘 작동한다.

📝 8-3

tictactoe_ai.py와 connectfour_ai.py의 코드는 거의 비슷하다. 이 두 코드를 두 게임 모두에서 사용할 수 있도록 두 메서드로 작성하여 리팩토링하라.

📝 8-4

컴퓨터 플레이어가 자신과 게임할 수 있도록 connectfour_ai.py 코드를 변경해보자. 첫 번째 플레이어와 두 번째 플레이어 중 누가 더 많이 이기는가? 매번 같은 선수가 이기는가?

connectfour.py

class C4Piece(Piece, Enum):
    B = "■"
    R = "□"
    E = " "

게임 진행을 보기 편하도록 B와 R 대신 보다 직관적인 기호를 사용했다.

_practice_question_8_4.py

...

if __name__ == "__main__":
    while True:
        player1_move:Move = find_best_move(board, 3)
        print(f"Player1이(가) {player1_move}열을 선택했습니다.")
        board = board.move(player1_move)
        print(board)
        if board.is_win:
            print("Player1이(가) 이겼습니다!")
            break
        elif board.is_draw:
            print("비겼습니다!")
            break
        player2_move:Move = find_best_move(board, 3)
        print(f"Player2이(가) {player2_move}열을 선택했습니다.")
        board = board.move(player2_move)
        print(board)
        if board.is_win:
            print("Player2이(가) 이겼습니다!")
            break
        elif board.is_draw:
            print("비겼습니다!")
            break

실행 결과

Player1이(가) 2열을 선택했습니다.
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | |■| | | | |

...

Player2이(가) 5열을 선택했습니다.
|□|□|■|□|□|□|□|
|□|■|■|□|■|■|■|
|■|□|□|□|■|□|□|
|□|■|■|■|□|■|■|
|■|□|□|■|■|□|□|
|□|■|■|■|□|■|■|

Player2이(가) 이겼습니다!

두 플레이어의 max_depth가 같은 경우(3) 항상 똑같은 진행으로 Player2가 승리한다. 하지만 Player1의 max_depth를 4로 증가시키면 최적의 이동을 계산하는 과정에서 더 많은 연산 과정을 거치므로 Player1이 승리할 수 있다.

📝 8-5

connectfour_ai.py에서 평가 방법을 최적화하여 같은 시간 내에 더 높은 탐색 길이를 가능하게 하는 방법을 찾아보라

(기존 코드를 프로파일링하거나 다른 방법을 사용해도 좋다).

📝 8-6

합법적인 체스 이동 생성 및 체스 게임 상태 유지 관리를 위해 이 장에서 개발한 alphabeta() 함수를 파이썬 라이브러리와 함께 사용하여 체스 AI를 개발하라.

체스 게임의 구성 요소를 이미 구현한 제네릭으로 정형화하는 작업을 거친다.

Piece

흰색(백)과 검은색(흑)으로 진행한다.

Board

8 x 8 크기의 게임 판에서 진행한다.
turn

백이 먼저 시작하며, 한 턴씩 번갈아 진행한다.
move

이동하려는 위치가 비어 있을 때 - 원래 위치를 비우고, 새 위치로 말을 옮긴다.

이동하려는 위치에 상대의 말이 존재할 때 - 원래 위치를 비우고, 상대의 말을 제거하고, 새 위치로 말을 옮긴다.

이동하려는 위치에 자신의 말이 존재할 때 - 이동할 수 없다.

legal_moves

각 기물의 이동 방식을 바탕으로 적합한 움직임을 검사한다.

기물	이동 방식
폰(Pawn)	폰은 일반 이동과 잡을 때의 이동이 다르다. 일반 이동은 앞으로 하며, 잡을 때는 대각선으로 간다. 폰은 한 번에 한칸만 앞으로 이동할 수 있지만, 처음으로 움직이는 폰은 두 칸을 이동할 수도 있다. 잡을 때는 대각선으로 한 칸 앞에 있는 상대기물만 잡을 수 있다. 절대 뒤로 이동하거나 뒤로 잡을 수 없으며, 폰 바로 앞에 다른 기물이 있을 경우 그 것을 뛰어넘거나 잡을 수 없다.
나이트(Knight)	한 방향으로 두 칸을 이동하고 그와 90도를 이루는 방향으로 한칸 이동하여 “L”자 모양으로 간다. 나이트는 기물 중 유일하게 다른 기물을 뛰어넘을 수 있다.
비숍(Bishop)	비숍은 원하는 만큼 움직일 수 있지만, 대각선으로만 이동이 가능하다.
룩(Rook)	룩은 원하는 만큼 움직일 수 있지만 앞, 뒤, 혹은 양옆으로만 이동이 가능하다.
퀸(Queen)	룩과 비숍의 이동 방식을 합친 기물로, 원하는 만큼 모든 방향(앞, 뒤, 양옆, 대각선)으로 이동이 가능하다.
킹(King)	모든 방향으로 이동이 가능하나, 한 칸씩밖에 움직일 수 없다. 또한 공격받는 위치로는 갈 수 없다.

is_win

킹이 공격받아 다음 턴에 죽을 수도 있다면(체크), 다른 어떤 움직임보다도 킹의 피신이 우선시된다. 만약 어느 방향으로 도망치더라도 공격을 받아 움직일 수 없다면(체크메이트), 플레이어는 패배한다. 즉, 상대가 승리한다.
is_draw

체스에서 무승부는 한 플레이어가 더 이상 움직일 수 없을 때 발생한다. 가장 대표적인 예로 움직일 수 있는 기물이 킹밖에 없을 때 어느 방향으로 움직이더라도 공격받는다면(스테일메이트), 게임은 무승부로 끝난다. 체크메이트와 굉장히 유사하다. 움직일 ㅅ ㅜ없을 때 현재 킹이 공격받고 있으면 체크메이트, 공격받고 있지 않으면 스테일메이트이다.
evaluate

일반적으로 체스 기물의 가치는 폰(1점), 비숍과 나이트(3점), 룩(5점), 퀸(9점)으로 여겨진다. 킹은 넉넉하게 백만 점쯤 주면 알고리즘이 최우선 기물로 인식할 것이다.

기타 고려 사항

체스에는 프로모션, 앙파상, 캐슬링이라는 몇 가지 예외가 존재한다. 프로모션이란, 폰이 게임판 끝까지 이동(6칸 전진)했을 때 다른 기물로 교체(킹 제외)하는 규칙이다. 앙파상은 폰의 첫 전진인 두 칸 전진으로 상대 폰의 공격을 회피할 때, 이를 무시하고 공격할 수 있는 규칙이다. 캐슬링은 킹의 보호와 룩의 진출을 위해 킹과 룩의 위치를 바꿀 수 있는 규칙이다. 킹과 룩은 한 번도 움직인 적 없어야 하고, 둘 사이에는 어떤 기물도 존재해서는 안 되며, 현재 위치와 교환 후 위치가 공격받아서는 안 된다. 조건이 성립하면, 킹이 룩 방향으로 두 칸 이동하고 룩이 킹을 뛰어넘어 바로 옆에 위치하는 방식으로 교환이 이루어진다.

이 세 규칙은 적대적 탐색 알고리즘만으로 구현이 어렵다.