게임트리

인공지능과 게임

게임은 이전부터 인공지능의 매력적인 연구 주제

이유

• 지적 능력과 연관이 있다.
• 추상적으로 정의가 가능하다.
• 비교적 적은 수의 연산자
• 연산의 결과는 엄격한 규칙으로 정의됨

게임의 정의

• 2인용 게임, 제로썸 게임, 순차적인 플레이를 가정
  • 제로썸 게임 - 한 경기자는 반드시 승리 다른 경기자는 반드시 패배를 의미
• 두 경기자 : MAX, MIN
  • MAX : 먼저 수를 두는 플레이어
  • 휴리스틱을 정해야한다. 한 사람이 MAX의 N을 갖고 다른 사람이 MIN의 N을 갖는다.

Tik-Tao-Toe

• 간단한 게임임에도 불구하고 노드가 기하급수 적으로 증가한다.
• 컴퓨터의 계산이 길어지거나 메모리 공간이 부족하다.
• # of winning row : 이기는 행
  • 계산 법 -> 그림 참조
  • A* 와 다르다. 게임 트리는 expend 해서 계산하지 않아도 된다.
  • 게임트리의 핵심은 몇 수 앞을 볼지 결정해서 정해야 한다. 게임 판들의 값 중 가장 큰 값을 택해야한다.

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

• 3by3 크기를 가지고 있고 한 곳에 수를 놓으면 다른 사람이 놓을 수 있는 곳은 하나가 줄어들게 된다.
  • 987*…*1=9! = 362880

 

미니 맥스 알고리즘

• MAX는 평가 함수 값이 최대인 자식 노드를 선택하고 MIN은 평소 함수 값이 최소인 자식 노드를 선택
• 상대방이 최선의 수를 둔다고 가정.

두 수 앞을 본 미니 맥스 알고리즘, 3,6,2,8 중에 택해야함

위와 같이 MIN은 앞서 계산한 수 중 작은 값을 가질 것이라고 상정하고 MAX값 예측

 

알파베타 가지치기

• 미니맥스 알고리즘에서 형성되는 탐색 트리 중에서 상당부분은 결과에 영향을 주지 않으면 가지들을 쳐낼 수 있다는 데서 고안됨.
• 더 이상 방문하지 않는 노드들이 생긴다.
• 탐색 결과의 수를 줄이는 idea에서 착안하였다.