| [ QuizWit ] in KIDS 글 쓴 이(By): guest (123) <stc03-cs.cs.unc.> 날 짜 (Date): 2000년 11월 7일 화요일 오전 06시 46분 27초 제 목(Title): Re: 5x5 바둑 으음, 유한한 횟수에 끝난다는 건 증명하지 않아도, 유한한 space만 뒤지면 된다는 건 증명 가능할 것 같은데요? * 바둑판의 크기는 19*19. 따라서 가능한 판의 상태는 최대 2*3^361 가지. (곱하기 2는 백 차례냐 흑 차례냐에 따라서...) * 가능한 모든 대국을 탐색한다고 하자. 만약 무한한 대국이 존재한다면, 바둑판의 상태가 유한하므로 어떤 상태 a가 두 번 이상 나타나야 한다. * 가정 : 착수는 history에 의존하지 않는다. (즉, 현재의 판의 상태가 같다면 최적의 알고리즘이 선택하는 장소는 언제나 같다.) <-- reasonable한가요? 승패의 여부가 history에 관계없이 현재 판의 상태만으로 결정된다면 reasonable한 것 같은데, 바둑에 문외한인고로 이 가정이 맞는지... * 따라서, 위의 가정에 의해 a -> (sequence S) -> a의 반복이 나타났다면, 이 판은 aSaSaS...를 그 이후 무한반복하게 된다. 따라서 무승부. * 즉, 가능한 대국을 탐색할 때, 같은 상태가 두 번 이상 등장하면 그 자리에서 탐색을 중단하면 된다. 따라서 탐색해야 하는 대국의 길이는 최대 2*3^361이다. 그러므로 가능한 대국의 가짓수는 최대 361^(2*3^361)이다. QED |