스튜어드 러셀의 인공지능을 읽어보자(17) : 대항 검색4

https://startagainbornagain.tistory.com/115

스튜어드 러셀의 인공지능을 읽어보자(15) : 대항 검색3

검색의 차단

  검색을 차단하는 것이 적당한 지점에 도달했으면 발견법적 EVAL 함수를 호출하도록 ALPHA-BETA-SEARCH를 수정해야 합니다. 또한 현재 각 재귀 호출에서 depth가 증가하도록 일부 관리(bookkeeping)코드를 배치할 필요도 있습니다. 검색의 양을 제어하는 가장 직접적인 방법은 고정된 깊이 한계를 정해두고, 인수 depth가 그 깊이보다 클 때에는 CUTOFF-TEST(state, depth)가 항상 True를 돌려주게 하는 것입니다.

깊이는 할당된 시간 내에서 하나의 수를 선택할 수 있을 정도의 값으로 설정해야 합니다. 좀 더 안정적인 접근 방식은 반복 심화를 적용하는 것입니다. 할당된 시간이 지나가면 프로그램은 가장 깊게 들어간 검색이 선택한 수를 돌려줍니다. 또한 반복 심화는 수들의 적절한 순서 결정에도 도움이 됩니다.

그런데 평가 함수의 근사적 성질 때문에 이러한 간단한 접근방식들이 오류로 이어질 수 있습니다. 

기물 개수만 따지는 간단한 체스 평가 함수를 다시 생각해봅시다. 

https://www.chess.com/ko/article/view/ceseu-geimeul-seoljeonghaneun-bangbeob 이미지 참고 사이트

프로그램이 깊이에 제한을 두고 검색을 수행해서 우리가 흑이 현재 나이트 하나와 폰 2개만큼 앞서 있다고 가정해봅시다. 프로그램이 이를 그 상태의 발견법적 값으로 사용한다면 흑이 이길 가능성이 더 크다고 판단해봅시다. 그러나 백이 퀸과 룩이 살아있는 상태라면 기물로 봤을 때 누가 이길지는 알 수 없습니다. (만약 백이 흑의 퀸을 잡으면 백이 더 유리한 상황일 수 있다.)

따라서 훨씬 더 정교한 차단 판정이 필요합니다. 평가 함수는 무활동(quiescent) 상태들에서만, 즉 가까운 미래에서 값들이 크게 요동칠 가능성이 적은 상태들에서만 적용해야 합니다. 예를 들어 체스에서 상대의 중요한 기물을 잡을 수 있는 국면은 기물 개수만 따지는 평가 함수를 적용하기에 적합한 무활동 상태가 아닙니다. 그런 경우 조용한 국면들이 나올 때까지 조용하지 않은 국면들을 더욱 확장해 볼 수 있습니다. 이러한 추가적인 검색을 무활동 검색(quiescence search)이라고 부릅니다. 

이러한 검색은 국면의 불확실성을 빠르게 해소할 수 있는 특정 종류의 수들(이를 테면 상대 말을 잡는 수 등)만 고려하는 제한된 형태로 실행되는 경우가 많습니다.

지평선 효과(horizon effect)는 제거하기가 좀 더 어렵습니다.

이 효과는 심각한 피해를 입히는, 그리고 궁극적으로는 피할 수 없지만 지연 전술을 통해서 일시적으로 피할 수는 있는 상대의 수를 만났을 때 발생합니다.

이런 지평선 효과를 완화하는 한 가지 전략은 특이 연장(singular extension)입니다. 주어진 국면에서 다른 모든 수보다 '확실히 더 나은' 수를 '특이 수'(singular move)라고 부릅니다. 검색 도중 트리의 어딘가에서 특이 수를 발견하면 그것을 기억해둡니다. 검색이 통상적인 깊이 한계에 도달하면 알고리즘은 특이 수가 적법한 수인지 점검해서 만일 적법한 수이면 그 수를 좀 더 고찰합니다 이렇게 하면 트리가 더 깊어지나 특이 수들이 그리 많지 않으므로 트리의 전체 노드 개수가 크게 늘어나지는 않습니다.

 

다음 내용인 전방 가지치기, 검색 대 참조가 내용이 많아서 하나하나씩 설명하겠습니다. 감사합니다.