TopCoder Marathon Match 99 후기

거의 7년 만에 탑코더 마라톤 매치(Marathon Match, MM)를 해 보았습니다. MM은 Single Round Match(SRM)와 달리 정해진 정답을 빠르고 정확하게 계산하는 대회가 아니라, 문제에서 요구하는 최적해를 30초 ~ 1분 정도의 다소 넉넉한 수행시간을 가지고 계산할 수 있는 알고리즘을 고안하는 대회입니다. 대회를 치르는 시간도 SRM은 1시간 15분인 것에 비해 MM은 최소 1주 ~ 2주의 긴 시간 동안 이루어집니다.

이번 MM 문제 내용을 한 문구로 요약하면 '슬롯 머신을 이용한 도박'이라고 할 수 있습니다.

문제 본문은 다음 링크( MM 99 Problem Statement )에서 보실 수 있습니다.
대회 결과는 다음 링크 ( MM 99 Standings )에서 보실 수 있습니다.
저는 토요일에 참가신청을 해서 문제를 본 후, 일요일에 생각을 하고 월요일부터 참가해서 금요일에 끝이 났습니다.

Day 1 (토요일)
문제를 다 이해하고 나니, 딱히 좋은 방법이 떠오르지 않았습니다. 입력으로 주어지는 초기 자본과 시간이 생각보다 적었기 때문에, 단순하고 좋은 방법이 떠올라야 할 것 같았습니다. 사용할 수 있는 쿼리가 2가지 종류인데, 두 가지 중 하나만 사용하는 게 더 나을 수 있겠다는 생각을 했습니다. 예를 들면, 초기 자본이 극도로 적을 때에는 quickPlay만 쓰는 게 이득이겠구나... 코딩을 하려고 보니, 스켈레톤 코드는 있는데 테스트를 하기 위해 참고할 코드로는 자바 코드 하나 뿐이었습니다.

Day 2 (일요일)
로컬에서 테스트 하기 위한 코드를 C++로 작성했습니다. 제공되는 자바 코드를 참고해서, 정해진 시드값이 아닌 랜덤한 시드값에 대해 내가 원하는 횟수 만큼 돌아보고, 초기에 주어진 코인에 대비해서 몇 배의 이윤을 남기는지 통계를 낼 수 있게 하였습니다. 그리고 입력의 각 parameter에 따라 규칙을 찾기 쉽게 하기 위해서 각 parameter별 분포에 따른 통계치도 저장할 수 있게 하였습니다.

Day 3 (월요일)
스켈레톤 코드에 생각한 방법들을 하나씩 작성해보고 테스트했습니다. notePlay를 쓰지 않고, quickPlay만 쓰니까 평균적으로 130~140% 정도의 수익만 낼 수 있었습니다. 당시 스코어보드의 1등이 약 240% 정도의 수익을 낸다고 판단되어서 다른 방법을 써야겠구나 생각했습니다. 각 슬롯 머신마다 일정한 횟수의 notePlay만 써서 통계를 내고, 가장 좋은 슬롯 머신만 가능한 많이 사용하는 전략을 사용했더니 170% 정도의 수익을 낼 수 있었습니다. 그럼에도 불구하고, 제 점수는 참가자 중 중간도 되지 못했고, 하위 20% 였습니다.

Day 4 (화요일)
코드를 살펴보니 잘못 생각한 부분이 있었습니다. 가장 좋은 슬롯 머신을 선택한 후, 가능한 많이 사용할 때에 min(남은 시간, 슬롯 머신 선택 후 남은 코인) 만큼 quickPlay를 하도록 했습니다. 그런데 남은 코인의 경우, 수익을 지속적으로 내다보면 더 큰 값으로 될 수 있었기 때문에 남은 시간과 현재 가진 코인이 양수일 때에 quickPlay를 할 수 있도록 바꾸었습니다. 이 부분을 바꾸니 230~240% 정도의 수익을 낼 수 있었습니다. 참가자 중 상위 40% 정도에 위치하였습니다.

Day 5 ~ Day 7 (수요일 ~ 금요일)
이런 저런 상수값을 바꾸어보고, 통계적 관점에서 가설을 세워서 검증을 시도해보았지만 하나도 빠짐없이 다 기각되었습니다. 점수는 더 오를 기미가 보이지 않았지만, 개선점을 찾고자 노력했습니다. 가장 좋은 슬롯 머신을 선택하기 위해서 모든 슬롯 머신에 대해 일정 횟수 notePlay를 수행할 때에, 도중에 아니라고 확신이 드는 슬롯 머신들은 제외하면 어떨까 해서 이 부분을 추가해서 제출했더니 점수가 1% 정도 올랐고 등수에는 변화가 없었습니다. noteTime이 크면 notePlay가 비효율적이지 않을까 생각했지만, 생각보다 효율적이었습니다. 별 다른 수정은 하지 않는 것이 좋겠다 싶어서 Provisional Score로 77만점, 상위 50% 정도에서 끝냈습니다.

대회가 다 끝난 후, Forum에서 참가자들이 사용한 방법이 대부분 비슷함을 알 수 있었습니다. 가능한 적은 횟수의 notePlay 호출로 가장 좋은 슬롯 머신을 찾아내서, 그 슬롯 머신으로 가능한 많이 quickPlay를 호출하는 것입니다. 다만, 상위권일수록 케이스를 잘 나누어 최적의 상수값을 잘 찾아내었고, 베이지안 추론 등의 추가적인 계산을 통해 평균 성능을 높이는 최적화를 하였습니다.
대회가 열린 날부터 열심히 참가했으면, 제가 시도해보고 안 좋다고 빠르게 단정한 방법들을 여유를 가지고 개선해서 보다 좋은 결과를 얻을 수 있지 않았을까 하는 아쉬움이 듭니다. 또한 다음 대회는 이번 대회보다 User Friendly하면 좋겠다는 생각이 들었습니다.