체스 검문 알고리즘의 복잡성

Question

그래프 검색 알고리즘의 복잡성이 Big O 표기법에서 체스의 장군을 결정하는 데 어떤 영향을 미치는지 궁금합니다.

Answer 1

답은 알고리즘이 나머지 체스 조각 (N)으로 가능한 모든 동작을 해결할 것이라는 것입니다. 복잡성이 O (N) (Linear) 인 경우에만 각 조각을 통과하기 때문에.

Answer 2

각면에 8 개. 첫 번째 이동은 단지 폰만의 경우 16 가지 가능성이 있고 기사의 경우 4 가지, 두 번째 영화의 양은 같은 양입니다. 이 후 가능성 목록은 계산 불가능한 수준으로 증가합니다.

세계 최고의 체스 엔진은 '가장 가능성있는'그래프 검색을 사용합니다. 으로 "http://en.wikipedia.org/wiki/Game_complexity이

(35)의 요소 80의 평균 게임 길이 분기 평균을 기준으로"알리스는 게임 트리의 복잡성은 적어도 10,123로 추정 ".

이 위키 피 디아 기사는 매우 유용합니다 비교할 때 관찰 할 수있는 우주의 원자 수는 종종 비교되는데, 4 × 1079와 1081 사이 인 것으로 추정된다.

Answer 3

왕은 최대 8 개의 이동을합니다. 그리고 매 이동 후 왕이 위협 받는지 확인하는 데 일정한 시간이 걸립니다. 왕이 머물러있는 경우도 플러스 (그리고 다른 조각이 움직이는 경우). 그래서 그것은 일정한 시간입니다. 당신은 그냥 주어진 보드는 장군이 포함되어 있는지 확인하려면

Answer 4

, 당신은 이런 식으로 뭔가를 할 수 :

1. 는 (왕)을 결정하여 왕이로 이동할 수있는 사각형의 세트 (8 모든 방향으로 - 자신의 조각이 차지하는 필드 - 필드의 경계)
2. 모든 적의 조각을 반복하여 공격하는 사각형을 결정합니다. 그 사각형들이 당신의 킹 제트에 있다면 제거하십시오. 귀하의 왕이 공격 받고 있는지를 나타내는 부울 값을 유지하십시오. 당신의 kingset는 빈 얻고 왕은 공격

조각의 수는 역할을 수행 중입니다, 그래서 당신은 n 개의 조각으로 임의의 크기의 보드가있는 경우,이 문제를 않습니다

장군합니다. 이 경우 병목 현상은 다른 부분이 공격을 차단할 수 있기 때문에 위치를 공격했는지 여부를 확인하여 모든 부분을 확인하는 것입니다. 간단한 구현은 2 차 시간에이를 수행 할 수 있습니다. 세트의 조각의 위치를 ​​유지하고 add() 및 contains()를 최적화하여 이것을 n으로 선형화 할 수 있습니다 (보드 크기도 영향을 미칩니다). 따라서 선형 복잡성은 실현 가능합니다. .