Null 이동
Null move게임 이론에서, null move or pass는 플레이어가 그 플레이어가 움직일 차례가 되었을 때 움직이지 않기로 한 결정이다.null 이동은 많은 게임의 규칙에 어긋나지만, 이러한 게임을 분석할 때 종종 고려하는 것이 유용하다.그 예로는 저그즈왕 분석(체스나 다른 게임의 경우, 만약 그것이 허용된다면 null 이동이 다른 어떤 움직임보다 좋을 상황)[1]과, 게임 트리 분석의 null-move 휴리스틱(null-move를 한 다음 더 낮은 깊이로 검색하는 게임 트리를 가지치기하는 방법)이 있다.[2]
게임트리 알파베타 검색 축소에 심도 축소 null 이동이 효과적인 이유는 한두 동작만으로 전술적 위협이 매우 빠르게 나타나는 경향이 있기 때문이다.상대가 null move search에 의해 밝혀진 전술적 위협이 없는 경우, 그 위치는 트리의 다른 가지(즉, "베타")에서 얻을 수 있는 최상의 결과를 초과할 정도로 양호할 수 있으므로 현재 노드에서 더 이상의 검색이 필요하지 않으며, null move의 결과는 검색값으로 반환될 수 있다.null move search 값이 베타 값을 초과하지 않더라도 반환된 값은 현재 알파보다 위치의 가치평가에 더 높은 바닥을 설정할 수 있으므로 해당 위치에서 하위 형제 노드에서는 더 많은 컷오프가 발생할 수 있다.
기본적인 가정은 최소한 노드에서 이동 중인 플레이어가 이용할 수 있는 어떤 법적 움직임이 전혀 움직이지 않는 것보다 낫다는 것이다.이동 중인 플레이어가 저그즈왕에 있는 경우, 그 가정은 거짓이며, null 이동 결과는 무효다(그 경우, 실제로 포지션 가치의 상한선을 설정한다).따라서 저그즈왕(Zugzwang)이 가능한 트리의 노드에서 null 이동을 배제하는 논리가 필요하다.체스에서 저그즈왕 포지션은 킹과 폰 엔데임에서 발생할 수 있으며, 때로는 다른 피스를 포함하는 엔드 게임에서도 발생할 수 있다.
참조
- ^ Beal, Don F. (1990), "A generalised quiescence search algorithm", Artificial Intelligence, 43 (1): 85–98, doi:10.1016/0004-3702(90)90072-8.
- ^ Goetsch, G.; Campbell, M. S. (1990), "Experiments with the null-move heuristic", in Marsland, T. Anthony; Schaeffer, Jonathan (eds.), Computers, Chess, and Cognition, Springer-Verlag, pp. 159–168.
