AI의 몬테카를로 트리 탐색, 제약조건 만족 문제와 최적화 방법

게임탐색 – 몬테카를로 트리 탐색

실제로 단말 노드의 형세를 판단하여 제대로 수치화 하는 것은 쉽지 않다. 따라서 무작위 적인 시뮬레이션에 의해 형세의 유리한 정도를 결정하여 게임 트리를 구성하는 알고리즘이 몬테카를로 트리 탐색이다. 이 알고리즘은 휴리스틱이 필요 없을 뿐만 아니라 성능이 뛰어나다는 것이 확인되었다.

실제로 수 많은 이슈화가 되었던 알파고도 이러한 몬테카를로 트리 탐색 방법을 사용한다. 알파고에는 현재 주어진 바둑판에서 돌을 놓을 수 있는 유리한 정도의 점수 값을 계산하는 정책망, 전체 바둑판의 형세가 얼마나 유리한지에 대한 평가 값을 계산하는 가치망이 있다. 이렇게 알파고는 바둑 기보와 자체 경기 데이터를 사용하여 4개의 정책망과 1개의 가치망을 기계학습 방법으로 만들어졌다.

몬테카를로 트리 탐색 방법은 다음과 같은 4가지 단계가 있다.

1. 선택 단계 게임 트리를 사용하여 루트 노드로부터 아래로 이동하기 위해 자식 노드를 순차적으로 선택하는 것을 말한다. 자식 노드를 선택할 때 승률이 큰 것과 방문횟수가 작은 것을 선호하도록 우선순위를 둔다.

2. 확장 단계 선택 과정을 통해 마지막에 도달한 노드에 새로운 노드를 추가할 수 있다. 특정 조건을 만족하면 해당 수에 해당하는 노드를 추가한다.

3. 시뮬레이션 단계 시뮬레이션 단계는 노드의 형세 평가를 위해 승패가 결정될 때까지 무작위로 게임을 해보는 단계다 무작위로 선택하거나 약간 똑똑하지만 빠르게 계산되는 방법으로 게임을 한다.

4. 역전파 단계 역전파 단계는 시뮬레이션 게임의 승패 정보를 현재 노드에서 루트 노드까지의 경로 상에 있는 노드들의 이긴 횟수/전체 횟수 정보에 반영한다.

제약조건 만족 문제

제약조건 만족 문제는 주어진 제약조건을 만족하는 조합해를 찾는 것이다. 제약조건 문제는 문제 영역의 변수, 변수가 가질 수 있는 후보 값의 집합, 제약조건들로 정의된다.

1. 백트래킹 탐색 방법

백트랙킹 탐색 방법은 깊이 우선 탐색을 하는 것처럼 변수에 허용되는 값을 하나씩 대입해보는 방법이다. 모든 가능한 값을 대입해서 만족하는 것이 없으면 이전 단계로 돌아가서 이전 단계의 변수에 다른 값을 대입해서 다시 탐색한다.

2. 제약조건 전파 방법

제약조건 전파 방법은 인접 변수 간의 제약 조건에 따라 각 변수에서 허용되지 않는 값들을 제거하는 방식으로 변수들의 값을 결정하는 방법이다.

최적화

최적화는 허용되는 값들 중에서 주어진 기준을 가장 잘 만족하는 것을 찾는 일을 말한다. 최적화 문제에서 최적화의 대상이 되는 목적함수는 최소 또는 최대가 되도록 만들려는 함수를 뜻한다.

1. 조합 최적화

조합 최적화는 순회 판매자 문제와 같이 주어진 항목들의 조합으로 해가 표현되는 최적화 문제이다. 여기서 목적함수는 경로길이는 구하는 것이 된다.

2. 유전 알고리즘

유전 알고리즘은 대표적인 진화 연산의 하나로, 생물 진화를 모방해서 만든 집단 기반의 확률적 탐색 기법이다. 유전 알고리즘에서는 개체에 해당하는 후보해를 염색체처럼 코딩하여 표현한다. 개체는 후보해가 되고 환경은 문제, 적합도는 해의 품질이 된다.

유전 알고리즘은 많은 수의 후보해들로 구성된 모집단을 만들어서 염색체를 진화시킨다. 자연과 같이 환경에 잘 적응하는 개체를 골라내는 역할은 적합도 함수라고 불리는 함수가 한다. 이는 후보해가 주어진 문제에 얼마나 적합한 해인지 평가하는 역할을 한다. 또한 자연의 세대 교체를 위해 적합도가 높은 것은 자식을 낳을 가능성이 높게, 아닌 것은 낮게 하도록 한다. 이를 위해 룰렛 휠을 사용한다. 자연에서 개체들이 자식을 낳는 것처럼 유전 알고리즘에서도 가능하게 해야 하는데 이 때 사용하는 방법을 유전 연산자라고 한다. 그 중, 교차 연산자는 두 개의 염색체의 일부분씩을 교차해서 연결해 새로운 염색체를 만드는 것이고 돌연변이 연산자는 염색체를 무작위로 변경시켜서 새로운 염색체를 만든다. 부모 세대 모집단에서 적합도가 높은 것들을 자식 세대 모집단에 그대로 복사해 오도록 하는 엘리트주의 방법을 사용하여 우수한 개체를 다음 세대에 유지하는 방법을 사용하기도 한다.

이러한 유전 알고리즘처럼 최적해는 아니지만 우수한 해를 빠르게 찾기 위한 휴리스틱적인 문제해결 전략들을 메타 휴리스틱 기법이라고 한다. 대표적으로 유전 알고리즘, 모방 알고리즘, 입자 군집 최적화 기법 등의 기법들이 있다.

3. 함수 최적화

함수 최적화는 어떤 목적 함수가 있을 때, 이 함수를 최대로 하거나 최소로 하는 변수나 파라미터의 값을 찾는 것을 말한다. 최대값이나 최소값을 갖는 위치는 함수의 1차 미분이 0이다. 즉, 목적함수의 1차 편 미분 값이 0이 되는 x1, x2를 찾으면 해가 얻어진다.

4. 제약조건 최적화 문제

제약조건이 있는 함수 최적화 문제도 있는데 이러한 문제를 제약조건 최적화라고 한다. 제약조건을 만족하는 해들을 가능해라고 한다. 이러한 문제는 목적함수와 제약조건 함수들을 선형결합한 라그랑주 함수를 사용하여 해결한다. 추가로 사용되는 라그랑주 승수, 쌍대함수, 상보적 여유성 조건으로 최적해를 찾을 수 있다.

5. 최소제곱평균법

최소제곱평균법은 입력 값 x에 대한 함수 값과 데이터의 출력 값 y의 차이를 제곱한 것의 평균을 최소화하는 파라미터를 찾는 방법이다. 즉, 오차함수나 에너지 함수를 최소로 하는 함수를 찾는 방법이다. 이러한 회귀문제에서 최적함수는 주어진 데이터를 가장 잘 근사하는 함수를 의미한다.

6. 경사 하강법

경사 하강법은 오차 함수의 그레디언트를 사용하여 오차 함수의 값이 최소가 되는 위치의 파라미터를 찾는 방법이다. 여기서 그레디언트는 각 파라미터에 대해 편미분한 벡터를 의미한다. 이렇듯 오차를 줄이기위해 그레디언트 반대방향으로 파라미터 값을 조금씩 움직여서 오차 함수가 최소가 되는 파라미터를 찾는 것이 경사 하강법이라고 할 수 있다.

Writer: Jae-Hwan Lee