http://clien.net/cs2/bbs/board.php?bo_table=lecture&wr_id=311716

MiniMax, 알파 가지치기 탐색 혹은 몬테카를로 트리 검색을 하는 AI에는 수평선 효과(Horizon Effect)라고 알려진 약점이 있습니다.

https://en.wikipedia.org/wiki/Horizon_effect

먼저 체스나 바둑의 AI가 동작하는 방식을 간단히 설명 드리면요.

앞으로 둘 수 있는 가능한 수순을 제한 시간 안에 최대한 따져보고,

그 나아간 결과가 가장 자기한테 유리해질 수 있도록 하는, 자신의 수를 결정하게 됩니다.

수평선 효과란, 자기가 불리해지는 미래 상태가 예상되는 경우, 어떻게든 그 상태가 되지 않도록 하려다 보니..

불리해지는 상태를 방지하는 것이 아니라 자기 시야에 안보이는 미래로 미루는 수를 선택하는 것을 말합니다.

말하자면 미봉책을 반복하는 거죠.

예를 들어, 4수 앞까지 따져 보는 바둑 AI가 있다고 합시다.

내 차례가 되고 보니 방금 상대가 둔 수 때문에 4수 후에 대마가 잡히게 생겼습니다! - '망했어!'

하지만 대마가 잡히지 않도록 하는 수를 도통 찾지 못하자 뜬금없이 팻감을 쓰는 것입니다. - '이렇게 하면 일단 죽지 않지!'

이렇게 하면, 대마가 잡히는 것이 6수 뒤로 미뤄지므로 AI가 볼 수 있는 4수 이내에서는 최선의 선택을 한 것이지만,

그렇다고 대마가 살아날 방법이 생긴 것은 아니기 때문에 바둑은 점점 더 망하게 됩니다.

4국에서 이세돌이 위 78수를 둔 뒤의 알파고의 이상 행동은

이와 같은 수평선 효과에 의한 것이라고 본다면 매우 그럴듯하게 들어 맞아 들어서,

프로그래머들이 많은 해외 커뮤니티에서는 거의 확신범으로 지목되고 있습니다.

이세돌의 78수. 이 때 알파고는 아직 불길한 미래를 예지하지 못한 것 같습니다.

이 국면에서 인간이 보기에 흑 대마는 도저히 살 수가 없는 상태라고 쉽게 파악할 수 있는데요.

알파고는 일단 늘면, 당장의 탐색 깊이 이내에서는 죽지 않을 수 있다고 판단한 것 같습니다.

참고로 축의 경우 탐색 깊이가 매우 깊어지기 때문에 알파고가 예외 처리를 하고 있습니다.

인간이 보기에 축은 탐색 깊이랑 상관 없이 쉽게 보이는데, 알파고한테는 쉽게 안보인다는 거죠.

심지어는 손해로 이어지는 팻감까지 사용합니다.

본래, 알파고는 국면이 복잡해지는 경우 시간을 더 써서 판단을 하도록 되어 있습니다.

이는 수평선 효과를 막기 위해서도 특히 중요한 기능입니다.

https://en.wikipedia.org/wiki/Quiescence_search

그러나, 알파고가 사용한 시간을 보면, 78수 이후 충분한 시간을 들여 판단을 해야 했음에도 그러지 않다가

판세가 다 기울어진 다음에야 시간을 들여 탐색을 하는 것을 볼 수 있습니다.

즉, 수평선 효과를 막는 알고리즘이 제대로 동작을 하지 않은 것으로 보이고요. 이 부분이 향후 보완할 부분이라고 판단됩니다.

보통 상용으로 판매되는 게임 AI들의 경우, 수평선 효과 처리가 어느 정도 되어 있어야 정상인데요..

알파고는 수읽기 자체는 강력하지만, 만들어진 지 얼마 안된 AI라서 해당 부분에 대한 충분한 테스트가 되지 않았던 것 같네요.

4국 패배후 딥마인드 직원들 표정을 보면, 바로 위 문제를 짐작하고 '이거 X됐다' 생각하고 있는 것 같습니다. ㅋ

--------------------------------------------

퍼옴

요약 =

1. 지금 쓰이는 경우의 수 탐색 알고리즘은 일정 수 이상 멀리 예측하지 못함 그 안에서만 최선의 판단을 함

2. 근데 그 일정 수 이내에서 딱히 타개할 루트가 보이지 않으면 그냥 팻감 같은걸 써서 예측 가능한 범위 이후로 미뤄버림 

3. 결국 빚더미 미루듯 점점 손해가 커지면서 악순환 테크 더 이상한 수를 두기 시작함