NYPC CODE BATTLE 예선 후기

 

 

들어가며

대 넥슨이 NYPC 10주년 이벤트로 대학생을 위한 판을 열어줬다.

대학에 와서 코딩에 입문했기에 싱글벙글하며 대회를 신청했다.

팀은 jinhan814, yeonee, jungh150(진), swoon 요렇게 나갔고,

모두 신촌연합이었기에 팀명은 자연스럽게 NYPC_Sinchon이 되었다.

이때까지만 해도 대체 어케 코드로 배틀한다는건지 몰랐당

 

 

연습문제. [버섯 게임]

 

 

유행했던 사과 게임을 1대 1로 하는데, 땅을 더 많이 가져가는 쪽이 이기는 게임이었다.

근데 우리 팀 모두 사과게임을 해본 적이 없어서 서로 대결해보면서 대충 감을 익혔다.

 

여러가지 테스트와 내전을 진행하며 

그냥 더 많은 뎁스로 돌리는 팀이 장땡이라는 것을 알아냈고 jinhan814가 7뎁스인가를 짰더니 걍 절대 못이기겠더라

그래서 걍 그거냈음

첫날

 

첫날에 2위를 하고 다들 할일 하러가서 나중에 확인해봤는데

 

 

마지막 날

마지막 날까지 대충 버티긴 했음... 대진한

 

 

문제 풀며 든 생각은 확실히 PS랑은 좀 느낌이 다른거같았다.

PS하다보면 러프하게 시간복잡도만 따지지 상수깎는건 애매한 TLE가 아닌 이상 잘 안했는데

이걸 하다 보니까 연산을 두 배 줄이는 게 얼마나 중요한지 알게 되었다.

 

 

온라인 라운드. [요트 옥션]

 

초반

 

처음엔 휴리스틱 대잔치를 했다.

요트 옥션을 우리끼리 해보고 사람 입장에서 나름 괜찮은 전략을 나열해보고 적용시켜봤다.

 

strange bid heuristic이라는 이상한 휴리스틱을 jinhan814가 짰는데, 초반에는 좀 괜찮다가 

사람들이 뭔가를 깨우친 듯 너무 잘해지길래 해볼 수 있는 게 있나 싶었다.

 

중반

 

dp에 사용한 족보의 마스크와 주사위 5개, 현재 상단합으로 최적을 구할 수 있는걸 이제야 눈치채서

전처리를 했당 

근데 그걸 10Mib인가 거따 넣는게 너무 어려웠다...

 

그래서 투트랙으로 갔는데,

swoon은 모든 경우를 학습시켜서 현재 상태의 기댓값을 예측하는 친구를 만들었고 (학습에 32시간씀)

jinhan814은 뭐 양자화인지 어떻게 막 해서 코끼리를 지갑에 넣는 것에 성공했다.

나중에 말할 방식으로 인해 학습보다는 잘 압축시키는 것이 결과적으로 좋았다.

 

다 해놓고 보니까 배팅을 어케할지 잘 모르겠어서 맨 처음에는 샘플 7번이랑 대결한 로그를 많이 뽑아놓고

7번과 유사한 배팅을 하도록 해봤다. 

 

배팅을 좀 살펴보니까 (A골랐을때 내총이득 - B골랐을때 내총이득)/2 이러면 벽보고 싸울순 있다는 것을 알았다.

그렇게 해서 돌려보니까 상대에 무관하게 그냥 주사위 억까를 당하면 지더라 그래서 폐기함...

 

문제가 뭘까 생각해봤는데 너무 이상세계만을 다루는 것 같았다.

100%로 둘 중 원하는 것을 선택할 수 있는 세계는 꿈만같지만... 존재하지 않기에

tX 시리즈를 만들었다. X%로 경매를 이기는 세계선에서의 최적을 계산한 dp를 해뒀음...

 

근데 샘플 AI 핑크빈들가지고는 내 전투력이 얼마인지 알기가 굉장히 어려웠다.

스위스에서는 1600한테도 지고 2600한테도 이기고 그냥 뭐가 쌘지 모르겠더라 그래서 늦게나마 전쟁터를 만들었다.

 

후반

최대한 in 100의 상황을 비슷하게 재현하고자 60개의 코드를 풀리그로 10~20판씩 하루에 10번은 돌린 것 같다.

그래서 그냥 올림픽 국대 뽑듯이 제일 잘한놈을 뽑기로 했다.

 

에이전트가 실수는 하지 않는지 그 친구에 대한 통계와 게임 로그를 따로 다 저장해둬야 했기 때문에 대회 막날에 내전 폴더 용량이 21GB를 넘는 슬픈 일이 발생했다.

 

그와 동시에 jinhan814이 양자화의 뭐 비트를 하나 올렸다고 했는데 사실 난 잘 모르겠다. 

암튼 코끼리를 지갑이 아니라 카드지갑에 넣는것에 성공한거같다.

 

jinhan814, yeonee, jungh150, swoon 모두 내전마다 엎치락 뒤치락 하다가

마지막 날에 swoon의 핑크빈으로 하기로 정해졌다.

 

내 전략은 다음과 같았다.

벽보고 배팅하는 것은 당연히 옳지만, 럭키펀치 맞는 게 너무 싫었다.

따라서 게임을 진행하며 상대의 성향을 파악해서

벽보고 게임하는 친구인지 본인 패만 보고 게임하는 친구인지 분류한다.

 

본인 패만 보고 게임하는 친구면 딱 걔만 이길 정도로 플레이한다.

 

의도적으로 배팅승률 66%일 때의 테이블을 사용하여 벽보고 배팅하는 친구를 잡아먹으려 했다.

아마도 50% 테이블을 쓸거같기때문에? 암튼 이게 제일 괜찮았다.

 

 

최종

 

 

루비 상대로는 50%정도 나오는 것 같고 다이아 상대로는 66%? 정도 나오는 것 같았다. 물론 409팀은 한번도못이김

물론 스위스는 운빨이니까 못갈 확률이 높을거같긴 하다. 암튼 일주일동안 빡세게 했는데 재밌었다.

SCPC 준비하러 가자

 

재밌는 대회 열어주신 NYPC에 감사드리고 문제는 아래 링크에서 확인할 수 있다고 합니다.

https://nypc.github.io/