d라이브러리

카드를 무작위하게 섞는 데 이렇게 심오한 수학이 필요한 줄 정말 모르셨죠?
15퍼즐과 루빅스 큐브 섞기는 뭔가 더 어려워 보이는데요, 퍼즐의 무작위에 대해 물어보겠습니다.

15퍼즐은 155번, 2×2×2 큐브는 19번!

15퍼즐 고수가 화를 낸 것은 심판이 155번 이상 퍼즐을 섞지 않았기 때문이었습니다. 로버트 휴 미국 뉴욕대 수학과 교수팀이 15퍼즐을 마르코프 연쇄로 나타내서 연구해보니 nⁿlogn회 이상 섞어야 무작위해진다는 걸 알게 됐거든요.

여기서 n은 퍼즐판에서 가로와 세로칸의 수인데 15퍼즐의 경우는 4칸입니다. 즉, 4⁴log4=154.13이기 때문에 155회 이상 섞어야 공정한 대결을 할 수 있죠.

그런데 15퍼즐이 어떻게 마르코프 연쇄냐고요? 15퍼즐에서는 숫자 조각을 하나씩 이동하는 것을 섞는 방법이라고 할 수 있는데, 한 번 움직일 때마다 생기는 배열은 바로 직전 배열에만 영향을 받으니까 마르코프 연쇄라고 할 수 있죠.

루빅스 큐브를 뒤섞는 건 카드 섞기를 입체적으로 확장한 형태라고 볼 수 있습니다. 무작위하게 섞이는 횟수를 찾는 방법도 카드 섞기와 똑같죠. 다만 루빅스 큐브는 경우의 수가 엄청나게 많습니다. 그래서 잘 알려진 3×3×3 큐브는 무작위하게 섞어주는 횟수를 계산하기가 너무 어렵습니다.
그래서 티모시 개러니 호주 모내시대학교 수리과학부 교수는 2×2×2 큐브를 연구했습니다. 큐브를 좌우, 위아래 방향으로 돌릴 때마다 변하는 배열을 마르코프 연쇄로 보고 확률 분포의 차이가 0에 가까워지게 만드는 횟수를 계산했죠.

2×2×2 큐브라고 해도 좌우, 위아래로 각각 90°, 180°, 270° 회전할 수 있어 가능한 배열의 수가 367만 4160가지나 됩니다. MCMC 기법을 적용한 컴퓨터 알고리듬을 만들어서 푼 결과 19회를 기점으로 확률 분포의 차이가 급격히 작아져서 0에 가까워졌습니다. 최소 19회를 섞으면 2×2×2 큐브는 무작위하다고 할 수 있는 거죠!

카드 섞기와 전혀 다른 형태의 퍼즐이지만 같은 원리로 무작위하게 만드는 횟수를 알아낼 수 있다니 놀랍지 않나요? 사실 카드 섞기에 대한 설명을 듣고 더 어려운 개념이 등장할 줄 알고 난처했는데 다행입니다. 하하. 말씀드리는 사이에 인공지능 퍼즐 로봇 알파와 피에로 고수가 발가락으로 루빅스 큐브 맞추기 대결을 시작할 준비를 마쳤다고 합니다. 자, 그럼 공정한 대결의 결과가 어떻게 될지 지금부터 중계해드리겠습니다. 채널 고정!