둘째날은 인공지능 대회가 있는 날이었다. 이번에 했던 게임은 비주얼드를 변형하여 커서와 방해블록 개념이 추가된 형태였다. 또한 기존 비주얼드 게임[footnote]Bejeweled. PopGames 참조.[/footnote]은 두 블록을 맞바꿨을 때 없어지는 블록 조합이 있어야 바꿀 수 있지만 이 게임은 그런 제한이 없었다. (따라서 의도적으로 연쇄 제거를 만들기 위해 미리 판의 상태를 바꾸도록 할 수 있다)

뭐, 대략적인 게임 화면은 아래와 같다. 작년인가 ESCamp 및 카포전 인공지능 대회에 참여했던 상위 랭킹 학생들이 만든 서버-클라이언트 프레임웍을 이용해 개발된 것이다.

UPNL팀이 만든 AI 동작 화면

팀 구성은 서울대, 포항공대, KAIST 사람들을 한 명씩 섞어서 3명씩 조를 만드는 방식이었다. 나는 포항공대 04학번 송종혁 형(한살 위)과 서울대 06학번 김은솔 양(동갑)과 함께 팀이 되었는데, 은솔은 알고리즘을 짜는 아이디어는 있었지만 구현을 못한다고 해서 종혁이 형과 내가 다 짜게 되었다. 우선 기본으로 주어진 simple AI와 같이 당장 없앨 수 있는 조합을 찾아서 처리하는 것을 만들고, 한 수를 놓았을 때의 판 상황을 시뮬레이션하는 것과 이를 바탕으로 game tree[footnote]게임 AI 프로그래밍을 할 때, 내가 어떤 수를 놓았을 때 상대방이 어떤 수를 놓을지, 또 그에 대해 어떻게 대응하는 수를 놓을지, 또 그에 대한 상대방의 반응 등을 적절한 평가함수를 통해 예측하여 각 게임 진행과정을 모두 시뮬레이션해보고 가장 좋은 점수를 얻은 경로를 따라 게임을 진행하는 방식이다. 트리의 depth가 깊어질수록 더 멀리까지 내다보게 되지만 연산량이 급격히 증가하는 경우가 많아 최적화를 하지 않는다면 3~4 depth까지 하는 것이 보통이다. 이번 게임의 경우는 번갈아 가며 수를 놓는 방식이 아니라 같은 판으로 시작하여 동시에 실시간 진행을 하는 방식이라서 의미가 조금 다르기는 하다.[/footnote]를 구성하여 평가함수를 통해 최적의 수를 찾아내는 방식으로 만들기로 했다. 그러나 3년째 ESCamp에 참가한다는 형의 조언에 따라 우선 형은 없앨 수 있는 조합을 찾아내는 것을 먼저 완성하기로 했고, 나는 그것과 동시에 같은 기능을 짜고 시간이 허락하면 게임트리를 짜기로 하였다. (사실 하다보니 그렇게 되었다 -_-) 즉, 단시간 내에 구현해야 하므로 너무 완벽하게 짜려고 한다면 아주 실력이 좋지 않은 이상 돌려보지도 못할 가능성이 높다는 것이었다. (실제로 작년 ESCamp에서 우승했던 민종이형의 경우 multithreading을 시도하다가 꼬이는 바람에 기권하고 말았다. -_-)

오전 11시쯤 게임 규칙 설멍을 듣고 코딩을 시작했고, deadline은 오후 8시였다. 문제는, 일단 나와 형 모두 C++에 익숙하지 않았다는 것과, MYTRACE라는 매크로를 이용하여 별도의 디버거 프로그램으로 디버깅 메시지를 출력하는 방법을 제대로 몰라 한참 동안 간단한 버그로 삽질했다는 것, 그리고 내가 평소에 행렬 기반의 알고리즘을 짤 때 사용하는 좌표계(배열의 1차원 index가 x좌표이고 2차원 index가 y좌표인...)와 프레임웍에서 사용된 좌표계가 반대라서 헷갈렸던 것, 그리고 일정 시간 간격으로 호출되는 Action 메소드를 통해 코딩해야 하면서도 모든 오브젝트가 매 호출시마다 새로 생성되기 때문에 별도의 static value들이 보관되지 않는다는 프레임웍 특성을 몰라 삽질했던 것 등으로 초반에 시간을 너무 많이 보냈다는 것이다. Simple AI와 비슷한 수준을 구현하고 나니 오후 5시가 넘었다. 그러나 종혁이 형은 boundary 검사를 잘못해서 발생한 불규칙적인 메모리 오류로 또 한참 삽질하고, 나는 게임트리로 변환하기 위해 코드를 리팩토링하다가 꼬여서 바꾼 블록을 다시 제자리로 되바꾸는 무한 루프에 빠져서 결국 헤어나오지 못했다. (다른 팀에서도 그런 무한 루프가 많이 있었는데 일부는 어찌저찌해서 랜덤하게 탈출하도록 만들기도 했다)

그래도 대진운(?)이 있었는지 부전승, 종혁이 형의 AI 1승으로 8강까지 갔으나 결승진출팀을 만나 5초만에 방해블록이 꽉 차 개관광 당하는 것으로 끝났다. -_-; (이 게임에서 하나의 조합을 없애고 나서 생기는 판의 변경 후 없어질 수 있는 조합이 있을 경우 연쇄가 일어나는데, 이 연쇄 횟수에 따라 점수는 제곱으로 증가하고 상대방 판에 놓아지는 방해블록 개수는 점수에 비례해 증가한다. 따라서 연쇄를 얼마나 빨리 만들어내는지가 관건인데, 우리팀이 1연쇄 정도 만들 동안 그 팀은 6연쇄 만들어서 터뜨림으로써 한 방에.....orz)

결승전 장면. 두 팀의 실력은 비슷하지만 한 번 저렇게 당하고 나면 속수무책이다. -_-

어쨌든 AI 대회는 그렇게 끝났다. 몇 가지 아쉬웠던 점이라면, 코딩스킬이 높은 사람들(특히 ACM ICPC 쪽에서 두각을 보인 분들)와 다른 사람들의 격차가 너무 커서 대부분의 팀이 1사람이 코딩하고 나머지는 구경하거나 전략 보조 정도만 하게 된다는 것, 그리고 잘못된 http 요청을 받으면 out of memory를 뱉고 뻗어버리는 프레임웍의 패킷 검사 버그로 인한 대회 진행 차질이다. (그나마 토끼군이 netstat을 해보라고 해서 겨우 찾아내었다) 프레임웍 코드 자체가 그다지 깔끔하지 않았던 데다가 다른 사람들이 짠 코드를 조금씩 고쳐서 쓴 거라 그런 버그 발생 소지가 더 높았다. (차라리 프레임웍을 새로 만들고 싶었지만 그 또한 삽질이라... -_-)

이 대회를 통해 다른 학교 사람들도 좀 사귀고, 색다른 프로그래밍 경험도 쌓을 수 있어서 좋았다. 역시 경시대회 준비할 때처럼 단시간 내에 주어진 문제를 푸는 훈련이 어느 정도 되어야 이런 인공지능 대회에서 성과를 거둘 수 있는 것 같다. (PS 기말 프로젝트는 시간이 충분히 주어졌기 때문에 토너먼트 2등을 기록할 수 있었다)