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

https://startagainbornagain.tistory.com/122

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

검색 대 참조

  게임 시작 시 체스 프로그램이 폰을 e4로 움직이는 수를 결정하기 위해 수십 억 개의 게임 상태들로 이루어진 트리를 검색해야 한다는 것이 너무 과하게 느껴질 수 있겠습니다. 체스 게임의 개시와 끝내기에서의 좋은 플레이를 설명하는 책들이 나오기 시작한 지도 백 년이 넘었습니다. 따라서 여러 게임 플레이 프로그램들이 개시와 끝내기에 검색 대신 표 참조(table lookup)를 사용하는 것도 놀랄 일은 아닙니다.

게임 개시부에서 컴퓨터는 주로 인간의 경험에 의존합니다. 개시의 좋은 플레이에 대한 인간 전문가의 조언을 책에서 복사해서 컴퓨터가 사용할 표에 집어 넣는 것입니다. 그러나 컴퓨터는 이전에 플레이한 게임들을 모은 데이터베이스에서 통계치를 구해서, 승리로 이어지는 경우가 가장 많은 개시 수들을 파악하는 능력도 가지고 있습니다. 개시부에서는 선택할 수 있는 수들이 그리 많지 않으며, 따라서 전문가의 조언이나 예전 게임들의 자료가 잘 맞을 가능성이 큽니다. 그러나 대략 10수 후에는 이전에 보지 못한 국면이 나오며, 그때부터는 프로그램이 표 참조 대신 검색을 사용해야 합니다.

게임이 끝날 무렵에는 선택 가능한 수가 다시 적어지며, 따라서 표 참조에서 좋은 결과를 얻을 확률이 높아집니다. 그런데 이 지점에서 컴퓨터의 전문성이 빛을 발합니다. 끝내기에 대한 컴퓨터의 분석은 사람이 할 수 있는 수준을 훨씬 상회합니다. 사람은 킹과 루크 대 킹(king-and-rook-versus-king, KRK) 끝내기를 위한 일반적인 전략을 말해 줄 수 있습니다. 그 전략은 상대 킹을 체스판 가장자리로 몰아서 이동성을 줄이되, 자신의 킹을 이용해서 상대 킹이 압박을 벗어나지 못하게 한다는 것입니다. 킹, 비숍, 나이트 대 킹(KBNK) 같은 다른 끝내기는 숙달하기가 어렵고 그 전략을 간결하게 서술할 수 없습니다. 반면 컴퓨터는 하나의 방침(policy)을 생성함으로써 끝내기 문제를 완전히 풀 수 있습니다. 여기서 방침이란 모든 가능한 상태마다 그 상태에서의 최선의 수를 계산할 필요 없이 그냥 표를 참조하기만 하면 됩니다. KBNK참조 표는 얼마나 클까요? 체스판에 두 킹을 서로 인접하지 않게 배치하는 방법은 462가지입니다. 킹을 배치한 후 비숍을 놓을 수 있는 빈칸은 62개이고 나이트를 놓을 빈칸은 61개입니다. 그리고 그다음에 수를 둘 수 있는 플레이어가 둘이므로, 가능한 국면은 단 462 * 62 * 61 * 2 = 3,494,568개입니다. 이들 중 일부는 체크메이트가 됩니다.

표의 해당 국면들에 그 국면이 체크메이트 상황임을 표시해 둡니다. 그런 다음 퇴행(retrograde) 최소최대 검색을 수행합니다. 즉, 체스의 규칙을 뒤집어서, 주어진 수의 이동을 되돌리는 역수(unmove)를 검색하는 것입니다. 승리에 해당하는 국면으로 이어지는 백의 수는 그 수에 대한 흑의 응수가 무엇이든 백에게 유리한 수입니다. 이러한 검색을 3,494,568개의 국면 모두가 승, 무, 패로 분류될 때까지 수행하고 나면 모든 KBNK 끝내기를 위한 결코 틀릴 수 없는 참조 표가 만들어집니다.

이러한 기법과 신묘한 최적화 요령들을 이용해서 켄 톰슨과 루이스 스틸러는 최대 다섯 개의 말들로 이루어진 모든 체스 끝내기와 일부 여섯 말 끝내기를 풀어서 인터넷에 공개했습니다. 스틸러는 외통수가 존재하나 무려 262개의 수가 필요한 경우를 발견했습니다. 이는 다소 당황스러운 결과인데, 왜냐하면 체스 규칙에 따르면 포획이나 폰 이동이 50수 이내에 일어나야 하기 때문입니다. 이후 마르크 부르주츠스키와 아코프 코노발은 폰이 없는 모든 여섯 말 끝내기와 일부 일곱 말 끝내기를 풀었습니다. 끝내기 중에는 최선의 플레이에서 포획에 이르기까지 517개의 수가 필요하고 그 후 체크메이트로 이어지는 것도 있습니다.

체스 끝내기 표를 말 6개에서 32개로 확장하면 백은 첫 수에서 승, 무, 패를 알 수 있습니다. 아직까지 체스에서 그런 일은 일어나지 않았지만, 역사 참고사항에 나오듯이 체커에서는 이미 일어났습니다.

 

오늘은 이렇게 끝났구요 다음에는 확률론적 게임을 끝으로 대항 검색을 끝내겠습니다.