좀 지난 일입니다만 한게임 테트리스를 하면서 정말 테트리스를 못한다는걸 알게되었습니다...
어려서 오락실을 잘 안다녀서 그런가... 다들 잘 하는데 저만 맨날 꼴지를 하니 재미가 없더군요. 그래서 집에서 심심할때 테트리스를 자동으로 해주는 오토를 한 번 만들어 보기로 마음 먹었습니다.  

프로그램이 자동으로 테트리스를 하게 하려면 우선 테트리스에 대해 잘 알아야겠죠. 분석을 시작했습니다.

테트리스의 게임 방식은 모두가 알고 있을 만큼 단순합니다. 떨어지는 블럭을 회전시키고 이동시켜서 빈칸이 없게 쌓아 한 줄을 만들면 한 줄이 지워지는 방식인거죠. 


표준 테트리스의 경우 블럭은 총 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등은 하지 마세요.. 그냥 적당히 테스트만 해 보시는게... ^^;;

마지막으로 정말 테트리스의 신이라 불릴만큼 잘하는 분의 동영상을 링크해 봅니다. 

http://youtu.be/cDCpv8gEC4w

인간의 머리를 대신해서 비슷한 일을 하게 하는 인공지능. 어짜피 인공지능도 사람이 만들어 내는 것이므로 사람을 뛰어넘기는 정말 힘들죠. 인간을 뛰어넘기 보다 인간을 편리하게 보조하는 쪽으로 발전해서 영화에 나오는 그런 세상이 오기를 꿈꿔 봅니다. 


Posted by 소가 아닙니다. 타우렌입니다. 두루별

댓글을 달아 주세요

  1. Anon_Admin 2011.12.22 15:35 신고  댓글주소  수정/삭제  댓글쓰기

    멋있어요.....

  2. 2012.01.13 03:44  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

    • 소가 아닙니다. 타우렌입니다. 두루별 2012.01.30 11:56 신고  댓글주소  수정/삭제

      좋게 봐주셔서 감사합니다. ^^
      아이폰 앱을 개발해 보셨다면 기본적으로 C/C++언어에 대한 이해는 어느정도 있으시겠네요.
      언어에 대한 이해가 선행된다면 그 후엔 윈도우 프로그래밍에 대해 공부하시면 되겠습니다.
      MS Visual studio라고 들어보셨지요? 윈도우용 응용프로그램을 개발하기 위한 라이브러리 및 API 함수를 이해하신다면 크게 어렵지 않은 작업입니다.
      운영체제에 맞는 응용프로그램을 개발하기 위해서는 해당 운영체제에 대한 개발지식이 필요합니다.
      지금은 IOS에 대한 이해가 있으신듯 하니 MS Windows라는 OS에 대한 이해를 먼저 하시고 개발 언어에 적응하시면 됩니다.

      부족한 답변이었습니다. ^^

  3. BlinkingStar 2012.01.29 15:28  댓글주소  수정/삭제  댓글쓰기

    좋은 글 잘 봤습니다. 저기 궁금해서 그런데 최적화 상수값을 구하는 것은 어떻게 하는 것인가요? 직접 노가다(?)로 하시나요 아니면 다른 방법이 있나요??

  4. 소가 아닙니다. 타우렌입니다. 두루별 2012.01.30 12:00 신고  댓글주소  수정/삭제  댓글쓰기

    우선 예측에 의해 상수값을 결정한 후 속도와 평균값을 통해 튜닝해 나갑니다.
    설계시 우선순위에 의한 상수값이 결정되고 그 이후 테스트를 통해 얻은 데이터로
    값을 수정해 나가는 것이지요. 노가다라고 한다면 노가다입니다. ^^;

  5. 2012.04.30 11:00  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  6. 2012.04.30 11:06  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  7. 2012.07.04 17:03  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  8. 안녕나야 2014.09.19 10:48  댓글주소  수정/삭제  댓글쓰기

    안녕하세요. 처음에 와우 자동 낚시 프로그램 글보고 들어왔는데요.
    전 와우를 하는 사람은 아니고 영상처리 프로그래밍을 공부하는 학생입니다. 그런데,
    이런 영상처리를 게임에 적용하는것도 참 재밌고 흥미롭네요!!
    정말 대단하신거 같습니다.

    혹시 이 테트리스 프로그램도 영상처리를 이용하신건가요?즉, 화면를 계속 캡쳐하면서 정보를 얻어내는 것인가요?

    • 소가 아닙니다. 타우렌입니다. 두루별 2014.09.30 17:18 신고  댓글주소  수정/삭제

      벌써 몇 년 전에 만들었던 프로그램이라 기억이 가물가물 합니다만... 화면의 일부만 캡쳐해서 사용하는 것은 맞습니다. 다음에 나올 블럭만 캡춰해서 사용하는 것이고요. 해당 블럭에 대한 처리가 되었으면 그 다음에 나올 블럭을 또 캡쳐해 오고... 이런식으로 동작합니다. 실제 화면을 얻어 오는 건 필요 할 때만 하는 것이죠.

  9. logbug 2014.11.11 23:00  댓글주소  수정/삭제  댓글쓰기

    안녕하세요 ㅎ 프로그래밍 배우는 대학생입니다.
    저희가 과제로 테트리스가 나왔는데, 사이트좀 찾아보다가 들리게 되었습니다 ㅎ
    한게임 테트리스로 인공지능을 만들어서 하신게 대단하신거같아요 ㅎ
    만약 오래 살아남는 방향으로 프로그램 목적을 바꾼다면 위에서 제시하신 알고리즘과 차이가 있을까요?

    그리고 기억나신다면, 블록에 어떻게 우선순위를 부여하신건지도 여쭙고 싶습니다 ㅎ

    • 소가 아닙니다. 타우렌입니다. 두루별 2014.11.26 15:04 신고  댓글주소  수정/삭제

      오래 플레이하는 것이 목적이라도 상수를 크게 변경할 필요는 없을겁니다. Score의 계산은 어디까지나 주관적인 내용이므로 상황에 맞게 튜닝은 필요합니다. 그리고 블럭의 우선순위를 질문하셨는데 질문의 의도를 제가 이해하지 못하겠습니다.

  10. 2016.04.27 21:05  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  11. 2016.11.18 11:06  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  12. 질문 2016.12.26 01:40  댓글주소  수정/삭제  댓글쓰기

    혹시 완성된 줄의 갯수란 무엇을 말하는건가요? 잘 이해가 안 되네요..

  13. 질문 2017.01.18 20:39  댓글주소  수정/삭제  댓글쓰기

    한가지 더 궁금한게 있습니다.
    이 인공지능 테트리스는 켜 두면 얼마나 버틸 수 있나요?
    여기 사이트에서 나온 논리대로 구현해서 돌려보니깐 잘 못 버티더라고요..

    요약하면
    1. 사이트에 나온 논리대로 구현(A~G까지)하면 얼마나 플레이가 가능한가요? 켜두고 5분이상 플레이해도 죽지 않나요?

    궁금합니다.

  14. 2017.03.28 15:41  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  15. 질문 2018.11.30 01:18  댓글주소  수정/삭제  댓글쓰기

    현재도 답변을 해주실지 모르겠지만 혹시 블럭 사이에 있는 빈공간의 갯수 * -8.8 부분에 있어서, -8.8이면 다른 값에 비해 상대적으로 높은 가중치를 둔 것 같은데 높은 값이라면 높개 책정된 이유나 블럭 사이에 빈공간이 당연히 저정도의 가중치를 가질만한 문제인지를 알 수 있을까요?

    • 소가 아닙니다. 타우렌입니다. 두루별 2018.12.11 20:56 신고  댓글주소  수정/삭제

      오래전 작업이라 기억이 가물가물 합니다만... 블록과 블록 사이에 빈공간이 많이 생길 수록 블록이 높게 쌓이게 될 것입니다. 또 면에 밀착되는 블록 수도 줄게 될 것이고요. 이처럼 블록 사이의 빈공간은 여러 상황에 나쁜 영향을 주는 인자이기 때문에 높은 가중치를 설정하게 되었을 것으로 생각됩니다.