Alpha-Beta 잘라내 기 의사 코드에 대한 Minimax 수정

Question

Alpha-Beta 의사 코드를 배우고 있으며 알파 베타 잘라 내기에 대한 가장 간단한 의사 코드를 작성하려고합니다.

나는 최소 최대에 대한 의사 코드를 작성했습니다 :

function minimax(node, depth) 
    if node is a terminal node or depth ==0 
      return the heuristic value of node 
    else 
      best = -99999 
    for child in node 
      best = max(best, -minimax(child, depth-1)) 
    return best 

는 그러나, 나는 알파 베타 가지 치기로 수정하는 방법을 모르겠어요. 누구든지 도와 줄 수 있습니까?

Answer 1

알파 베타에서는 한 위치에 대해 보장 된 점수를 추적합니다. 상대가 이미 이전 위치에서 보장 된 점수 (이전 이동 한 점수)보다 나은 이동을 발견하면 즉시 중지 할 수 있습니다.

기술적으로 각 측면은 하향 점수 (알파)를 추적하며 상대방의 하향 점수 (베타)에 액세스 할 수 있습니다.

다음 의사 코드

테스트하지만, 여기에 생각이되지 않습니다

function alphabeta(node, depth, alpha, beta) 
    if node is a terminal node or depth ==0 
      return the heuristic value of node 
    else 
      best = -99999 
    for child in node 
      best = max(best, -alphabeta(child, depth-1, -beta, -alpha)) 
      if best >= beta 
       return best 
      if best > alpha 
       alpha = best 
    return best 

검색의 시작에서, 당신은 + 무한대로 무한대에 알파와 베타를 설정할 수 있습니다. 엄밀히 말하면, 스케치 된 알고리즘은 알파 베타가 아니라 Negamax입니다. 둘 다 동일하므로 구현 세부 사항입니다.

알파 베타에서는 이동 순서가 중요합니다. 대부분의 경우, 최선의 움직임, 또는 적어도 아주 좋은 움직임으로 시작한다면, 당신은 Minimax에 비해 큰 발전을보아야합니다.

제한된 알파 베타 윈도우 (-INFINITY 및 + INFINITY가 아닌)로 시작하는 추가 최적화. 그러나 귀하의 가정이 틀린 것으로 밝혀지면 더 개방 된 search window으로 검색을 다시 시작해야합니다.