좀 지난 일입니다만 한게임 테트리스를 하면서 정말 테트리스를 못한다는 걸 알게 되었습니다...
어려서 오락실을 잘 안 다녀서 그런가... 다들 잘하는데 저만 맨날 꼴찌를 하니 재미가 없더군요. 그래서 집에서 심심할 때 테트리스를 자동으로 해주는 오토를 한 번 만들어 보기로 마음먹었습니다.
프로그램이 자동으로 테트리스를 하게 하려면 우선 테트리스에 대해 잘 알아야겠죠. 분석을 시작했습니다.
테트리스의 게임 방식은 모두가 알고 있을 만큼 단순합니다. 떨어지는 블록을 회전시키고 이동시켜서 빈칸이 없게 쌓아 한 줄을 만들면 한 줄이 지워지는 방식인 거죠.
표준 테트리스의 경우 블록은 총 7개로 구성되어 있고 보드는 10x20 칸으로 구성되어 있습니다.
위 그림처럼 총 7개의 블록으로 구성되며 블록별 회전 상태는 최대 4가지의 형태를 가지게 됩니다. 1번 블록 같은 경우는 회전시켜도 그 모양이니 굳이 회전된 상태를 구할 필요가 없는 것이죠.
각 블록의 그림에 검은색 동그라미가 있는데 그것은 회전축이 되겠습니다. 이 회전축은 게임마다 다르지만 표준 테트리스의 블록은 위와 같은 형태라고 보시면 되겠습니다.
이런 7종류의 블록을 아래와 같은 가로 10, 세로 20개의 칸으로 구성된 테트리스 보드에서 회전과 이동을 하게 됩니다. 종류에 따라 보드의 크기나 블록의 가짓수가 많고 적은 경우가 있습니다만 표준은 이렇다고 합니다.
지금까지 설명한 게 테트리스의 기본이자 전부입니다.
실제 게임으로 만든다고 가정하면 7개의 블록 중 랜덤 하게 하나를 선택해서 정해진 속도대로 한 칸씩 아래로 이동시키면 되고 사용자의 입력을 받아 블록을 좌우 이동 혹은 회전이 가능하도록 하면 되죠. 블록이 쌓여서 하나 이상의 라인이 만들어지면 지워주고 위에 남은 블록들을 아래로 이동시키면 되고요. 그와 동시에 점수를 계산해서 뿌려주면 되는 거죠.
현재의 블록이 놓일 최적의 장소와 블록의 회전 형태를 찾는 것이 테트리스 인공지능의 기본이 되겠습니다.
테트리스를 잘하려면 크게 세 가지 규칙을 지켜야 합니다.
첫째. 블록이 높이 쌓이지 않도록 한다. 즉, 최대한 평평하게 쌓는다.
둘째. 빈 공간이 최대한 생기지 않도록 한다.
셋째. 좌우 벽면과 바닥에 최대한 많은 면이 닿도록 한다.
이 세 가지가 가장 기본이 되는 테트리스 플레이 방식이죠. 이 방식만 잘 지켜도 오래도록 끝나지 않고 플레이할 수 있을 겁니다. 이론적으로는요...
일반적으로 블록을 쌓는다는 것은 아래와 같은 겁니다.
각각 쌓인 블록들이 층을 이루게 되고 쌓인 층의 높이가 낮을수록 유리합니다. 한 줄을 모두 채우지 못하고 계속 층이 생긴다면 굉장히 불리해집니다.
또, 쌓인 층들에 빈 공간이 많이 생기지 않도록 쌓아야 합니다.
위의 그림에서 하얀색 사각형이 블록을 쌓을 수 없는 빈 공간입니다. 위에 다른 블록들이 막고 있어서 저 공간은 채울 수가 없는 거죠. 저런 공간이 많아질수록 한 줄을 모두 채우기가 힘들어지고 높은 점수를 얻기가 어렵습니다.
반대로 위 그림의 하얀 사각형들은 블록 사이의 빈 공간을 막고 있는 블록들을 표시한 것입니다. 블록 사이에 있는 빈 공간과 이 빈 공간을 막고 있는 블록의 개수가 적을수록 유리하죠.
지금까지 얘기한 내용을 통해 최적의 장소를 찾기 위한 항목들을 알 수 있습니다.
1. 블록 높이의 합.
2. 완성된 줄의 개수
3. 블록 사이에 있는 빈 공간의 개수.
4. 빈 공간을 막고 있는 블록의 개수.
이 총 네 개의 항목을 통해 현재 떨어지고 있는 블록을 조합 가능한 모든 지점에 회전까지 적용해서 미리 배치하고 각 지점별로 최적의 값을 계산해 볼 수 있습니다.
즉, 블록을 떨어트려서 쌓기 전에 미리 시뮬레이션을 해 보는 거죠. 그중에서 가장 큰 값이 나오는 곳이 블록이 위치하기 좋은 위치가 되는 것입니다. 참 쉽죠???
그럼 계산은 어떻게 하는 건지 간단한 공식을 보겠습니다.
점수(Score) = (A x 블록 높이의 합) + (B x 완성된 줄의 개수) + (C x 블록 사이에 있는 빈 공간의 개수) + (D x 빈 공간을 막고 있는 블록의 개수)
이 공식으로 점수를 계산할 수 있습니다.
위 공식 중 A, B, C, D는 정해지지 않은 상수입니다. 최적의 상수값을 찾는 게 실제로 어려운 부분이죠.
그럼 최종적으로 테트리스를 잘하는 방법에서 설명한 항목과 위에서 설명한 점수 공식을 통합하여 최적의 블록 위치를 찾는 공식은 아래와 같은 항목을 갖게 됩니다.
A. 블록 높이의 합
B. 블록 사이에 있는 빈 공간의 개수
C. 빈 공간을 막고 있는 블록의 개수
D. 완성된 줄의 개수
E. 현재 블록이 기존 블록들과 닿는 면의 개수
F. 현재 블록이 좌우 벽면과 닿는 면의 개수
G. 현재 블록이 바닥면과 닿는 면의 개수
이 값들을 모두 더 한 값 중 가장 높은 값이 나오는 곳이 최적의 위치라고 볼 수 있습니다.
앞서도 설명했지만 테트리스 보드 이미지의 X축 칼럼 별로 1~10까지 하나씩 현재 블록을 위치시켜 보고 칼럼 별로 가능한 회전까지 모두 고려하여 각각의 점수를 계산하는 것입니다.
그럼 한 블록당 4개의 회전 블록을 가지고 있다고 가정하면 총 10개의 칼럼을 검사해야 하니까 블록 하나당 40번의 검사가 필요하겠군요. 이건 최대의 경우고 2번 블록처럼 4개의 칼럼을 차지하는 블록의 경우는 계산이 줄어듭니다.
이렇게 생각할 수 있는 항목별로 상수를 곱해서 최적의 값을 찾아야 하는데요. 높이 쌓이지 않아야 하고 최대한 평평하게 쌓아야 하며 블록 사이에 빈 공간이 최대한 생기지 않도록 하려면 항목에 어떤 값들이 상수로 곱해져야 할지는 테스트를 거쳐서 결정해야 합니다.
한게임 테트리스의 인공지능을 만드는데 퇴근 후 집에서 작업하면서 코딩은 2일 정도 걸렸습니다만 최적의 상수값 튜닝을 위해 2주 정도가 소요되었습니다. 정답이 없는 작업인 거죠.
제가 한게임 테트리스에 사용한 상수값은 아래와 같습니다.
A. 블록 높이의 합 x -3.78
B. 블록 사이에 있는 빈 공간의 개수 x -8.8
C. 빈 공간을 막고 있는 블록의 개수 x -0.59
D. 완성된 줄의 개수 x 8.2
E. 현재 블록이 기존 블록들과 닿는 면의 개수 x 3.7
F. 현재 블록이 좌우 벽면과 닿는 면의 개수 x 2.5
G. 현재 블록이 바닥면과 닿는 면의 개수 x 4.0
이렇게 결정한 상수값을 각각의 항목에 곱한 후 모두 합하면 점수가 계산되어 나오고, 가장 높은 점수가 나오는 곳이 현재 블록의 최적의 위치가 되는 것입니다.
한게임 테트리스의 대전방에서 사용하기 위해 만든 것이 아니라 40라인을 최단 시간에 깨는 싱글모드용으로 최적화된 상수값입니다. 이렇게 얻어진 결과로 한게임 테트리스 40라인 최단시간에 도전해 보았고 결론은 랭킹 1위가 되었습니다.
다들 절대신이거나 최소 영웅인데 저만 평민... 그것도 하급 이군요. ^^;;
20초 60의 기록으로 1위를 했습니다만 심심풀이로 계속 돌리다 보니 나중엔 19초로 1위를 기록했었습니다. 한게임 테트리스가 키를 너무 빨리 보내면 꿀꺽~ 해 버리는 바람에 키 반응 속도로만 시간을 단축시키는 데는 한계가 있었고요. 인공지능 상수값의 튜닝으로 속도를 더 올릴 수 있었습니다. 물론~ 랜덤 하게 나오는 블록들의 배치가 좋아야 더 좋은 기록이 나오기 때문에 어느 정도 운도 필요하죠.
저는 프로그램으로 1등을 했습니다만 다른 분들 기록을 보면 정말 인간의 한계는 끝이 없다는 걸 느끼게 됩니다. 정말 엄청난 기록이죠 21초 82라는 2위 한 분의 기록은요...(실제로는 이분이 1등이시죠 ^^)
20초대로 40라인을 클리어하려면 어느 정도의 속도로 테트리스를 플레이해야 하는지 테트리스 인공지능으로 게임을 플레이한 화면을 동영상으로 찍어봤습니다. 한 번 보시죠. (정상 속도로 플레이한 영상입니다. 빨리 감은 거 아니에요.)
빠르죠? ^^; 속도는 더 올릴 수 있었습니다만 공교롭게도 제가 지난 9월에 심심풀이로 테트리스 인공지능을 만들 당시 한게임에서 이벤트를 하고 있었어요. 랭킹 30위까지였나? 기억은 잘 안 납니다만 키보드를 선물로 주는 이벤트였죠.
전혀 이벤트와는 상관없이 순수한 호기심으로 작업을 한거였습니다만 결론적으로 계정 블록 당했습니다. ㅠㅠ...
혹시 만들어 보실 분이 계시다면 1등은 하지 마세요.. 그냥 적당히 테스트만 해 보시는 게... ^^;;
인간의 머리를 대신해서 비슷한 일을 하게 하는 인공지능. 어차피 인공지능도 사람이 만들어 내는 것이므로 사람을 뛰어넘기는 정말 힘들죠. 인간을 뛰어넘기보다 인간을 편리하게 보조하는 쪽으로 발전해서 영화에 나오는 그런 세상이 오기를 꿈꿔 봅니다.
