Code Sprint의 round 2 post-mortem

지난 11월 16일 Planet X 컨퍼런스에서 있었던 Code Sprint 우승자 발표를 끝으로 Code Sprint의 주요 일정이 마무리되었습니다. 많은 실력있는 프로그래머 분들이 관심을 갖고 지켜봐주셨고 또 참여해주셨습니다. 치열한 접전 끝에 round 2에서는 황태현님이 우승을 차지했습니다.

출제 의도

기존의 알고리즘 대회가 정해진 알고리즘에 대한 사고 능력 위주로 평가하는 데 반하여, 데이터가 주어졌을 때 그것을 분석하고 그에 맞춘 접근 및 풀이를 보여주는 참가자들에게 높은 점수를 주기 위해 두번의 라운드 모두 문제와 데이터를 함께 공개하는 방식으로 진행되었습니다. 그러다 보니 데이터 크기가 다른 대회에 비해 비교적 큰 편이었습니다. 라운드 1은 10GB에 달하는 큰 graph가 입력으로 주어졌는데, 라운드 2의 경우에도 400MB가 넘는 board가 입력으로 주어졌습니다. 통상적인 프로그래밍 대회의 입력 데이터가 아무리 커도 수백KB 내외인 것과 비교해보면 상당히 데이터 사이즈가 큰 편이었습니다. 그러나 대회 기간이 일주일이 넘는 긴 기간이었기 때문에 데이터의 크기는 대회의 공정성에 큰 영향을 주는 요소는 아니었습니다.

라이프 게임…왜?


라이프 게임은 2차원 격자 평면에서 이루어지는 게임이기 때문에 보면서 플레이하기가 쉬운 편입니다. 오픈소스 라이프게임 시뮬레이터인 Golly의 Script 기능을 활용하거나, Golly의 소스코드를 일부 수정함으로써 입력 데이터를 import할 수 있습니다. 또 사용할 수 있는 룰이 많이 있고, 각각의 룰이 제각기 특징을 갖고 있다는 것도 장점이었습니다.

데이터 소개

입력 데이터는 다음 9개의 작은 데이터로 구성되어 있습니다. 각 데이터의 설명은 다음과 같습니다.

  1. r0-example.txt : 문제 소개에 나와있는 예제 데이터입니다. 채점에 영향을 주지 않을만한 작은 데이터를 사용했습니다.
  2. r1-handmade.txt : Life(B3/S23)룰에서 존재하는 Still-Life(턴이 지나도 형태가 변화하지 않는 모양) 유형들을 비교적 작은 범위에 배치하였습니다. 무턱대고 턴을 진행시키기 보다는 적절한 변화를 먼저 주고 턴을 진행하는 편이 훨씬 효율적입니다.
  3. r2-seeds.txt : Seeds(B2) 룰을 활용했고, 몇 가지 미리 지정해둔 3가지 패턴들을 랜덤한 위치에 배치해두었습니다. Cell들이 조금만 모여있어도 턴이 진행됨에 따라 폭발적으로 증식하게 되기 때문에 초기 데이터에서 SET 명령을 통해 자연적으로 사멸하는 조합을 만들어내는 것이 중요합니다. 그러나 패턴의 종류가 많지 않기 때문에 각 패턴별로 대응하는 방법을 찾아 설정하면 비교적 적은 비용으로 문제를 해결할 수도 있습니다.
  4. r3-night-and-day.txt : Night and Day(B3678/S34678) 룰을 활용했고, 이 룰의 특징 중 하나인 커다란 직사각형 형태의 Still-Life들을 맵 여기저기에 랜덤하게 배치하는 방식으로 데이터를 만들었습니다. 2번째 데이터와 같이 모든 데이터가 Still-Life 형태이기 때문에 무턱대고 턴을 진행하기보다는 직사각형 블록을 어떤 방식으로 해체하는게 효율적인지를 공략하는 문제가 될 것으로 기대했습니다.
  5. r4-diamoeba.txt : Diamoeba(B35678/S5678) 룰을 사용하며, 맵 여기저기에 랜덤한 직사각형 크기의 영역들을 선택하여 Cell들을 몰아넣는 방식으로 데이터를 만들었습니다. 턴이 진행됨에 따라 각 블록 영역의 Cell들이 서로 뭉쳐 오랜 시간동안 활동하게 되는데, 이를 분해하기가 상당히 까다로울 것으로 예상했습니다.
  6. r5-spotlife.txt : 위의 데이터와 같은 형식으로 Cell들을 배치하되, 해당 보드의 룰만 Life(B3/S23)으로 변형한 데이터입니다. Life 게임에서의 일반적인 상황을 해결하는 알고리즘을 평가하고자 하였습니다.
  7. r6-halfspotlife.txt : 위 r5 데이터와 거의 흡사하지만, 초기 Cell들의 수가 더 적은 버전입니다. Life 룰의 평가 비중을 높이기 위해 두개를 넣었습니다.
  8. r7-morley.txt : 데이터의 배치는 4,5,6과 흡사하고, Morley(B368/S245) 룰을 사용한 데이터입니다. Morley 룰의 경우 Life와 유사한 양상으로 진행되지만, 더 빠르게 안정화되는 경향이 있기 때문에 다른 데이터와는 다른 특징이 있을 것으로 기대했습니다.
  9. r8-full-gliders.txt : 맵 전체에 100만 개의 글라이더 패턴(게임 소개 부분에 나오는 패턴입니다. 시간이 지남에 따라 대각선 방향으로 이동하는 것이 특징)을 이리저리 박아놓은 패턴입니다.

각 데이터를 크게 분류하면 Still Life들을 분해하는 유형, NEXT를 많이 쓰면서 일부 덩어리에 SET을 써야 하는 유형, 맵 여기저기에 흩어져 있는 패턴들을 찾아 각 패턴별로 SET을 해야 하는 유형, 그리고 이 모든 것들에 해당하지 않는 Diamoeba 유형으로 나눌 수 있습니다.

대회 결과

대회 초중반에는 주로 모든 셀들을 SET으로 제거하는 초보적인 방법과, 거기에 일부 NEXT를 활용하는 방법으로 문제를 해결하는 참가자들이 많았습니다. 하지만 시간이 지나면서 데이터에 따라 다른 접근으로 문제를 해결하려는 움직임이 보이기 시작했습니다.

작은 패턴의 나열에 불과한 r2, r8 데이터의 경우 비교적 초반부터 높은 수준의 개선이 이루어졌습니다. 하루만에 최종 점수의 95% 수준 이상의 답안이 나왔고, 이후로는 점수에 거의 영향을 주지 않는 미미한 수준의 개선만 이루어지게 됩니다.

r1의 경우에는 비교적 꾸준히 점수 개선이 이루어지다가, 166점이 등장한 이후로 그 점수보다 높은 점수가 나오지 않았습니다.

r5,r6,r7의 경우 Simulated Annealing 기법을 통해 조금씩 더 좋은 답안이 나오는 경향을 보였습니다. 아마 대회 기간이 더 길었다면 더 좋은 점수도 나왔을 것 같습니다.

r3의 경우 극초반에는 거의 모든 셀들을 SET으로 지우는 답안 위주였으나, 점차 점수가 개선되면서 일부 셀만 SET으로 지우고 NEXT를 하는 방식으로 개선이 되어나갔습니다. 대회 막판까지 크고 작은 폭의 개선이 계속 이루어진 데이터였습니다.

r4의 경우 초반에 큰 폭으로 점수 개선이 이루어졌으나, 70만점 근처에서 대회 막바지까지 개선이 이루어지지 않았습니다. 그러나 대회 막판에 16만점짜리 답안이 나와 결과적으로 대회의 승부를 가르는 데이터가 되었습니다.

이와 같이 여러 부분에서의 점수 개선이 이루어지면서 대회 초중반에는 엎치락 뒤치락하는 점수 경쟁이 계속 벌어졌습니다.

그러나 대회 마지막 날에 그동안 제출을 하지 않고 있던 사람들이 답안을 제출하면서 순위표에 대격변이 일어납니다. 가장 큰 점수 격차는 r4 데이터에서 발생했는데, 이는 1등 참가자가 다른 참가자들이 발견하지 못한 규칙을 발견해서 비교적 효율적으로 패턴 제거에 성공했기 때문으로 생각됩니다. 2등과 무려 4배 정도의 점수차를 내서 다른 사람들과 9만점 이상의 점수차를 벌리는 데 성공합니다. 또한 r5,6,7의 경우에도 Simulated Annealing의 적절한 활용을 통해 다른 참가자들에 비해 약 20% 가량 효율적인 답을 내는 데 성공했습니다.

풀이 소개

2라운드의 1위 입상자분께 요청을 드려서 풀이 문서 및 PT 자료를 제공합니다. 흔쾌히 자료 제공을 허락해주신 황태현(xenosoz)님께 감사드립니다.
황태현 님께서 직접 작성해주신 우승 보고서도 보시고,
시상식날 발표하셨던 자료도 보세요~ 이 문서는  구글 크롬에서만 제대로 보입니다.

아쉬운 점

첫 대회이다 보니 대회 진행이 매끄럽지 못한 부분이 많이 있었습니다. 대회 초반에 서버가 불안하게 작동하기도 했고, 대회 규칙 상 대회 초중반에 굳이 답안을 제출할 이유가 없다는 점도 많은 참가자들이 대회 후반부터 참여하게 만드는 원인이 되었습니다

제출해야 하는 답안 파일도 비교적 큰 용량이어서 해외 참가자들의 경우 답안을 제출하는 데 어려움을 겪었을 것으로 생각됩니다.

Reference

온라인 상에서 프로그래밍 대회를 여는 곳은 생각보다 많습니다. ACM-ICPC의 경우 문제 Archive 사이트를 제공하고 있으며, TopCoder에서는 주기적으로 여러가지 형태의 Online Competition을 개최합니다. Google Codejam은 전 세계의 프로그래머들이 각자 선호하는 프로그래밍 언어를 사용해서 알고리즘 문제를 풀 수 있다는 장점이 있습니다.

정헌 Platform software개발1팀

읽기 5분, 생각 5분, 코딩 1시간, 뿌듯해 하다가 더 쉬운 방법 발견하기 15분, 후회 1일, 다시 코딩 10분, 문제 해결…

공유하기