인공지능 4강 (게임트리)

학습개요

1. 게임은 지능적 판단과 전략을 활용해야 하기 때문에 인공지능 기법을 적용함으로써 지능적 메커니즘 구현을 확인할 수 있는 응용분야이다. 이번 시간에 학습할 게임트리는 장기나 바둑과 같은 게임을 진행할 때 활용할 수 있는 접근방법이다. 상대방이 있는 게임에서 다음 둘 수를 결정하는 과정과 탐색의 효율을 높이기 위한 방법에 대하여 논의할 것이다.

 학습목표

1. 최대최소 탐색을 통해 게임의 수를 결정하는 방법을 설명할 수 있다.
2. 게임트리에서 불필요한 가지의 탐색을 줄여 효율성을 높이는 방법을 설명할 수 있다.
3. 몬테카를로 트리 탐색의 개념을 설명할 수 있다.
4. 몬테카를로 트리 탐색 알고리즘의 선택, 확장, 시뮬레이션, 역전파 단계를 설명할 수 있다.

 주요용어

1. 최대최소 탐색 : 교대로 수를 두는 2인 게임에서 나의 수와 상대의 응수를 나타내는 게임 트리에서 수를 결정하기 위한 탐색 기법
2. α-β 가지치기 : 최대최소 탐색트리의 불필요한 가지를 잘라냄으로써 탐색의 성능을 높이기 위한 알고리즘
3. 몬테카를로 트리 탐색 : 게임과 같은 의사결정 문제의 해결을 위해 무작위 표본화를 바탕으로 구성되는 탐색 트리로부터 최적의 선택을 하기 위한 경험적 탐색 알고리즘
4. A* 알고리즘 : 다음 확장할 노드를 결정할 때 그 노드까지 도달하는 경로비용과 그 노드로부터 목표노드에 도달하기 위한 경로비용 예측치의 합이 최소인 노드를 선택하여 탐색하는 방법

정리하기

1. 1. 최대최소 탐색
2.   1) 나와 상대방이 최적의 선택을 한다는 가정하에 나에게 최악인 선택을 하는 상대방을 대상으로 나의 결정의 가치가 최대가 되는 결정을 내리는 방식으로 게임을 진행한다.
3.   2) 최대화와 최소화를 번갈아 반복하여 가장 우수한 후계노드를 선택한다.
4.   3) 계산시간이나 메모리 등의 자원 한계를 고려하여 적절한 깊이 이상이 되면 경험적 지식을 반영하여 정의한 평가함수를 이용해서 그 상태의 가치를 추정한다.
5.   4) 탐색이 불필요한 가지를 잘라 내어 탐색의 성능을 높이기 위해 α-β 가지치기 알고리즘을 활용할 수 있다.
6. 2. 몬테카를로 트리 탐색
7.   1) 의사결정 문제에 활용되는 경험적 탐색 알고리즘으로, 탐색공간의 무작위 표본화를 바탕으로 탐색트리를 구성한다.
8.   2) 선택, 확장, 시뮬레이션, 역전파 단계를 반복한다.
9.   3) 선택 단계에서는 탐사와 활용의 균형을 이룰 수 있는 전략을 활용하며, UCT 알고리즘은 잘 알려진 선택전략 중 하나이다.
10.   4) 시뮬레이션 단계에서는 순수한 무작위 방법이나 적절한 전략에 따른 유사 무작위 방법으로 수를 선택하는 방법을 사용할 수 있다.
11.   5) 최종적인 최적 행동 선택을 위해서는 최대 자식, 강인한 자식, 최대-강인 자식, 안전한 자식 등 적절한 전략을 선택할 수 있다.