9장 인공지능을 이용한 게임 만들기

목표

• 검색 알고리즘으로 효과적인 게임 전략 세우기
• 검색 알고리즘을 사용하는 지능형 로봇 만들어 여러 게임에 적용하기

게임에서 검색 알고리즘 사용하기

검색 알고리즘 - 게임을 더 똑똑하게 만들기

• 속도, 정확도, 복잡성 등 요소를 고려해 가능한 이동 경로 중 최선의 경로를 찾음

• 게임의 승리 조건을 고려해 게임이 진행되는 일련의 과정 동안 상황에 맞는 최적의 이동 경로를 찾아 승리로 이끄는 전략을 제시함

• 2인용 게임에서, 기본적으로 자기 차례가 올 때마다 이동 경로를 다시 계산해야 함 <- 상대 플레이어의 방해로 인해 애초에 계획한 대로 이동하기 힘들기 때문

• 컴퓨터의 입장에서 게임

  • 트리: 게임의 진행에 따라 발생 가능한 모든 상황
  • 트리를 검색하는 과정: 게임
  • 노드들: 게임의 진행 방향에 따라 도달 가능한 미래의 상태들
  • 루트 노드: 게임의 시작
  • 자식 노드들: e.g., 틱택토 게임에서 돌을 놓을 수 있는 위치들
  • 마지막 노드: 게임이 끝났을 때의 최종 결과 (무승부 or 한쪽이 이김)

• exhaustive search(철저한 검색) or brute force search(무차별 검색)

  • 기본적으로 모든 가능한 경우를 철저히 탐색하고 가능한 모든 선택의 결과를 예측하는 검색 방법
  • 최악의 경우, 가능한 모든 경우의 수를 탐색해야 함
  • 게임이 복잡할수록 계산량이 많아 결과를 빠르게 예측할 수 없어 무차별 검색을 사용하기 어려움 -> solution: 조합 검색

조합 검색

• heuristics(휴리스틱) 사용하거나 검색 공간의 크기를 줄임으로써 솔루션 공간을 효율적으로 탐색하는 검색 방법
  • cf) 휴리스틱의 예시: "우선순위 큐"를 사용한 탐색 알고리즘 - 우선순위가 높은 노드를 먼저 탐색하고, 그 다음으로 덜 중요한 노드를 탐색, 이를 통해 탐색 공간을 효율적으로 줄일 수 있음. A* 알고리즘과 같은 경로 탐색 문제에서 유용하게 사용됨.
• 체스, 바둑 등 복잡한 게임에서 유용하게 사용됨
• pruning strategy(가지치기 전략) 사용하여 검색 공간 탐색함; 명백하게 잘못된 선택을 미리 제거해 모든 솔루션을 검증하지 않아도 되도록
  • cf) 가지치기 전략의 예시: "알파-베타 가지치기" - 두 플레이어 게임에서, 각 플레이어는 각각 최선의 수를 둘 것을 가정하며, 게임 트리는 현재 게임 상태에서 가능한 모든 수를 포함함. 알파-베타 가지치기는 이 트리를 검색하면서, 현재 검색 중인 서브 트리가 현재의 최선을 보장하지 않을 때 더 이상 탐색을 진행하지 않음. 따라서, 더 이상 필요하지 않은 서브트리를 검색하지 않고도 최적의 해를 찾을 수 있게 됨.

미니 맥스 알고리즘

• 조합 검색에서 사용되는 휴리스틱
• 휴리스틱: 검색 전략의 속도를 높이기 위해 조합 검색에서 사용되는 방법. 최적의 다음 수만을 예측함.
• 대표적으로 미니맥스 알고리즘이 있음
• 목표: 상대방의 목표 달성을 방해하는 것
• 방식:
  • 컴퓨터는 게임의 승패가 결정되는 말단 노드로부터 거슬러 올라가 현재 시점에서 최적의 선택을 고를 수 있도록 이동 경로를 계산하며, 가능한 선택지별로 점수를 매김
  • 점수는 상대방이 승리하는 상황을 얼마나 쉽게 회피할 수 있느냐에 따라 결정됨
  • 점수 계산이 끝나면 최고 점수가 매겨진 노드를 선택하여 다음 돌의 위치 결정
• 한계:
  • 여전히 승리와 무관한 이동 경로까지 탐색에 포함시킴

알파-베타 가지치기(pruning)

• 불필요한 노드 탐색 회피하도록 알고리즘 디자인하는 것을 의미

• 최적 경로에 포함되지 않은 서브트리 탐색 회피

• 가정: "합리적인 플레이어라면 상대방에게 가장 좋은 경로를 피할 것이다."

  • 이러한 경로를 가지치기 함

• 알파, 베타 매개변수:

  • 계산 중에 사용되는 두 개의 기준값에 관련된 변수
  • 가능한 솔루션 집합의 수를 제한하기 위해 사용
  • 이미 탐색된 부분 트리에 따라 결정됨
  • 알파: 가능한 솔루션의 최대 하한 점수 (플레이어가 얻을 수 있는 최대 점수)
  • 베타: 가능한 솔루션의 최소 상한 점수 (상대방에게 가장 유리한 점수)

• 각 노드에 점수 할당 시 (잠재적인 이동 경로로 간주) 노드 점수의 현재 추정치가 알파와 베타 사이에 있는지 판단하여 가지치기 할지 결정 -> 탐색 공간 줄어들음

네가맥스(Negamax) 알고리즘

• 미니맥스 알고리즘의 변형

• 실제 환경에서 자주 이용됨

• 2인용 게임은 일반적으로 제로섬 게임임 - 한 플레이어의 손실이 다른 플레이어의 이득이 됨

• 이 특징을 활용하여 게임에서 승리할 확률 높이는 전략 제시

• 게임 진행 시, 상대방의 점수는 최소화하고 내 점수는 최대화하는 방향으로 움직임

• 즉, 상대방에게 불리한 위치뿐만 아니라 동시에 나에게 가장 유리한 위치를 찾는 것

• 미니맥스 알고리즘보다 더 간결함

• 알파-베타 가지치기 사용할 수 있음

easyAI 라이브러리 설치

• 2인용 게임 구축 위한 기본 함수 제공 라이브러리

pip3 install easyAI

마지막 동전 피하기 게임 봇 만들기

• 각 플레이어가 주어진 동전 뭉치에서 자기 차례마다 몇 개의 동전을 가져가는 게임
• 목표: 마지막 동전을 가져가는 것을 피함
• 각 차례마다 가져갈 수 있는 동전의 최소 개수와 최대 개수가 정해져 있음
• EasyAI 라이브러리의 Bones 레시피 사용

# This is a variant of the Game of Bones recipe given in the easyAI library

from easyAI import TwoPlayersGame, id_solve, Human_Player, AI_Player
from easyAI.AI import TT


class LastCoinStanding(TwoPlayersGame):
    def __init__(self, players):
        # Define the players. Necessary parameter.
        self.players = players

        # Define who starts the game. Necessary parameter.
        self.nplayer = 1

        # Overall number of coins in the pile
        self.num_coins = 25

        # Define max number of coins per move
        self.max_coins = 4

    # Define possible moves. 1 to 4 coins in the example
    def possible_moves(self):
        return [str(x) for x in range(1, self.max_coins + 1)]

    # Remove coins
    def make_move(self, move):
        self.num_coins -= int(move)

    # Did the opponent or I take the last coin?
    def win(self):
        return self.num_coins <= 0

     # Stop the game when somebody wins
    def is_over(self):
        return self.win()

    # Compute score
    def scoring(self):
        return 100 if self.win() else 0

    # Show number of coins remaining in the pile
    def show(self):
        print(self.num_coins, 'coins left in the pile')


if __name__ == "__main__":
    # Define the transposition(전치) table, saving the location and movement
    tt = TT()

    # Define the method returning the # of coins remaining
    LastCoinStanding.ttentry = lambda self: self.num_coins

    # Solve the game
    result, depth, move = id_solve(LastCoinStanding,
                                   range(2, 20), win_score=100, tt=tt)
    print(result, depth, move)

    # Start the game
    game = LastCoinStanding([AI_Player(tt), Human_Player()])
    game.play()

• id_solve 함수:
  • 반복적인 심화 분석을 통해 게임의 해법 찾음
  • 기본적으로 모든 경로를 탐색해 누가 이길 수 있는지 분석
  • 네가맥스 알고리즘 사용해 최적의 경로 탐색
  • 두 번째 매개변수 depth는 알고리즘의 탐색 깊이를 나타냄
    • 이 예제에서는 2 to 20 사이의 모든 깊이에 대해 탐색 시도

/Users/eunseo-ko/AIStudy/ESKAI/.venv/bin/python /Users/eunseo-ko/AIStudy/ESKAI/ch09/coins.py 
d:2, a:0, m:1
d:3, a:0, m:1
d:4, a:0, m:1
d:5, a:0, m:1
d:6, a:0, m:1
d:7, a:0, m:1
d:8, a:0, m:1
d:9, a:0, m:1
d:10, a:100, m:4
1 10 4
25 coins left in the pile

Move #1: player 1 plays 4 :
21 coins left in the pile

Player 2 what do you play ? 1

Move #2: player 2 plays 1 :
20 coins left in the pile

Move #3: player 1 plays 4 :
16 coins left in the pile

Player 2 what do you play ? 4

Move #4: player 2 plays 4 :
12 coins left in the pile

Move #5: player 1 plays 1 :
11 coins left in the pile

Player 2 what do you play ? 1

Move #6: player 2 plays 1 :
10 coins left in the pile

Move #7: player 1 plays 4 :
6 coins left in the pile

Player 2 what do you play ? 1

Move #8: player 2 plays 1 :
5 coins left in the pile

Move #9: player 1 plays 4 :
1 coins left in the pile

Player 2 what do you play ? 1

Move #10: player 2 plays 1 :
0 coins left in the pile

Process finished with exit code 0

틱택토 게임 봇 만들기

# This is a variant of the Tic Tac Toe recipe given in the easyAI library

from easyAI import TwoPlayersGame, AI_Player, Negamax
from easyAI.Player import Human_Player


class GameController(TwoPlayersGame):
    def __init__(self, players):
        # Define the players
        self.players = players

        # Define who starts the game
        self.nplayer = 1

        # Define the board - 3x3 board in this example
        self.board = [0] * 9

    # Define possible moves
    def possible_moves(self):
        return [a + 1 for a, b in enumerate(self.board) if b == 0]

    # Make a move
    def make_move(self, move):
        self.board[int(move) - 1] = self.nplayer

    # Does the opponent have three in a line?
    def loss_condition(self):
        possible_combinations = [[1, 2, 3], [4, 5, 6], [7, 8, 9],
                                 [1, 4, 7], [2, 5, 8], [3, 6, 9], [1, 5, 9], [3, 5, 7]]

        return any([all([(self.board[i - 1] == self.nopponent)
                         for i in combination]) for combination in possible_combinations])

        # Check if the game is over

    def is_over(self):
        return (self.possible_moves() == []) or self.loss_condition()

    # Show current position
    def show(self):
        print('\n' + '\n'.join([' '.join([['.', 'O', 'X'][self.board[3 * j + i]]
                                          for i in range(3)]) for j in range(3)]))

    # Compute the score
    def scoring(self):
        return -100 if self.loss_condition() else 0


if __name__ == "__main__":
    # Define the algorithm - depth of tree = 7 in this example
    algorithm = Negamax(7)

    # Start the game
    GameController([Human_Player(), AI_Player(algorithm)]).play()

메인 함수에서 정의

• AI 알고리즘으로 네가맥스 사용
• 알고리즘이 분석할 트리의 깊이는 7

/Users/eunseo-ko/AIStudy/ESKAI/.venv/bin/python /Users/eunseo-ko/AIStudy/ESKAI/ch09/tic_tac_toe.py 

. . .
. . .
. . .

Player 1 what do you play ? 5

Move #1: player 1 plays 5 :

. . .
. O .
. . .

Move #2: player 2 plays 1 :

X . .
. O .
. . .

Player 1 what do you play ? 3

Move #3: player 1 plays 3 :

X . O
. O .
. . .

Move #4: player 2 plays 7 :

X . O
. O .
X . .

Player 1 what do you play ? 9

Move #5: player 1 plays 9 :

X . O
. O .
X . O

Move #6: player 2 plays 4 :

X . O
X O .
X . O

Process finished with exit code 0