[인공지능] 3. 게임트리

1. 게임 프로그램

게임 조건

두 명의 경기자: 경기자들이 연합하는 경우는 다루지 않음

Zero-sum 게임: 한경기자의 승리는 다른 경기자의 패배(협동적인 승리 없음)

순차적인 게임

 

인공지능과 게임

 Tic-Tac-Toe나 체스, 바둑과 같은 게임은 추상적으로 정의할 수 있고 지적 능력과 연관이 있는 것으로 생각되었다.

▪ 게임의 상태(state)를 나타내기 쉽다

▪ 비교적 적은 수의 연산자, 연산의 결과는 규칙으로 정의된다.

 

하지만 체스나 바둑같은 게임을 완벽하게 분석하기는 아주 어렵다.
▪ 예) 바둑
▪ 처음 바둑판에 돌을 놓을 수 있는 곳은 19 x 19 = 361이다 ▪ 발생할 수 있는 경우의 수 = 361 x 360 x … 2 x 1 = 361!

    ▪ 즉, 바둑의 탐색트리에서 가능한 단말 노드의 개수는 361!

▪ 따라서 완벽한 탐색은 불가능

 

게임을 성공적으로 프로그래밍하려면?
▪ 주어진 시간 안에 효율적으로 탐색하여 최선의 수를 찾을 수 있는 능력이 필요 

   ▪ 최선의 수를 찾는 알고리즘: 미니맥스 알고리즘

   ▪ 시간이 제한된 상황에서 가장 좋은 수 찾기: 알파베타 가지치기

게임의 정의

-2인용 게임

-두 경기자를 MAX와 MIN

-항상 MAX가 먼저 수를 둔다고 가정

ex) Tic-tae-toe

 

Tic-Tac-Toe의 게임 트리

Tic-Tac-Toe의 게임 트리의 크기

Tic-Tac-Toe의 게임 트리는 크기가 얼마나 될까?
   ▪ 즉, 경우의 수? (단말 노드 수)
Tic-Tac-Toe 게임 보드는 3×3 크기를 가지고 있고 한 곳에 수를 놓으면 다른 사람이 놓을 수 있는 곳은 하나가 줄어들게 된다.

=9x8x7x...x1 = 9! =362,880

 

2. 미니맥스 알고리즘

게임에서의 탐색 (Adversarial Search)

2장에서 탐색의 정의와 다르다

▪ 게임에서의 목표 상태는 승리에 해당되는 단말 상태
▪ 상대방이 탐색에 영향을 미친다. 상대방이 어떻게 나올 것인지를 알아야 탐색이 진행될 수 있다. 어떻게 할까? 

▪ 적대적 탐색 (adversarial search)
   ▪ “적” 또는 “상대＂가 매번 내가 원하지 않는 방향으로 상태를 변화시킬 때 탐색하는 방법

안전하게 하려면 상대방이 최선의 수를 둔다고 가정한다
▪ 상대방이 실수할 수도 있으나, 최선의 수를 둔다고 가정하고 탐색하면 어떤 경우가 발생하더라도 이길 수 있을 것

미니맥스(Minimax) 알고리즘

게임트리가 아래와 같이 생성되었다고 가정할 때, 최선의 수를 찾기위한 알고리즘

목표 상태: 단말노드가 이기는 상태

탐색 전략

-MAX는 평가 함수값이 최대인 노드를 선택

-MIN은 무조건 평가 함수값이 작은 노드를 선택

Tic-Tac-Toe의 게임에서의 미니맥스

Example

Psedo Code

주어진 노드에서 minimax value를 결정하여 return함 (recursive algorithm)

 

최대화일때는 value를 -inf로 두어서 값을 비교, 최소화 노드일때는 +inf로 두어서 비교, 이때 코드는 재귀적으로 구현된다.

시간 복잡도

완벽한 깊이 우선 탐색을 수행

만약 트리의 최대 깊이가 m이고 각 노드에서의 가능한 수가 b개라면 시간복잡도는 O(b^m)

실제 게임 적용을 위해서는 비현실적으로 많아서

-> 게임이 끝날 때까지 검색하지 않고 몇 개의 수만을 검색해야 함, 상태 평가 함

 

4. 알파베타 가지치기

Alpha-Beta Pruning

Minimax 알고리즘은 시간 복잡도가 지수적으로 증가한다 -> 탐색시간 high

탐색시간을 어떻게 줄일 수 있을까?

▪Minimax 알고리즘에서 형성되는 탐색 트리 중에서 어떤 부분은 제외하여도 결과에 영향을 주지 않음

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

 

알파=MAX 경기자가 지금까지 발견한 최선의 값(최대값), MAX 경기자만 변경

베타=MIN 경기자가 지금까지 발견한 최선의 값(최소값), MIN 경기자만 변경

"미니맥스 알고리즘의 최적화 버전"

▪ 게임 트리에서 필요없는 가지를 잘라냄으로써 훨씬 빠르게 탐색

 

Root 노드의 알파값=-inf, +inf 로 초기화

탐색을 할 때 알파값과 베타값이 자식 노드로 전달된다

▪자식 노드에서는 알파와 베타를 비교하여 쓸데없는 탐색을 중지

▪즉 알파>=베타이면 다른 자식 노드 탐색 중지

 

MAX는 알파값만, MIN은 베타값만을 업데이트한다!

5. 불완전한 결정 

Imperfect Real-Time Decisions

미니맥스 알고리즘은 탐색 공간 전체를 생성하여 탐색 

▪ 실제로는 탐색 공간이 매우 커서 실현할 수 없다
알파베타 알고리즘
▪ 전체 탐색 공간 중 많은 부분을 가지치기 한다
▪ 그러나 탐색하는 부분에 대해서는 단말노드까지 탐색 필요

실제 환경에서는 적당한 시간 안에 다음 수를 결정하여야 한다. 어떻게 하면 될까?

 

불완전한 결정 필요
▪ 탐색을 끝내야 하는 시간에 도달하면, 탐색을 중단하고 탐색 중인 상태에 대하여 휴리스틱 평가 함수(evaluation function)를 적용해야 한다
▪ 즉, 비단말 노드이지만 단말 노드에 도달한 것처럼 생각한다
   ▪ 비단말 노드의 평가함수 값을 계산하여 탐색에 활용
   ▪ 이때 평가함수는 탐색에서의 휴리스틱 함수와 유사
        ◼ 휴리스틱 함수는 목표상태까지의 거리에 대한 추정치를 반환

 

불완전한 결정을 위한 평가함수 설계 원칙
▪ 승리 상태 > 무승부 상태 > 패배 상태 순으로 추정치가 높아야한다. 

▪ 추정치 계산에 너무 많은 시간이 걸리면 안된다 

▪ 실제 승리 확률과 유사한 추정치를 반환해야 한다