하아... 드디어 대장정을 끝냈다. 전산과 2학년 전공 중에 SP(System Programming)와 함께 양대산맥을 이루는 가장 어려운 과목인 Problem Solving의 인공지능 토너먼트가 오늘 있었다. (게임 규칙은 이곳 참고) 준수, 상돈, 나로 구성된 우리팀은 이번 카포전에서 인공지능 대회 우승을 이끌었던 멤버들로 구성된 본좌팀(...)을 결승전에서 만나 아쉽게 1점 차이로 져서 2등을 기록했다.

지난 주 주말부터 조교님이 잘못(-_-) 짜신 Java Client 디버깅하느라 이틀 삽질하다 포기하고—조교님이 잘못 짜신 걸 고쳤음에도 결국 Java 소켓의 문제인 것 같다고 결론이 났지만—결국 C#으로 처음부터 아키텍처 다시 잡아서 시작, 지난 주 내내 알고리즘 설계하고 이번 주말 내내 알고리즘 구현 및 뒤집어엎기(;;)를 반복했다. 처음에는 현재 게임판의 상태만 보고 적당히 내가 다음 수를 확보할 수 있는 장소를 찾는 알고리즘을 쓰다가, 그걸 좀더 발전시켜서 내가 수를 확보하고 상대방 수를 막는 장소를, 그러다가 내가 어떤 수를 놓았을 때 상대방이 어떤 수를 놓을지 예측하고 내가 그 다음에 놓을 수가 어떻게 되며 그때의 score는 얼마가 되는지 계산하고 그 중 max값을 주는 수를 선택하는 것 등을 순차적으로 구현했다.

특히 마지막 방법은 Game Tree를 구성하는 것으로, 현재 게임판 상태로부터 내가 놓는 수에 따라 어떻게 게임이 진행될지를 미리 시뮬레이션해보는 것이라고 볼 수 있는데, recursive하게 돌리다보니 생각보다 처리 시간이 매우 오래 걸렸다. (게임 규칙으로 한 수를 놓는 데 10초 이내여야 한다는 제한이 있었음) 멀티쓰레드로 구성하여 인공지능 처리 시간이 9.5초를 넘을 경우 강제로 종료시키고 그때까지 구해진 최선의 수를 선택하도록 제한한 후 알고리즘에서 정확도는 높여주지만 시간을 많이 잡아먹는 부분을 조금 잘라냄으로써 그럭저럭 빠른 실행 속도를 구현할 수 있었다.

일단 예선 리그전에서 seed 배정 받을 때 그 본좌팀하고 맞붙지 않게 되었던 것이 운이 좋았고, 우리가 상대했던 팀들을 생각보다 쉽게(알고리즘이 중간부터 계속 꼬여서 많은 부분을 포기했기 때문에 솔직히 1승이나 하자고 했었으니까..) 이겼던 것이 도움이 되었다.

우리팀 클라이언트 화면 (Manual AI)

사실, 알고리즘에 그다지 자신이 없었기 때문에, "멋진 UI 점수" (프로젝트 홈페이지 참조)로 가산점을 받으려고 했으나, 그 본좌팀(...)에서 단 하루만에 DirectX를 이용한 3D 화면을 구현해버리는 바람에(.....) 그것도 2등으로 밀린 게 아쉬웠다. 하지만 UI 자체의 완성도나 편리함은 우리팀이 가장 좋았다고 말할 수 있겠다. 특히 AI 종류를 선택할 수 있도록 설계하여, Manual AI를 선택할 경우 블록 선택창이나 방해블록 배치, 다음 수 선택하는 것을 직관적으로 구현(마우스로 위치 잡고 클릭 가능하게 구성)했기 때문에 알고리즘 개발 과정에서 테스트할 때 큰 도움이 되었다. (다른 팀에게 이 Manual AI 부분만 사용할 수 있도록 한 버전을 공유하기도 했다) 또한 멀티쓰레드로 만들었기 때문에 GUI가 돌아가는 Main Thread, 그리고 서버 접속과 게임 진행을 관리하는 Game Thread, 거기서 파생되어 인공지능이 작동하는 AI Thread로 나누어 프로그램 안정성과 GUI 응답성을 높일 수 있었다.

어쨌든 그동안 쌓았던 각종 코딩 스킬을 총동원해본 프로젝트였고(특히 위의 그림에 나오는 것과 같은 마우스 선택 화면은 중학교 때 한창 맵에디터 만들어본답시고 삽질을 꽤 해봤던 것인지라..), 아쉽게 명예의 전당까지는 못 올라갔지만 그래도 노력한만큼 좋은 성적을 거둔 결과를 얻었다. 상당히 빡센 과목이었지만 그만큼 남는 것도 많고 알고리즘 생각하는 방법을 많이 배울 수 있었다. (그나마 ACM에서 삽질하고 숙제에서 삽질했던 것들을 기말 프로젝트로 메꿀 수 있게 되어서 다행이다 -_-)

덧. 기쁜 소식 하나 더. 영어2 Writing class에서 기말 에세이 시험 본 게 (완전 개발로 썼음에도 불구하고) 만점(..)이 나왔다. 그나저나 Reading class는 완전 본문 암기 시험일텐데...

덧2. 역시 콘로 CPU를 쓴 새 데탑이 위력을 발휘했다. 클라이언트 제작 과정에서 쓰레드 처리를 잘못하여 무한루프에 걸린 AI가 CPU를 100% 점유하는 경우가 종종 있었는데, 내 컴퓨터는 듀얼코어였기 때문에 전혀 먹통이 되지 않았지만 다른 팀원들 컴퓨터는 원격접속 상태에서 룸메한테 전화해 재부팅시켜달라고 여러번 부탁해야 했었다.