조합 폭발

개념

조합 폭발은 가능한 경우의 수가 너무 빠르게 증가해 모두 탐색하기 어려워지는 현상이다. 탐색 기반 인공지능의 큰 한계 중 하나이다.

예시

게임에서 한 수마다 가능한 선택지가 많고, 여러 수를 앞까지 보려면 노드 수가 기하급수적으로 증가한다. 미니맥스 알고리즘도 작은 게임에서는 가능하지만 체스나 바둑에서는 끝까지 탐색하기 어렵다.

$$N(d)=\sum _{i=0}^d{b}^i=O(b^d)$$

분기 수 $b$나 깊이 $d$가 조금만 커져도 경우의 수가 급격히 증가한다.

대응

• 휴리스틱 탐색으로 유망한 후보를 먼저 본다.
• 알파-베타 가지치기로 불필요한 가지를 줄인다.
• MCTS로 많은 시뮬레이션을 통해 근사적으로 좋은 수를 찾는다.
• A star 알고리즘으로 실제 비용과 추정 비용을 함께 고려한다.