AI의 최소 최대 알고리즘: 구성 요소, 속성, 장점 및 제한 사항

Minimax로 널리 알려진 AI 의 최소 최대 알고리즘은 의사 결정, 게임 이론 및 인공 지능(AI)에 사용되는 역추적 알고리즘입니다. 상대방도 최적의 플레이를 하고 있다고 가정하고 플레이어에게 최적의 움직임을 찾는 데 사용됩니다. Chess, Tic-Tac-Toe, Checkers, Go 등과 같은 인기 있는 2인용 컴퓨터 또는 온라인 게임에서 이 알고리즘을 사용합니다.

역추적 알고리즘은 후보가 한 번에 한 단계씩 솔루션을 향해 점진적으로 구축되는 방식으로 계산 문제에 대한 솔루션을 찾는 데 사용됩니다. 그리고 솔루션을 완료하지 못한 후보자는 즉시 포기됩니다.

어떻게 작동합니까?

AI 의 최소 최대 알고리즘 에는 Maximiser와 Minimiser의 두 가지 플레이어가 있습니다. 이 두 플레이어는 한 사람이 가능한 가장 높은 점수 또는 최대 이익을 얻으려고 시도하는 동안 상대방이 가장 낮은 점수 또는 최소 이익을 얻으려고 시도하면서 게임을 합니다.

모든 게임 보드에는 평가 점수가 할당되어 있으므로 Maximiser는 최대 값을 선택하고 Minimiser는 카운터 이동으로 최소화된 값을 선택합니다. Maximiser가 우세하면 보드 점수는 양수 값이 되고 Minimiser가 우세하면 보드 점수는 음수 값이 됩니다.

이것은 총 유틸리티 점수가 두 플레이어에게 나누어지는 제로섬 게임 개념을 기반으로 합니다. 따라서 한 선수의 점수가 오르면 상대 선수의 점수가 낮아지므로 총 점수는 항상 0이 됩니다. 따라서 한 선수가 이기려면 다른 선수가 져야 합니다.

세계 최고의 대학에서 온라인으로 머신 러닝 인증 및 AI 과정 에 참여하십시오 . Masters, Executive PGP 또는 ACP를 획득하여 경력을 빠르게 추적하십시오.

AI의 최소 최대 알고리즘 분석

AI 의 최소 최대 알고리즘에서 깊이 우선 검색 알고리즘을 사용하여 전체 게임 트리를 탐색합니다 . 트리의 터미널 노드까지 완전히 진행한 다음 트리를 통해 역추적합니다.

목표는 플레이어에게 가능한 최고의 움직임을 찾는 것입니다. 평가 점수가 가장 높은 노드를 선택하여 수행할 수 있습니다. 상대방의 모든 잠재적인 움직임을 평가한 후 최선의 선택이 이루어질 것입니다. 알고리즘은 끝까지 가능한 모든 값을 미리 보고 플레이어를 위해 결정을 내립니다.

원천

위의 게임 트리는 움직임을 평가하는 데 사용되는 중첩 데이터 구조입니다. 여기서 루트 노드는 레벨 0이며, 레벨 1 또는 상위 노드로 분기되고, 레벨 2 또는 하위 노드로 추가 분기됩니다. 분기는 무한한 수준의 잠재력을 가진 많은 수준으로 계속될 수 있습니다. 레벨 0은 보드의 현재 상태와 같고 레벨 1은 다음 이동에 따라 보드의 가능한 모든 상태입니다.

따라서 플레이어 2가 이동했다면 루트 노드가 플레이어 1의 이동을 기다리는 보드의 현재 상태라고 가정할 수 있습니다. 레벨 1 노드에는 선수 1의 가능한 모든 움직임이 포함되고 레벨 2 노드에는 선수 1의 가능한 각 움직임을 기반으로 한 선수 2의 모든 가능한 움직임이 포함됩니다.

네 개의 최종 상태가 있고 이들에 도달하는 경로가 나무의 루트에서 네 개의 잎으로 이어지는 예를 고려하십시오. 네 잎의 값은 왼쪽이 3, 6이고 오른쪽이 4, 7입니다. 최대화자/플레이어 1이 움직일 차례입니다. 알고리즘을 실행하려면 각 이동에 대한 가정이 이루어져야 합니다.

참가자 1이 왼쪽으로 가기로 선택하면 Minimiser/Player 2는 3과 6 중에서 가장 작은 것을 선택해야 하므로 3을 선택할 것입니다. 반면에 참가자 1이 오른쪽을 선택하면 참가자 2는 최소값인 4를 선택합니다. 두 값 중 4와 7입니다. 따라서 레벨 1은 이제 값 3과 4를 갖습니다.

Player 1/Maximiser의 차례이므로 최대 레벨 1 노드를 선택해야 합니다. 따라서 그들은 3을 선택할 것입니다. 그런 다음 최적의 선택은 왼쪽으로 가는 것입니다.

AI의 최소 최대 알고리즘 단계는 다음과 같이 설명할 수 있습니다.

1. 전체 게임 트리를 만듭니다.
2. 평가 함수를 기반으로 리프 노드의 점수를 평가합니다.
3. 리프에서 루트 노드로 역추적:

Maximizer에 대해 최대 점수가 있는 노드를 선택합니다.

Minimizer에서 최소 점수를 가진 노드를 선택합니다.

4. 루트 노드에서 최대값을 가진 노드를 선택하고 각각의 이동을 선택합니다.

더 읽어보기: 기계 학습 프로젝트 아이디어

AI의 최소 최대 알고리즘 속성

• 알고리즘은 완전합니다. 즉, 유한 검색 트리에서 솔루션이 확실히 발견됩니다.
• 두 플레이어가 모두 최적의 상태로 플레이하는 것이 최적입니다.
• 게임 트리에 대한 깊이 우선 탐색(DFS)으로 인해 알고리즘의 시간 복잡도는 O(b m )이며, 여기서 b는 분기 요소이고 m은 트리의 최대 깊이입니다.
• DFS와 마찬가지로 이 알고리즘의 공간 복잡도는 O(bm)입니다.

장점

• 검색 공간에 대한 철저한 평가가 수행됩니다.
• AI의 의사 결정은 쉽게 가능합니다.
• 이 알고리즘으로 새롭고 스마트한 기계가 개발됩니다.

제한 사항

• 거대한 분기 요인 때문에 목표에 도달하는 과정이 더 느립니다.
• 가능한 모든 노드 및 분기에 대한 평가 및 검색은 엔진의 성능과 효율성을 저하시킵니다.
• 두 선수 모두 선택의 여지가 너무 많습니다.
• 시간과 공간의 제약이 있는 경우 전체 트리를 탐색할 수 없습니다.

그러나 Alpha-Beta Pruning을 사용하면 알고리즘을 개선할 수 있습니다.

결론

이 기사는 AI에서 최소-최대 알고리즘의 모든 측면을 설명합니다. 먼저 이론 소개와 사용 사례와 함께 제공되며 그 후 알고리즘이 게임에서 어떻게 작동하는지 설명합니다.

알고리즘은 플레이어의 움직임과 카운터 움직임을 기반으로 최적의 움직임을 결정하는 방법을 설명하기 위해 세분화됩니다. 그런 다음 알고리즘의 속성이 나열됩니다. 마지막으로 알고리즘의 장점과 단점을 제시한다.

머신 러닝에 대해 자세히 알아보려면 IIIT-B & upGrad의 기계 학습 및 AI 경영자 PG 프로그램을 확인하세요. 이 프로그램은 일하는 전문가를 위해 설계되었으며 450시간 이상의 엄격한 교육, 30개 이상의 사례 연구 및 과제, IIIT를 제공합니다. -B 동문 자격, 5개 이상의 실용적인 실습 캡스톤 프로젝트 및 최고의 기업과의 취업 지원.