알파베타 가지치기 예제

다행히도, 게임 트리의 모든 노드를 살펴보지 않고도 실제 minimax 결정을 찾을 수 있습니다. 따라서 분석하지 않고 트리에서 노드를 제거하고 이 프로세스를 가지 치기라고 합니다. 참고: 각 노드는 알파 및 베타 값을 추적해야 합니다. 알파는 MAX의 턴에만 업데이트할 수 있으며, 마찬가지로 베타는 MIN의 확률이 높을 때만 업데이트할 수 있습니다. 알파-베타 검색은 좁은 검색 창만 고려하여 더 빠르게 만들 수 있습니다(일반적으로 경험에 따라 추측에 의해 결정). 이를 포부 검색이라고 합니다. 극단적인 경우, 검색은 알파와 베타 와 동일하게 수행됩니다. 제로 윈도우 검색, 널 창 검색 또는 스카우트 검색으로 알려진 기술입니다. 이는 좁은 창에서 얻은 추가 깊이와 간단한 승/패 평가 기능이 결정적인 결과로 이어질 수 있는 게임의 끝 부분 근처에서 승/패 검색에 특히 유용합니다. 흡인 검색에 실패하면 높음(창의 높은 가장자리가 너무 낮음) 또는 낮음(창의 아래쪽 가장자리가 너무 높았음)이 실패했는지 여부를 감지하는 것은 간단합니다.

이렇게 하면 위치를 다시 검색할 때 유용할 수 있는 창 값에 대한 정보를 제공합니다. 알파 베타 가지 치기의 구현은 종종 “실패 소프트” 또는 “fail-hard”인지에 따라 설명될 수 있습니다. 의사 코드는 실패 소프트 변형을 보여 줍니다. fail-soft 알파 베타를 사용하면 alphabeta 함수는 함수 호출 인수에 의해 설정된 α 및 β 경계를 초과하는 값(v)을 반환할 수 있습니다. 이에 비해 페일 하드 알파 베타는 α 및 β의 포괄 범위로 함수 반환 값을 제한합니다. 알파 와 베타 매개 변수를 정의 해 봅시다. 알파는 최대화자가 현재 해당 수준 이상에서 보장할 수 있는 최상의 값입니다. 베타는 최소화자가 현재 해당 수준 이상에서 보장할 수 있는 최상의 값입니다. 알파-베타 가지 치기는 검색 트리의 minimax 알고리즘에 의해 평가되는 노드 수를 줄이려는 검색 알고리즘입니다.

그것은 2 플레이어 게임 (틱 택 토, 체스, 이동 등)의 기계 재생에 일반적으로 사용되는 적대적 검색 알고리즘입니다. 이전에 검토된 이동보다 이동이 더 나쁘다는 것을 증명하는 가능성이 하나 이상 발견되면 이동 평가를 중지합니다.