인공 지능의 알파 베타 가지 치기

알파 베타 가지 치기는 최소 최대 알고리즘에 대한 최적화 기술입니다. 이 블로그의 과정을 통해,우리는 알파 베타 가지 치기가 무엇을 의미하는지 논의 할 것이고,우리는 미니 맥스 알고리즘,좋은 순서를 찾기위한 규칙 등을 논의 할 것입니다.

1. 소개
2. 최소 최대 알고리즘
3. 알파-베타 가지 치기의 핵심 포인트
4. 가지 치기의 이동 순서
5. 좋은 순서를 찾는 규칙
6. 파이썬 코드

소개

‘가지 치기’라는 단어는 가지와 잎을 자르는 것을 의미합니다. 에 데이터 과학 가지 치기 의사 결정 트리 및 무작위 포리스트에서 포스트 및 사전 가지 치기를 나타내는 많이 사용되는 용어입니다. 알파-베타 가지 치기는 의사 결정 나무에서 쓸모없는 가지를 가지 치기 일뿐입니다. 이 알파-베타 가지 치기 알고리즘은 1900 년대에 연구자들에 의해 독립적으로 발견되었다.

알파-베타 가지 치기는 다음 섹션에서 논의되는 미니 맥스 알고리즘에 대한 최적화 기술이다. 가지 치기의 필요성은 어떤 경우에는 의사 결정 나무가 매우 복잡해진다는 사실에서 비롯되었습니다. 이 트리에서 일부 쓸모없는 분기는 모델의 복잡성을 증가시킵니다. 그래서,이를 방지하기 위해,알파-베타 가지 치기는 컴퓨터가 전체 트리를 볼 필요가 없도록 재생 온다. 이러한 비정상적인 노드는 알고리즘을 느리게 만듭니다. 따라서 이러한 노드를 제거하면 알고리즘이 빨라집니다.

*알고리즘에 대해 알아보십시오.

미니 맥스 알고리즘

미니 맥스는 순차적 인 2 인용 게임에 대한 고전적인 깊이 우선 검색 기술입니다. 두 선수는 최대 및 최소라고합니다. 최소 최대 알고리즘은 루트 노드의 플레이어 인 최대에 대한 최적의 이동을 찾기 위해 설계되었습니다. 검색 트리는 게임의 끝 또는 최대 검색 깊이에 도달 할 때까지 깊이 우선 방식으로 루트에서 모든 노드를 재귀 적으로 확장하여 생성됩니다. 이 알고리즘을 자세히 살펴 보겠습니다.

이미 언급했듯이 게임에는 최대 및 최소의 두 플레이어가 있습니다. 맥스는 첫 번째 단계를 재생. 맥스의 임무는 보상을 극대화하는 반면,분의 임무는 맥스의 보상을 최소화하고 동시에 자신의 보상을 증가시키는 것입니다. 게임이 끝날 때 그들 중 어느 하나가 최대에게 최고의 보상을 줄 것이다? 이 질문에 대답하기 위해,우리는 충분한 깊이에 게임 트리를 탐구하고 최소 최적으로 최대의 보상을 최소화하기 위해 재생한다고 가정 할 필요가있다.

다음은 예이다. 네 개의 동전은 행에 각 플레이어는 그/그녀의 차례에 하나의 동전 또는 두 개의 동전을 선택할 수 있습니다. 마지막 동전 승리를 집어 플레이어. 맥스가 먼저 플레이한다고 가정하면 맥스가 이기기 위해 어떤 움직임을 취해야합니까?

맥스가 두 개의 동전을 선택하면 두 개의 동전 만 남아 있고 분은 두 개의 동전을 골라 이길 수 있습니다. 따라서 동전 1 개를 집어 올리면 맥스의 보상을 극대화 할 수 있습니다.

알 수 있듯이 아래 그림의 트리 노드에는 몇 가지 값이 새겨 져 있습니다. 노드의 최소값은 터미널 노드인 경우 노드의 유틸리티입니다.

노드가 비단말 최대 노드인 경우,노드의 최소값은 노드의 모든 후계자의 최소값의 최대값이다. 한편,노드가 비단말 최소 노드인 경우,노드의 최소값은 노드의 모든 후계자의 최소값 중 최소값이다.

이제 알파 베타 가지 치기의 아이디어를 논의 할 것입니다. 우리는 표준 최소 최대 알고리즘에 알파-베타 가지 치기를 적용하는 경우는 표준 알고리즘과 동일한 결정을 제공하지만 자두 또는 알고리즘에 의해 만들어진 최종 결정에 영향을 미치지 않는 의사 결정 트리,즉 특이한 노드를 잘라냅니다. 이 복잡한 나무의 해석의 복잡성을 방지하는 데 도움이 될 것입니다.

알고리즘이 어떻게 작동하는지 확인하십시오.

이제이 기술의 직관에 대해 논의하겠습니다. 우리가 아래의 트리에서 미니 맥스 결정을 찾기 위해 노력하자 :

이 경우,

여기에서 위 결과에서 당신은 우리가 결측값에서 최대를 찾아낼 수 있는 방법 당신의 마음에 있는 의심이 있어야 한다. 그래서,여기에 당신의 의심의 해결책도 있습니다:

두 번째 노드에서 우리는 최소값을 다음과 같이 선택합니다. 이제 경우 씨<=3 그리고 우리는 3 의 최대를 선택해야합니다,씨,2 최대 값은 3 이 될 것입니다.

우리는 그 노드를 보지 않고 결정에 도달했습니다. 그리고 이것이 알파-베타 가지 치기가 시작되는 곳입니다.

알파-베타 가지 치기의 핵심 포인트

• 알파:알파는 최대화 경로를 따라 모든 인스턴스에서 찾은 최상의 선택 또는 가장 높은 값입니다. 알파의 초기 값은-1000 입니다.

• 베타:베타는 최소화의 경로를 따라 모든 인스턴스에서 찾은 최상의 선택 또는 가장 낮은 값입니다. 알파에 대한 초기 값은+100 입니다.

• 알파-베타 가지 치기의 조건은 다음과 같습니다.

• 각 노드는 알파 및 베타 값을 추적해야합니다. 알파는 최대 차례 일 때만 업데이트 할 수 있으며 마찬가지로 베타는 최소의 기회 일 때만 업데이트 할 수 있습니다.

• 최대 만 알파 값을 업데이트하고 최소 플레이어는 베타 값을 업데이트합니다.

• 노드 값은 트리의 역으로 이동하는 동안 알파 및 베타 값 대신 상위 노드로 전달됩니다.

• 알파 및 베타 값은 자식 노드에만 전달됩니다.

알파-베타 가지 치기 작업

1. 먼저 초기 이동부터 시작합니다. 우리는 처음에 알파와 베타 값을 최악의 경우,즉 알파와 베타 값을 정의 할 것입니다. 알파가 베타보다 크거나 같아질 때만 노드를 잘라낼 것입니다.

2. 알파의 초기 값이 베타보다 작기 때문에 우리는 그것을 가지 치기하지 않았다. 이제 맥스에 대한 차례입니다. 그래서 노드 디,알파 값이 계산됩니다. 노드의 알파 값은 최대(2,3)입니다. 따라서 노드 디에서 알파 값은 3 이 될 것입니다.

3. 이제 다음 움직임은 노드에있을 것입니다. 따라서 노드에서 비,알파 베타의 값은 최소(3,9,9,10)입니다. 그래서 노드 B 값이 될 것입니다 alpha=–∞및 베타 3.

다음 단계에서는 알고리즘이 노드의 다음 후계자를 트래버스합니다.

4. 이제 맥스에 대한 차례입니다. 그래서,노드 전자에서 우리는 최대를 찾을 것입니다. 알파의 현재 값은—–그리고 그것은 5 와 비교 될 것입니다. 그래서,MAX(-∞,5)5. 그래서,노드 이자형,알파=5,베타=5. 이제 알파가 베타보다 크다는 것을 알 수 있듯이 가지 치기 조건을 만족하므로 노드 전자의 올바른 후계자를 가지 치기 할 수 있으며 알고리즘은 통과되지 않으며 노드 전자의 값은 5 가 될 것입니다.

6. 노드에서 알파는 최대값으로 최대값으로 변경됩니다. 그래서 지금의 가치는 알파와 베타에서는 노드가 될 것입니다(3,+∞)각각 전송됩니다 C. 노드 이러한 동일한 값이 전송될 노드에프케

7. 에서 노드 에프 알파의 값은 0 인 왼쪽 분기와 비교됩니다. 따라서 최대(0,3)는 3 이되고 1 인 오른쪽 자식과 비교되고 최대(3,1)=3 은 여전히 3 이 남아 있지만 노드 값은 에프 1 이됩니다.

8. 이제 노드 에프 노드 값을 반환합니다 1 에 씨 그리고 비교 베타 값…에서 씨.이제 그 차례 최소. 따라서 최소(++1)는 1 이됩니다. 이제 노드 씨,3,및 3=1 및 알파는 베타보다 크며 가지 치기 조건을 다시 만족시킵니다. 그래서,노드의 다음 후속 즉. 지 정리되고 알고리즘은 전체 하위 트리를 계산하지 않았습니다.

이제,씨에 노드 값을 반환합니다 ㅏ 그리고 최고의 값 에이 될 것입니다 최대(1,3)3 이 될 것입니다.

위의 표현 된 트리는 계산 된 노드와 계산되지 않은 노드를 보여주는 마지막 트리입니다. 따라서,이 예에서 최대화의 최적 값은 3 이 될 것입니다.

오픈 소스 파이썬 라이브러리를 살펴보십시오.

가지 치기의 이동 순서

알파–베타 가지 치기의 효과는 노드를 검사하는 순서를 기반으로합니다. 이동 순서는 알파 베타 가지 치기에서 중요한 역할을합니다.

알파 베타 프루닝에는 두 가지 유형의 이동 순서가 있습니다:

1. 최악의 순서:알파 베타 가지 치기의 경우 알고리즘에 의해 가지 치기 된 노드가 없으며 표준 미니 맥스 알고리즘처럼 작동합니다. 이것은 알파 및 베타 요인 때문에 많은 시간을 소비하며 효과적인 결과를 제공하지 않습니다. 이를 가지 치기에서 최악의 순서라고합니다. 이 경우 최상의 이동은 트리의 오른쪽에서 발생합니다.
2. 이상적인 순서:알고리즘에 의해 정리 된 노드의 알파 베타 가지 치기 많은 경우에. 이것은 가지치기안에 이상적인 주문에게 부른다. 이 경우 최상의 이동은 트리의 왼쪽에서 발생합니다. 따라서 트리 왼쪽의 첫 번째 검색을 적용하고 동일한 시간에 최소 최대 알고리즘으로 두 배 깊이 이동합니다.

좋은 순서를 찾는 규칙

• 가장 낮은 노드에서 최고의 이동이 발생
• 최고의 이동을 찾는 동안 도메인 지식 사용
• 노드의 순서는 가장 좋은 노드가 먼저 계산되는 방식이어야합니다

초보자를위한 파이썬 자습서를 확인하십시오

파이썬 코드

class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target

이 문서에서 우리는 게임 이론의 중요한 구성 요소를 보았다. 미니 맥스 알고리즘의 성능은 좋지만 알고리즘은 느립니다. 그래서 빨리 만들기 위해 우리는 성능을 향상시키기 위해 의사 결정 트리에서 특이한 노드를 줄일 알파-베타 가지 치기 알고리즘을 사용합니다. 요즘 빠르고 잘 수행 알고리즘이 널리 사용됩니다.

훌륭한 학습에서 도메인의 업 스킬 및 마스터 알파 베타 가지 치기 및 기타 알고리즘에 이르기까지 이러한 인공 지능 및 기계 학습 과정을 확인하십시오.

추가 읽기

1. 인공 지능의*검색 알고리즘(인공 지능)
2. 의사 결정 트리 알고리즘 예제와 함께 설명
3. 인공 지능|개념,구현,장점,단점에서 최고의 첫 번째 검색 알고리즘
4. 인공 지능이란 무엇입니까? 인공 지능은 어떻게 작동합니까,유형 및 미래?