Min-max tree search

1. 2 player 게임에만 적용할 수 있다
2. 이러한 특징을 만족시켜야 한다
   1) 게임의 모든 룰과 약속들이 명시되어야 함
   2) 모든 플레이어에게 모든 정보가 똑같이 균등하게 제공되어야 함

트리 구성 과정

1. root에서 각각의 방향에 돌을 두었을 때 나타날 수 있는 모든 경우의 수가 다음 depth에 나타남
2. 그 다음 depth에는 상대방이 놓는 돌에 대한 경우의 수가 나타남
3. 나의 movement와 상대의 movement가 번갈아가면서 트리가 생성됨
4. 가능한 next movement만큼 트리의 branch factor가 생성되기 때문에 해공간이 매우 큼

가장 중요한 부분은 어떠한 노드를 우선적으로 선택할 것인가

Max는 내가 움직여서 점수를 얻는 부분이고
Min은 상대가 움직여서 '내가' 점수를 얻는 부분이다

즉 나와 상대가 모두 최선의 선택을 했다고 가정하는데,
Max level에서는 내가 최선의 선택을 해서 가장 높은 점수를 얻은 것이고
Min level에서는 상대가 최선의 선택을 해서 내가 가장 낮은 점수를 얻은 결과이다

그래서 나와 상대가 모두 최선의 선택을 했음에도 얻을 수 있는 최대의 점수를 계산하는 것이
Min-max tree의 목적이라고 할 수 있을 것 같다

Min-max tree의 pseudo code

- 내가 보기 쉬우려고 Visual studio code에서 작성하였다

1. 루트에서 MinMax()를 호출
2. 그리고 MinMax()에서는 MaxMove() 호출
   - 가장 최대 점수를 찾는 것이 목적이므로 MaxMove()의 리턴값이 MinMax()자체의 리턴값이 된다
3. MaxMove()에서는 현재 노드에서 가능한 다음 수를 모두 만들고, 그 수들에 대해 MinMove()를 호출한다
   -> Min value들 중 가장 Max를 찾고자 하기 때문
   -> 따라서 Min Move로부터 넘겨받은 move 중 가장 나은 move를 찾아서 최종 반환한다
4. MinMove()에서는 MaxMove()로부터 넘겨 받은 수들에 대해 다시 MaxMove()를 호출한다
   -> Max value들 중 가장 Min를 찾고자 하기 때문
   -> 따라서 Max Move로부터 넘겨받은 move 중 가장 나은 move를 찾아서 반환한다
5. 게임이 종료되거나 depth limit에 걸릴 때까지 MaxMove()와 MinMove()가 번갈아가면서 진행된다

Min-max tree는 가능한 다음 move들에 대해 모두 확인을 하기 때문에 오래걸린다
하지만 게임을 진행할 때에는
최대한 트리의 depth를 더 깊게 보고, 한 수 앞이라도 더 내다보는 것이 중요하다

따라서 속도를 향상시키기 위한 방법들이 존재하는데 다음과 같다
1. depth limit을 거는 것
- 위에서 보았던 pseudo code가 간단한 예시이다
2. 평가함수를 사용하는 것
- 모든 branch factor를 보지 않고 평가함수를 사용하여 낫다고 판단되는 노드만을 보는 것
- 그렇지만 평가함수를 잘 정의하는 것이 실질적으로 어렵다

더욱 빠른 min-max tree를 위해 alpha-beta cutoff라는 것이 존재한다

Alpha-Beta cutoff

• Alpha - Max value 중 가장 큰 값
• Beta - Min value 중 가장 작은 값
  

1. Alpha cut off

• 가운데 Min level 기준으로 보면,
  Min level의 첫번째 자식 노드가 왼쪽 서브트리로 부터 받은 B값이 부모가 가진 A값 보다 작으면 Alpha cut-off 가 발생한다
• 부모는 A값보다 큰 값을 기다리고 있는데,
  B가 이미 A보다 작으면 그 노드는 부모에게 A보다 큰 값을 줄 가능성이 없어지기 때문이다
• 왜냐하면 Min level이기 때문에 해당 노드가 다음 오른쪽 서브트리로부터 더 큰 값을 얻는다 한들
  B보다 작지 않으면 받지 않을 것이기 때문이다
  

2. Beta cut-off

• 비슷하게 가운데 Max level기준으로 보면,
  Max level의 첫번째 자식 노드가 왼쪽 서브트리로 부터 받은 A의 값이 부모가 가진 B값 보다 작으면 Beta cut-off가 발생한다
• 부모는 B값보다 작은 값을 기다리고 있는데,
  이미 A가 B값보다 크다면, 해당 노드는 부모에게 B값보다 작은 값을 줄 가능성이 없어지기 때문이다
• 왜냐하면 Max level이기 때문에 해당 노드의 오른쪽 서브트리가 A보다 작은 값을, 혹은 B보다 작은 값을 준다고 해도
  A보다 크지 않은 이상 값을 교체하지 않을 것이기 때문이다