적대적 탐색은 우리가 세상보다 앞서 계획하려고 할 때 다른 에이전트가 우리에 대해 계획을 세울 때 발생하는 문제를 조사하는 탐색입니다.

• 이전 주제에서 우리는 종종 일련의 동작 형태로 표현되는 솔루션을 찾는 것을 목표로 하는 단일 에이전트와 관련된 검색 전략을 연구했습니다.
• 그러나 동일한 검색 공간에서 둘 이상의 에이전트가 솔루션을 검색하는 상황이 있을 수 있으며 이러한 상황은 일반적으로 게임 플레이에서 발생합니다.
• 둘 이상의 에이전트가 있는 환경을 다음과 같이 부릅니다. 다중 에이전트 환경 , 각 에이전트는 다른 에이전트의 상대이며 서로 대결합니다. 각 에이전트는 다른 에이전트의 작업과 해당 작업이 성능에 미치는 영향을 고려해야 합니다.
• 그래서, 서로 상충되는 목표를 가진 두 명 이상의 플레이어가 솔루션을 찾기 위해 동일한 검색 공간을 탐색하려고 시도하는 검색을 적대적 검색이라고 하며, 흔히 게임이라고 합니다. .
• 게임은 검색 문제와 휴리스틱 평가 기능으로 모델링되며, 이는 AI에서 게임을 모델링하고 해결하는 데 도움이 되는 두 가지 주요 요소입니다.

AI 게임 유형:

완벽한 정보:완벽한 정보를 가진 게임은 에이전트가 전체 보드를 들여다볼 수 있는 게임입니다. 에이전트는 게임에 대한 모든 정보를 갖고 있으며, 서로의 움직임도 볼 수 있습니다. 예를 들면 체스, 체커, 바둑 등이 있습니다.불완전한 정보:게임 내에서 에이전트가 게임에 대한 모든 정보를 갖고 있지 않고 무슨 일이 일어나고 있는지 알지 못하는 경우 이러한 유형의 게임을 tic-tac-toe, Battleship, blind, Bridge 등과 같이 정보가 불완전한 게임이라고 합니다.결정론적 게임:결정론적 게임은 엄격한 패턴과 게임 규칙 세트를 따르며 이와 관련된 무작위성이 없는 게임입니다. 예로는 체스, 체커, 바둑, 틱택토 등이 있습니다.비결정적 게임:비결정론적 게임은 예측할 수 없는 다양한 이벤트가 있고 기회나 행운의 요소가 있는 게임입니다. 이러한 기회나 행운의 요소는 주사위나 카드에 의해 소개됩니다. 이는 무작위이며 각 동작 응답은 고정되어 있지 않습니다. 이러한 게임을 확률적 게임(stochastic game)이라고도 합니다.
예: 주사위 놀이, 독점, 포커 등

참고: 이 주제에서는 결정론적 게임, 완전히 관찰 가능한 환경, 제로섬 및 각 에이전트가 교대로 작동하는 위치에 대해 논의합니다.

제로섬 게임

• 제로섬 게임은 순수한 경쟁을 포함하는 적대적 탐색입니다.
• 제로섬 게임에서 각 에이전트의 효용 이득 또는 손실은 다른 에이전트의 효용 손실 또는 이득과 정확하게 균형을 이룹니다.
• 게임의 한 플레이어는 단일 값을 최대화하려고 시도하고 다른 플레이어는 이를 최소화하려고 시도합니다.
• 게임에서 한 플레이어의 각 동작을 플라이라고 합니다.
• 체스와 틱택토는 제로섬 게임의 예입니다.

제로섬 게임: 내재된 사고

제로섬 게임에는 한 에이전트나 플레이어가 다음을 알아내려고 노력하는 내재된 사고가 포함됩니다.

• 무엇을 해야할지.
• 이사를 결정하는 방법
• 상대도 생각해야지
• 상대도 어떻게 해야 할지 고민 중

각 플레이어는 자신의 행동에 대한 상대방의 반응을 찾으려고 노력합니다. 이를 위해서는 AI의 게임 문제를 해결하기 위해 내장된 사고 또는 역추론이 필요합니다.

문제의 공식화:

게임은 다음 요소로 공식화될 수 있는 AI 검색 유형으로 정의할 수 있습니다.

초기 상태:게임이 시작될 때 어떻게 설정되는지 지정합니다.플레이어:상태 공간에서 어떤 플레이어가 이동했는지 지정합니다.행위):상태 공간에서 유효한 이동 집합을 반환합니다.결과(들,a):상태 공간에서의 이동 결과를 지정하는 전환 모델입니다.터미널 테스트:터미널 테스트는 게임이 끝나면 true이고, 그렇지 않으면 false입니다. 게임이 끝나는 상태를 종료상태(terminal states)라고 합니다.유틸리티(들, p):유틸리티 함수는 플레이어 p에 대한 최종 상태 s로 끝나는 게임의 최종 숫자 값을 제공합니다. 보수함수라고도 한다. 체스의 경우 결과는 승리, 패배 또는 무승부이며 보상 값은 +1, 0, ½입니다. 그리고 tic-tac-toe의 경우 유틸리티 값은 +1, -1, 0입니다.

게임 트리:

게임 트리는 트리의 노드가 게임 상태이고 트리의 가장자리가 플레이어의 움직임인 트리입니다. 게임 트리에는 초기 상태, 작업 기능 및 결과 기능이 포함됩니다.

예: Tic-Tac-Toe 게임 트리:

다음 그림은 tic-tac-toe 게임에 대한 게임 트리의 일부를 보여줍니다. 다음은 게임의 몇 가지 핵심 사항입니다.

• MAX와 MIN 두 명의 플레이어가 있습니다.
• 플레이어는 번갈아 가며 MAX로 시작합니다.
• MAX는 게임 트리의 결과를 최대화합니다.
• MIN은 결과를 최소화합니다.

예시 설명:

• 초기 상태에서 MAX는 처음 시작할 때 9개의 가능한 움직임을 가지고 있습니다. MAX 위치 x 및 MIN 위치 O, 두 플레이어는 한 플레이어가 연속으로 세 개가 있거나 모든 사각형이 채워지는 리프 노드에 도달할 때까지 교대로 플레이합니다.
• 두 플레이어 모두 각 노드인 minimax, 즉 최적의 적에 대해 달성할 수 있는 최고의 유틸리티인 minimax 값을 계산합니다.
• 두 플레이어 모두 틱택토를 잘 인식하고 최고의 플레이를 한다고 가정해 보겠습니다. 각 플레이어는 다른 플레이어가 승리하지 못하도록 최선을 다하고 있습니다. MIN은 게임에서 Max를 상대로 행동하고 있습니다.
• 따라서 게임 트리에는 Max 레이어, MIN 레이어가 있고 각 레이어는 다음과 같이 호출됩니다. 주름 . Max 장소 x, 그 다음 MIN은 O를 넣어 Max가 승리하는 것을 막고, 이 게임은 터미널 노드까지 계속됩니다.
• 이 경우 MIN이 이기거나 MAX가 이기거나 무승부가 됩니다. 이 게임트리는 MIN과 MAX가 번갈아 가며 틱택토 게임을 하는 가능성의 전체 검색 공간입니다.

따라서 minimax 절차에 대한 적대적 검색은 다음과 같이 작동합니다.

• MAX가 게임에서 승리하기 위한 최적의 전략을 찾는 것을 목표로 합니다.
• 이는 깊이 우선 탐색의 접근 방식을 따릅니다.
• 게임 트리에서 최적의 리프 노드는 트리의 어떤 깊이에도 나타날 수 있습니다.
• 터미널 노드가 발견될 때까지 최소최대 값을 트리까지 전파합니다.

주어진 게임 트리에서 최적의 전략은 각 노드의 최소값(MiniMAX(n))으로 결정될 수 있습니다. MAX는 최대값 상태로 이동하는 것을 선호하고 MIN은 최소값 상태로 이동하는 것을 선호합니다.