2018 삼성 육목대회 결선 후기

부산 예선을 잘 넘기고, 성능을 개선시키기 위해 많은 노력을 기울였습니다. 다행히 시간적 여유는 좀 있는 편이어서 예선때의 프로그램에서 이래저래 많이 뜯어고쳤습니다.

첫 번째로는 착수를 pair<int, int>와 pair<pair<int,int>, pair<int,int> >로 주고받던 것을 둘 다 그냥 int 하나로 만들었습니다. x와 y 좌표 각각을 5bit으로 표현할 수 있기 때문에 int 하나 안에 두어도 문제가 없었습니다. 이로 인해 x, y 좌표를 그 때 그 때마다 비트연산으로 추출해야하는 번거로움은 있었지만 그 불편함을 안고서라도 인자의 크기를 줄이는 것이 중요하다고 생각했습니다.

두 번째로는 score를 나의 점수와 상대의 점수로 분리했습니다. 이전에는 무조건 흑을 기준으로 흑이 연속한 돌을 1/2/3개 만들어내면 점수를 부여하고 백이 연속한 돌을 1/2/3개 만들어내면 점수를 제거하는 식으로 했기 때문에 나의 점수와 상대의 가중치가 1대1인 셈이었고, 내 턴이 끝나는 순간 상대의 공격이 시작되기 때문에 내 점수를 늘리는 것 보다는 상대의 점수를 줄이는 것이 더 중요한데 그것이 감안이 되지 않았습니다. 그렇기 때문에 흑의 점수와 백의 점수를 따로 저장하고 해당 착점의 점수를 계산할 때는 나의 점수 - 상대의 점수 * SCORE_FACTOR 로 비교했습니다. 가장 좋은 SCORE_FACTOR를 알아내기 위해 다양한 시도를 할 수 있으면 좋았겠지만 시간이 충분치않아 그냥 임의로 1.5로 설정했습니다.

세 번째로는 코드 상에서 STL을 전부 제거했습니다. 정렬을 위해 맨 처음에는 STL을 썼는데, 정렬해야하는 데이터가 30개가 채 되지 않기 때문에 오히려 STL을 생성하는데 시간이 더 오래걸리는듯해 그냥 STL을 제거하고 직접 $N^2$ 알고리즘으로 정렬을 처리했습니다.

Threading을 하고 싶었지만 다른걸 끝내놓고 나니 기간이 이틀정도 남았고, Threading을 짜다가 엉켜서 그냥 포기했습니다.

올해도 작년과 비슷하게 적절한 evaluaton을 통한 Minimax Tree로 프로그램을 만들었습니다. alpha-beta pruning은 하지 않았습니다. 다만 작년 프로그램과의 가장 큰 차이는 이전의 계산 결과를 Memoization하는 것입니다. 자세한 설명은 아래와 같습니다.

편의상 breadth = 4, depth = 3라고 해봅시다. 작년에는 내가 흑이라고 가정할 때 현재 보드에서 내가 둘 곳을 찾기 위해 후보군 B1,B2,B3,B4를 생성하고, B1에 대한 상대의 대응수 W11,W12,W13,W14, B2에 대한 상대의 대응수 W21,W22,W23,W24, B3에 대한 상대의 대응수 W31,W32,W33,W34, B4에 대한 상대의 대응수 W41,W42,W43,W44를 찾았을 것입니다. 그리고 W11~W44에 대한 나의 대응수 또한 계산을 해볼 것입니다.

이후 나는 B2를 선택해 착수했다고 하고, 상대는 W23을 착수했다고 해봅시다. 그렇다면 W23에 대한 나의 대응수는 이전에 계산을 해두었지만 작년의 제 코드는 계산을 Recursion으로 수행하면서 결과를 return만 받을뿐, 이전의 계산 결과를 따로 저장해두지 않았기에 이전에 했던 연산을 이번 턴에 다시 해야합니다. 그러나 올해의 제 코드는 이 과정들을 Tree로 만들어두었기 때문에 했던 연산을 또 할 필요 없이 이전에 했던 연산의 결과로부터 확장을 해나갈 수 있습니다. 구현은 MinimaxTree 클래스와 Node 클래스를 만들어 OOP 스타일로 했습니다.

Breadth = 7로 두었고, 처음에는 대략 6-7수 정도를 볼 수 있습니다. 그리고 경기가 진행됨에 따라 memoization한 곳을 계속 상대가 건들여주면 최대 8-9개의 수 정도까지 따라들어갑니다. 자세한 원리는 다음에 시간이 나면 아예 게시글을 따로 만들어서 길게 글을 써볼까 합니다.

작년의 프로그램이 있어서 아예 밑바닥에서 쌓아올리는 것에 비하면 조금 더 편하게 개발을 하긴 했지만 그럼에도 불구하고 OOP 스타일로 아예 갈아엎은 것이나 마찬가지였기 때문에 작년보다 오히려 개발기간이 더 길었던 것 같습니다. 만들면서 가장 힘들었던 점은 디버깅이 너무나 어렵다는 점이었습니다. 두다가 오류가 발생했을 경우 그 원인을 탐색해야하는데 외부 의존적인 프로그램이라 중간값을 확인하는게 불가능에 가까워서 오류가 어느 함수에서 발생했는지를 찾는게 너무 힘들었습니다. 이를 해결하기 위해 로그를 파일 입출력으로 계속 남기면서 진행하긴 했지만 오류가 생길 때 굉장히 당혹스러웠습니다.

아무튼 대회날이 되어서 9시까지 양재역으로 갔는데 좀 피곤했습니다. 거기서 버스를 타고 회사로 갔습니다. 가서 왕중왕전 진행 방식을 듣고 3개의 그룹으로 나눠져서 작년과 비슷하게 각 사업부에서 오신 멘토님들과 얘기를 나눠볼 수 있는 시간을 가졌습니다. 취업이 아직 많이 멀게 느껴지긴 했지만 그래도 회사가 어떻게 굴러가는지, 개발자로서 어떤 역량을 가지고 있으면 좋은지 등을 들을 수 있었습니다. 밥을 먹고 나서는 우선 예선전을 진행했습니다. 총 지역별로 4팀씩 총 16팀 중에 2팀은 불참해서 14팀이 참석했고, 7팀씩 2조로 예선전이 진행되었습니다. 예선은 단판승부였는데 전승으로 통과해서 신기했습니다.

본선부터는 토너먼트로 진행이 되었고 동일한 블록 배치에서 흑/백을 번갈아하며 2경기를 진행하고 1승 1패가 나온다면 블록이 없는 배치에서 흑/백을 가위바위보로 정해 마지막 경기를 하는 방식이었습니다. 블록의 배치에 따라 흑과 백의 유불리가 심각하게 달라진다는 점을 고려할 때 예선보다 공평한 룰이라고 생각합니다. 그렇지만 작년에 비해 블록의 배치가 훨씬 큰 영향을 주게끔 룰이 변경되었음을 감안할 때 3판 2선승보단 5판 3선승 정도는 해도 괜찮지 않았을까 싶긴 했습니다.

토너먼트 조를 나눌 때 예선 순위와 무관하게 나누어 하필 다른 조의 1위 팀과 4강에서 맞붙게 되는 대진표라 조금 걱정을 했습니다만 다행히도 8강 4강 결승 모두 2승 1패로 간신히 우승을 했습니다. 블록의 배치가 선수 혹은 후수에 많이 유리한 쪽으로 나와서 동일한 블록 배치에서 1승 1패를 기록한 것일지, 아니면 제 프로그램이 상대 프로그램에 비해 월등히 강력하지는 않아서 1승 1패를 기록한 것인지는 잘 모르겠습니다.

확실히 '자신이 없어요. 질 자신이요'라고 패기 넘치는 인터뷰를 지르고 예선, 본선 모두 전승우승을 했던 작년에 비해서는 다소 약한 모습을 보였습니다. 우승에 운도 좀 따른 것 같습니다. 다른 분들의 프로그램의 수준이 많이 올라왔던 것 같습니다. 그래도 작년 올해 모두 1인팀으로 우승한 것은 정말 엄청난 성과라고 생각합니다. 상금 혼자 맛있게 독식할게요 ><

작년에 만났던 분들과 인사도 많이 나누고, 회사 소개도 받고 좋은 시간이었습니다. 우승한 것도 좋았고요. 내년에도 대회 열어주신다면 열심히 참가할게요!!