d라이브러리

최근 중독성 있는 한 모바일 게임이 인기를 끌고 있다. ‘캔디 크러쉬 사가’라는 이름의 이 게임은 단순히 같은 종류의 캔디를 가로나 세로 방향으로 3개 이상 맞춰 없애는 게임이다. 이 게임은 2012년에 출시되어 하루에 9300만 명이 즐길 정도로 인기가 높다.

그런데 최근, 호주 뉴사우스웨일즈대의 토비 월시 교수가 이 게임의 원리가 ‘NP-하드 문제’의 원리와 같다는 흥미로운 연구결과를 발표했다. NP 문제란 답을 구하기는 어렵지만 답이 될 수 있는 후보들을 통해 답이 맞는지는 확인할 수 있는 문제를 말한다. 쉽게 말하면, 모든 경우의 수를 전부 확인해 보는 방법 이외에는 정확한 답을 구할 수 있는 방법이 없는 문제들을 뜻한다. NP 문제 중에서 가장 어려운 문제를 NP-하드 문제라고 하는데, 최적화와 관련된 문제들과 깊은 연관이 있다.

토비 월시 교수는 ‘캔디 크러쉬 사가’ 게임에 나오는 6개의 사탕 종류 중에서 5개를 가지고 연구를 실시했다. 또한 포장이 되어 있거나 줄무늬가 있어서 더 많은 사탕이 제거되는 특수한 사탕들은 연구에서 제외했다. 연구팀은 처음 주어진 게임 상황에서 같은 종류의 사탕이 연달아 있는 부분을 찾았다. 이어 그 주위에 있는 다른 사탕들을 여러 방향으로 움직여 보면서 게임을 공식화하려고 했다. 하지만 매번 높은 점수를 만드는 공식을 발견할 수 없었고, 결국 ‘캔디 크러쉬 사가’ 게임이 NP-하드 문제와 같은 최적화 문제의 일종이라는 결론을 내렸다.

그러니 ‘캔디 크러쉬 사가’ 게임을 하면서 좌절에 빠질 필요는 없다. 처음부터 이 게임을 완벽히 해결할 수 있는 방법은 없기 때문이다. 다만, 게임을 해결했을 때에야 비로소 지금까지의 과정이 답이라는 것을 알 수 있다.

토비 월시 교수는 “캔디 크러쉬 사가 게임을 손쉽게 해결하는 방법을 알아낸다면, 이를 통해 ‘외판원 문제’ 등 최적화와 관련된 문제에 즉시 적용할 수 있을 것”이라고 연구 의의를 밝혔다.