NYPC CodeBattle의 예선이 종료되었다. 꽤 진심으로 임했기 때문에, 기록으로 남겨두는 게 좋을 것 같아서 이렇게 정리해본다. 같이 참여한 팀 멤버는 ICPC를 함께할 Endgame 팀(ystaeyoon113, playsworld16)이다.
2일차 : 8월 9일 (토)
전략 1 - 3차원 DP, 규칙 상태 비트마스킹 쪼개기 전략
가장 먼저 떠올린 아이디어는 3차원 DP를 활용한 기대값 계산이었다. 구체적으로는 다음과 같은 DP 테이블을 설계했다.
- DP[주사위 5개 조합(252)][상단 점수 합(0~63, 63 이상은 보너스 확정이라 63으로 통일)][현재 열려 있는 규칙 상태(2^12 비트마스킹)] = 앞으로 더 얻을 수 있는 점수의 기댓값.
코드를 짜서 실제로 DP를 채워보니, 결과 파일(data.out)이 무려 262MB나 나왔다. 그런데 문제는 메모리 제한이었다. 10MB라는 메모리에 262MB의 데이터를 담기에는 메모리가 너무 컸다.
메모리를 줄이기 위해, 규칙 상태(2^12 = 4096)를 상단점수(상단 6개 규칙, 2^6 = 64)와 하단점수(하단 6개 규칙, 2^6 = 64)로 나누는 전략을 썼다. 이렇게 하면 전체 DP 크기가 훨씬 줄어들어 8MB 정도로 압축되었다.
접근을 정리하면 다음과 같다.
- 상단점수 DP와 하단점수 DP를 별도로 관리
- 각 DP에서 기대값을 계산한 후, 두 DP의 결과를 가중치로 결합해 전체 상태의 기대값을 평가
이 접근의 핵심은 가중치 매기는 과정이었는데, 다음과 같은 아이디어를 도입했다.
- 남은 비트 개수 기반 가중치 - 상단점수 남은 비트 개수와 하단점수 남은 비트 개수를 고려해 기대값을 다르게 조정. 예를 들어, 상단점수가 거의 채워지지 않아서, 보너스 35점을 받기 어려운 상황인데 당장 하단점수를 통해 획득하는 점수의 기대값이 높으면 하단점수 쪽에만 집중하는 문제가 생길 수 있었다.
- Choice 특수 가중치 - 실제 봇 간 대전 로그를 뜯어보니, Choice 규칙이 초반에 너무 일찍 소모되는 비직관적인 케이스가 많았다. 이를 방지하기 위해 Choice 사용 시 턴에 따라 점진적인 가중치를 적용했다. 구체적으로, 1턴에 사용하면 2/3 배율, 마지막 턴에 사용하면 1 배율로 적용했다. 이렇게 하면 초반부터 Choice를 허비하지 않고, 후반으로 미루는 전략을 유도할 수 있었다.
배팅은 다음과 같이 진행하였다.
- 각 가능한 패(주사위 조합)를 선택했을 때의 기대값을 계산한 뒤, 그 기대값의 차이를 4로 나눈 만큼 배팅 금액으로 설정하였다. 이렇게 하면, 기대값 관점에서 배팅에 승리하든 패배하든 최종적으로 받는 기대값이 동일해진다.
전략 1 결과
퍼포먼스가 500점이 차이나는 팀이 두 팀 있었다.
rule base만으로도 훨씬 좋은 전략을 구상할 수 있는 듯 하여, 더 좋은 전략을 찾기 시작했다.
3일차 : 8월 10일 (일)
전략 2 - 3차원 DP 양자화 - 10MB 안에 최대한의 정보를 넣기 전략
앞서 262MB 크기의 3차원 DP를 만들었지만, 실제로 DP 값을 16비트 int로 조정하면 130MB까지 줄일 수 있었다. 여기서 더 나아가, 압축 기술을 활용해 130MB 데이터를 10MB로 압축할 수 있지 않을까 하는 생각이 들었다.
여러 압축 전략을 검색하고 실제로 테스트해 보았는데, 무손실 압축으로는 대략 30% 정도만 줄어들었고 그 이상은 잘 안 됐다. 이제 와서 돌이켜보니, 데이터 배열의 순서가 문제였다. 만약 DP의 차원을 [현재 열려 있는 규칙 상태(2^12 비트마스킹)][상단 점수 합(0~64)][주사위 5개 조합(252)]이나 [현재 열려 있는 규칙 상태(2^12 비트마스킹)][주사위 5개 조합(252)][상단 점수 합(0~64)]로 배치했다면 압축이 훨씬 수월했을 텐데, 그걸 미처 고려하지 못했다.
고민 끝에 발견한 특징은, 상단 점수 합과 규칙 상태를 고정했을 때 주사위 5개 조합(252)의 기대값 변동성이 크지 않다는 점이었다. 이걸 활용해 다음과 같은 양자화 전략을 썼다.
- 상단 점수 합과 규칙 상태를 고정한 상태에서, 252개 주사위 조합의 값을 MSE(Mean Square Error)가 최소가 되도록 정확히 두 개의 값으로 분류.
- 각 조합을 0 또는 1로 매핑하면, 전체 상태를 비트 1개로 관리할 수 있게 됨.
이렇게 하면 데이터를 10MB 안에 전부 담을 수 있었다. 게다가 원본 3차원 DP와 비교해 평균 기댓값 차이가 2000 정도에 불과했기 때문에, 원본의 맥락을 꽤 잘 반영할 거라는 기대가 컸다.
전략 2 결과
봇전에서 6승 4패를 기록했다. 아직 3일차쯤 이었기에 아직 봇전에 대한 신뢰가 있었기도 했고, 로그를 자세히 보니 비직관적인 플레이가 너무 많아서 아이디어를 금방 취소했다. 주사위 조합을 단순히 0과 1로 결정짓는 전략 자체가 위험하다는 걸 크게 느꼈다. 이 접근은 메모리 효율은 좋았지만, 주사위 조합을 잘 관리하지 못하는 문제가 있었다.
추가) 압축 전략을 테스트하다 보니, 압축된 데이터가 원본 3차원 DP와 얼마나 차이가 나는지 객관적으로 평가할 필요가 생겼다. 그래서 별도로 data_judge.py 스크립트를 만들어, 압축 데이터와 원본 DP 간의 평균 차이를 계산하는 기능을 구현했다. 덕분에 각 양자화 전략들에 대해서 얼마나 복원률이 높은지를 숫자로 비교할 수 있게 됐다.
4일차 : 8월 11일 (월)
전략 3 - 2차원 DP 합성 전략
초기 전략 1을 돌이켜보니, 3차원 DP에서 상단점수와 하단점수 남은 규칙 상태를 비트마스킹으로 나누었지만, 실제로 상단점수와 하단점수 사이에는 깊은 연관성이 있었다. 이 때문에 단순 분리가 완벽한 해결책이 아니었다.
고민 끝에 떠올린 아이디어는, (주사위 조합)과 (상단 점수 합) 간의 연관성은 상대적으로 적을 수 있다는 점이었다. 또한,
- 전략 2처럼 DP에서 손패를 제외하면(즉, 규칙 상태와 상단 점수 합만 고려), 전체 3차원 DP와 굉장히 비슷한 결과를 얻을 수 있을 거라 예상.
- 반대로 상단 점수 합을 제외하면(규칙 상태와 손패만 고려), 같은 전략 안에서 최선의 손패 관리를 할 수 있을 거라 생각.
그래서, 두 가지 2차원 DP를 만들어 합성하는 접근을 시도했다.
- 주사위 손패를 제거한 DP - 규칙 상태와 상단 점수 합 기반으로 기대값 계산.
- 상단 점수 합을 제거한 DP - 규칙 상태와 손패 기반으로 기대값 계산.
- 이 두 DP의 결과를 적절한 가중치로 합쳐 전체 기대값을 판단.
전략 3 결과
다시 한 자리수 등수로 되돌아왔다. 하지만 여전히 더 강한팀이 많았고, 더 좋은 전략을 찾기로 했다.
5일차 : 8월 12일 (화)
전략 4 - 2차원 DP, 보너스 지우기 전략
ystaeyoon113이 보너스 35점을 반드시 받는다고 가정하면, 상단 점수 합 및 보너스 정보를 DP에서 아예 지워도 괜찮지 않을까 하는 생각을 했다. 그래서 3차원 DP에서 보너스 관련 항목을 완전히 제거하는 아이디어를 새로 만들었다.
참고로 이 접근은 보기보다 효과가 아주 좋아서, 이후 모든 전략은 이 접근 기반으로 진행하게 됐다.
처음 아이디어를 구상할 때 고려한 디테일은 다음과 같다.
- 해당 DP는 상단 점수를 63점 이상을 만드는 것을 전제로 플레이한다.
- 이를 위해 상단 점수를 63점 달성하기 위한 추가 정책이 필요하다.
- 하지만, 정책을 함부로 만들면 의도치 않은 곤란한 상황이 생길 수 있는데, 이 부분은 설명하기 좀 어렵다.
전략 4 결과
봇전 상대로 10승을 진행해서 좋아하고 있었지만, 전략 3에 비해 순위가 떨어졌다.
로그를 분석해 보았을 때, 확실히 비직관적인 플레이어가 많았어서 전략이 충분히 완성되지 않았다는 느낌을 받았다.
전략 5 - 2차원 DP, 보너스 지우기 전략 ver.2
전략 4의 보너스 지우기 접근을 실제 게임에 적용해 보니, 비직관적인 플레이가 꽤 많았다. 가장 큰 문제는 추가 정책 때문에 시도 때도 없이 상단 점수에 달려들어서 오히려 전체 점수가 떨어지는 경우가 발생한 거였다.
어쨌든 상단 점수에 긍정적인 효과를 주는 건 필요했지만, 평범한 휴리스틱 정책으로는 제대로 작동하지 않았다. 전략 4를 만든 시점에 토론을 했을 때 가장 좋은 휴리스틱 정책이라고 판단했던 것은 다음과 같다.
- 상단 63점을 채우면 보너스 35점을 받는다는 점 때문에, 63점 달성까지는 각 상단 점수가 (63 + 35)/63 = 14/9의 가중치 가치가 있다고 계산했다.
이 아이디어 자체는 맞았지만, 문제는 DP를 만들 때 이 가중치를 고려하지 않았다는 점이었다. 즉, 추가 정책을 만들더라도 DP와 연계되어 기대값이 제대로 관리되어야 했다. 이 문제를 발견한 후, DP 생성 단계부터 상단 점수를 얻을 때 항상 14/9 가중치를 적용하는 특수 정책 최적화 DP를 새로 만들었다.
전략 5 결과
순위도 순위지만, 로그를 분석했을 때 비직관적인 베팅이나 비직관적인 손패 관리가 아얘 없어서 긍정적이었다.
해당 전략으로 메모리와 계산 복잡도를 줄이면서도 실전 성능이 안정적이었고, 보너스 가정을 바탕으로 한 단순화가 게임의 본질을 잘 유지했다. 이전 전략들의 약점을 보완한 느낌이었다.
6일차 : 8월 13일 (수)
전략 6 - 2차원 DP, 보너스 지우기 전략 ver.3 - 동적 DP 교체
로그를 분석하다 보니, 더 개선할 수 있는 부분을 발견했다. 특수 DP가 상단 63점을 채운 후에도 여전히 14/9 가중치를 상단점수에 부여하는 바람에 베팅이 과도해졌고, 후반부에 손패를 관리하는 방식에서도 최선의 플레이를 하지 않았다. 그로 인해 최상위권 대전에서 점수 차이로 지는 판이 몇 번 발생했다.
그래서 보너스(63점 달성)를 채운 이후부터는 14/9 가중치가 없는 기존 DP를 불러와, 상황에 따라 두 개의 기대값 DP를 동적으로 교체하는 아이디어를 추가로 적용했다. 이로써 보너스 전후의 전략을 더 유연하게 조정할 수 있게 됐다.
또한, 이 시점부터 내 코드끼리 서로 대전하는 시스템을 개발했다. 전략 5 버전과 500판을 붙여보니 승률이 58%에 달했다. 승률이 눈에 띄게 향상된 걸 보고, 내 전략에 대한 신뢰가 조금 더 생기기 시작했다. 500판 대전은 연습 순위보다 훨씬 신뢰도 높은 메트릭을 제공하는 것 같아서, 이후 대부분의 실험은 로컬 환경에서 진행하게 됐다.
전략 6 결과
18승 2패, 최상위권 모두와 매칭되었는데도 여유롭게 승리하며 처음으로 1위를 받게 됐다.
참고로, 이 코드는 우리팀의 최종 제출이기도 하다. 이후의 전략들도 의미가 있었지만, 일단 20등에 드는것이 제일 중요하다고 생각해서, 마지막까지 제일 결과가 안정적이었던 해당 코드를 최종 제출하였다.
8월 13일 이후
전략 6에서 패배한 판들의 로그를 분석하여, 더 개선할 수 있는 것들을 고민했다. 아래에 있는 전략들은 모두 전략 6과의 상대 전적이 좋다. 하지만 side effect를 고려하여 최종 제출로 선정하지는 않았다.
전략 7 - 보너스 위치 바꾸기 전략
전략 6을 적용하다 보니, 상단 점수가 63점을 넘기 전에는 14/9의 보너스 가중치를 제공하지만, 정확히 63점에서 보너스가 끝나기 때문에 기대값이 그 지점에서 크게 변동하는 경향이 있었다. 이로 인해 63점 달성을 미루는 비효율적인 선택이 종종 발생했다.
이를 해결하기 위해, 보너스 기점을 63점이 아닌 66점이나 68점으로 변경하는 전략을 도입했다. 이렇게 기대값의 위치를 조정하면, 보너스 달성 과정이 더 부드럽게 전환되고, 미루는 문제를 줄일 수 있었다.
이 전략은 관련 문제들을 효과적으로 해결했으며, 상대 전적은 꽤 좋았지만, 예선 순위는 약간 더 낮게 나왔다.
전략 8 - 보너스 가중치 바꾸기 전략
전략 7에서 보너스 기점을 조정했지만, 여전히 가중치 자체에 대한 고민이 남아 있었다. 상단 점수가 63점을 넘기 전에는 14/9의 보너스 가중치를 제공하지만, 실제 대부분의 게임에서 상단 점수가 63점이 아니라 70점을 넘길 정도로 높게 나오는 경우가 많다. 이 경우, 단순히 63점으로 35점 보너스를 얻었다고 보는 게 아니라, 기본점수 70점으로 보너스 35점을 얻었다고 해석할 수 있다는 생각이 들었다.
그래서 보너스 가중치를 조금 더 낮추는 전략을 시도해 보았다. 이로써 과도한 상단 집중을 피하고, 전체 균형을 더 맞출 수 있을 거라 기대했다.
이 전략 역시 상대 전적은 꽤 좋았지만, 확실하고 안정적인 결과를 위해 결국 전략 6을 채택하게 됐다. 가중치 조정이 세밀한 효과를 주긴 했지만, 과도한 변동성을 초래할 위험이 있어서 보수적인 선택을 했다.
마무리
1주일간 PS 공부량을 조금 줄이고, 그 시간에 정말 즐겁게 대회에 임할 수 있었던 것 같다. 그래도 취업이나 ICPC 같은 더 중요한 목표들이 있으니, 이제 다시 정신 차리고 바짝 공부해야겠다.
결과에 대해서는 사실 20전 스위스 리그를 그렇게까지 신뢰하지 않는다. 그래서 상위 20위 안에 들지 안 들지 지금으로서는 잘 모르겠다. 그래도 평균 등수가 5등 안팎인데, 붙지 않을까? 하는 막연한 기대를 품고 기다리고 있다.
정말 좋은 퀄리티의 문제와, 능력 있는 참가자들이 많았던 덕에 더더욱 즐겁게 대회에 임할 수 있었던 것 같다.
대회 열어주신 넥슨 관계자분들께 정말 감사합니다!
문제 링크: https://nypc.github.io/2025-codebattle
'PS 개인 공부 > 대회 후기' 카테고리의 다른 글
| 2025 ucpc 후기 (3) | 2025.07.30 |
|---|---|
| 2024 SUAPC summer 후기 (5) | 2024.09.03 |
| 2024 UCPC 후기 (2) | 2024.08.06 |
| 2024 ICPC Asia Pacific Championship 후기 (0) | 2024.03.24 |
| SCPC 2023 본선 후기 (1) | 2023.09.24 |