전제 조건: 게임 이론의 미니맥스 알고리즘 , 게임이론의 평가기능
알파-베타 가지치기는 실제로 새로운 알고리즘이 아니라 minimax 알고리즘을 위한 최적화 기술입니다. 이는 계산 시간을 크게 줄여줍니다. 이를 통해 훨씬 더 빠르게 검색할 수 있으며 게임 트리의 더 깊은 수준으로 이동할 수도 있습니다. 더 나은 이동 방법이 이미 존재하기 때문에 검색할 필요가 없는 게임 트리의 가지를 잘라냅니다. 이는 minimax 함수에서 2개의 추가 매개변수, 즉 알파와 베타를 전달하기 때문에 알파-베타 가지치기라고 불립니다.

매개변수 알파와 베타를 정의해 보겠습니다.

알파 최고의 가치는 최대화기 현재 해당 수준 이상을 보장할 수 있습니다.
베타 최고의 가치는 최소화 현재는 해당 수준 이하를 보장할 수 있습니다.

유사 코드:

 function minimax(node, depth, isMaximizingPlayer, alpha, beta): if node is a leaf node : return value of the node if isMaximizingPlayer : bestVal = -INFINITY for each child node : value = minimax(node, depth+1, false, alpha, beta) bestVal = max( bestVal, value) alpha = max( alpha, bestVal) if beta  <= alpha: break return bestVal else : bestVal = +INFINITY for each child node : value = minimax(node, depth+1, true, alpha, beta) bestVal = min( bestVal, value) beta = min( beta, bestVal) if beta  <= alpha: break return bestVal 

 // Calling the function for the first time. minimax(0, 0, true, -INFINITY, +INFINITY) 

위의 알고리즘을 예를 통해 명확하게 만들어 보겠습니다.

• 최초 통화는 다음에서 시작됩니다. ㅏ . 여기서 알파의 값은 다음과 같습니다. -무한대 그리고 베타값은 +무한대 . 이러한 값은 트리의 후속 노드로 전달됩니다. ~에 ㅏ 극대화자는 최대값을 선택해야 합니다. 비 그리고 씨 , 그래서 ㅏ 전화 비 첫 번째
• ~에 비 최소화 프로그램은 최소값을 선택해야 합니다. 디 그리고 그리고 따라서 호출 디 첫 번째.
• ~에 디 , 리프 노드인 왼쪽 자식을 봅니다. 이 노드는 값 3을 반환합니다. 이제 알파 값은 디 max( -INF, 3)는 3입니다.
• 올바른 노드를 살펴볼 가치가 있는지 여부를 결정하기 위해 beta <=alpha 조건을 확인합니다. beta = +INF이고 alpha = 3이므로 이는 거짓입니다. 따라서 검색을 계속합니다.
D는 이제 5라는 값을 반환하는 오른쪽 자식을 살펴봅니다. 디 , alpha = max(3, 5) 즉 5입니다. 이제 노드의 값은 디 5입니다. D는 5의 값을 반환합니다. 비 . ~에 비 , beta = min( +INF, 5) 즉 5입니다. 이제 최소화 도구는 5 이하의 값이 보장됩니다. 비 지금 전화해 그리고 5보다 낮은 값을 얻을 수 있는지 확인합니다.
• ~에 그리고 alpha와 beta의 값은 -INF와 +INF가 아니라 각각 -INF와 5입니다. 왜냐하면 beta의 값이 다음과 같이 변경되었기 때문입니다. 비 그리고 그게 뭐야 비 에 전달 그리고
• 지금 그리고 왼쪽 자식인 6을 봅니다. 그리고 , alpha = max(-INF, 6) 즉 6입니다. 여기서 조건은 true가 됩니다. 베타는 5이고 알파는 6입니다. 따라서 베타 <=알파는 참입니다. 그러므로 그것은 깨지고 그리고 6을 반환합니다. 비
• 값이 무엇인지는 중요하지 않습니다. 그리고 오른쪽 아이는. +INF 또는 -INF일 수도 있지만 여전히 중요하지 않습니다. 최소값은 5 ​​이하의 값이 보장되었기 때문에 살펴볼 필요조차 없었습니다. 따라서 최대화자는 6을 보자마자 왼쪽에 5를 얻을 수 있기 때문에 최소화자가 결코 이쪽으로 오지 않을 것이라는 것을 알았습니다. 비 . 이렇게 하면 9를 볼 필요가 없어 계산 시간이 절약됩니다.
E는 6의 값을 반환합니다. 비 . ~에 비 , beta = min( 5, 6) 즉 5입니다. 노드의 값 비 역시 5

지금까지 이것이 우리 게임 트리의 모습입니다. 9는 계산되지 않았기 때문에 삭제되었습니다.

B는 5를 다음에게 반환합니다. ㅏ . ~에 ㅏ , alpha = max( -INF, 5) 즉 5입니다. 이제 최대화 도구는 5 이상의 값을 보장합니다. ㅏ 지금 전화해 씨 5보다 높은 값을 얻을 수 있는지 확인합니다.
• ~에 씨 , 알파 = 5, 베타 = +INF. 씨 전화 에프
• ~에 에프 , 알파 = 5, 베타 = +INF. 에프 1인 왼쪽 자식을 봅니다. alpha = max( 5, 1) 은 여전히 ​​5입니다.
F는 2인 오른쪽 자식을 봅니다. 따라서 이 노드의 가장 좋은 값은 2입니다. 알파는 여전히 5로 남아 있습니다. F는 값 2를 반환합니다. 씨 . ~에 씨 , 베타 = 최소( +INF, 2). 조건 beta <= alpha는 beta = 2이고 alpha = 5일 때 참이 됩니다. 따라서 이 조건은 깨지며 전체 하위 트리를 계산할 필요도 없습니다. G .
• 이 중단 뒤에 있는 직관은 다음과 같습니다. 씨 최소화 값은 2 이하로 보장되었습니다. 그러나 최대화자는 그가 선택한 경우 이미 5의 값을 보장받았습니다. 비 . 그럼 왜 극대화자는 선택을 했을까요? 씨 2보다 작은 값을 얻으시겠습니까? 다시 한 번 마지막 2개의 값이 무엇인지는 중요하지 않다는 것을 알 수 있습니다. 또한 전체 하위 트리를 건너뛰어 많은 계산을 절약했습니다.
C는 이제 2라는 값을 반환합니다. ㅏ . 그러므로 최고의 가치는 ㅏ max( 5, 2)는 5입니다.
• 따라서 최대화가 얻을 수 있는 최적의 값은 5입니다.

이것이 최종 게임 트리의 모습입니다. 보시다시피 G 계산되지 않았기 때문에 삭제되었습니다.

CPP

자바

파이썬3

씨#

자바스크립트

The optimal value is : 5