Code Sprint 2015 Round 1 – RoboCode 출제 후기

대회 소개

안녕하세요. 올해 처음으로 Code Sprint 라운드 1의 출제를 김준섭 매니저님과 함께 맡은 송재혁입니다.  이번 라운드1은 Robocode 문제를 냈습니다.

출제 의도

올해 Code Sprint의 라운드1 문제는 게임을 하듯 즐거움을 줄 수 있는 Robocode였습니다. 빅데이터 학습과 대량의 데이터를 파악하는 알고리즘에서 벗어나, 재미있게 알고리즘을 개발해보자는 의도로 시작하였습니다.

Robocode는 참가자 간 대결 방식의 게임인데, 이를 조금 변형하여 문제를 출제하였습니다. 변형을 하게 된 이유는 다수의 경쟁자들이 대결을 펼칠 경우, 일관된 기준으로 평가를 해야 하는 공정성이 훼손될 것이라 판단하였습니다. 그리고 무엇보다 오랫동안 사용된 문제인 만큼 많은 오픈소스들이 공개되어 있어 부정행위에 대한 우려가 있었기 때문에 문제를 변형하였습니다. 탱크 로봇이라는 게임 디자인에 맞게 자연스러운 변형을 가하려고 한 것이 연료였고, 연료 사용으로 인해 움직임이 많이 제한될 것이라 기대하였습니다.

Robocode

Robocode는 2000년 후반 Matthew A. Nelson이 처음 개발한 JAVA 교육목적의 게임입니다.  2000년도 초반부터 여러 challenge형식의 대회가 있었으며, 현재는 roborumble이란 이름으로 온라인 리그가 항상 열려있습니다.

Robot Algorithm

Robocode에서는 다양한 전략을 사용하여 점수를 많이 얻으면 승리하게 됩니다. 이번 대회에는 1:1 대전이고 오래 살아남는 것이 점수로 계산되었습니다. 그렇기 때문에 로봇을 잘 움직여 상대 로봇의 총알을 피할수록 높은 survival점수를 획득할 수 있었습니다. 여러 참가자들이 다양한 알고리즘을 구현해 주셨는데요, 그 중 잘 알려진 알고리즘 하나를 소개하도록 하겠습니다.

Wave Surfing

 그림 1. 출처: http://robowiki.net/wiki/File:Waves.png

Robocode에서는 상대 로봇의 총구가 어디를 겨냥하는지 현재 총알이 어디에 있는지 정확히 알 수 있는 API를 제공하지 않습니다. 이를 추측하는 다양한 방법이 나왔고, 그 중 하나가 Wave Surfing입니다. 상위권에 입상한 몇몇 로봇들도 이 알고리즘을 사용하였습니다. 전반적인 알고리즘은 다음과 같습니다.

  • 상대로봇이 발포할 때마다 wave를 생성합니다.
  • 발포 시점은 상대로봇의 에너지의 감소 (발포될 때 총알의 파워만큼 에너지감소)로 추측합니다.
  • 원모양의 wave는 발포된 총알이 도달 가능한 지점을 가상으로 simulation 한것입니다.
  • wave는 총알의 속도에 따라 커져갑니다.
  • 자신의 로봇 또는 발포한 총알이 wave에 부딪혔을때 사라진 경우 상대 로봇이 어떻게 총구를 겨냥하는지에 대해 (다음에 피하기 위해) 학습을 수행합니다.
  • 학습된 결과를 바탕으로 총알이 wave중 어느 곳에 있을 확률이 높은지 추론합니다.
  • 각각의 wave마다 가장 안전하다고 생각되는 곳으로 이동합니다.

예제 영상(link)에 어떻게 동작하는지 자세히 나와있습니다.

실제로 구현에서 학습을 어떻게 할 것인지, 어디로 피할 것인지에 따라 결과는 달라질 수 있습니다.

이번 대회에서는 master로봇이 에너지가 줄지 않기 때문에, 총알의 발포타이밍과 세기를 알 수 가 없었습니다. 하지만 평가용 로봇이 변경되지 않았고, 동영상으로 정보를 제공해드렸기 때문에 로봇이 발포하는 시간과 간격 등의 발포 패턴을 가정하고, 해당 알고리즘을 적용할 수 있었습니다.

또한 위와 같은 wave를 타는 것을 포함하면서도, 계속해서 움직이기 위해 연료를 먹으러 가야 하는 등 이동에 대한 구현이 참가자간의 점수차이를 많이 내게 했던 것 같습니다.

대회 통계

총 74명의 참가자가, 216개의 로봇을 제출해 주셨습니다.

개발과정이  local에서 많은 테스트 후 제출하는 문제의 특성상 후반에 참가자가 몰렸습니다.

day1 day2 day3 day4 day5 day6(최종)
참가자 4 13 28 44 62 76

때문에 하루 하루 채점할 때마다 발전하는 로봇들을 보는 재미도 있었고, 중간 순위에서 상위권에 있던 로봇과 새로 상위권으로 올라가는 로봇들간의 점수 경쟁 또한 흥미로웠습니다.

채점 과정

먼저 채점 및 SDK배포에 사용된 소스는 github에 추후 공개해드리겠습니다.

master로봇들로 사용된 로봇은 다음과 같습니다.

  • master.beginner는 sample로봇 중 하나인 Wall
  • master.advanced 로봇은 Diamond 1.0
  • master.evaluator 로봇은 Diamond 1.8.9

로봇의package만 변경하여 사용하였습니다. 제출 받은 소스코드를 살펴보니 Diamond를 눈치채신 분들도 몇 분 계셨습니다. 🙂

공지해드린 대로 날짜 별로 채점에 사용된 random seed는 다음과 같습니다.

day1 day2 day3 day4 day5 day6(최종)
randomseed 30001 30002 30003 30004 30005 30006

채점은 배포하였던 SDK를 통해 다음 명령어로 가능합니다. battle파일을 평가용 로봇과 자신으로 수정했다는 가정하에 아래와 같은 방법으로 채점 가능합니다.

java -Xmx512M -DROBOTPATH=robots -DRANDOMSEED=30006 -cp lib/robocode.jar robocode.Robocode -nodisplay -battle battles/skplanet.codesprint.battle

대회에도 안내 드렸듯이 random seed에 따라 연료의 생성위치가 달라지며, 이는 게임에서 큰 영향을 미치는 요소로 작용합니다. 따라서 모든 참가자에게 매 round마다 동일한 seed가 적용되도록 하였습니다. 동영상을 확인해보면(#1, #2) 같은 위치에서 연료가 나타나는 것을 확인 할 수 있습니다.

random성이란것이 때문에 재현 불가능한 채점 결과가 발생할 수 있어서, random부분을 제어할 필요가 있었습니다. Robocode에서는 Math.random()을 사용하여 Random을 생성하면 Deterministic한 게임을 만들 수 있습니다만, Random Class를 사용하여 별도의 Random generator가 생성된 경우에는 제어할 수 없었습니다. 이 때문에 JRE1.8의 Random class 기본 constructor를 수정하여 (System.nanotime() 부분 제거) 항상 같은 Random seed를 사용하도록 하였습니다.

아쉬웠던 점

개인적으로는 처음으로 대회를 진행하여 미숙한 점들이 많았습니다. 특히 몇몇 버그로 인해 SDK를 다시 배포했던 일들이 가장 미숙한 점이 아니었나 싶습니다. 위에서 말씀 드린 random성을 미처 제대로 제어하지 못해 밤새 채점 프로그램을 고쳤던 것이 기억에 남습니다.

문제의 점수 밸런스도 아쉬운 점으로 남습니다. 주로 상위권 로봇들이 움직임에만 치중한 점이 그러한데, 타격 점수를 높여서 다양한 전략 및 알고리즘이 나올 수 있었으면 좀 더 재미있는 대회가 되지 않았을까 합니다.

미숙한 점이 많았음에도 불구하고 많은 참여를 해주신 참가자 분들께 깊은 감사를 드립니다. 내년에는 더욱 재미있는 문제가 출제 되기를 기대해 봅니다.

송재혁 Platform Architecture팀

이것 저것 만들기를 좋아하는 wannabe hacker/developer 입니다.
Platform Architecture팀에서 가리지 않고 개발 업무를 맡아서 하고 있습니다.

공유하기