Minimax algorithm와 Alpha-beta pruning

By | 2009/10/26

  인공지능 시간에 배운 것입니다.

  다음과 같은 게임이 있다고 합시다.

minimax

  이 게임은 두 사람이 진행합니다. 게임은 Tree의 한 vertex에서 게임 플레이어가 가야 할 길을 정합니다. Tree이기에 root인 A에서 출발합니다. 선택은 서로 돌아가면서 동등하게 진행합니다.

  게임의 목표는 처음에 시작하는 사람이 가장 큰 숫자를 가져가는 것입니다. 따라서 처음에 시작하는 사람은 고를 수 있는 숫자 중 가장 큰 숫자를 고를 것이고, 다른 사람은 고를 수 있는 숫자 중 가장 작은 것을 고를 것입니다.

  두 사람 모두 똑똑하여 잘못 선택하는 경우가 없다고 할 때 처음 시작하는 사람이 가장 큰 숫자를 얻기 위해서는 어떤 길을 선택해야 하는가가 이 게임의 문제라고 이해하고 있습니다.

  그럼 처음에 시작하는 사람이 당신이라고 할 때 과연 얼마의 점수(숫자)를 얻을 수 있을까요? 그것을 알아보고자 tree를 탐색합니다.

 

  일단 간단한 알고리즘은 밑에서 하나씩 올라오는 것입니다. 예를 들어 정점 D의 경우 상대방이 선택하는 곳이기에 가장 작은 값을 선택합니다. 밑의 정점인 E와 F에서 값이 올라오는 값은 각각 10과 12입니다. 따라서 D의 값은 작은 값인 10을 선택합니다. 마찬가지로 정점 G에서는 14와 11 중 작은 값인 11을 선택합니다.

  다음으로 정점 C에서는 당신이 선택하기에 가장 큰 값을 선택합니다. 밑에서 올라오는 값인 10과 11 중 큰 값이 11이기에 이것을 선택합니다. 이런 식으로 차츰차츰 올라와서 정점 A에서 가야 할 길을 선택합니다.

  하지만 문제가 있습니다. 이 방법은 모든 정점을 방문해야 한다는 문제가 있는 것입니다. 위의 문제에서는 그 수가 많지 않아 충분히 할만 하지만, 만약 tree의 높이(height)가 100, 1000 혹은 그 이상이라면 정점의 개수가 얼마나 될까요? 이진나무(Binary Tree)의 경우 높이가 k일 때 정점의 개수는 2^(k+1) – 1이 되니 그 수가 매우 많습니다.

 

  따라서 이를 조금이나마 해결하고자 머리를 짜낸 것이 Alpha-beta pruning입니다.

c1

  아이디어는 다음과 같습니다. 위에서 어떤 범위의 것을 원하는지 얘기하면 자신의 밑에서 하나를 받아 그 범위에 들어가는지 비교합니다. 만약 들어간다면 그 범위를 수정한 후 다른 것도 확인해야 하지만, 만약 범위에 들어가지 않는다면 그것을 위로 올려도 선택이 되지 않는다는 뜻이니 버립니다.

  이를 좀 더 정형화하여 책에서는 이렇게 표현하였습니다.

AB(n; α, β)

  1. If n at depth bound, return AB(n) = static evaluation of n. Otherwise, let n_1, …, n_k, …, n_b be the successors of n (in order), set k <- 1 and, if n is a MAX node, go to step 2; else go to step 5.
  2. Set α <- max[α, AB(n_k; α, β)].
  3. If α ≥ β, return β; else continue.
  4. If k = b, return α; else proceed to n_(k+1), k <- k+1 and go to step 2.
  5. Set β <- min[β, AB(n_k; α, β)].
  6. If α ≥ β, return α; else continue.
  7. If k = b, return β; else proceed to n_(k+1), k <- k+1 and go to step 5.

출처 : Nils J. Nilsson, <Artificial Intelligence : A New Synthesis>, Morgan Kaufmann, 1998, pp. 205

  영어로 적혀있으니 조금 어렵네요.^^;;; 거기에 알고리즘만을 적었습니다. 따라서 제가 이해한 것을 바탕으로 한글로 적어보았습니다.

  처음에 AB(A; -∞, ∞)으로 시작합니다. 여기서 s는 Tree의 root입니다. 처음에는 모든 수를 받아들일 수 있습니다.

  1. 만약 정점 n이 잎(leaf)라면 그 자체의 값을 반환합니다. 아니라면 그것의 자식(child)을 각각 n_1, …, n_k, …, n_b으로 설정합니다. 그리고 k를 1로 설정합니다. 만약 정점 n이 MAX node 즉, 당신 차례라면 step 2로 가세요. 그렇지 않다면(즉, 상대방 차례라면) step 5로 가세요.
  2. 기존의 α 와 AB(n_k; α, β)를 비교하여 큰 값(max)을 α에 대입합니다. 즉, 자식의 것을 하나 가져와서 기존의 α와 비교하여 큰 값을 α에 대입합니다.
  3. 만약 α ≥ β라면 β를 반환합니다. 아니면 step 4로 갑니다. 즉, α ≥ β는 범위가 잘못된 것이니 α는 필요가 없습니다. 그리고 그 뒤로도 필요가 없으니 β를 반환합니다. 만약 문제가 없다면 다음 step인 step 4로 갑니다.
  4. 모든 자식을 살펴보면(k = b) α를 반환합니다. 그렇지 않다면 다음 자식을 살펴보기 위해 k를 증가시킨 후 step 2로 갑니다.
  5. 기존의 β 와 AB(n_k; α, β)를 비교하여 작은 값(min)을 β에 대입합니다. 즉, 자식의 것을 하나 가져와서 기존의 β와 비교하여 작은 값을 β에 대입합니다.
  6. 만약 α ≥ β라면 α를 반환합니다. 아니면 step 6으로 갑니다. 즉, α ≥ β는 범위가 잘못된 것이니 β는 필요가 없습니다. 그리고 그 뒤로도 필요가 없으니 α를 반환합니다. 만약 문제가 없다면 다음 step인 step 6으로 갑니다.
  7. 모든 자식을 살펴보면(k = b) β를 반환합니다. 그렇지 않다면 다음 자식을 살펴보기 위해 k를 증가시킨 후 step 5로 갑니다.

 

  이렇게 글을 적었지만 사실 저 개인적으로는 잘 이해가 되지 않았습니다. 하지만 밑에 소개하는 이미지를 보고 곰곰이 생각해보니 어떻게 하는지 이해할 수 있었습니다.

alpha_beta

  아마 이 글을 보는 여러분도 이 이미지를 통해 쉽게 이해할 수 있으리라 생각합니다. 이 이미지는 기존에 gif로 있는 것을 제가 애니메이션으로 만든 것으로 이미지를 클릭하시면 원본을 보실 수 있습니다. 정지된 이미지가 필요하시면 참조하시길 바랍니다.

 

  이렇게 제가 배운 것 중 이해가 잘 되지 않았던 것을 정리하였습니다. 여기에 대해 좀 더 세부적이고 자세한 얘기가 있으나 그것은 잘 정리가 되지 않아 소개할 정도가 되지 못합니다. 대신 참조 링크를 적어두었으니 필요하시면 찾아보시길 바랍니다.^^

 

참조

3 thoughts on “Minimax algorithm와 Alpha-beta pruning

  1. nvec

    사실 alpha beta pruning는 너무나 당연하고 자연스러운 방법입니다.
    대부분의 사람들은 문제해결시에 이렇게 쓸데없는 범위를 버려버리는
    방식을 무의식적으로 사용합니다.
    이런 자연스러운 과정을 알고리즘적으로 딱딱하게 이해하려고 하면
    오히려 쉽게 이해가 안되는 경우가 발생하는것 같습니다.

    Reply
    1. NoSyu

      사실 수업시간에 저 얘기를 들었을 때 처음에는 이해가 잘 되지 않다가 설명을 다 제치고 ‘내가 만약 저것을 좀 더 똑똑하게 푼다면 어떻게 할까?’를 고민하니 바로 나왔습니다.
      그런데 문제가 제가 내놓은 것을 어떻게 알고리즘으로 정형화를 하느냐가 상당히 어려웠습니다.OTL
      그런 의미에서 인공지능에 관심이 있는 것이 정형화된 알고리즘이 아닌 알고리즘으로 문제를 풀 수 있다면 여러 문제가 의외로 쉽게 풀리는 것이 아닐까 하는 생각을 하고 있기 때문입니다.^^;;
      과연 가능할지는 모르겠네요.OTL

      Reply
  2. Pingback: 2009년 2학기 인공지능 – Report 02 | NoSyu의 주저리주저리

Leave a Reply