Chinook은 보드 게임 체커(드라프트라고도 함)를 플레이하는 컴퓨터 프로그램이다. 컴퓨터 과학자 Jonathan Schaeffer가 이끄는 앨버타 대학교 팀이 개발한 Chinook은 인간 체커 최고 수준에서 경쟁하도록 설계되었다. 1994년, 마리온 틴슬리(Marion Tinsley)를 꺾고 전략 게임에서 인간 세계 챔피언을 상대로 세계 선수권 대회에서 우승한 최초의 컴퓨터 프로그램이 되는 역사적인 이정표를 달성했다. 2007년, Chinook 팀은 이 프로그램이 체커를 사실상 해결했다고 발표했는데, 이는 양측이 완벽하게 플레이할 경우 게임이 항상 무승부로 끝난다는 것을 의미한다.
Chinook의 개발은 1989년 인공 지능 및 게임 이론 연구 프로젝트로 시작되었다. 이 프로그램은 검색 알고리즘, 평가 함수, 방대한 오프닝 북의 조합을 사용한다. 그 성공은 알파-베타 가지치기를 사용한 미니맥스 검색 원리에 기반을 두었으며, 이 기법은 프로그램이 초당 수백만 개의 위치를 탐색할 수 있게 해주었다. 이 프로그램은 수년에 걸쳐 개선되었으며, 평가 함수와 검색 효율성에서 상당한 발전이 있었다.
세계 선수권 대회 업적
Chinook의 가장 유명한 업적은 1990년 미국 전국 체커 선수권 대회에서 2위를 차지하며 세계 선수권 대회에 도전할 권리를 얻은 것으로, 인간 세계 타이틀에 자격을 얻은 최초의 컴퓨터가 되었다. 1992년, Chinook은 현 세계 챔피언이자 널리 역대 최고의 체커 선수로 여겨지는 마리온 틴슬리와 경기를 치렀다. 이 경기는 40게임 후 무승부로 끝났으며, 틴슬리가 타이틀을 유지했다. 1994년, 재경기가 열렸지만 틴슬리는 건강상의 이유로 6게임 후 기권했고, Chinook이 승자로 선언되어 보드 게임에서 세계 선수권을 보유한 최초의 컴퓨터 프로그램이 되었다.
틴슬리의 은퇴 후, Chinook은 1995년 돈 래퍼티(Don Lafferty)를 상대로 타이틀을 방어하며 경기에서 승리했다. 이 프로그램은 인간 토너먼트에서 계속 경쟁했지만, 1996년 시즌 후 경쟁에서 은퇴했다.
체커 해결
2007년, Chinook 팀은 저널 Science에 체커를 해결했다고 발표하는 논문을 게재했다. 이 해결은 역행 분석과 검색 알고리즘의 조합을 사용하여 완벽한 플레이로 게임이 무승부임을 증명하는 대규모 계산 노력을 포함했다. 팀은 보드에 최대 10개의 말이 있는 모든 위치의 데이터베이스를 계산했으며, 이는 약 10^14번의 계산이 필요했고 분산 컴퓨팅을 사용하여 18년 이상의 연속 계산 시간이 걸렸다. 결과는 표준 시작 위치에서 체커가 이론적으로 무승부임을 보여주었으며, 이는 양측이 최적으로 플레이할 경우 어느 쪽도 승리를 강요할 수 없음을 의미한다.
체커의 해결은 기계 학습 및 게임 AI에서 획기적인 업적이었으며, 당시 해결된 가장 큰 게임으로 약 5×10^20개의 가능한 위치의 검색 공간을 가졌다. 이는 검색 알고리즘과 대규모 계산의 결합의 힘을 입증했으며, 게임에서 인간 전문성의 한계에 대한 통찰력을 제공했다.
기술적 접근
Chinook의 아키텍처는 고전적인 게임 플레이 AI 설계에 기반을 두었다. 알파-베타 가지치기를 사용한 깊이 우선 검색을 사용하여 위치를 평가했으며, 물질, 기동성, 위치적 이점을 고려한 정교한 평가 함수를 사용했다. 이 프로그램은 또한 전문가 플레이의 수백만 위치를 포함하는 대규모 오프닝 북과 역행 분석으로 구축된 엔드게임 데이터베이스를 가지고 있었다. 엔드게임 데이터베이스는 해결 과정에서 중요했으며, 프로그램이 게임 후반 단계에서 완벽하게 플레이할 수 있게 해주었다.
해결 노력을 위해 팀은 "증명-수 검색"이라는 기법을 사용하여 승리 또는 패배일 가능성이 가장 높은 위치로 검색을 안내했다. 또한 분산 컴퓨팅 네트워크를 사용하여 엔드게임 데이터베이스의 수십억 개의 위치를 처리했다. 최종 해결은 체커가 무승부임을 증명했지만, 팀은 또한 어느 한쪽이 실수하면 다른 쪽이 승리를 강요할 수 있음을 보여주었다.
유산과 영향
Chinook의 성공은 인공 지능 및 게임 연구 분야에 상당한 영향을 미쳤다. 이는 Connect Four(1988년 해결) 및 나중에 AlphaGo와 같은 프로그램이 다룬 바둑 게임과 같은 다른 게임을 해결하려는 후속 노력을 고무했다. Chinook은 또한 큰 상태 공간을 가진 게임을 해결하는 기법 개발에 기여했으며, 그 접근 방식은 다른 조합 문제에도 적용되었다.
기술적 기여 외에도 Chinook은 인간 대 기계 지능의 본질에 대한 철학적 질문을 제기했다. 인간 세계 챔피언에 대한 이 프로그램의 승리는 체스(1997년 Deep Blue)와 바둑(2016년 AlphaGo)에서의 후속 업적의 전조였다. 오늘날 Chinook은 컴퓨터가 복잡한 전략 게임을 마스터할 수 있는 잠재력을 입증한 선구적인 노력으로 기억된다.
Chinook 프로젝트는 또한 검색 알고리즘의 성능을 측정하는 데 사용되는 테스트인 Fhourstones 벤치마크 개발로 이어졌다. 이 프로그램의 코드와 데이터베이스는 연구 목적으로 제공되었으며, 그 유산은 게임 플레이 AI 시스템 설계에 계속 영향을 미치고 있다.