Code Sprint 2015 Round 1 – 로보코드에서 가늘고 길게 살아남기

안녕하세요. Code Sprint 2015 round 1에 1위로 입상한 문진상이라고 합니다. 어떤 방법으로 문제에 접근하였는지 공유하고자 합니다.

 초기 접근 전략

첫 번째 라운드는 로보코드에 관한 문제였습니다. 먼저 문서와 관련자료를 읽으면서 로보코드 프로그램이 어떻게 동작하는지 개괄적으로 파악하는데 시간을 썼습니다. 로보코드는 대회까지 있을 정도로 상당히 연구가 많이 된 종목이었고 API 문서와 위키, 오픈 소스 등 참고할 자료는 아주 풍부했습니다.

조사하면서 알게 된 것은 유용한 것으로 판명된 정형화된 알고리즘이 이미 상당수 존재한다는 것과 널리 알려진 알고리즘에는 카운터가 되는 알고리즘이 존재한다는 것입니다. 따라서 문제의 조건에 따라 상대해야 할 마스터로봇의 동작 원리를 파악하는 것에 중점을 두고 관찰된 내용을 바탕으로 대책을 생각하기로 하였습니다..

마스터로봇의 동작 방식 관찰

제공된 SDK에서 시험한 결과 마스터로봇은 그 어떤 예제로봇도 상대가 되지 않는 화력과 정확도를 보여주었습니다. 게다가 무제한인 연료를 바탕으로 상대방의 유효한 공격에 대해 뛰어난 회피기동을 보여주었으므로 공격을 통한 점수 획득도 쉽지 않았습니다. 따라서 고득점을 위해서는 반드시 오래 살아남을 수 있는 대책이 필요했습니다.

마스터로봇의 특징을 레이더, 이동, 공격의 세 가지 부분으로 정리하자면

 레이더

적을 포착하면 Lock을 걸고 그 범위는 상당히 넓다. 한 번 포착되면 벗어나는 것은 불가능하다.

 이동

공격 당하거나 상대가 먼저 움직이지 않으면 기본적으로 정지상태를 유지한다. 상대와 거리를 두고 원을 그리듯 움직이며 먼저 다가오는 경우는 거의 없다.

 공격

상황에 따라 공격력을 조절해가며 끊임없이 쏜다. 거리가 멀어도 매우 정확하게 맞추며 특히 일정한 속도로 움직이는 표적이나 정지한 표적은 100턴도 버티기 힘들다. 본체가 이동 중이라도 명중률이 높다.

 대책

이기겠다는 생각은 깔끔하게 접고 오래 살아남는 쪽으로 방향을 잡았습니다.

우선 득점 요소 3가지를 살펴보면 오래 살아남아서 받는 점수와 공격이 명중했을 때 받는 점수, 그리고 상대방을 들이받아서 획득하는 점수가 있는데 현실적으로 생존점수 외에는 얻기가 매우 어렵습니다. 특히 마스터로봇에게 가까이 다가간다는 것은 적어도 제가 실험했던 결과 중에는 긍정적이었던 경우가 한 번도 없었습니다.

한편 연료가 떨어져서 정지하는 경우 금방 파괴되므로 반드시 연료를 보충하기 위한 알고리즘이 필요했습니다.

따라서 기본적인 방침은

 레이더

어차피 Lock을 걸어봐야 탐지 범위만 좁아지고 마스터로봇을 맞출 수도 없으니 과감히 Lock을 버리고 계속 회전시키면서 연료를 찾는데 집중한다.

 이동

최대한 멀리서 불규칙적으로 움직이며 마스터로봇의 예측사격을 피한다. 연료를 발견하면 바로 연료를 확보하러 이동한다.

 공격

공격 할 때마다 내 체력이 깎이므로 아주 근접한 경우가 아니면 공격력을 0.1로 한다.

 몇 번의 시행착오 끝에 이렇게 가닥을 잡고 좀 더 알고리즘을 정교화 시켰습니다.

최종 형태

이동

널리 알려진 알고리즘을 그대로 사용하면 마스터로봇의 카운터 알고리즘에 걸려서 허무하게 파괴되는 경우가 많았기 때문에 최종적으로는 상대방의 움직임을 대칭적으로 모방하는 알고리즘에 불규칙하게 속도를 바꾸는 부분을 추가하여 최대한 피격 횟수를 줄이려고 노력했습니다. 사실 닷지 봇(Dodge bot)이라고 알려진 훌륭한 알고리즘이 이미 존재하지만 마스터로봇은 탄환을 쏴도 체력이 깎이지 않기 때문에 공격을 했는지 안 했는지를 알 수가 없고, 따라서 마스터로봇을 상대로는 사용할 수가 없었습니다. 결국 무작위성을 추가한 이동이 최선이라고 판단했고, 이 방법은 의외로 효과적이었습니다.

공격

처음에는 공격을 해도 내 체력만 낭비될 뿐이라고 생각해서 공격을 하지 않았습니다. 그런데 그 경우 마스터로봇은 제자리에서 움직이지 않기 때문에 상대의 움직임을 모방하는 내 로봇도 정지하게 됩니다. 쌍방이 정지한 상태라면 화력에서 마스터로봇의 상대가 되지 않기 때문에 이것은 심각한 문제였고, 따라서 적을 포착하면 공격력 0.1의 탄환을 끊임없이 발사하도록 하였습니다. 이때 마스터로봇의 예상되는 미래 위치를 향해 공격을 해서 마스터로봇이 최대한 요란하게 움직이도록 하였습니다. 이 방법은 마스터로봇과 연료와 내 로봇이 일직선으로 배치되거나 연료가 마스터로봇과 가까이 있어서 연료를 확보하러 갈 수 없을 경우에도 마스터로봇을 멀리 움직이게 만드는 아주 좋은 효과가 있었습니다.

레이더의 경우는 큰 변화가 없었습니다.

사실 의외로 수고가 많이 든 부분이 연료를 확보하러 가는 기능이었습니다. 무식하게 연료를 향해 돌진하는 방법은 때때로 치명적인 결과를 낳았기 때문입니다. 예컨대 연료가 마스터로봇과 너무 가까운 곳에 나타나거나 연료를 확보하러 움직이는 도중에 강력한 공격을 정면에서 고스란히 맞게 되는 경우, 혹은 체력이 너무 적은 경우는 차라리 연료를 포기하고 남은 연료로 계속 움직이는 편이 평균적으로 더 좋은 결과를 보였습니다.

최종적으로는 어떤 획기적인 알고리즘의 발견보다도 레이더, 이동, 공격 등 각각의 활동에서 예상 가능한 치명적인 상황을 얼마나 잘 피하는가에 초점을 맞춘 결과물이 되었습니다.

후기

익숙해지기 전에는 좌회전 우회전도 못 하던 로봇이 점점 모양새를 갖춰서 나중에는 키보드와 마우스로 조종하는 로봇보다 훨씬 똑똑하게 움직이는 것을 보며 묘한 뿌듯함이 느껴졌습니다. 결과가 시각적으로 보인다는 점에서 참 재미난 문제가 아니었나 싶습니다. 특히 최종 제출물의 동영상에서 로봇이 정확히 의도한 대로 움직이는 장면들을 봤을 때는 짜릿함마저 느껴졌습니다.

 

일반적으로 알고리즘 문제는 무작위 요소가 있더라도 평균적인 성능이 수학적으로 예상 가능한 범위에 들어오는 경우가 많은데 비해 로보코드 문제는 똑같은 로봇을 가지고도 랜덤 시드에 의해 결과가 크게 바뀌었기 때문에 과연 내가 추가한 알고리즘이 이전보다 더 나은 것인가를 확신하기가 어려웠습니다. 따라서 최대한 튼튼한 알고리즘을 찾아야 했는데 정말 쉽지 않은 문제였습니다. 퇴근하고 시간을 쪼개서 실컷 구현한 코드가 오히려 점수를 더 떨어뜨리는 무서운 상황도 몇 번인가 마주쳤고, 어떤 방법이 더 좋은지 마지막까지 고민하다가 끝끝내 주석을 정리하지 못해서 상당히 지저분한 코드를 제출하게 됐는데 운이 따른 것인지 좋은 결과를 낼 수 있어서 기쁘게 생각합니다.

Code Sprint를 이야기로만 듣다가 올해 처음으로 참가하게 되었는데 정말 좋은 경험이었다고 생각합니다. 매번 새로운 문제를 찾고 대회를 준비하느라 고생하셨을 관계자 여러분께 감사 드리며 앞으로도 많은 개발자들이 즐길 수 있는 멋진 행사가 되기를 기대하겠습니다. 감사합니다.

문진상

스마트앤와이즈에서 소프트웨어 엔지니어로 일하고 있습니다.

공유하기