Adversarial Search
게임 프로그램과 machine planning 같은 AI 프로그램들은 가끔 탐색 알고리즘으로서 Minimax algorithm, search tree pruning, alpha-beta pruning 등등을 사용하는데, 그러한 탐색을 적대탐색 (Adversarial Search) 라고 한다. ..... (Wikipedia : Adversarial search)
계획, 행동 그리고 학습에서 어려운 문제 중 하나는 다른 능동적인 에이전트들이 존재하는 환경에서 계획하고 행동하는 것이다. 다른 에이전트들이 어떻게 행동할 것인지에 대한 지식이 없다면, 예측 불가능한 미래에 대해 멀리 계획하지 않고 감지/계획/행동(sense/plan/act) 구조를 사용할 수밖에 없다. 그러나 그러한 지식이 있다면, 에이전트는 다른 에이전트들의 행동 결과를 명시적으로 고려하는 계획을 수립할 수 있다. 두 개의 에이전트가 있는 특수한 경우를 생각해 보자. 이들이 서로 상대방의 행동을 고려할 수 있는 이상적인 설정은 에이전트의 행동이 서로 번갈아 일어나는 것이다. 우선 한 에이전트가 행동하고, 다음 다른 에이전트가 행동하는 식으로 진행하는 것을 말한다 .......... 두 개의 에이전트가 둘 중 하나가 이기거나 (따라서 다른 쪽이 지거나) 또는 비길 때까지 번갈아 행동한다. 각 플레이어는 환경과 자신에 관한 완전한 모델과 상대방의 가능한 행동 및 그 결과에 대한 완전한 모델을 가지고 있다 (물론 어느 쪽도 상대방이 어떤 상황에서 실제로 무슨 행동을 할 것인지에 대해 완벽한 지식을 가지고 있는 것은 아니다). 이런 종류의 게임에 대한 연구를 수행함으로써, 에이전트 사이의 목표가 상호 충돌하지 않더라도, 다수의 에이전트가 있는 상황에서 계획을 수립하는 보다 일반적인 문제에 대해 통찰할 수 있다. ............. 체스 (chess) 나 체커 (checker), 바둑 등 일반적인 게임들이 이 범주에 들어간다는 것을 알 수 있을 것이다 ............... (Nils J.Nilsson 1998)
term :
게임 (Game) 최소최대 (Mini-max) 알파베타 가지치기 (Alpha-Beta Pruning) 인공지능 (Artificial Intelligence) 적대 탐색 (Adversarial Search) 제약조건 만족 문제 (Constraint Satisfaction Problem) 탐색 (Search) 휴리스틱 탐색 (Heuristic Search) 계획 (Planning) 체스 (chess) 문제해결 (Problem Solving) 바둑 (baduk) 에이전트 (Agent) 평가함수 (Evaluation Function)
paper :
적대 탐색 (Adversarial Search) : Nils J.Nilsson