탐색 - 게임트리 탐색, 제약 조건 문제 / 탐색기법의 활용

게임을 위한 탐색

- 다수가 상호 배타적인 환경에서 승리하기 위한 경로를 탐색하는 것.

- 승리하기 위해선 한 수가 아닌 n 수 앞을 봐야 함! -> 이를 통해 현재 상태의 선택을 결정

- 휴리스틱한 기준에 의한 추정치만을 제공

1. 말패게임(last-on-loses) //31게임 같은거

- 임의의 수의 칩에서 시작하여 1~3개의 칩을 냄. 마지막 칩을 들어낸 사람이 승자.

- 4개의 칩인 경우, 탐색트리 

출처 : https://slidesplayer.org/slide/11068593/

- 4k+1개의 칩이 남아있게 되면 이김.

- 평가함수 :

- 평가함수를 사용한 말패게임 // n = 1, 2, 3    

2. 최소최대 탐색법

- 최소화자와 최대화자로 구성되어 있다고 가정하고 탐색해 나가는 저략.

- 몇 수 앞을 내다보느냐가 탐색의 양을 결정. //탐색의 은 휴리스틱 기법을 이용하여 조절

- 최소최대법을 사용할 때 알파-베타 가치지기를 사용하면 탐색의 영역을 줄일 수 있다.

*알파-베타 가지치기

- 최대화 노드에서 가능한 최소의 값(알파 a)과 최소화의 노드에서 가능한 최대의값(베타 b)를 사용한 게임 탐색법

- 기본적으로 깊이우선탐색(DFS)를 이용

3. 제약 조건 만족 문제 (8-queen문제)

- 여왕은 다음과 같은 제약조건에 맞아야 함.

이는 곧  < 같은 행, 열(위치) 안돼 | 대각선 안돼 > 이다.

*서로 다른 x(여왕) 값을 가져야 함.

---

탐색기법의 활용

- 공장 자동화, 로보트의 경로 계획에 사용될 수 있음.
//NASA의 GPSS(ground processing scheduling system) : 주어진 인원과 장비로 우주왕복선의 보수를 마치도록 적절한 일정을 탐색하는 것

- 비행기 좌석 예약 시스템 : 승객의 요구를 최대 수용하고, 항공사의 이익을 극대화하는 탐색

- 게임 //체스(딥러닝), 바둑(알파고)

- 경제학적 응용

- 실제 게임의 경우 탐색의 양이 폭증 -> 지식 활용에 대한 연구가 많이 요구됨.