게임과 수학 2탄

마스터마인드(Mastermind)

마스터마인드(Mastermind)는 이스라엘의 우체국장이자 전기 통신 전무누가인 모르데카이 마이로비츠가 1970년에 발명한 보드 게임입니다. 마스터마인드는 일종의 암호 해독 게임입니다. 모르데카이 마이로비츠(Mordecai Meirowitz)가 발명한 이 게임은 1970년대 나와 큰 성공을 이뤘습니다. 

 

게임 플레이어는 2명 이상으로 암호를 만드는 사람 1명과 1인이상의 암호를 해독하는 사람으로 나누어집니다. 암호 제작자가 여섯 가지 색깔 중에서 네 가지로 색으로 조합된 비밀코드를 만들어 한 줄로 놓습니다. 당연히 암호를 해독하는 사람은 조합된 것을 알 수 없습니다.  암호 해독자는 이 비밀코드를 가능한 적은 횟수로 추측해서 맞혀야 합니다.  암호 제작자는 색깔과 자리가 맞는 것이 몇 개이고, 색깔만 맞는 것이 몇 개인지 알려줍니다. 이런 방식으로 암호를 맞힐 때까지 게임은 계획 진행됩니다. 조금씩 드러나는 힌트를 조합해 가장 먼저 비밀 코드를 맞추는 사람이 이기는 방식입니다. 6가지 색깔 중 4개를 뽑아 만들 수 있는 암호의 가짓수는 모두 1296가지입니다.

 

마스터마인드는 새로운 수학적 연구의 계기가 되었습니다. 1977년 미국 컴퓨터 과학자인 도널드 커누스(Donald Ervin Knuth)는 5번 이내의 추측 횟수로 반드시 암호를 맞출 수 있는 전략을 발표했습니다. 그 뒤 암호를 맞출 수 있는 전략에 관한 많은 논문이 발표됩니다. 마스터마인드는 진화 생물학으로부터 영감을 얻은 기술인 유전적 알고리즘을 이용해 연구된 적도 있습니다. 

 

이터니티 퍼즐

이터니티 퍼즐(Eternity Puzzle) 몽크턴(Christopher Monckton)이 만들고 에르틀 컴퍼니(Ertl company)에서 출시한 극도로 어려운 직소퍼즐입니다. 1999년 6월 출시되어 퍼즐 애호가들에게 열풍을 불러일으켰습니다. 그 이유는 이 퍼즐이 사실상 풀 수 없는 것으로 알려졌으며, 4년 내에 풀 수 있는 사람에게는 상금 100만 파운드가 지급되었기 때문입니다. 이터니티 퍼즐은 넓이는 같지만 모양이 다른 209개의 조각으로 정12각형에 가까운 커다란 다각형을 만드는 것입니다. 하나의 퍼즐 조각은 정삼각형과 이 정삼각형의 절반인 직각삼각형을 합친 모양으로 되어 있습니다. 한 조각의 넓이는 정삼각형 6개의 넓이와 같습니다. 이터니티 퍼즐은 본격적인 수학적 분석과 컴퓨터 분석의 대상이 되었습니다. 몽크턴은 이 퍼즐에 대해 컴퓨터 시물레이션을 실시해 보고, 퍼즐을 완성하려면 꽤 오랜 시간이 필요하다고 생각하였습니다. 하지만 2000년 케임브리지 출신의 두 수학자에 의해 이터니티 퍼즐은 해결되고, 그들에게 100만 파운드의 상금이 지급되었습니다. 2007년 몽크턴은 정사각형 퍼즐 조각 256개를 맞추는 이터니티 퍼즐 2를 출시합니다.

 

아와리 게임(Awari Game)

오와레(Oware) 또는 아와리(Awari)는 만칼라에서 파생된 아프리카의 보드 게임입니다. 이 게임은 추상전략 보드게임으로 오늘날에는 가나의 국민 게임입니다. 12개의 홈에 담긴 씨앗을 자기 쪽의 항아리로 옮겨 씨앗을 더 많이 가져간 사람이 승리하는 게임입니다. 

아와리는 퍼즐을 풀거나 게임을 하기 위해 알고리즘을 개발하는 인공 지능 분야의 연구자들에게 꽤 매력적인 게임입니다. 암스테르담 자유 대학교 컴퓨터 과학자인 존 로메인과 헨리 발이 아와리 게임 또한 틱택토처럼 두 사람 모두 실수를 하지 않으면 무승부로 끝나게 될 수 있음을 증명하게 됩니다. 이는 889,063,398,406가지 상태의 결과를 계산하는 컴퓨터 프로그램을 작성하여 증명하였습니다. 이 엄청난 과정을 수행하는 데는 144개의 프로세서로 이루어진 컴퓨터 클러스터를 동원하여 51시간 걸렸습니다.

 

 

 

체커(Checkers)

체커는 체스판에 말을 놓고 움직여, 상대방의 말을 모두 따먹으면 이기는 보드게임입니다. 그 기원이 확실하지 않으나 가장 역사가 오래된 보드 게임 중 하나인 것으로 추정됩니다. 체커는 매우 간단한 게임 같아 보이지만, 시실 깊이 파고들면 전혀 간단한 게임이 아닙니다. 오히려 인간이 마스터하기에 불가능할 정도로 복잡한 게임입니다. 이 게임도 틱텍토, 아와리 게임과 마찬가지로 양쪽 선수들이 잘못된 수를 하나도 두지 않으면 승부가 나지 않는 게임입니다. 2007년 컴퓨터 과학자인 조너선 새퍼(Jonathan Schaeffer)와 동료들은 컴퓨터를 이용해 이 사실을 증명했습니다. 새퍼의 증명은 18년간 컴퓨터 수백 대를 동원한 끝에 이루어졌고, 덕분에 체커는 지금까지 그 승패가 해명된 게임 중에 가장 복잡한 게임이 되었습니다. 또한 이 증명은 인간에게 절대로 지지 않는 기계를 만드는 것이 가능하다는 말이기도 합니다.

 

유명한 체커 선수로는 마리온 틴슬리(Marion Tinsley)라는 수학자가 있었습니다. 틴슬리는 당시 챔피언십에서 우승을 놓친 적이 없었습니다. 1994년에 치누크(Chinook)라는 이름을 가지 새퍼의 프로그램이 체커 세계 챔피언인 마리온 틴슬리를 상대로 연달아 무승부를 이끌어냈습니다. 틴슬리는 살아생전에 체커 게임에서 7번밖에 패한 적이 없는 플레이어로, 1995년에 사망하였습니다.

 

 

체커 연구 팀은 우선 판 위에 10개 이하의 말이 있는 배치 39,000,000,000,000(39조) 가지를 살펴본 다음 붉은색이 이길지 검은색이 이길지에 대해 판정했습니다. 체커 문제가 해결된 것은 인공 지능 분야의 기념비적 사건이라고 할 수 있습니다.