민서 개발일기

https://youtu.be/Yr_nRnqeDp0

어느 날 유튜브 알고리즘에서 해당 영상이 뜨게 되었고 스스로 학습하는 AI라는 것에 흥미를 느껴 개발을 시작하게 되었다.

해당 영상에서는 '유전 알고리즘'을 이용하여 AI에게 그네를 더 넓은 폭으로 움직이도록 탈 수 있도록 학습하게 하였다.

그렇다면 개발을 시작하기 전 '유전 알고리즘'의 원리부터 알아보자

유전 알고리즘이란

유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 한다. -위키피디아 글 인용

조금 더 쉽게 정리하면 최적해를 찾기 위해 탐색을 반복해가며 더 좋은 해를 찾아가는 알고리즘이라고 할 수 있을 것 같다.

즉 유전 알고리즘을 구현하기 위해선 '해'를 유전자의 형식으로 표현할 수 있어야 하고 '더 좋은 해'를 구분하기 위한 적합도 함수를 짤 수 있어야 한다.

유전자의 형태는 여러 형태가 있을 수 있지만 가장 설명하기 쉽고 간단한 배열로 설명할 것이다.

유전 알고리즘을 구현할 때 우선 초기 해 집단은 랜덤으로 구성된다. 그 후 적합도 함수에 따라 우수한 해들을 선택하고 선택한 유전자들 중 보통 2개를 합쳐 교배하여 후대 유전자를 만든다. 그리고 그 과정에서 낮은 확률로 변이를 일으키고 현재 유전자를 후대 유전자로 교체하는 과정을 반복해야 한다.

이때 변이가 필요한 이유는 지역최적점에 빠지지 않게 하기 위해서인데 변이를 통하여 한 경로만 탐색하지 않고 여러 경로를 탐색하여 더 좋은 경로가 있는지 확인할 수 있다.

선택(Selection)

선택의 종류는 매우 다양한데 예를 들면 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등이 있다.

해의 선택 방식에 따라 최적해를 구하는 속도가 빨라지고, 지역 최적점에 빠지지 않게 할 수 있으므로 선택의 과정은 매우 중요하다 할 수 있다.

일반적으로 선택을 하는 방식은 가장 좋은 해일수록 선택될 확률이 높아진다. 반대로 말하면 나쁜 해라도 선택될 가능성이 있다는 것을 의미하고 이를 통해 지역 최적점에 빠지지 않게 할 수 있다.

균등 비례 룰렛 휠 선택

유전자의 적합도에 비례하여 선택될 확률을 결정하는 선택 방식이다. 주로 전체 적합도 합에서 본인 적합도를 나누어 확률을 결정한다.

토너먼트 선택

K개의 랜덤한 해를 고르고 그 중 가장 적합도가 높은 해를 결정하는 방식이다.

음수인 적합도값에도 사용할 수 있다.

순위 기반 선택

적합도 점수를 기준으로 정렬하여 순위가 높을수록 선택될 확률을 높게 하는 방식이다.

ex) 1위 : 40%, 2위 : 30%, 3위 : 20%, 4위 10%

필자는 해당 방식을 사용했다.

교배, 교차(Crossover)

유전자를 교차하여 다음 세대의 유전자를 만드는 과정이다. 일반적으로 두 개의 유전자를 선택하여 교차 연산을 수행하며 이렇게 생성된 유전자는 각각의 부모 유전자의 교차 연산을 통한 서로 겹치지 않는 유전인자를 받아 새로운 유전자를 구성한다.

교차 연산에는 N-점 교차, 일정 교차, 산술 교차 등이 있다.

N-점 교차

해당 방식처럼 N개의 점을 골라 해당 점을 지날 때마다 다른 부모의 유전 인자를 가져가는 방식이다.

일정 교차

비트열 등을 이용한 마스크를 사용하여 일정한 형태로 교차하는 방식이다.

필자는 해당 방식을 사용했다.

산술 교차

실수 값이 사용되는 경우에 사용하며, 각 인자에 대해 두 부모 인자의 평균값을 사용한다.

변이

교차 과정에서 지역 최적점에 빠지지 않기 위해 낮은 확률로 인자 값을 랜덤 한 값으로 변환하는 것을 의미한다.

정적 변이와 동적 변이가 존재하는데 정적 변이는 변이될변이 될 확률이 고정이지만 동적 변이는 세대를 지날수록 변이 될 확률이 점점 낮아진다.

동적 변이를 사용하는 이유는 세대가 지날 수록 최적해에 가까워졌을 것이라고 판단했기 때문일 것이다.

유전 알고리즘의 기본적인 원리 설명은 끝났으니 결과물을 확인해 보자

해당 프로젝트는 https://github.com/s53809/Genetic-Algorithm를 통하여 열람, 다운로드할 수 있다.

해당 프로젝트에서는 크게 3개의 시스템으로 유전 알고리즘을 이용한 길 찾기 프로그램을 설계하였다.

유전 알고리즘의 전반적인 연산을 담당하는 GenerationManager.cs 와 GenerationManager에서 받아온 정보를 가지고 이동하고 최적해를 계산하여 다시 GenerationManager로 전달하는 EntityController.cs, 그리고 몇 세대인지, 해당 세대에서 가장 최적의 결괏값을 가졌던 유전자의 정보를 사용자에게 보여주는 UIManagement.cs 가 있다.

Entity

Entity는 실제로 탐색하는 객체들이며 GenerationManager에서 들어온 정보를 토대로 움직이고 그에 따라 최적해를 계산하는 간단한 연산을 수행한다.

GenerationManager

유전 알고리즘 연산을 수행하는 메인 시스템으로 유전자들을 생산하고, 선택, 교차, 변이, 교체 등 여러 연산을 수행하며 각 Entity에게 유전자 정보를 전달하는 역할을 한다.

Setting 헤더에 포함된 해당 변수들은 사용자로부터 Entity 객체의 개수, 변이 확률, 행동 변화 간격 시간, 행동(유전자) 개수, 움직임 속도를 입력받게 할 수 있다.

Init()에서는 초기 해 집단을 랜덤으로 구성하기 위하여 생성된 함수이다.

Select()에서는 선택 연산을 위한 함수,

DestroyObj ()에서는 교차 연산이 끝나고 새로운 유전자로 교체하기 위해 기존 Entity 객체들을 삭제하는 함수이다.

Crossover()에서는 교차 연산을 위한 함수이지만 선택, 교차, 변이의 과정이 모두 들어가 있다. 또한 선택 연산을 위하여 유전자 정보들을 정렬하기 위하여 정렬되는 대상인 EntityController에 IComparable <EntityController> 인터페이스를 상속시켜 원하는 순서대로 정렬되게끔 설계하였다. ICompareable 인터페이스에 관해서는 요긴하게 써먹을 수 있기 때문에 모르고 있었다면 찾아보는 것을 추천한다.

UIManagement

세대 정보와 해당 세대에서의 최적해의 정보를 사용자에게 표시하는 시스템이다.

결과물

https://youtu.be/LlMiof0 cqHo

느낀 점

유전 알고리즘을 공부하면서 시행착오가 많았다.

불필요한 움직임으로 인하여 내가 생각했던 것과 같은 매우 효율적인 움직임을 300세대를 거쳐도 나오지 않았으며 내가 설계한 알고리즘에 따르면 세대를 지나면 지날수록 지역 최적점에 수렴하기 쉬워졌기 때문에 도착지까지 도달하는 시간이 단축되는 빈도가 점점 줄어들었다.

교차 방법을 N-점 교차에서 일정 교차로 교체해보기도 하고 변이 확률을 늘려보았지만 개선되긴 하였으나 결국엔 세대를 지나면 지날수록 효율적인 움직임을 위해 변이에 의존하는 수밖에 없었다. 왜 사람들이 AI 분야에서 유전 알고리즘 대신 다른 알고리즘을 쓰는지 어느 정도 체감이 되었던 것 같다.

하지만 처음으로 AI라는 분야를 다뤄보면서 스스로 학습하여 경로를 찾아가는 AI를 구현했다는 사실이 나에겐 너무 신기했고 재밌었다.

유니티 개발 현황 #2까지 쓰고 신경을 못 써버린 게임인 Danma가 완성되었습니다.

Danma를 개발하면서 많은 게임 알고리즘 기법들을 공부하고 발전할 수 있는 계기가 되었던 것 같아 좋았습니다.

Danma는 4월 15일에 열리는 한국애니메이션고등학교 2022 게임박람회에 출품할 예정이라 빌드 파일 역시 4월 15일에 올려보도록 하겠습니다.

Danma는 기본적으로 리듬, 탄막 게임입니다.

'Just Shape and Beats'와 '로스트아크' 라는 게임에서 영감을 얻어 제작하게 되었으며 2스테이지 구성으로 되어있습니다. 게임의 흐름은 일반스테이지 - 보스스테이지로 구성이 되어있으며 일반스테이지에서는 조작법을 익히고 이 게임의 특징 중 하나인 기믹을 인지할 수 있도록 설계를 해보았으나 의도대로 잘 되었을진 모르겠습니다.

첫번째 스테이지

첫번째 스테이지는 소행성지대라는 컨셉을 갖고 만들어진 스테이지입니다.

소행성지대라는 컨셉에 걸맞게 운석이 떠다니며 여러분들은 그 운석을 피하셔야 합니다.

이때 분홍색으로 강조된 운석은 파괴하지 않으면 게임의 난이도를 상승시켜주는 커다란 운석이 나타나게 됩니다.

하지만 보통 플레이어는 특정한 오브젝트는 파괴할 수 있다는 사실을 모를 것이기 때문에 약간의 힌트를 주기 위하여

분홍색 운석을 파괴하지 않고 넘어갔을 때 빨간색 파티클이 뜨게 하였고, 튜토리얼에서도 특정한 오브젝트는 파괴할 수 있다고 언급을 하였습니다. 이를 통하여 플레이어는 다음스테이지에서도 이러한 '기믹'을 의식하도록 만들었습니다.

두번째 스테이지

두번째 스테이지는 본격적으로 보스와 싸우는 스테이지입니다. 2개의 스테이지로밖에 구성이 안되어있었기 때문에 난이도 부분을 통하여 플레이 타임을 늘리려 했습니다. 하지만 가능성이 안보일정도로 높을 경우에는 게임의 흥미를 잃을 수 있기에 난이도 조절에서 많은 시행착오가 있었습니다. 보스 스테이지에서는 1스테이지에서 경험했던 '기믹' 패턴과 탄막 패턴을 적절하게 섞었습니다. 이 방식으로 마치 로스트아크의 '선발대' 라는 개념처럼 플레이어가 여러번의 트라이를 통해 본인만의 공략법을 만들어 나가도록 게임을 설계했습니다. 파훼를 못하면 즉사하는 기믹도 있으나 여러 오브젝트로 힌트를 주어서 플레이어가 그 힌트들로 상황을 판단하여 기믹을 깰 수 있도록 만들었으나 다른 친구들에게 테스트해본 결과 생각보다 피하는데에만 집중을 하고 있어서 아쉬웠습니다.

아쉬웠던 점

기본적으로 모든 에셋들이 대부분 아트 1명이 디자인한 오브젝트와 디자인에 무지한 제가 제작한 몇몇개의 오브젝트로 이루어져있어 넣을 수 있는 애니메이션에 한계가 있었습니다. 그렇기에 게임이 약간 단조로워 보일 수 있다는 생각이 들었습니다. 또한 장기간에 걸쳐 제작된 프로젝트이기에 초반에 제작한 스테이지 선택 화면에서 개선해야 할 부분이 생겼을 때 더럽게 짠 코드로 수정하는데 힘들었던 경험이 있었습니다. 그리고 스테이지가 2개밖에 안된다는 점에서 난이도로 플레이타임을 억지로 늘릴 수 밖에 없었기에 자칫하면 난이도 문제로 흥미를 잃을 수 있겠다는 생각이 들었습니다.

느낀 점

유니티를 이용하여 처음으로 제작한 제대로 된 게임이라는 점에서 의의를 두고 싶습니다. 최대한 게임을 재미있게 만들기 위해서 여러 게임알고리즘과 기법들을 공부하면서 많은 지식을 얻어갈 수 있었습니다.

빌드파일은 4월 15일날 올리도록 하겠습니다. 긴 글 읽어주셔서 감사합니다.

구현한 것

플레이어에 대쉬 기능을 추가하였다. 밋밋해보이지 않기 위해 약간의 파티클도 넣어줬다.

베지어 곡선을 이용하여 운석 움직임을 구현하였고 약간의 기믹을 추가하여 만약 분홍색 운석을 파괴를 하지 못할 시 왼쪽에 빨간 이펙트와 함께 위에서 거대한 운석이 출현하도록 해보았다.

느낀점

베지어 곡선을 이해하는데 약간은 힘들었지만 만족스러운 결과물이 나온 것 같아서 기분이 좋았다.

파티클을 배우면서 다양한 방면에서 활용할 수 있었고 게임의 완성도도 높아진 것 같았다.

개선할 점

작은 운석의 무작위성과 속도가 너무 빠르다는 점에서 난이도가 너무 어려울 수 있겠다는 생각이 들었다. 운석의 속도를 적당한 난이도에 맞출 예정이다.

스테이지 길이가 1분 32초에 비해 패턴이 단순 반복 패턴이기에 지루할 수 있다. 패턴을 조금 더 추가할 예정이다.

플레이어의 움직임이 딱딱하기 때문에 약간의 애니메이션을 줘서 자연스럽게 만들 예정이다.

원이 화면 밖에서 안으로 들어온 뒤 탄막을 쏘고 사라진다.

이 역시 탄막에도 적용했던 오브젝트 풀링을 이용하여 더 효율적으로 만들었다.

하지만 Object Pooling 시스템에 하자가 있는 것 같다.

플레이어가 갑자기 총을 쏘던 도중에 총알은 안 나가고 체력을 닳길래 콜라이더를 꺼봤더니 갑자기 적 탄막을 쏘고 있었다. Object Pooler 파일에는 분명 tag로 분류하여 시스템을 만들고 있는데 충돌이 일어난 것 같다.

심지어 가끔 플레이어 총알이 랜덤으로 다시 나타날 때도 있다. 내일 다시 오류를 고쳐봐야 할 것 같다.

5. 돌 무더기 게임 (9점)

문제

   A, B 두 사람이 다음과 같은 게임을 한다.

   두 사람은 테이블 하나에 서로 마주 보고 앉아있다.

   테이블 위에는 세 개의 돌 무더기가 있고, 각 무더기에는 각각 1개, 2개, 3개의 돌이 있다. A부터 시작해서 돌아가면서 게임을 진행하는데, 세 돌 무더기 중 하나를 고르고, 가져가고 싶은 개수만큼의 돌을 가져간다.

   단, 돌을 최소한 한 개는 가져가야 한다. 돌을 가져간 다음, 테이블에 돌이 남아있지 않다면, 이 사람이 이긴다.

   A, B 모두 항상 자신이 이기기 위해서 최선을 다한다. 이 때 게임의 결과는 어떻게 될까?

1. A가 항상 승리한다.

2. B가 항상 승리한다.

3. A가 승리할 수도, B가 승리할 수도 있다.

정답

2번

풀이

이 문제는 NIM game에서 유래된 게임으로 A, B와 같이 2명이서 하는 경우에는 필승법이 존재한다.

바로 플레이어의 차례일 때 불균형상태인 돌들을 균형 상태로 맞춰주면 된다.

이때 균형상태는 세 줄의 돌들을 2의 거듭제곱의 합으로 표현했을 때 2의 거듭제곱이 쌍으로 존재하는 것을 의미한다.

예를 들어 지금 문제의 경우에는 1,2,3 개가 있는데 1=1, 2=2, 3=2+1 이므로 1이 2개, 2가 2개가 존재한다.

이에 대한 증명은 구글에 NIM game이라고 검색하면 나온다.

A, B 모두 항상 자신이 이기기 위해서 최선의 수를 선택한다고 하였으므로 지금 돌 무더기는 균형 상태이기 때문에

A는 어쩔 수 없이 불균형상태로 만드는 수밖에 없고 결국 균형 상태로 만드는 B가 항상 승리하게 된다.

나는 NIM game 을 이 링크를 통해 공부하였다. 새로운 알고리즘을 알게 된 것 같아서 기분이 좋았다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nyseul&logNo=220009539606

4. 발표 순서 (8점)

문제

   조별 발표를 위해 A부터 F까지 6개 조에 대한 발표 순서를 정하려고 한다.

   모든 가능한 발표 순서를 알파벳 순서로 나열해보면 ABCDEF부터 FEDCBA까지 720가지가 있는데, 그중 CBADEF는 몇 번째인가?

1. 241

2. 253

3. 265

4. 385

5. 409

정답

3번

풀이

경우의 수를 구하는 문제이다.

자릿수 마다 나올 수 있는 경우의 수를 구해보면

맨 왼쪽 자릿수는 5 * 4 * 3 * 2 * 1 = 120번째마다 알파벳이 바뀐다.

CBADEF이므로 맨 왼쪽이 C가 나오려면 최소 241번째가 돼야 한다.

2번째 자릿수는 4 * 3 * 2 * 1 = 24번째마다 알파벳이 바뀐다.

2번째 자릿수가 B가 나오려면 241 + 24 = 265번째가 된다.

나머지 자릿수는 알파벳 변동이 없는 초기값이므로 정답은 265번째 3번이다. 

3. 동전과 확률 (8점)

문제

   10개의 동전이 있는데, 앞면은 모두 같은 모양이지만 뒷면은 x개의 동전에는 A, 10 − x개의 동전에는 B 라고 표시가 되어 있다. 이 10개의 동전들이 앞면이 위가 되게 놓여 있다. 이 중 공평하게 두 개를 한번에 골라서 뒤집었을 때, 둘 모두 뒷면에 A가 나올 확률이 0.4 이하가 되는 가장 큰 x의 값은?

1. 8

2. 7

3. 6

4. 5

5. 4

정답

3번

풀이

두 뒷면에 A가 나올 확률이 40% 이하중 가장 큰 값이여야 하므로 가장 높은 확률부터 차례대로 확률을 모두 구해보면 된다.

1. 64% ( 40% 이상 )

2. 49% ( 40% 이상 )

3. 36% ( 40% 이하 ) | 실제 문제를 풀때는 여기서 정답을 적는다.

4. 25% ( 40% 이하 )

5. 16% ( 40% 이하 )

고로 답은 3번이다.

2. 구슬 경로의 수 (8점)

문제

   아래 그림과 같은 통로에 구슬을 떨어뜨리면 통로를 빠져나올 때까지 지나는 경로는 구슬을 떨어뜨릴 때마다 다를 수 있다. 통로 안에서 구슬이 아래에서 위로는 움직일 수 없다고 가정할 때, 구슬이 지날 수 있는 서로 다른 경로는 몇 가지 존재하는가?

1. 12

2. 24

3. 35

4. 64

5. 128

정답

3번

풀이

이건 단순한 경우의 수 계산 문제이기 때문에 구간별로 총몇번 올 수 있는지 더해주면 된다.

그렇기에 총 경우의 수는 35가지 답은 3번이다.