유전 알고리즘을 이용한 테트리스

Minsuk Jang·2021년 10월 16일
0

토이프로젝트

목록 보기
2/3
post-thumbnail

🤔 개발 동기

2018년도 대학교 3학년 때, C++언어 강좌의 중간 프로젝트로 A.I 테트리스를 제작하는 프로젝트가 주어졌다. 그 때 당시, 프로젝트를 진행하기 위해서 자동으로 두는 테트리스 방법을 찾던 도중, 유전 알고리즘을 이용하여 테트리스를 제작했다는 글을 보았다.
당시 A.I 테트리스 프로젝트를 진행할 때 봤던 글, 당시에 해당 방법으로 구현하지 않았다.

그 때 당시에 굉장히 "간지" 가 났었다. 하지만, 프로그래밍 실력이 형편없었기 때문에 단순히 brute force 방식으로 테트리스 블럭을 둘 공간을 하나하나 살펴보고 테트리스 블럭의 주위에 많은 블럭이 접하도록 유도하는 방식으로 구현을 진행하였다. (최저: 98줄, 최고: 468줄)

거두절미하고 그 때, 당시의 방법이 워낙 인상 깊게 남았기 때문에 유전 알고리즘을 이용한 테트리스를 제작하였다.

🔨 개발 과정

크게 두 가지로 나눠서 프로젝트를 진행하였다.

1. Java를 이용하여 테트리스 로직 구현 / Swing을 이용하여 UI 구현
2. 유전 알고리즘 구현 및 적용

Java를 이용하여 테트리스 로직 구현

로직은 아래의 그림과 같다.

위의 로직으로 테트리스 블럭을 둘 때, 이슈가 발생한다.

현재 테트리스 블럭을 두는 방법의 기준은 **테트리스 블럭을 내린 후, 우측으로 탐색이 진행**된다는 점이다.
우측과 같은 그림에서는 테트리스가 빨간색 테두리에 들어갈 수 있음에도 탐색을 하지 못한다. 왜냐하면 테트리스를 위로 올려서 탐색을 진행하지 않기 때문이다,

테트리스에 유전 알고리즘을 적용

프로젝트의 목표를 유전 알고리즘을 이용해서 최대한 테트리스를 오랫동안 살리는 것 으로 잡았다.
최대한 오랫동안 살리는 것 == 지우는 줄 수가 많다는 것

유전 알고리즘을 어떤 식으로 테트리스에 적용하는 것이 궁금하였고 동영상을 보면서 하나의 유전자를 테트리스 한 게임으로 간주하면 되겠다는 아이디어를 얻었다.

마지막으로 어떤 가중치를 사용할 건지에 대한 문제였다.
※ 유전 알고리즘의 경우, 알고리즘을 진행하기 위해서는 가중치의 값이 필요하다.

필자는 블로그에서 설명하는 가중치 값들을 이용하여 4개의 가중치를 설정하였다.
※ 블로그 글을 읽으면서 이해가 안되는 부분은 위 작성자의 GitHub에 올라가 있는 코드를 보고 해결했다.

최종적인 알고리즘 순서는 아래와 같다.

1. 사용자가 설정한 크기만큼 초기 유전자 개수를 만든다.
2. 주어진 가중치를 가지고 사용자가 설정한 게임 횟수만큼 게임을 진행한다.
3. 게임에서 지운 줄을 현재 유전자의 fitness(지운 줄) 에 누적한다.
4. fitness(지운 줄) 을 대상으로 내림차순 정렬을 한다.
5. Tournament Selection을 이용해서 사용자가 설정한 횟수만큼 토너먼트를 진행하여 유전자 두 개를 선택한다.
6. 선택된 두 개의 유전자를 가지고 Cross over를 진행한다.
7. 현재 유전자의 30% 개수를 지운다. 5~6번 과정을 거쳐서 만들어진 30%의 새로운 자식 유전자를 현재 유전자에 추가한 후, fitness(지운 줄)을 대상으로 내림차순 정렬을 한다.
8. 2~7번 과정을 반복한다.

🎉 결과

세대를 지날수록 성능이 좋아지는 것과 최대 2만줄까지 지우는 것을 확인하였다.

소스 코드

🔖 참고

profile
Positive Thinking

0개의 댓글