체커 프로그램은 보드 게임 체커(드라프트라고도 함)를 플레이하도록 설계된 컴퓨터 소프트웨어입니다. 이러한 프로그램은 알고리즘 기법을 사용하여 포지션을 평가하고, 최적의 수를 탐색하며, 인간 플레이어나 다른 컴퓨터와 경쟁합니다. 가장 대표적인 체커 프로그램은 앨버타 대학교에서 개발된 치누크(Chinook)로, 조너선 셰퍼(Jonathan Schaeffer)가 이끄는 팀이 제작했으며(프로젝트는 토론토가 아닌 그곳에 기반을 두었음), 경쟁 플레이와 게임 해법 모두에서 역사적인 이정표를 달성했습니다.
치누크는 1989년부터 2007년까지 앨버타 대학교의 팀(조너선 셰퍼, 롭 레이크, 폴 루, 마틴 브라이언트, 노먼 트렐로어)에 의해 개발되었습니다. 머신 러닝에 의존하는 현대적 접근 방식과 달리, 치누크의 지식은 제작자가 완전히 수작업으로 코딩했으며, 탐색 알고리즘과 평가 함수 같은 전통적인 인공 지능 기법을 사용했습니다. 이러한 차이는 AI가 규칙 기반 시스템에서 데이터 기반 방법으로 진화했음을 보여줍니다.
인간 대 기계 세계 챔피언
1990년, 치누크는 미국 내셔널스에서 매리언 틴슬리(Marion Tinsley)에 이어 2위를 차지하며 인간 세계 챔피언십에 참가할 자격을 얻었습니다. 처음에는 미국 체커 연맹과 영국 드라프트 협회가 인간 챔피언십에 컴퓨터 참가를 반대했습니다. 틴슬리가 항의의 뜻으로 타이틀을 사임하자, 이들 기관은 인간 대 기계 세계 챔피언십이라는 새로운 타이틀을 만들어 경쟁이 진행되도록 했습니다. 틴슬리는 첫 매치에서 4승 2패 33무로 승리했습니다.
1994년의 재경기에서는 6경기가 무승부로 끝난 후 틴슬리가 췌장암으로 기권하면서 치누크가 인간 대 기계 세계 챔피언으로 선언되었습니다. 이로써 치누크는 인간을 상대로 세계 챔피언 타이틀을 획득한 최초의 컴퓨터 프로그램이 되었지만, 가장 가까운 동료들보다 훨씬 뛰어났던 틴슬리를 이기지는 못했습니다. 1995년, 치누크는 32경기 매치에서 돈 래퍼티(Don Lafferty)를 상대로 1승 31무로 타이틀을 방어했습니다. 이후 셰퍼는 경쟁 플레이를 중단하고 체커 해법에 전념하기로 결정했습니다.
알고리즘
치누크의 알고리즘은 네 가지 주요 구성 요소로 이루어져 있습니다: 그랜드마스터 경기의 수를 포함한 오프닝 북, 가능한 수를 탐색하는 깊은 탐색 알고리즘, 수 평가 함수, 그리고 8개 이하의 말을 가진 모든 포지션을 다루는 엔드게임 데이터베이스입니다. 평가 함수는 말 수, 킹 수, 갇힌 킹, 턴, 그리고 도주 체커(킹이 되기 위한 방해받지 않는 경로를 가진 말)와 같은 특징을 고려한 선형 수작업 함수였습니다. 모든 지식은 나중에 딥마인드의 접근 방식과 같은 AI 시스템과 대조적으로, 학습이 아닌 제작자에 의해 프로그래밍되었습니다.
타임라인과 체커 해법
치누크 개발의 주요 이정표는 다음과 같습니다: 1997년, 셰퍼가 "One Jump Ahead: Challenging Human Supremacy in Checkers"라는 책을 출판(2008년 11월 업데이트); 2003년 5월 24일, 10개 말 데이터베이스(측면당 5개 말) 완성; 2004년 8월 2일, 오프닝 "화이트 닥터"(10-14 22-18 12-16)가 무승부로 증명됨. 추가 오프닝은 2006년 1월 18일(09-13 21-17 05-09)과 2006년 4월 18일(09-13 22-17 13-22)에 무승부로 증명되었습니다.
2007년 3월 10일, 셰퍼는 ACM SIGCSE 회의에서 3-5개월 내에 최종 해법이 예상된다고 발표했습니다. 2007년 7월 19일, 저널 Science는 "Checkers Is Solved"를 게재하여 완벽한 플레이 시 최상의 결과가 무승부임을 증명했습니다. 이로써 체커는 더 단순한 게임에 대한 초기 연구에 이어 완전히 해법이 밝혀진 최초의 주요 보드 게임이 되었습니다. 경쟁 정점 시점에 치누크의 레이팅은 2814 Elo였습니다.
유산
치누크의 성공은 딥 러닝의 부상 이전에 깊은 탐색과 수작업 평가를 포함한 고전적 AI 기법의 힘을 입증했습니다. 체커 해법은 딥 블루(Deep Blue)와 같은 체스 컴퓨터에 비견되는 게임 AI의 획기적인 성과로 남아 있습니다. 현대 체커 프로그램이 신경망을 사용할 수 있지만, 치누크의 접근 방식은 게임 이론과 조합 게임 해법에 대한 후속 연구에 영향을 미쳤으며, 그 방법은 카네기 멜론 대학교와 MIT CSAIL 같은 기관의 AI 과정에서 여전히 연구되고 있습니다.