Code Sprint 2015 Round 1 – 다른 로봇들을 활용하고 연료 잘 쓰기로 우승!

참가자 소개

저는 이번 SK planet Code Sprint Round1 – 로보코드 챌린지게임에서 2위를 한 박상권이라고 합니다.

저는 셀폰이라는 중고폰 거래 플랫폼 어플리케이션을 제공하는 선의의경쟁 이라는 스타트업의 창업자이자 개발자입니다.현재 서울대학교 연구공원단지에 위치한 SK플래닛의 상생혁신센터에 입주해 있습니다.

저희 회사 직원들 뿐만 아니라 옆 스타트업 지인들까지도 같이 이 대회에 참여해서 자체적으로 서로의 코드로 대결을 펼치기도 했었습니다.

이 대회를 참여하면서 제가 이 게임에 대해 접근한 방식에 대해 공유하도록 하겠습니다.

로보코드란?

(출처: http://robocode.sourceforge.net/)

로보코드는 IBM에서 만든 로봇 대전 프로그래밍게임입니다.1:1 혹은 N:N의 전투방식으로 상대방의 탄알은 피하면서 상대방의 에너지를 0으로 만들면 이기는 게임입니다.

레이더를 통해 들어온 상대방의 위치(좌표값)를 기준으로 가속도,cos,sin등의 수학적인 공식을 이용해 예상되는 위치로 탄알을 발사 할 수도 있고 또한 반대로 상대방의 예측되는 탄알을 피해 생존율을 높여야 합니다.

더 많은 정보는 아래 사이트에서 확인 가능합니다.

로보코드 전략 소개

1. 상대방은 무적이다. 무조건 피해서 오래 살아남자

(출처: http://www.hooverlibrary.org/sites/default/files/styles/blog_image/public/the-maze-runner-1-sheet-banner.jpg)

로보코드에서 에너지가 감소하는 경우는 아래와 같습니다.

  1. 탄알을 발포할 때
  2. 탄알을 맞았을 때
  3. 로봇끼리 부딪혔을 때
  4. 벽에 충돌했을때
  5. 경기 전체에서 에너지 감소가 10 이하일때

또한 내가 쏜 탄알에 상대방이 맞았을경우 내 로봇은 해당 탄알 파워의 3배만큼을 에너지로 돌려 받습니다.

즉, 내가 쏜 탄알 3발중에 1발이상이라도 명중하는 경우 내 에너지는 현재 에너지 이상을 유지 할수 있다는 뜻입니다.

여기서 1번의 경우에 주목할 필요가 있습니다.이번 경기에서 상대방은 마스터 로봇입니다.

내가 탄알을 발포하면 에너지가 감소하지만, 마스터로봇이 탄알을 발포하면 에너지가 감소하지 않았습니다.

마스터로봇은 프로그래밍이 아주 잘 되어있는 로봇입니다.(많은 알고리즘이 들어갈수록 파일의 용량은 커지는데 마스터 로봇의 용량크기는 67KB였고, 이번 대회에 제출할 수 있는 제 로봇의 용량제한은 15KB였습니다)

그래서 저는 기본적인 전략을 [무조건 도망다니자]로 결정했습니다.그 이유는 다음과 같습니다.

  1. 탄알을 발포할수록 내 에너지가 감소하기 때문에(마스터 로봇은 감소하지 않음)
  2. 마스터 로봇을 3발중 1발이상을 명중시킬 확률은 낮기 때문에

이번 대회에서 채점 방식은 아래와 같습니다.

total score = (Survival score) + (Bullet damage score) + (Ramming damage score)
Survival score = (Number of turns in a round) * 0.1
Bullet damage score = Bullet damage you give
Ramming damage score = Ramming Hit Count * 1.2

1의 데미지를 주었을경우 = 10턴 살아남았을경우가 같은 점수를 얻기때문에 탄알을 쏘지않고 살아남아서 점수를 얻는 방법을 택했습니다.

2. 다른 로봇들을 활용하자

(출처: http://gamedownloade.com/wp-content/uploads/2013/12/Robocode-Download.jpg)

기본적으로 움직임의 전략에 대해 수많은 이론과 알고리즘에 대해서 분석하고 테스트해 보았습니다.(이동전략)

또한 로보코드는 이미 많은 대회를 거쳐 왔습니다.그렇기때문에 수많은 로봇 종류가 있고 각 용량제한별 대회도 존재하고 있습니다.

  • Roborumble: 무제한급
  • Minirumble: 15KB이하
  • Microrumble: 7.5KB이하
  • Nanorumble: 2.5KB이하

용량이 커지면 커질수록 많은 알고리즘과 기능들이 들어가기 마련입니다.반대로 용량의 제한이 있다면 최대한 효율적인 알고리즘을 사용해야 합니다.

이번 Code Sprint대회에서는 15KB 제한이 있었기 때문에 Minirumble(15KB 이하)의 로봇들을 활용하기로 하였습니다.수많은 로봇들의 소스코드를 살펴보고 실제 적용해본결과 그중 Raiko라는 로봇의 알고리즘을 많이 활용하였습니다.

이 로봇의 강점은 랜덤움직임이라는 것입니다.

성능이 좋은 로봇들은 상대 로봇의 이동 움직임 패턴을 분석하고 이를 토대로 탄알을 발사합니다. 그런데 로봇이 랜덤으로 움직인다면 상대방은 제 로봇의 움직임을 예측하기 어려워집니다.

또한 탄알을 맞을 경우 움직임방식을 다시 보정해서 움직입니다.(Musashi Trick)

사실 Raiko 로봇은 상대방의 움직임을 감지하고 타겟팅하는 알고리즘도 훌륭하지만 1번의 전략에서 밝힌대로 도망다니고 탄알을 발사하지 않는 로봇을 만들기로 하였기에 이부분은 활용하지 않았습니다.

3. 연료가 관건이다

사실 다른 대회와 이번 대회의 가장 큰 차이점은 [연료]라는 개념이 존재 한다는 것입니다.

움직일때마다 연료가 소진되고 200턴마다 연료가 다시 생기기 때문에 연료관리를 잘 해야 합니다.(당연히 마스터로봇은 연료가 무제한이지만…)

만약 이번 대회의 문제를 제대로 살펴보지 않고 다른 로보코드 대회의 우수한 로봇들의 소스코드를 그대로 가져와서 사용하였다면 좋은 점수를 받지 못했을 것입니다.(다른 로봇 코드들은 연료라는 개념이 없기때문에 금방 연료부족으로 이동이 멈추기 때문에)

수많은 테스트를 해본 결과 제 로봇은 평상시에는 마스터로봇의 탄알을 효율적으로 잘 피하지만, 연료를 찾고 연료를 향해 가는 도중에 마스터로봇으로부터 많은 피해를 받았습니다.

그래서 최대한 연료를 먹으러 가지 않으면서 정말 연료가 필요한 상황일때 연료를 향해 가도록 설계하였습니다.

제가 구현한 연료관리 알고리즘은 아래와 같습니다.(아래 상세 에너지나 연료값들은 더 많은 시뮬레이션을 통해 최적값을 보정하면 좋습니다)

  • 200턴마다 레이더를 계속 돌려서 연료를 찾는다.
  • 연료가 경기장 크기의 1/2 이상 떨어져있다면 연료를 향해 가지 않는다.
  • 상대 로봇과 연료가 가까이 있을 경우(200이하) 연료를 향해 가지 않는다.
  • 연료가 80 이상이고 에너지가 40 이하일경우 연료를 향해 가지 않는다.(아직 충분히 움직일수 있으므로 살아남는게 중요)
  • 에너지가 20 이하일경우 연료를 향해 가지 않는다.(연료를 먹으러가다가 에너지가 0으로 떨어질수 있기때문)
  • 그 외의 경우는 연료를 향해 간다

4. 테스트 그리고 테스트

로봇의 알고리즘을 적용하고 그안에 들어가는 발동 기준값들을 보정해가면서 한번의 테스트당 최소 10만번의 테스트를 수행 하였습니다.

New Battle -> Rules탭 -> Number of Rounds 를 10,000번정도로 설정하고 10번정도 테스트했습니다.

평균 점수를 측정해서 해당 알고리즘이 이전 알고리즘보다 더 우수한지를 판단하였습니다.

후기

이번 대회는 이전 대회와는 다르게 게임적인 요소가 들어가서 프로그래밍을 하는데 더 재미있게 할 수 있었습니다.

대회를 늦게 참여하게 되면서 준비할 수 있는 시간도 부족하였고 마감 마지막에 처음으로 소스코드를 제출하게 되어 중간순위를 확인하지 못해 약간의 불안감이 있었습니다.(패키지명이 제대로는 되어있는지, 제대로 채점이 가능한지, 내 로봇의 수준이 어느정도 인지)

다행히도 채점이 가능하였고 운이 좋게도 2등까지도 하였습니다.

올해 처음으로 Code Sprint 대회를 알게되었는데 매년 대회를 개최하고 또한 문제를 제출하기 위해 수많은 고민을 하셨을 출제자분들의 노고가 느껴집니다.

이 대회가 매년 진행되고 많은 사람들에게 알려지면서 모든 개발자들이 함께 참여하면서 즐길수 있는 또 하나의 축제의 장이 되었으면 좋겠습니다.

감사합니다.

(이 글은 제 블로그에서 먼저 작성되어 옮겨졌습니다)

[셀폰]이라는 중고폰 거래서비스를 운영중인 선의의경쟁의 창업자 입니다.
스타트업관련, 서버/클라이언트관련 정보들을 서로 공유하는것을 좋아합니다.

공유하기