[4목 게임 인공지능 제작] 1. 기본적인 그리디 알고리즘 구현

게임이란?

에이전트를 구현하기 전에 먼저 게임을 어떻게 정의하고 구성하는지 알아둘 필요가 있다. 먼저 게임이 존재하기 위해서는 게임을 수행하기 위한 환경과 게임을 수행하는 주체가 있어야 한다. 마리오 게임으로 비교하자면, 마리오 게임 프로그램이 환경, 게임을 하는 사람이 주체에 해당한다.

주체는 본인의 행동을 환경에 전달한다. 행동은 마리오 게임이서 이동, 달리기 및 점프에 해당한다. 그러면 환경은 주체에게 행동 후의 상태와 행동으로 얻은 보상을 전달한다. 상태는 마리오 게임에서 현재 스테이지와 위치, 맵 모양 등에 해당하고, 점수는 행동으로 얻은 점수에 해당한다. 이때, 보상은 게임 시작부터 지금까지 얻은 총점수가 아니라 이 행동 하나만으로 얻은 점수로 정의한다.

게임의 기본 구성

또한 게임에서 가장 중요한 건 내 행동은 현재 상태에만 영향을 받는다는 점이다. 현재 마리오 게임에서 2-1 스테이지에 있을 때, 1-4를 깨고 2-1로 왔든 아니면 1-2에서 워프하여 바로 2-1 스테이지로 왔든 현재 내 행동에는 영향을 주지 않는다는 것이다. 이를 마르코프 성질이라고 한다.

4목 게임의 구성

4목 게임은 2인용 게임이기 때문에 두 개의 주체가 필요하다. 따라서 두 개의 주체를 플레이어와 적으로 구분한 뒤, 적을 환경에 포함시켰다. 즉, 내가 환경에 행동을 취하면 환경은 내 행동을 실행하고, 환경이 가지고 있는 적의 행동을 실행한 뒤의 상태를 반환한다. 이렇게 해서 위처럼 하나의 환경과 하나의 주체가 있는 것처럼 게임을 구성하였다.

그리디 알고리즘 구현

이후에 AI를 구현하고, AI를 평가하기 위해서는 평가를 위한 표본이 필요하다. 따라서 표본으로 사용할 그리디 에이전트를 구현할 것이다.

그리디 알고리즘은 현재 상태만 보고 가장 좋은 다음 상태를 선택하는 알고리즘이다. 지금 당장의 상태만 보고 선택하더라도 가장 쉽게 생각해본다면, 현재 상태에서 만약 4목을 만들 수 있다면 바로 4목을 만들고 그렇지 않다면 랜덤하게 행동을 하는 알고리즘을 구상해볼 수 있다. 하지만 이 알고리즘은 너무 단순해서 쉽게 뚫리게 된다. 따라서 현재 상태에 대한 가치를 정의해보자. 현재 상태에서 이길 확률이 높으면 가치가 큰 것이고 이길 확률이 낮으면 가치가 작은 것이다.

이 가치함수를 아주 잘 정의했다고 가정하자. 그렇다면 가능한 행동 중에서 상태의 가치가 최대가 되도록 하는 행동을 하면 된다. 따라서 가치 함수를 잘 정의할수록 그리디 알고리즘이 보다 효과적이다. 본인은 아래와 같이 가치 함수를 정의하였다.

 

7종류의 행동 후의 가치로 평가하면 좋은 성능이 나오지 않았다. 상대방의 행동을 고려하지 않아 상대의 4목을 바로 허용하는 행동을 취하기도 하였다. 따라서 나의 7종류의 행동과 상대방의 7종류의 행동을 고려한 총 49개의 상태를 고려하였다.

내 기준으로는 가치가 최대가 되도록 하는 상태를 선택해야 한다. 그렇다면 상대방 기준에서는 가치가 최소가 되도록하는 상태를 선택할 것이라 추측할 수 있다. 따라서 내 행동 후의 가치는 해당 상태에서 상대가 행동한 후의 상태의 가치 중 가장 작은 가치로 정의할 수 있다.

이렇게 설계를 해도 4목을 완성할 때만을 기준으로 가치를 결정하면 좋은 결과가 나오지 못한다. 따라서 가치를 잘 계산해 줄 필요가 있다.

4목을 완성하기 위해서는 4개의 말이 필요하다. 이 중 3개의 말만 놓아도 상대방은 나머지 한 칸을 무조건 막아야 하므로 큰 압박이 된다. 또한 2개의 말만 놓아도, 4목의 가능성이 있다면 잠재적으로 3목을 만들 수 있으므로 조금의 압박은 있을 것이다.

따라서 모든 가능한 4목의 경우의 수 중, 4개의 말이 놓여있는 경우, 3개의 말이 놓여있는 경우, 2개의 말이 놓여있는 경우가 몇 가지인지 구한 뒤 이를 이용해 가치를 결정하였다. 4개의 말이 있다면 이미 이긴 것이므로 무한 가치를 추가하고, 3개의 말이 있다면 5의 가치, 1개의 말이 있다면 1의 가치를 추가하였다. 가치의 값은 config.py에 정의해 두었다. 이렇게 상대의 가치와 나의 가치를 계산한 뒤, 나의 가치에서 상대의 가치를 뺀 값을 상태의 가치로 정의하였다.

그리디 알고리즘을 위처럼 구현한 결과 랜덤 AI는 항상 이기고 직접 게임해도 이기기 힘든 수준의 AI를 완성할 수 있었다.

 

코드 링크