BattleShip Game AI 만들기 (1)

 

 

BattleShip Game AI 만들기

 

 

 

 

 

1. 게임 룰

BattleShip Game이 국내에서는 그리 잘 알려진 게임은 아니니 우선 게임 룰부터 짚고 넘어가자. 

게임은 8x8의 보드에서 이루어지고, 우선 각자 자신의 보드에 각각 크기가 5,4,3,2,2인 다섯 개의 배(종류는 4종류, 각각 Aircraft(크기 5), Battleship(크기 4), Cruiser(크기 3), Destroyer(크기 2))를 가로 혹은 세로로 겹치지 않게 배열한다. 그리고 서로 돌아가며 상대의 배의 위치를 추측한다. 한 번씩 돌아가며 상대의 배가 있을 걸로 예상되는 위치(게임 보드 위의 한 점)를 지목한 뒤, 그 결과를 듣고 다시  그 결과를 바탕으로 추측하여 먼저 상대의 배가 있는 위치를 모두 맞춘 쪽이 승리한다. 한 점을 찍었을 때 추측의 결과는 Miss(배가 없음), Hit(배를 맞춤), Destroy(배를 맞췄고, 배가 침몰됨. 이 때 어떤 종류의 배가 침몰되었는지 가르쳐줘야 함.) 셋 중 하나다.

 원래 게임 규격은 10x10 보드에 각각 5,4,3,3,2의 배 5개를 맞추는 게 정석인 듯 하지만, 여기서는 내가 만들 때 사용한 규격(위에 제시한 룰)을 기준으로 진행하겠다. 

2. 랜덤 알고리즘

우선 랜덤 알고리즘부터 시작해보자. 말 그대로 아직 안 찍은 지점들 중 랜덤하게 한 점을 찍는 방식으로 진행하는 것이다. 효율이 굉장히 떨어질게 뻔하지만 그래도 결과는 확인해보자.

랜덤 알고리즘으로 10만 번 게임을 수행한 결과 그래프다. 평균 61.20394턴이 걸렸고, 최소 45턴 최대 64턴 만에 맞췄다.

3. HUNT - TARGET 알고리즘

유명한 배틀쉽 알고리즘이다. 일단 어느 한 점에 배가 있다는 걸 맞췄으면, 그 배 주변에 배가 있을 확률이 굉장히 높다.(4방향으로 배를 배치하고 배의 길이가 모두 1보다 크니까) 따라서 랜덤하게 찍다가(hunt) 하나를 맞추면 그 주변의 배를 destroy가 될 때까지 찾는(target) 알고리즘이다.

이 알고리즘의 target 상태에서 나는 아래와 같은 로직을 사용했다.

1. 해당 점의 아래 방향부터 반시계 방향으로 점을 체크해 나간다.

2. HIT이 나온 경우 해당 방향으로 계속해서 탐색해나간다.

3. 계속 탐색하다가 MISS가 나오면 찾던 방향의 반대 방향으로 시작점부터 다시 탐색한다(배는 1자로 놓여 있으므로). 이미 반대방향을 모두 체크한 경우 1에 따라 남은 방향을 마저 체크한다.

4. DESTROY가 나온 경우, destroy된 배를 체크하고 보드에 destroy가 아닌 남은 hit 지점이 있으면 그 지점을 기준으로 다시 1부터 알고리즘을 수행한다.(해당 hit 지점을 포함하는 배가 아직 남아있다는 이야기이므로)

5. DESTROY가 나왔고 남은 hit지점이 없으면 target 상태에서 다시 hunt 상태로 돌아간다. (가능한 모든 배를 격추했으므로)

10만번 수행한 결과, 평균 42.60639, 최소 17턴에서 최대 64턴까지 걸렸다. 평균 턴수가 거의 20턴 가까이 비약적으로 감소한 것을 볼 수 있다.

4. CHECKER-BOARD 개념

8x8보드를 체스 판처럼 검은색과흰색이 번갈아 있다고 생각해보자. 

배의 크기는 아무리 작아봤자 길이가 2이상이기 때문에, 여기서 검은 색 칸만(혹은 흰색 칸만) 찾아도 모든 배에 대해 최소 한 칸씩은 맞출 수 있다. 이 때 한 점만 맞추면 그 나머지 부분은 target 알고리즘에 의해 모두 맞출 수 있기 때문에, hunt에서 이 개념을 이용해 찍으면 턴수를 많이 단축시킬 수 있을 것이다.

10만 번 수행한 결과 평균 ​37.55637턴, 최소 16턴에서 최대 50턴까지 나오는 것을 확인할 수 있다. 이 정도면 이제 슬슬 실제로도 쓸만한 AI인 듯 하다.

5. 경우의 수 줄이기

현재 남아 있는 배의 종류와, 배의 miss/hit 상태를 이용해 가능한 경우의 수를 줄일 수 있다. 예를 들어 현재 남은 배의 종류가 Battleship(크기 4) 하나 뿐이라면, 어떤 점에 대해 그 점을 포함하는 가로 세로의 최대 길이가 4보다 작다면 그 칸은 반드시 miss일 수 밖에 없다.

이런 식으로 현 상황에서 절대로 배가 있을 수 없는 점을 계산하여 이런 점들을 모두 후보에서 제외하는 방식을 이용하면 턴수를 조금 줄일 수 있다.

10만번 수행한 결과 평균 36.93162, 최소 16에서 최대 50까지 나오는 것을 확인할 수 있다. 약 0.6턴 정도 정말 미묘하게 감소한 것을 확인할 수 있다.

두 그래프의 비교. 약간 낫다는게 확연히 보인다.

6. HUNT - TARGET 개선

hunt-target에서 무조건 반시계 방향으로 체크하도록 했는데, 이것보다는 방향 선택시에 있을 확률이 높은 쪽으로 하는 것이 좋을 것이다. 각 방향으로 배를 놓을 수 있는 칸이 가장 많은 쪽이 확률이 높으므로(배를 배치할 수 있는 경우의 수가 가장 많이 존재하기 때문), 각 방향으로 아직 찍지 않은 칸이 일렬로 가장 길게 있는 방향을 우선으로 체크하도록 바꿔보자.

10만번 수행 결과 평균 36.55334, 최소 19회에서 최대 48회까지 나온다. 역시 0.5턴 정도 굉장히 미묘한 수준의 이득이 있다는 것을 알 수 있다.

4,5,6 세 개의 비교. 그래프가 점점 앞쪽으로 이동하고 있는게 보인다. 

7. HUNT 개선

단순히 체커보드에 랜덤하게 찍는 건 너무 비효율적인 것 같고, 그렇다고 인터넷 검색하면 심심찮게 나오는 확률을 이용한 hunt 방식은 구현하기 복잡해서 일단 간단한 방식으로 한 번 개선해보았다. 기본적인 방식은 checkerboard 방식과 동일하나, 실행전에 미리 각 점들에 대해 우선순위를 4단계로 부여하고 우선순위가 높은 점을 먼저 검색하도록 했다.

 

 

이 우선순위 책정의 기본 아이디어는, 위 그림에서 먼저 빨간 점을 모두 검사하고, 그 점들이 만드는 내부 십자 모양의 한 가운데를 나중에 검사하는 것이다. 2개짜리 크기의 배가 있을 수 있는 장소의 경우의 수를 최소화한다는 전략이다.

 

여기서 각 모서리에 배가 있을 확률이 안 쪽보다 낮으므로, 안쪽 빨간색 -> 바깥쪽 빨간색 -> 안쪽 하늘색 -> 바깥쪽 하늘색 순서대로 검색하도록 우선순위를 부여했다. 정확히는 아래 그림과 같이 우선순위를 부여했다.

 

 

빨강 - 노랑 - 하늘 - 회색 순서대로 검사한다. 결과는 아래와 같다.

 

 

10만번 수행하여 평균 35.67962턴, 최소 16에서 최대 49턴만에 수행되었다. 평균 턴수는 약 1턴 정도 줄었지만 그래프 모양이 훨씬 깔끔해져서 분포가 전체적으로 균등하게 나온다.

비교샷. 확실히 낫다. 전체적으로 앞으로 오면서 그래프 모양도 좋아졌다.

 

8. HUNT 개선 2​

 

위의 우선 순위를 이용하는 알고리즘에서 약간의 개선을 더해보았다. 여기서 이용한 개념은, 어떤 점을 찍을 때 주변 4칸이 모두 빈(무슨 상태인지 모르는) 점이 그렇지 않은 점에 비해 hit할 확률이 높다는 것이다. 주변이 비어 있는 쪽이 당연히 배가 배치될 수 있는 경우의 수가 많으므로 확률이 높을 수 밖에 없다. 

그래서 위의 우선 순위에 추가로 이 요소를 더하여, 주변 4칸이 비어있는 점들을 우선적으로 검사한 후 그런 점이 아예 없다면 그렇지 않은 점들을 조사하도록 만들었다. 이렇게 개선하면 평균 턴 수를 조금 줄일 수 있다.

10만 번 수행 결과 평균 34.92317턴이 나왔다. 최소 턴수는 17, 최대 턴수는 49. 개선한 게 개선하기 전보다도 더 매끄러운 그래프를 보인다.

비교샷. 전체적으로 확실히 낫다.

9. 이후 개선 방향

이제 기본적인 알고리즘은 거의 다 적용시켜보았으니, 다음에는 1. 확률 반영(수학적으로 확실하게), 2. 경험 반영(같은 상대와 여러 번 대전할 시 그 상대의 패턴을 파악하는 능력 반영)을 추가해 볼 생각.

그리고 맞추는 알고리즘을 확실히 짜면 이제 배를 배치하는 알고리즘도 비슷한 방식으로 짜 볼 생각이다.

* 추가로 이 알고리즘(8번)을 이용해 랜덤하게 배치된 배를 격추하는 프로그램을 첨부해놓았다. Enter키를 누를 때마다 내부 알고리즘에 따라 다음 점을 추측해나가며, 다 맞췄을 경우 자동으로 다음 판을 진행한다. 이 프로그램을 몇 판 돌려보면 알고리즘의 동작을 정확히 이해할 수 있을 것 같다.

BattleShip.exe