포스트

인공지능 5. Minimax

게시
By 신희곤
7 분읽는 시간
인공지능 5. Minimax

GAN 알고리즘이란?

위조지폐범과 식별기가 서로 경쟁하면서 계속 성장한다는 아이디어에서 착안한 알고리즘. 서로 적대적인 관계를 경쟁붙여야 한다.

Minmax 알고리즘이 무엇인가?

Minmax Algorithm이란, 2인용 제로섬 게임에서 나의 이득은 최대한으로, 상대방의 이득을 최소한으로 하는 최선의 수를 찾는 알고리즘이다. 이런 알고리즘을 적대적 탐색이라고 한다. 제로섬 게임이란, 내가 이득을 보면 상대는 손해를 보기 때문에 이득과 손해의 합이 0인 게임이다. 민맥스 알고리즘은 다음과 같은 게임에 적용하면 좋다.

  1. 게임의 모든 상태 변화가 규칙에 의해 예측 가능해야 한다. Logic games
  2. 모든 정보가 오픈되어 있다. Full information games 스타크래프트 (규칙만으로 게임 상태 변화 예측 힘듬), 포커 (일부 정보가 비공개임) 등의 게임엔 적용하기 어렵다. 오목, 바둑, 체스, 틱택토 등에 사용하기 좋다.

그래서 Minmax가 뭔데? Minmax는 Serach tree를 생성한다.

  • Root node는 현재 게임의 상태와 같다.
  • Child node는 현재 상태에서 게임 규칙에 의해 선택할 수 있는 선택지와 같다. 현재 상태에서 가능한 상태 노드를 생성하는 Move generator가 필요하다.
  • Terminal node는 게임의 종료 상태와 같다. 나는 나의 이득을 최대로 하는 선택지를 항상 선택하고, 상대는 나의 이득을 최소한으로 만드는 선택지를 항상 선택한다고 가정해야 한다. 어떤 선택지가 좋은 선택지고, 나쁜 선택인지 평가하는 heuristic function을 만들어야 한다.

여기까지가 기본 셋팅이고, 민맥스 알고리즘은 다음과 같이 구현한다.

  1. MaxMove, MinMove 두 함수를 만든다.
    1. 현재 게임 상태에서 최대한의 이득을 선택하는 플레이어를 MAX라고 한다. 내 상대 플레이어는 최소한의 이득인 선택지를 선택해야 하므로 MIN라고 한다.
  2. MaxMove는 현재 게임 상태와 \(\alpha, \beta\)을 파라미터로 갖는다.
    1. 현재 게임 상태가 종료 상태거나, 최대 깊이 상태라면 Eveluation function 값을 반환한다.
    2. 아니라면, Move generator로 다음 게임 상태를 생성한다.
    3. 모든 Childs 상태에 대해 다음을 반복한다.
      1. Child 상태를 기준으로 MinMove를 돌려본다.
      2. 반환된 값과 현재 \(\alpha\)을 비교해서 더 큰 값을 \(\alpha\)으로 취한다.
      3. 만약 \(\alpha\)가 \(\beta\)보다 더 크거나 같다면 더이상 탐색을 종료하고, \(\alpha\)을 반환한다.
  3. MinMove는 현재 게임 상태와 \(\alpha, \beta\)를 파라미터로 갖는다.
    1. 현재 게임 상태가 종료 상태거나, 최대 깊이 상태라면 Eveluation function 값을 반환한다.
    2. 아니라면, Move generator로 다음 게임 상태를 생성한다.
    3. 모든 Childs 상태에 대해 다음을 반복한다.
      1. Child 상태를 기준으로 MaxMove를 돌려본다.
      2. 반환된 값과 현재 \(\beta\)을 비교해서 더 작은 값을 \(\beta\)로 취한다.
      3. 만약 \(\beta\)가 \(\alpha\)보다 더 작거나 같다면 더이상 탐색을 종료하고, \(\beta\)을 반환한다.
  4. Minmax는 현재 게임 상태를 파라미터로 갖는다.
    1. MaxMove(현재 게임 상태, \(-\infty\), \(\infty\))를 호출한다.

왜? MaxMove를 기준으로 생각해보자. 나(MAX)의 부모(MIN)가 최선의 수로 기대하고 있는 상태가 갖는 값은 \(\beta\)이다. 즉 부모(MIN)가 나를 선택하려면 \(\beta\)보다 더 작은 값이 와야 한다. 그러나 나(MAX)는 항상 최대값 \(\alpha\)을 선택한다. 즉 현재 \(\alpha\) (내가 반환할 값)보다 \(\beta\) (부모가 선택할 최선의 값)가 같거나 크면, 어차피 부모(MIN)는 나(MAX)를 절대 선택하지 않는다. 따라서 나의 자식들을 더이상 탐색할 이유가 없다!

이번엔 MinMove를 기준으로 생각해보자. 나(MIN)의 부모(MAX)가 최선의 수로 기대하고 있는 상태가 갖는 값이 \(\alpha\)다. 즉 부모가 나를 선택하려면, \(\alpha\)보다 더 큰 값이 와야 한다. 그러나 나(MIN)는 항상 최솟값 \(\beta\)를 선택한다. 즉 현재 \(\beta\) (내가 반환할 값)가 \(\alpha\) (부모가 선택할 최선의 값)보다 작거나 같으면, 어차피 부모(MAX)는 나(MIN)를 절대 선택하지 않는다. 따라서 나의 자식들을 더 이상 탐색할 이유가 없다!

결론적으로, 민맥스 알고리즘은 DFS 방식으로 Search Tree를 확장하는 알고리즘이다. 이런 Game State Tree는 깊이가 깊어질수록 Tree가 기하급수적으로 넓어진다. 따라서 깊이 제한을 두고, 종료 상태가 아닌 게임의 상태를 Heuristic하게 평가하는 Evaluation Function을 정의해야 한다.

IT, 인공지능