2018년 4월 13일부터 22일까지 진행되었던 '네코동 AI 챌린지: Five!'에 참가하는 동안의 이야기를 담은 저장소입니다.
bots/congrats.py를 '성공적인 대회 개최를 축하합니다'라는 이름으로 제출하였습니다. 시간을 많이 못써서 아쉽지만, 상위권에 입상하지 못할 것이 예상되는 상황에서도 꿋꿋하게 대회를 끝까지 마친 점에 스스로를 칭찬하려고 합니다. 즐겁고 뜻깊은 행사 만들어주신 넥슨 프로그래밍 동호회 네코동 여러분께도 감사의 말씀을 전합니다.
이 글에서는 편의상 '12345!'를 (0, 1, 2, 3, 4, 5)에 대응시켜 표현하였습니다.
-- (xenosoz, 2018-dapr-23)
- 가위바위보와 유사한 1:1 AI 대전입니다.
- '12345!' 여섯개의 패가 있습니다. 보통 큰 패가 작은 패를 이깁니다.
- 1은 5를 이기고, !는 짝수패를 이깁니다.
- 패를 다 쓰거나 어느 한 쪽이 상대보다 세 번 더 많이 이기는 순간까지를 한 경기로 정합니다.
- 11경기 중 6선승한 쪽을 승자로 정합니다.
- 승은 3점, 무승부는 1점으로 하는 풀 리그를 시행하여 8강 진출 팀을 선발합니다.
- 8강부터는 1:1 대전이고, 무승부의 경우 단판 승부를 더 합니다. 그래도 무승부이면 먼저 제출한 사람이 승리.
- 패를 하나 낼 때마다 1초의 제한 시간이 있습니다.
과거 경기의 승부 결과를 이용하면 전략이 얼마나 상대에게 적합한지 계산할 수 있습니다. 여러개의 전략을 구현해두고, 그 중 가장 퍼포먼스가 좋은 전략을 선택하는 메타 전략을 두었습니다. Five에 제출하는 봇에는 상태를 저장할 수 없으므로 history, old_games를 이용하여 과거에 수행되었던 계산을 모두 다시 수행하는 방법으로 역사를 돌아볼 수 있도록 했습니다.
모든 전략 S에 대해서, 다음의 permutation을 여러번 적용한 메타 전략을 만듭니다.
- P0 = (0, 1, 2, 3, 5, 4)
- P1 = (0, 1, 3, 5, 2, 4)
- P2 = (0, 1, 5, 2, 3, 4)
이 수열에는 P[n] vs P[(n+1)%6]을 하면 항상 후자가 이긴다는 좋은 특징이 있습니다. (lab/winning-cycle.py 참고)
- 랜덤으로 패 내기
- [나|상대]의 가장 최근 게임을 따라하기
- [나|상대]의 len(history)번째 패를 살펴보기
- [나|상대]의 최근 1~5번째 히스토리를 살펴보기
미래의 몇 수를 미리 두어보는 코드도 작성하였으나, 1초 시간 제한을 쉬이 넘기는 것을 보고 관련 코드를 모두 삭제하였습니다.
여기에 몇가지 전략을 더 추가할 시간이 있었다면 하는 아쉬움이 남습니다.
메타 전략이 역사를 살펴보며 좋은 전략을 찾을때까지는 시간이 오래 걸리는 편입니다. Five! 경기는 기본 11전 6선승이며, 8강에서의 단판 승부를 더해도 최대 12전까지만 경기가 이루어집니다. 6~12전 안에 메타 전략이 잘 수렴하도록 하는 별도의 장치가 필요해 보입니다.
게임 규칙을 이해하고 나니 완전 우세 전략을 찾기 힘든 대회라는 생각이 들었습니다. 노력을 들이더라도 확실하게 1등을 하는 방법은 없다는 생각을 한 뒤로는 손이 잘 가지 않았습니다. 저도 모르게 노력의 '가성비'를 생각한 것이지요.
(운좋게) 여러 대회에서 1등을 몇번 했더니 지는 대회에는 나가기 싫은 마음이 생긴 것 같았습니다. 여러가지 일을 즐겁게 경험하고 배움을 얻는 것이 성장의 길이라면 이런 '심리적 거품'은 여러모로 좋지 않다는 결론을 내리고 반성했습니다. 보이지 않는 마음과 싸우고 나니 대회 시간이 대략 8시간만 남아있었어요.
친구들과 모여서 간식을 먹으며 각자 하고싶은 일을 했습니다. 마음을 정하지 못하고 까먹은 대회 시간이 아까운 마음이 들기도 했지만, 남은 시간동안은 즐겁게 대회에 임할 수 있었습니다. 제출하고 나니 시원섭섭하고 또 홀가분하네요.
마음에 쓸데없는 거품이 낄 때마다 오늘을 돌아보려 합니다. 저는 이런 제가 너무 멋집니다 :)
- Iocane Powder (RoShamBo Programming Competition)
- 2010 Kick-bot League