[인공지능] Min-Max Algorithm 요약

Min-Max 알고리즘은 두 명의 플레이어가 참여하는 게임에서 적용된다.

예시: 체스, 바둑, 틱택토 등과 같은 게임

두 명의 플레이어 게임의 특징

• 논리 게임: 게임은 규칙과 약속의 집합으로 설명이 가능하다.
• 완전 정보 게임: 게임의 특정 시점에서 가능한 다음 움직임을 알 수 있다.

Min-max Algorithm은

• 깊이 우선: 현재 게임 위치에서 시작하여 종료 게임 위치까지 이어진다.
• 최종 게임 위치는 Max 플레이어의 관점에서 평가된다.
• 트리의 내부 노드 값은 하향식으로 평가된 값으로 채워진다.
• Max 플레이어에 속하는 노드는 자식 노드 중 최대 값을 받는다.
• Min 플레이어에 속하는 노드는 자식 노드 중 최소 값을 받는다.
• Max 플레이어는 마지막에 가장 높은 가치를 갖는 움직임을 선택하려고 노력한다.
• Min 플레이어는 자신에게 유리한 움직임을 선택하여 Max의 결과를 최소화하려고 노력한다.
• 미래를 미리 보는 시점이 더 길수록 게임이 더 좋아진다.

 

짧은 시간 내에 전체 검색 트리를 갖는 것은 불가능하다.

• 기본적인 최적화 방법 중 하나는 검색 트리의 깊이를 제한하는 것
• 그리고 평가 함수를 사용하는 것
• 현재 게임 위치를 어떤 플레이어의 관점에서 평가하는 것
• 현재 게임 위치가 게임을 종료하는 데 어떻게 도움이 될 수 있는지 계산하는 것
• 이 함수는 일부 휴리스틱을 고려해야 한다.

---

Alpha-beta Cutoff(Pruning)

 

알파(Alpha) 값은 가장 큰 MAX 값 보유

베타(Beta) 값은 가장 작은 MIN 값 보유

 

Max 레벨(내 차례)에서,

• 각 자식 경로를 평가하기 전에 이전 경로의 반환 값과 베타 값과 비교
• 값이 베타 값보다 큰 경우 현재 노드의 검색을 중단
• 아래에서 위로 간다고 생각하자. 현재 나는 Max고 자신보다 위에 있는 min의 베타 값보다 큰 알파 값을 가지고 있다고 치자. 그렇다면 위의 min은 나 자신(max)의 값을 택하지 않을 것이다.(Alpha cutoff)

Min 레벨(상대방 차례)에서,

• 각 자식 경로를 평가하기 전에 이전 경로의 반환 값과 알파 값과 비교
• 값이 알파 값보다 작은 경우 현재 노드의 검색을 중단
• 아래에서 위로 간다고 생각하자. 현재 나는 min이고 자신보다 위에 있는 max의 알파 값보다 작은 min 값을 가지고 있다고 치자. 그렇다면 위의 max는 나 자신(min)의 값을 택하지 않을 것이다.(Beta cutoff)

Alpha-Beta cutoff 예시

세 군데에서 alpha-beta cutoff가 일어났는데, 왼쪽부터 하나씩 들여다보자.

 

왼쪽 아래의 5를 탐색하기 전

1. 만약 4보다 높은 수가 나오면?

• 상대방은 4를 택한다.

1. 만약 4보다 낮은 수가 나오면?

• 상대방은 4보다 낮은 수를 택하겠지만 나는 5를 선택한다. 그래서 더 볼 필요가 없으므로 cutoff가 일어난다.

(그리고 알파 값 5가 베타 값 4보다 크므로 alpha cut off가 일어난다고 생각할 수 있다.)

 

가운데 아래의 9를 탐색하기 전

1. 만약 6보다 높은 수가 나오면?

• 상대방은 6을 택한다.

1. 만약 6보다 낮은 수가 나오면?

• 상대방은 낮은 수를 택하겠지만 나는 6을 선택한다. 그래서 더 볼 필요가 없으므로 cutoff가 일어난다.

(그리고 알파 값 9가 베타 값 6보다 크므로 alpha cut off가 일어난다고 생각할 수 있다.)

 

오른쪽 아래를 탐색하기 전

1. 만약 5보다 높은 수가 나오면?

• 상대방은 5를 택한다.

1. 만약 5보다 낮은 수가 나오면?

• 상대방은 낮은 수를 택하겠지만 나는 6을 택한다. 그러므로 더 볼 필요가 없으므로 cutoff가 일어난다.

(그리고 9,8,6이 베타 값 5보다 크므로 alpha cut off가 일어난다고 생각할 수 있다.)