INDIES

도전! 초난문이라는 스마트폰 게임이 있다. 하루에 한 문제씩 어려운 문제가 주어지고 이 문제를 풀면 되는 굉장히 심플한 게임이다. 문제의 룰도 간단하다. 위의 그림과 같은 8x8의 보드에서, 상하좌우 4방향으로 흰색 블록을 옮기는 과정을 반복하여 모든 흰색 블록이 검은 테두리의 회색 블록에 들어가게 하면 된다. 말로 설명하는 것보다 한 번 플레이해보는게 이해하기 쉬우니 궁금하신 분들은 다운로드 추천. 다운 받기 귀찮으시다면 아래 동영상을 한 번 해보시면 바로 어떤 룰의 게임인지 이해할 수 있을 것이다. 이 걸 몇 번 플레이하다가, 갑자기 최단거리를 찾아내는 프로그램을 만들고 싶어져서 한 번 그 프로그램을 만들어 보았다. 1. 접근 방법 처음의 접근 방법은 심플했다. '목표에 도달할 때까지 각 step별 ..

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

BattleShip Game AI 만들기 1. 게임 룰 BattleShip Game이 국내에서는 그리 잘 알려진 게임은 아니니 우선 게임 룰부터 짚고 넘어가자. 게임은 8x8의 보드에서 이루어지고, 우선 각자 자신의 보드에 각각 크기가 5,4,3,2,2인 다섯 개의 배(종류는 4종류, 각각 Aircraft(크기 5), Battleship(크기 4), Cruiser(크기 3), Destroyer(크기 2))를 가로 혹은 세로로 겹치지 않게 배열한다. 그리고 서로 돌아가며 상대의 배의 위치를 추측한다. 한 번씩 돌아가며 상대의 배가 있을 걸로 예상되는 위치(게임 보드 위의 한 점)를 지목한 뒤, 그 결과를 듣고 다시 그 결과를 바탕으로 추측하여 먼저 상대의 배가 있는 위치를 모두 맞춘 쪽이 승리한다. 한 점..