BattleShip Game AI 만들기 (2)

BattleShip Game AI 만들기

 

 

 

 

 

10. 몬테 카를로 알고리즘

이전 편에서 마지막에 언급했던 것처럼 우선 수학적으로 확실히 확률을 구해 배의 위치를 찾는 알고리즘을 만들어보았다. 처음에는 현재 배 상황에서 만들 수 있는 모든 종류의 게임판을 다 만들어 그 결과를 종합하여 확률을 계산하려 했으나, 만들어질 수 있는 게임판의 종류라는게 정말 말도 안 될 정도로 많아서(만들어서 돌려보니 한 게임 끝내는데 삼십분은 넘게 걸릴 듯 했다. 너무 길어서 중간에 껐지만.) 포기하고 몬테 카를로 방법을 이용해서 근사치를 구하기로 했다. 좀 자세히 설명하자면 현재 내가 알아놓은 보드 상황에 맞게 남아있는 적 배를 100번정도 배치해보고 이 배치해본 결과 값을 이용해 가장 확률이 높은 쪽을 찍는 것이다. 그럴싸하게 말하자면 큰 수의 법칙을 이용한 수학적 확률 계산이라고 할 수 있을 것 같다.

10만번 수행 결과 평균 34.722턴, 최소 20턴에서 최대 47턴까지 나왔다. 평균은 0.2턴 정도 줄었지만 왜인지는 몰라도 그래프가 굉장히 들쑥날쑥하다(100번 밖에 배치를 안해봐서 나타나는 오차때문인 것같기도 하다). 

 

이전 방식과의 비교. 너무 들쭉날쭉해서 좀거슬리긴 하지만 전체적으로 효율이 좀 더 낫다. 확장성이나 응용적인 측면에서도 이 방식이 나으니 앞으로는 이 방식을 쓰기로 한다.

 

 

11. 경험 반영 알고리즘​

 

 

이제 몬테카를로에 더해 이전에 붙어본 게임 정보를 활용하는 방법까지 더해보자. 이 게임 정보를 이용해 상대의 패턴을 분석하는 방법은 굉장히 여러가지가 있고 유전 알고리즘이라든지 꽤 복잡하지만 고효율을 보여주는 알고리즘들도 많지만 그런건 솔직히 구현하기 너무 어려워서, 구현하기 편하면서도 효과를 어느정도 볼 수 있는 선에서 타협을 봤다.

 

내가 사용한 방법은 현재 게임 보드 상황에서 이 게임 보드와 유사한 패턴을 보인 적이 있는 이전 게임 기록 데이터를 활용하는 것이다(수행 시간 때문에 최근 1000판의 기록만을 사용한다).

 

​

예를 들어 현재 위와 같은 6판의 게임 데이터를 갖고 있다고 해 보자(설명의 편의를 위해 4x4 판에 2,3 길이의 배를 하나씩 배치하는 것으로 가정했다). 이 데이터는 상대가 이전 판에 배를 배치했던 위치를 모두 기억하고 있다.

이 때 내가 가진 현재 보드 상태가 위와 같다(초록색은 hit, 빨간색은 miss). 이 때 이런 보드 상태가 나타날 수 있는 보드만 내가 가진 데이터 중에서 간추려낸다.

이제 이 두 개의 데이터에서 ship이 배치된 숫자가 많은 칸을 선택하도록 만드는 것이다. 위 데이터 2개가 남은 경우를 숫자로 나타내면

0 1 1 2

0 2 0 1

0 2 0 1

0 0 0 0

이 된다. 이 때 이 중에서 이미 hit한 지점을 제외하고 가장 값이 높은 점을 선택해야하니 다음 공격지점은 3행 2열의 점이 될 것이다.

이제 이 원리와 몬테카를로 기법을 같이 고려하되 데이터 수가 적을 때는 몬테카를로 기법을 위주로, 데이터 수가 많을 때는 데이터를 위주로 고려하도록 만들기 위해 각 칸에 value값을 주고 그 value가 가장 높은 쪽을 선택하도록 했다. value의 계산식은 다음과 같다.

value = (몬테카를로 기법에서 해당 칸의 경우의 수) X (경험반영 데이터에서 해당 칸의 경우의 수 + 1)

경험반영 데이터에 1을 더해준 것은 현재 보드와 일치하는 데이터가 하나도 없을 때(혹은 처음 시작시) value 값이 모두 0이 되어버리므로 이런 경우 몬테카를로 기법을 따라 수행되도록 만들어주기 위한 것이다.

10만 번 수행하여 평균 34.62789턴, 최소 17턴에서 최대 50턴이 나왔다. 단순 몬테 카를로만 쓴 것에 비해 0.1턴 정도로 아주 조금 개선되었으며 그보다도 턴수가 좀 더 안정적이게 나오게 되었다. 이기는 게 목적이라는 걸 생각해보면 턴수도 중요하지만 그 분포도 상당히 중요하다. 그래프가 너무 들쭉날쭉하게 나오면 평균이 낮아도 좋은 승률을 기대하기 어려울 수 있기 때문이다.

 

단순 몬테카를로와의 비교.

 

 

12. 배치 방법에 따른 비교

현재까지의 비교는 배치가 모두 랜덤이라는 상황 하에서 이루어진 것이었다. 그러나 배치도 다양한 전략이 존재할 수 있으며, 이런 다양한 배치들 하에서 어떤 결과가 나오는 지도 알고리즘의 평가에 상당히 중요한 요소이다.

​12 - 1. 코너 배치​

보드의 네 구석에 배를 하나씩 배치하고 나머지 한 개의 배는 랜덤하게 배치하는 방식이다. 일반적으로 확률이 높은 가운데부터 검사하는 알고리즘들에 대해 거의 카운터 격인 배치 방식이다.

몬테카를로 방식으로 했을 때의 결과이다. 평균 39.56178턴에, 최소 28턴에서 최대  48턴까지 나왔다. 전체적으로 40 이상의 턴이 걸리는 경우의 수가 굉장히 많다. 기존 방식으로는 꽤나 비효율적이 된다는 이야기다.

경험을 반영했을 때의 결과이다. 평균 31.30919, 최소 16턴에 최대 50턴이 나왔다. 랜덤 배치일 때보다도 더 낮은 턴수가 나온다. 어떻게 보면 당연한게 이건 일종의 패턴이 있으니(그것도 꽤나 뚜렷한) 빠르게 맞출 수 밖에 없는 것이다. 패턴이 불분명할 수록 랜덤인 경우의 턴수(34.6턴 가량)에 가까워질 것이라고 생각한다.

두 경우의 비교. 정말 확연한 차이를 보인다.

​12 - 2. 한쪽 코너 집중 배치

​​이 배치 방식은 네 모서리중 왼쪽 아래 모서리에 집중적으로 배치하는 것이다. 왼쪽 아래 5x5 크기를 시작점으로 하여 랜덤하게 위쪽 혹은 오른쪽으로 배치하도록 구현했다. 딱히 왼쪽 아래에 의미가 있는 것은 아니고 위의 배치의 경우도 마찬가지지만 인터넷을 찾아보고 나온 대표적인 배치 한 두가지를 그대로 따와 실험해본 것이다.

 

우선 몬테카를로 기법만 사용한 경우이다. 평균 35.61752, 최소 18턴에서 최대 48턴까지 나왔다. 정말 왠지 이유는 모르겠는데 그래프의 괴랄함이 상상을 초월한다. 평균은 35턴대지만 42~44쪽에 많은 값이 몰려있어 평균 언저리의 결과를 기대하기 힘들어보이는 구성이다(10판하면 5판 정도는 38턴 이상이 나온다).

 

 

경험을 반영한 경우다. 평균 29.8726, 최소 16턴에서 최대 49턴으로 굉장한 효율을 보이는데, 도대체 그래프가 왜 이런 모양인지 이해를 못하겠다. 한쪽에 뭉쳐있다보니 서로 맞닿아 있을 때 target상태에서 연달아 잡히는 경우 20초반대, 그렇지 않고 배치가 좀 떨어져있는 경우 40대까지 가는게 아닌가 추측하긴 하지만 맞는지는 모르겠다. 여튼 굉장히 신기한 형태를 나타낸다.

비교샷. 진짜 특이하다. 몬테 카를로 방법에서 시간이 오래 걸리는(40초반대) 애들을 경험을 반영하는 방법이 좀 더 앞쪽으로 끌어오는건가싶기도 하다.

13. 앞으로의 방향

이제 수학적 확률 계산 모델과 데이터 축적/반영 모델을 모두 넣었으니 다음은 배를 배치하는 방법의 개선인 듯하다. 마찬가지 방식으로 상대가 찍었던 적이 있는 위치를 최대한 피해가는 방향으로 배를 배치하도록 만들 생각이다. 배를 그렇게 배치한다해도 결국 맞추는 쪽에서는 쌓은 데이터가 쓸모없어진다뿐이지 몬테카를로 모델 자체의 평균적인 소요 턴수는 별 영향을 안 받을 것 같아 내 생각에는 서로 33~36턴 정도 언저리를 왔다갔다하며 거기서 전체적인 평균이 형성될 것 같다. 물론 실제로 해보면 위의 그래프처럼 예상치 못한 해괴망측한 결과가 나올 수도 있다.  어쨌건 일단 만들어봐야지.