https://www.youtube.com/watch?v=l-hh51ncgDI
https://velog.io/@minjujuu/%EC%9D%B8%EA%B3%B5%EC%A7%80%EB%8A%A5-Min-max-tree
위 자료를 참고했다.

---

https://school.programmers.co.kr/learn/courses/30/lessons/92345
위 알고리즘 문제를 풀다가 minimax 알고리즘이 활용된다는 것을 알게 되었다.
분명 전에 접한 개념인데, 다시 보니 기억이 잘 안나 공부 겸 정리해보고자 한다.
내가 이해하기 위해 정리한거라 설명이 명쾌하지 않을 수 있다.

---

Minimax 알고리즘 규칙

1. 2 player 게임에만 적용 가능
2. 아래 특징을 만족시켜야 함
   • 게임의 모든 룰과 약속들이 명시되어야 함
   • 모든 플레이어에게 모든 정보가 균등하게 제공되어야 함

트리 구성 과정

• root에서 각 방향에 돌을 두었을 때 나타날 수 있는 모든 경우의 수가 다음 depth의 경우가 된다.
  • 즉, 다음 depth에는 상대방이 놓는 돌에 대한 경우의 수가 나타나게 되는 것
• '나'의 movement와 '상대'의 movement에 대한 경우로 번갈아가며 트리가 생성된다.
  • 가능한 다음 movement만큼 트리의 branch가 생성되기 때문에 해공간이 매우 크다
    • 즉, '어떤 노드를 우선적으로 선택할 것인지'가 중요하게 된다.
    • cf) Alpha-Beta Pruning

예시

• 각 player는 maximize / minimize하는 방향으로 노드를 선택하는데, 그렇기에 특정 노드값이 계산되는 시점에서 pruning이 가능하다

  • 어차피 해당 노드쪽으로 진행되지 않을것이라는 확신이 있는 경우, 더이상 계산하지 않음

• Beta, Alpha값을 통해 함수 호출 중 cut-off를 진행해준다.

  • 초기에 Alpha값은 -무한대로, Beta값은 +무한대의 값으로 초기화된다.
  • 각 노드 값이 계산되면서 Alpha, Beta가 갱신되는 과정은 영상을 참고하자.

아래 예시의 알파, 베타값은 최종 알파, 베타값을 나타낸 건데 함수가 호출되면서 노드값이 계산되는 과정을 생각하보면 이해할 수 있다.

• maximize 노드일 때는 alpha가, minimize 노드일 때는 beta가 갱신된다.
• Alpha가 Beta보다 클 때 cutoff가 일어난다.

코드랑 같이 봐야 이해가 편하다.
사실, 이렇게 정리해봤는데도 헷갈린다. 관련 문제 접하면서 익숙해져야 할듯

https://github.com/ljwljy51/Algorithm/blob/main/Programmers/ETC/Lv3_2022_KAKAO_%EC%82%AC%EB%9D%BC%EC%A7%80%EB%8A%94%EB%B0%9C%ED%8C%90.py
결국 솔루션을 참고해서 문제를 풀었는데,
여전히 이해가 어렵다 ^_^..................
나는 재귀&백트래킹 문제에 특히 약한 것 같다.(랑 DP....)
문제 많이 풀자 ㅜㅜ..