인공지능 게임에서의 탐색
Mini-max algorithm
Mini-max 게임은 1:1상황인 게임에서 일어난다.
먼저MAX노드와 MIN노드가 있다.
MAX노드는 자신에 해당하는 노드로 자기에게 유리한 최대값을 선택
MIN노드는 상대방에 해당하는 노드로 최소값을 선택하게 한다.
이 알고리즘은 단말 노드부터 위로 한 단계씩 올라가면서 최소-최대 연산을 반복하여 "자신"이 선택할 수 있는 방법중 가장 좋은 값을 결정하는 알고리즘이다.
그림으로 설명을 하겠다.
맨첨의 노드는 자신의 값을 나열을 했으며 이미 이 값들은 자신의 기준에서 MAX값들을 고른것이다. 그 다음에는 상대방 MIN값을 골라야한다.
상대방 입장에서는 작은값이 유리한 값이므로 위의 그림과 같이 수를 선택하고 이를 계속 반복을 한다.
이렇게 계속 반복을 하다보면 자신의 MAX값을 할당받게 된다.
즉 맨 꼭대기 위에 있는 노드를 정하는 순간 여러개의 노드들이 생성이 되며 이를 순차적으로 아래에서 위로 반복하여 맨꼭대기의 노드의 값을 정하는 방식이다.
a-b 가지치기
a-b가지치기는 검토해 볼 필요가 없다라고 판단하면 더 이상 탐색을 하지않는 기법이다.
이 기법은 깊이 우선 탐색으로 제한 깊이까지 탐색을 하고 MAX노드와 MIN노드의 값을 결정한다.
a: max node 로 a값이 커지면 커졌지 작아지지 않으므로 MIN노드의 현재값이 부모 노드의 현재 값보다 작거나 같으면 자식노드 탐색을 중지한다. 이를 cou-off라 부른다.
b: min node 로 b값이 작으면 작아졌지 커지지 않으므로 MAX노드의 현재값이 부모 노드의 현재 값보다 크거나 같으면 나머지 자식 노드 탐색을 중지.
위의 그림처럼 맨 아래에 있는 자식노드인 5와9가 a가지치기를 적용하였고, 위에서 두번째 노드인 5의 자식노드들도 가지치기를 당했다. 먼저 5와9가 당한이유는 이미 5가 나오생성되기도 전에 이미 작은값인 4인 노드가 생성이 되었기 때문에 자식노드를 생성할 이유가 없어진 것이다. 그래서 5가 a가지치기를 당한것이고 9도 이와같다.
통째로 a가지치기를 당한 두번째 노드인 5의 자식노드들은 맨 아래의 있는 자식노들이 9,8,6으로 이미 생겨났기에 5보다 작아질수 없기에 현재 MIN노드가 6인 부모노드의 현재 값보다 작기에 나머지 자식 노드 탐색을 중지 한것이다.
몬테카를로 트리 탐색 기법
탐색 공간을 무작위 표본 추출을 하면서 탐색트리를 확장하여 가장 좋아 보아는 것을 선택하는 휴리스틱 탐색 방법중 하나이다.
몬테카를로 트리 탐색기법은 총 4단계를 반복을 한다.
먼저 선택부분은 트리 정책을 적용을 하고 루트노드에서 시작을 한다.
이 트리정책에 따라 자식 노드를 선택하여 단말노드까지 내려가는 방식이다.
여기서 노드를 선택을 할 때 승률과 노드 방문횟수를 고려하여 선택을 하며 여기서 많이 쓰이는 방법은 ucb방식이라고 이 값이 큰 것을 선택한다.
먼저 활용부분에서 우선적으로 승률이 높은것을 선택하지만 탐험부분 무조건 승률이 안높아도 아직 탐색이 덜 된것이 있으면 그것을 합산하여 값읗 매긴다.
그리고 확장부분은 단말노드에서 트리 정책에 따라 노드를 추가한다.
이렇게 추가된 노드를 가지고 시뮬레이션을 돌리다보면 결과가 나오는데 그 결과를 역전파를 시켜주어서 단말노드에서 루트 노드까지 올라가면서 승점에 반영을 하는 방식이다.