[R] '끄투코리아' 사이트를 매개체로 한 강화학습을 통한 끝말잇기 봇 프로그램의 학습 알고리즘 구현 및 테스트

 정보

• 업무명    : 끄투코리아 사이트를 매개체로 한 강화학습을 통한 끝말잇기 봇 프로그램의 학습  알고리즘 구현 및 테스트

• 작성자     : 박진만

• 작성일     : 2020-11-28

• 설   명      : 

• 수정이력 :

 

 내용

[개요]

• 끝말잇기는 단어의 끝말을 계속해서 이어 나가는 게임을 의미하며, 더이상 단어를 이을 수 없는 쪽이 패배하게 되는 게임입니다.

• 끄투코리아는 상기 언급한 끝말잇기를 온라인으로 즐길 수 있는 사이트이며, 해당 사이트에서 많은 유저들과 끝말잇기 게임을 할 수 있습니다. (하단의 링크)

끄투코리아

• 강화학습은 기계학습의 한 영역이며, 특정한 환경 내에서 정의된 에이전트가 현재의 상태를 인식하여, 선택 가능한 행동들 중 보상을 극대화 하는 선택을 하도록 학습하는 것으로 정의내릴 수 있습니다. 

• 이번 내용에서 다루는 부분은 크게 두 가지 측면에서 설명을 할 예정입니다. 첫번째는 끄투코리아 사이스에서 끝말잇기를 스스로 수행하는 봇을 만드는 방법을 설명하고 있으며, 이는 단순히 프로그래밍적 기술에 대해 설명하는 부분입니다.

  • 해당 기능은 R 프로그램을 통하여 구현되었습니다.

• 두 번째는 해당 프로그램을 통해 유저들과 스스로 게임을 수행함에 잇어서, 어떻게 하면 게임에서 승리할 가능성이 가장 높은지 스스로 학습하는 알고리즘과 이를 만들어 나가는 과정에 대해서 설명하는 부분입니다.

 

[특징]

• 끝말잇기 강화학습을 위하여 적용된 가설 및 방법 

• 상기 언급된 끄투코리아 사이트를 통한 실제 구현 및 테스트

 

[기능]

• 본문에 후술함

 

[활용 자료]

• 없음

 

[자료 처리 방안 및 활용 분석 기법]

• 없음

 

[사용법]

• 예시 참조

 

[사용 OS]

• Windows 10

 

[사용 언어]

• R v4.0.3

 

 이론적 설명

[전제조건]

• 올바른 실험을 위하여, 게임을 한방에 끝낼 수 있는 한방단어는 사용하지 못하도록 조치 하였습니다. 또한 1대1의 경우를 가정 하였습니다.

• 예를 들어 '수산화나트륨' 과 같은 단어의 경우 학습과 관계없이 게임을 한번에 끝내버릴 수 있는 단어로 취급하여, 규정상 사용할 수 없도록 제외 하였습니다. 이는 의도하고자 하는 올바른 학습 방향이 아니기 때문입니다.

 

• 즉 학습이란 앞서 언급한 한방단어를 서로간에 사용할 수 없는 경우에 한하여, 게임에서 승리할 확률이 높은 가능성을 찾아가는 방식으로 학습이 수행된다고 할 수 있습니다.

• 즉 이미 사용한 단어는 해당 게임에서는 다시 사용할 수 없으며 이것이 이 게임의 핵심 룰입니다. 이를 이용하여 승리할 방법을 도모하는 것은 가능합니다.

• 즉 아래와 같은 경우는 가능합니다.

 

• 따라서 게임의 룰을 요약하자면 아래와 같습니다.

  • 1. 오로지 1대1 경우를 가정 하였다. 이는 3명 이상의 플레이어가 게임에 참가하는 경우 학습이 어려워지고 우연적 요소가 개입할 수 있기 때문이다.

  • 2. 한방 단어는 사용할 수 없다. 왜냐하면 이렇게 하는 경우 게임이 매우 단조로워지기 때문이다.

  • 3. 이미 사용한 단어는 다시 사용할 수 없다. 따라서 상대로 하여금 더이상 쓸 단어가 없게 만들어 게임에서 승리하는 방법을 도모하는 것은 가능하다.

 

[게임에 사용되는 단어의 2 가지 분류]

• 끝말잇기를 수행함에 있어서 사용할 수 있는 단어는 정말 많습니다.

• 그러나 이러한 단어들의 종류는 끝말잇기적 관점에서 살펴보았을 때 크게 2가지 분류로 나눌 수 있다는 사실에 착안합니다. 즉 게임에서 사용 가능한 모든 단어는 아래와 같이 2가지 그룹 내에 속해있다고 볼 수 있습니다.

  • 1. 시작과 끝이 같은 단어 (ex : 스위스, 석류석, 이하이)

  • 2. 시작과 끝이 다른 단어 (ex : 사이다, 가오리, 영화관)

• 이는 후술되는 단어를 더욱 세부적으로 분류 하는 것의 토대가 되며, 다음 섹션에서 자세히 후술 하도록 하겠습니다. 이 부분을 잘 기억해 두셨으면 합니다.

 

[어떤 단어가 승리할 확률이 높은가? - 단어의 가중치]

• 가중치란 실제 게임에서 사용하였을 때 긍정적인 효과 (여기서는 게임에서의 승리) 를 가져오는 단어인지 부정적인 효과 (여기서는 게임에서의 패배) 를 가져오는 단어인지 확인하고 이를 점수화 시켜 각 단어들에 부여하는 것을 의미하고 있습니다. 즉 가중치란 단어들이 가지고 있는 점수라고 요약될 수 있겠으며, 학습이 진행되지 않은 경우 이 가중치는 무작위이거나, 혹은 모두 같은 값을 가지고 있을 것입니다. (혹은 단어 자체를 아예 학습하지 않았거나)

• 초기에는 학습된 단어, 즉 사용할 수 있는 단어가 존재하지 않기 때문에 거의 무조건 게임에서 패배할 것입니다. 또한 각 단어들의 가중치 역시 초기값을 가지고 있을 것이므로 (여기서는 0) 자기 차례가 왔을 때 거의 무작위로 단어를 추출하여 선택할 것입니다. 

• 따라서 매 게임이 종료될 때마다 단어들의 가중치는 끝임없이 변화해야 할 필요가 있습니다. 왜냐하면 이렇게 변화하는 가중치를 바탕으로 어떤 단어가 승리하기 위해 사용되어야 하고 사용되지 말아야 할지 점차 학습 할 것이기 때문입니다. 그리고 일반적으로 이러한 가중치는 올바른 방법으로 주기만 한다면 게임이 무수히 반복될수록 더욱 정확해질 것입니다.

 

[가중치를 부여하는 방법]

• 그렇다면 각 단어들에 어떤 방식으로 가중치를 부여해야 하는가? 에 대한 문제가 새롭게 떠오르게 될 것입니다. 이 부분에 대해서는 다소 시행착오가 있었지만 최종적으로 아래와 같이 가중치를 부여하기로 결정 하였습니다.

  • 1. 실제로 게임을 진행합니다. 이것이 실제 유저들과의 게임이든 스스로의 자가 시뮬레이션인든 상관이 없습니다. 중요한 것은 자의적이든 타의적이든 한 게임을 어떻게든 완료 해야 합니다.

  • 2. 게임에 사용된 단어를 대상으로 가중치를 부여합니다. 

  • 3. 현재까지 학습한 모든 단어를 대상으로 가중치 계산을 확장 합니다. 이는 사용할 수 있는 모든 단어가 공통적인 특징을 보유하고 있기 때문에 가능하며, 학습 속도를 비약적으로 빠르게 하기 위한 방법 입니다.

  • 4. 위의 과정을 반복 합니다.

 

• 이것이 무슨 뜻인지 지금은 전혀 모르셔도 상관 없습니다. 이제부터 각 과정에 대해서 상세히 설명 하도록 하겠습니다.

• 1. 실제 게임을 진행하기 : 실제로 게임을 진행 하는 것은 매우 간단합니다. 그저 게임을 시키기만 하면 됩니다. 즉 스스로 프로그램끼리의 대결이든 사람과 프로그램의 대결이든 규칙에 따라 게임을 진행 시키기만 하면 됩니다. 이제 A 플레이어와 B 플레이어가 실제 게임을 수행하였으며, 최종적으로 아래와 같은 게임 결과를 얻었다고 가정 해 봅시다.

 

• 최종적인 승리자는 A 플레이어이며, 게임 플레이 도중 양측 플레이어가 사용한 모든 단어는 5개 입니다.

• 즉 이 5개의 단어에 대해 가중치를 부여해야 합니다.

• 여기서 가중치를 부여하기 위한 단순한 가정이 등장합니다.

  • 게임의 승자가 사용한 단어는 (여기서는 A 플레이어) 모두 사용했을 때 좋은 단어 (+ 가중치) 를 부여하며, 게임의 패자가 사용한 단어는 (여기서는 B 플레이어) 모두 사용했을 때 나쁜 단어 (-가중치) 를 부여한다. 즉 승자가 사용한 모든 단어는 좋은 단어이며, 패자가 사용한 모든 단어는 모두 나쁜 단어이다. 결과적으로 A 플레이어가 사용한 모든 단어인 ['그릇', '치킨', '디그릇'] 은 양(+) 의 가중치가 부여되며 B 플레이어가 사용한 모든 단어인 ['늣치', '킨디']는 음(-)의 가중치가 부여된다.

• 위의 이 가정은 단순히 생각 했을 때 조금 이상해 보입니다. 왜냐하면, 비록 게임에서 승리했다 하더라도 중간에 승리하기에 부적절한 단어를 사용하였을 수도 있으며, 그저 상대방이 올바르게 대응하지 못하였기 때문에 승리했을수도 있고, 그 반대의 상황이 되는 경우도 얼마든지 있을 수 있습니다. 즉 승자라고 해서 모두 좋은 단어를 사용했다거나, 패자라고 해서 모두 나쁜 단어를 사용했다고 하는 것은 상식적으로 생각 해 보았을 때 엉성하기 짝이 없는 전제가 될 수 있습니다.

• 그러나 그럼에도 불구하고 위와같은 가정을 쓰는 이유는 아래와 같습니다.

  • 우선 첫번째로 위와같은 방법을 사용하는 경우 가중치를 부여하기가 쉽다는 것입니다. 프로그램적으로 보았을 때 중간에 부적절한 단어를 어떻게 사용하였는지 정의 내린다는 것은 매우 모호합니다. 따라서 단순화를 위해 이같은 가정을 세워야 할 필요가 있습니다.

  • 두번째로 단 한번의 게임이 아니라 무수히 많은 게임이 같은 방식으로 수행되고 반복될 것이기 때문에, 큰 수의 법칙에 따라 올바르지 못하고 부적절한 시그널들은 무수한 게임 속에 묻혀버려 평균적인 추세를 따라가게 될 것이기 때문입니다. 한마디로 아주 많은 수의 게임을 수행하는 경우 결과적으로 좋은 단어는 큰 가중치를, 나쁜 단어는 작은 가중치를 가지는 방향으로 자연스럽게 수렴할 것으로 기대되기 때문입니다.

  • 세번째로 위의 모호한 경우를 가중치의 크기로서 보정할 수 있기 때문입니다. 즉 일반적으로 게임의 끝에 다가갈수록, 승패에 더욱 크게 영향을 미쳤을 것으로 보여지며, 게임의 시작점에 사용된 단어는 상대적으로 덜 중요한 단어로 가정할 수 있습니다. 결과적으로 보았을 때 이러한 중요도가 가중치의 크기로 정의할 수 있으며, 이 가중치의 크기를 어떤 방식으로 정하는지에 대한 부분은 시행착오 끝에 아래와 같이 사용하는것으로 결론 내렸습니다.

 

 참고 문헌

[논문]

• 없음

[보고서]

• 없음

[URL]

• 없음

 

 문의사항

[기상학/프로그래밍 언어]

• sangho.lee.1990@gmail.com

[해양학/천문학/빅데이터]

• saimang0804@gmail.com