세계적으로 유명한 AI대회인 CodinGame의 2022 Fall Chanllenge에 42seoul소속으로 참여하게 되었습니다. 42에서는 CodinGame의 데이터를 토대로 42를 대상으로하는 대회를 따로 열었는데, Amsterdam의 Codam 캠퍼스와 함께 랜덤으로 국제팀을 결성하여 3인 구성인 여러 팀을 만들어 대회를 진행하고 그들 중 가장 순위가 높은 인원에게 우승의 자격을 부여하는 것이었습니다.
팀원과의 소통
저희 팀은 같은 한국인인 minsuki2님과 저 그리고 네덜란드 codam 소속인 fras님이 한 팀 이었는데, 어떻게하면 멀리 떨어져있고 시차 8시간 이상 차이가 나는 다른 팀원과 함께 소통을 이어가고 효율적으로 진행해야할지 고민이었습니다.
대회는 3일이라는 그리 넉넉하지 않은 기간동안 진행되기도 하고 언어적인 부분이나 시간적인 부분 때문에 여러 소통하기 쉽지않은 상황때문에 코딩 전략과 룰 구성은 ZOOM 미팅을 통해 미리 정하고, 레포리토리를 하나 생성하고 최대한 코드를 공유하며, 알고리즘 전략은 파트를 나눠 구성하자는 결론을 내렸습니다.
하지만 팀플레이인만큼 소통이 중요성을 무시할 수 없기에, 서로의 배려를 통해 우선 최대한 밤낮을 어느정도 바꿔서 최대한 서로의 시차를 줄이기로 하였습니다.
이에 따라 시간을 일정을 맞출 수 있게 되어 룰숙지와 소통은 zoom을 통해 함께 학습하였고, 팀원의 부재 시 전달해야할 사항이나 변경사항은 git issue를 통해 공유하여 진행 상황을 빠른템포로 동기화할 수 있도록 계획하였습니다.
---
대회 룰
대회의 룰은 아래와 같은 룰과 규칙들이 열거되어 있었는데, 주요한 승리의 키 포인트는 200턴 내에 중립타일에 해당하는 타일을 최대한 많이 점령하여 적의 타일보다 자신의 타일을 더 많이 남기면되는 것입니다.
게임은 여러가지 역할을하는 오브젝트들이 있는데 크게 타일, 재생소, 유닛, 자원으로 나눌 수 있습니다.
타일은 중립, 불가침지역(grass), 적타일, 본인타일 이렇게 총 4가지 종류가 있고 grass와 특정 조건 타일을 제외한 모든 비어있는 타일은 유닛이 들어갈 수 있습니다.
유닛은 1칸 씩 움직일 수 있는 한 가지 종류만 있지만 타일에 여러 개의 유닛이 겹쳐져 서있을 수 있습니다. 유닛은 고유하게 타일을 점령할 수 있는 특성을 가지며, 본인의 유닛이 타일에 들어가면 타일의 색이 본인의 색으로 변경됩니다.
유닛은 상대편 유닛이 서있는 타일 또한 진입할 수 있는데, 상대방의 유닛과 유닛이 겹칠 경우, 유닛의 수 차이만큼 서로의 유닛이 사라지며 많은 수의 유닛이 있는 쪽이 타일을 점령할 수 있습니다. (같다면 둘다 사라짐)
재생소는 본인의 타일에만 지을 수 있고 주변땅에 놓여있는 자원(Matter)을 파밍하는데, 파밍이 된 지역은 grass로 변경이 됩니다. 재생소가 지어진 타일 또한 유닛이 지나갈 수 없습니다.
자원(Matter)을 파밍하는 이유는 유닛과 재생소를 생성하려면 10Matter씩 비용이 요구되기 때문입니다. (매턴이 지날 때마다 기본적으로 10scrap씩 지급받음)
실제 게임 영상
작업 진행 과정
첫째날 - 황혼에서 여명까지
대회가 시작되었을 때, 처음보는 형식의 코딩에 대회가 돌아가는 시스템 자체가 어색하여 많이 당황했습니다. 대회가 시작하기 전 codingame사이트에서 직접 코딩했을 때는 난이도가 기초적이어서 무난하게 대회를 진행해나갈 수 있을 거라 생각했는데, contest는 입력데이터만 자동적으로 주어지고, 나머지 전략은 알고리즘을 직접 개발하여 적용하는 시스템이었습니다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/**
* Auto-generated code below aims at helping you parse
* the standard input according to the problem statement.
**/
int main()
{
int width;
int height;
cin >> width >> height; cin.ignore();
// game loop
while (1) {
int my_matter;
int opp_matter;
cin >> my_matter >> opp_matter; cin.ignore();
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int scrap_amount;
int owner; // 1 = me, 0 = foe, -1 = neutral
int units;
int recycler;
int can_build;
int can_spawn;
int in_range_of_recycler;
cin >> scrap_amount >> owner >> units >> recycler >> can_build >> can_spawn >> in_range_of_recycler; cin.ignore();
}
}
// Write an action using cout. DON'T FORGET THE "<< endl"
// To debug: cerr << "Debug messages..." << endl;
cout << "WAIT" << endl;
}
}
룰 또한 영어로 되어있고 게임의 방식이 생소하던 탓에 언어의 장벽이 없는 코드로 게임에 적응해보자라는 생각으로 스타터 킷을 통해 구조의 틀을 잡고 룰의 이해를 위해 코드를 수정하고 기능을 생성해보며 게임의 본질을 이해하려 노력했습니다. 전략의 검증을 위해 각자의 코드를 가지고 AI와 대결을 통해 지속적으로 검증하였습니다.
대회 첫날은 룰을 이해하기에 바빴고 5 ~ 6시간이 지나서야 알게되는 개념이 있을 정도로 무작정 코드를 작성했던 것 같습니다. AI와 대결을 하면 항상 지고 어쩌다가 한번씩 운 좋게 이기면 너무 기쁜마음에 팀원과 내적댄스를 추곤했습니다.
좋은 전략이 나오면 서로서로 코드를 병합하는 식으로 알고리즘을 발전시켜 나갔지만 등수는 700명중 400등을 할 정도로 결과가 처참했습니다.
첫번째 날에서 두번째 날로 넘어가는 새벽녘에 이대로는 되지 않을 것 같다며, 전략을 수정해보자는 의견이 나왔습니다. codingame에 참가하는 인원들 중 상위 순위에 있는 팀들의 알고리즘을 분석하여 우리의 코드에 적용하자는 의견이었습니다. 그렇게 총 3가지의 핵심 전략이 구성되었습니다.
- 본진의 위치를 파악하여 상대방의 위치로 최대한 빠르게 접근하자.
- 자원 생성을 위한 재생소를 자신의 타일에 남발하여 짓는 것은 영역을 유지하는데 오히려 불리하기에 유닛의 진로를 막는 특성을 이용하여 적 유닛이 넘어오는 것을 방어하자.
- 유닛생산을 적 유닛과 맞닿은 위치에서만 담당하여 생산하여 불필요한 자원낭비를 방어하자.
- 목표위치에 도달 후 BFS로 검색하여 점령되지 않거나 뚫려있는 적타일 탐색
둘째날 - 리바이어던
클러스터에서 컨디션을 위해 쪽잠을 잔 뒤, 계획했던 수정안을 적용하여 플레이를 돌리기로 하였습니다. 2번 안을 우선적으로 수정하여 적 유닛이 우리의 타일에 진입을 시도하려할 때 방어를 해주었는데, 놀랍게도 기존 돌격성 코드에서 방어형 시스템인 2번안을 추가한 것만으로도 등수가 확 올라갔습니다.
가림막 추가 빌드
하지만 여전히 AI를 이기기에는 역부족인 상태였기에 1번 3번 전략을 재빨리 추가하고자 하였습니다.
1번 전략에서 가장 중요한 것은 어떻게 유닛을 랜덤한 지형에서 빠르게 원하는 위치로 접근시킬 것인가 였습니다. 처음에 계획했던 것은 무조건 맵의 중간을 도달하는 방식이 었으나, 맵의 중간을 목적지로 설정할 경우 적이 맵보다 가까운 상황일 때 우리의 본진이 쉽게 뚫린다는 약점이 있었습니다.
위치의 높이가 같은 대칭형태는 같은 거리여서 적과의 경계가 중간을 이룸
높이가 다른 대칭형태일 경우는 비율에 맞는 경계선을 다시 계산해주어야함
그리하여 기존 이동방식을 대폭 수정하였고 적의 진영과 우리의 진영 코드의 경계값을 계산하여 가장 양옆 쪽의 유닛들이 우선적인 핵심 지역 선점을 통해 지형적 유리함을 가져갈 수 있도록 수정하였습니다.
경계값 수정 전 코드
경계값 수정 후 코드
1번 2번이 성공한다고 하여도 적도 마찬가지로 비슷한 전략을 들고 나오던지 재빠른 경로탐색으로 우리보다 먼저 도착하게 된다면 유닛들은 유닛간의 경쟁을 통해 타일을 취득해야 하기에 여러 곳에 분산된 병력을 전방에 모을 필요가 있었습니다. 우리의 경계가 허물어져 오히려 반대로 함락당하는 결과가 생겼습니다.
전방 유닛의 스폰
if ((abs(opp_unit.x - my_unit.x) <= 1 && abs(opp_unit.y - my_unit.y) <= 1)
&& !(abs(opp_unit.x - my_unit.x) == 1 && abs(opp_unit.y - my_unit.y) == 1)) {
for (vector<Tile>::iterator it3 = neutral_tiles.begin(); it3 != neutral_tiles.end(); ++it3) {
const Tile& neutral_tile = *it3;
if (my_unit.checkLength(neutral_tile) <= 1.0f) {
amount = opp_unit.units > amount ? opp_unit.units : amount;
}
}
std::cerr << "enenmy : " << amount << endl;
}3번 전략에 따라 적과 가장 가까운 유닛인 경우에만 우선적으로 유닛을 생산하도록 유도하여 적과의 수싸움에 유리함을 선정한 결과, 유저들이 지속적으로 유입되어 1400명 가량음에도 불구하고 최고 순위 8위에 도달하는 쾌거를 이루었습니다.
셋째 날 - 또 다른 성장
현재 알고리즘은 나름 좋은 순위를 거두고 있지만, 여러 모로 문제가 많이 있었습니다. 가장 큰 단점은 필승하지 못하다는 단점입니다. 대부분의 케이스에 유리한 전략이지 필승하는 전략은 아니었기에, 낮은 순위를 가진 유저와의 싸움에도 간혹 패배를 하여 순위의 변동이 생기기 시작했습니다.
그리하여 다시 팀원과 모여 회의를 하기 시작하였습니다. 현재 코드를 수정하면 현재의 순위를 유지하는데, 도움은 되겠지만 궁극적으로 무결하지 못하기에, 남은 시간동안 완벽에 도전해보자라는 의지를 다지고 현재의 코드를 잠시 뒤로한채 다시 설계를 하기로 결정하였습니다. 전략을 다시 세팅하고 코드를 작성하였지만 대회의 시간이 부족하여 완벽하게 구현하여 아쉽게도 적용시키진 못했습니다.
필승을 가져가는 저희의 전략은 이러했습니다.
- 타일의 갯수로 승리를 하는 게임의 특성상 49대 51의 승리 또는 무승부를 하는 것이 변수 없이 순위를 올리는 방법으로 판단
- 경계면을 DDA알고리즘을 통해 직선을 생성 한뒤, 적과 정확히 동등하게 타일을 가져갈 수 있는 위치를 파악한다. (적과 우리의 이동속도는 같기 때문에, 알고리즘구성을 잘한 상위권 팀은 우리와 무조건 무승부할 수 밖에 없다.)
- 만약 적이 경계면에 늦게 도달할 경우 유닛을 전진 배치하여 유리한 상태를 만든다.
대회의 마무리
국제적으로 참여한 첫 대회이자 모든게 낯설었던 상황이었지만 다행히도 최종 순위 36/2,333이라는 좋은 결과와 42seoul X codam 순위 1등, 학장상까지 수상할 수 있었습니다.
이렇게 좋은 마무리를 할 수 있었던 배경은 배정받은 팀원분이 훌륭하셨던 것도 있지만 42에서 학습해오면서 지금까지 경험했던 모든 과제, 프로젝트들이 큰 도움을 줬다고 생각합니다.
코드를 짜는 법 뿐만아니라 팀원과 소통을 해나가며 문제를 해결해나가는 방식, 철저한 코드 리뷰 방식, 협업하는 법 등 지난 2년간 배웠던 것이 다시 검증되는 느낌이라 대회를 진행하면서 즐거운 마음만이 가득했던 것 같습니다.
도움을 주신 모든 분과 도움 받은 모든 것에 감사합니다.
