내가 빡대가리라서 오늘 아침부터 몸을 꼬면서 이해한 결과는

위키백과의 pseudo code를 기준으로




alpha-beta pruning은 조상 MIN node들의 최적치(최소 값)을 beta,  조상 MAX node들의 최적치(최대 값)을 alpha로 설정하고

탐색 과정에서 MAX node의 자식 중 조상 MIN node의 최적치 이상의 값을 가지는 자식 MIN node가 나오면 이후의 탐색을 cut-off하고 (beta cut-off)

MIN node의 자식 중 조상 MAX node의 최적치 이하의 값을 가지는 자식 MAX node가 나오면 이후의 탐색을 cut-off하는 (alpha cut-off) 방식으로 이해했어.


예를 들어 alpha=3, beta=INF인 상태의 A라는 MAX node에서 자식 MIN node B가 하나 있다고 하고 B의 손자 MAX node의 값이 탐색 순서대로 10 1 -2 3 100 -10000 100000이 나온다면 10에서 B는 alpha= 3, beta = 10이 되고, 그 다음 손자 MAX node의 값이 1이므로 B의 beta는 1로 업데이트 되지만 alpha보다 작아서 이후의 자식 노드에 대한 탐색은 alpha cut-off 되거든 하지만 이렇게 중단을 하여도 문제가 없는 이유는 손자 node의 값이  -2, -10000과 같은 매우 작은 값은 alpha라는 A의 최적 치보다 값이 작으므로 A가 선택하지 않을 것이고, 100, 100000과 같은 큰 값의 경우는 어차피 B라는 MIN node에서 거르기 때문에 상관이 없기 때문에 alpha-beta pruning에서 cut-off를 하여도 local optimum(적절한 용어인지 모르겠다)으로 빠지지 않을 것이라고 이해했어.


실제로 tic-tac-toe를 짜서 그냥 minimax알고리즘과 경쟁을 붙여봤는데 100판의 실행 결과에서는 100판 모두 비긴 것으로 나와서 크게 문제가 없는 것 같거든.


궁금한 점은

1. 내가 첫 문단에서 이해한 전반적인 alpha-beta pruning이 맞는지랑

2. 내가 두 번째 문단에서 예시로 든 상황 이외에 alpha-beta pruning을 돌렸을 때 brute-force방식의 minimax 알고리즘이 구하는 최적 답이 아닌 local optimum으로 빠질 수 있는지. (나도 반례를 계속 생각중인데 잘 모르겠네...)


혹시 똑똑한 형들이 있다면 제발 도와줘 ㅠㅠ