[4월의 퍼즐] 역추적 틱택토

틱택토^Tic-Tac-Toe는 가로 세로 세 칸씩 그려진 아홉 개의 칸에 두 사람이 번갈아가며 \(\bigcirc\)와 \({\Large\times}\)를 표시하여 가로, 세로, 또는 대각선으로 세 개를 먼저 한 줄을 완성하는 사람이 이기는 게임이다. 

이 게임은 매우 단순하지만 인공지능 테스트에도 자주 쓰이곤 하였다.

이번 호는 틱택토와 관련된 문제이다. 틱택토 자체는 양쪽이 최선을 다하면 비기는 것으로, 즉 어느 쪽도 같은 모양으로 한 줄을 만들지 못하는 것으로 끝나므로 최선의 수를 묻는 것은 조금 재미가 없다. 대신 틱택토 상황을 보고 역추적하는 문제를 생각해 보자.

다음 그림은 두 사람이 틱택토를 진행하다가 어느 쪽도 이길 수 없어서 중단한 상태이다. 두 사람 모두 대단히 논리적인 사람들이고 서로 최선을 다하였다면, 이 게임에서 첫 번째 수와 마지막 수는 무엇이겠는가?