PS 인공지능 프로젝트 끝!
- Posted at 2006/12/12 20:03
- Filed under 컴퓨터
하아... 드디어 대장정을 끝냈다. 전산과 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% 점유하는 경우가 종종 있었는데, 내 컴퓨터는 듀얼코어였기 때문에 전혀 먹통이 되지 않았지만 다른 팀원들 컴퓨터는 원격접속 상태에서 룸메한테 전화해 재부팅시켜달라고 여러번 부탁해야 했었다.
- Tag
- CS202, KAIST, PS, 문제해결기법, 인공지능, 토너먼트
- Response
- No trackback yet , 15 Comments
- RSS :
- http://daybreaker.info/blog/rss/response/547
Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다
Comments List
-
그네고치기 2006/12/12 22:58 # M/D Reply Permalink
수고하셨습니다. m(_._)m
-
daybreaker 2006/12/13 12:30 # M/D Permalink
고맙습니다.;
-
-
Yuyudevil 2006/12/12 23:44 # M/D Reply Permalink
원래 그런 에세이들은 발로 써야 좋은 점수가 나온대요 =3
(그런데 날뷁옹은 정말 발로 쓰셨을까요?)-
daybreaker 2006/12/13 12:30 # M/D Permalink
정말 발로 썼어요;; 오후 5시 넘어서 시작한 거라 배가 고파서 머릿속에서 아무것도 안 떠오르는 상태에서 억지로 쥐어짰거든요-_-
-
-
코카스 2006/12/12 23:50 # M/D Reply Permalink
본좌팀은 멀티쓰레드 안 써도 충분하다고 하면서 그냥 꺼버렸죠. 본좌팀도 메모리, CPU 줄이려고 각종 최적화 기법을 많이 썼는데 무지막지한 bitwise 연산들과 loop-unrolling을 비롯한 컴파일러 최적화 옵션 먹이기 등등이 있었습니다. 옆에서 소식을 많이 들어서..
축하드려요. :)-
daybreaker 2006/12/13 12:31 # M/D Permalink
저도 컴파일러 최적화 옵션을 먹일까 했는데 C#은 의외로(?) 옵션이 별로 없더라는.. -_-; (오버플로 검사 이런 거 빼볼까 했는데...)
bit연산까지 쓸 생각은 못해봤군요.;
-
-
진실's 2006/12/13 01:30 # M/D Reply Permalink
우아 축하해!
니 글을 보니까 PS 안 듣길 정말 잘했다는 생각이 들어..
고수들의 세계인 것이냐!-
daybreaker 2006/12/13 12:31 # M/D Permalink
그래도 이게 다 뼈가 되고 살이 되는(?) 것이야.;
-
-
Neon 2006/12/13 09:42 # M/D Reply Permalink
아니 Time cut을 멀티쓰레드로 구현하면 님하 그건좀 수준인데...
-
daybreaker 2006/12/13 12:34 # M/D Permalink
뭐, 전부다 클래스화해서 짠 데다 private 멤버변수로 주기적으로 결과값을 저장하게 해놓고, property 형식으로 받아오게 했더니 join 써서 간단히 해결되던데요? ;; (C++이 아니라 C#이라 언어적으로 lock 구조 등을 지원해서 보다 쉬웠음) 알고리즘에서 루프 돌면서 매번 tick count 계산하는 것보다는 차라리 쓰레드 join시키는 게 훨씬 효율이 낫지 않을까요;
-
Neon 2006/12/14 19:44 # M/D Permalink
CPU가 context switch+job scheduling하는데 드는 비용을 생각하면 외부에서 join하는게 빠를거라고는 동의 못하겠는데... lock 체크하랴, context switch하랴. 단순히 틱 계산하는것보다는 훨씬 로드가 큰 작업들이지; 상위 언어에서 한줄로 지원하는 기능이 알고보면 시간 잡아먹는 괴물이라던가 하는 경우 많아...
-
daybreaker 2006/12/15 02:25 # M/D Permalink
흠..
근데 어차피 context switch는 프로세스 사이에서만 이루어지는 거고 스레드 사이에서는 그 전환 cost가 매우 작지 않던가요? 게다가 priority 설정 같은 걸로 인공지능 스레드가 더 많은 cpu 시간을 잡아먹게 한다든가.. (그러면서 다른 것이 blocking되게 하지 않는..) 무엇보다도, 싱글스레드로 프로그램을 짰다고 해도 어차피 다른 스레드로의 전환은 운영체제가 해버릴 텐데, 멀티스레드로 짰다고 해서 특별히 효율이 떨어질 것 같진 않습니다. (Join 메소드 자체의 오버헤드가 얼마나 되는지는 모르겠지만, 생각만큼 클 것 같지는 않네요) 그리고 알고리즘 자체는 싱글스레드였기 때문에 lock에 의한 성능 저하는 없었습니다.
그리고 제가 프로그램을 짤 때 인공지능이 돌아가는 동안은 다른 스레드에서 할 일이 거의 없도록 해놨기 때문에 틱만 계산하는 것과 별다른 차이는 없을 거에요. 저는 일단 프로그램이 백지(..)되는 걸 원치 않았기 때문에..-_-
-
-
Neon 2006/12/18 23:09 # M/D Reply Permalink
이론적으로 동의하지 못하겠다면 실험을 해보는 수밖에 -_-; 그리고 멀티쓰레드는 디버거 사용이 꽤나 불편하지 않나 하는 생각도.
-
daybreaker 2006/12/18 23:25 # M/D Permalink
흠.. 실험을 한다고 해도 어차피 오차 범위 밖에서 수십 ms 이상 차이나지는 않을 것 같습니다만.. 정 원하신다면 시험 끝나고.. (....)
참고로 저거 디버깅은 전혀 어렵지 않았어요. 막강한 Visual Studio의 디버깅 기능으로 아주 편하게...(...) 리눅스에서 gdb로 멀티스레드 디버깅해봐서 알지만 거의 천국과 지옥 차이는 나는 같군요.;;;
물론 내부적으로 메모리가 꼬이기 시작하면 그때부터는 힘들어집니다만(예전에 VB.NET으로 IRC 봇 만들 때 여러 스레드에서 쓰는 오브젝트를 lock 제대로 안 걸어주니까 중간에 증발해버리는 현상이 나타난 적이 있었습니다-_-) 말씀드렸다시피 알고리즘 자체는 싱글스레드였기 때문에 lock이 전혀 없었고 따라서 멀티스레드에 따른 어려움은 전혀 없었습니다.
제가 멀티스레드를 사용한 것은 순전히 아키텍처 관점에서, GUI 응답성 확보 관점이었을 뿐, Timeout Join을 호출한 쪽에서 사용한 것 외에는 알고리즘에서 멀티스레드 프로그래밍 요소가 들어있지 않기 때문에, 새 스레드를 하나 만들어서 Join을 해서 기다리는 동안 그 스레드가 실행되는 시간과 그냥 현재 스레드에서 작업을 수행하는 것과의 차이 외에는 발생하지 않을 겁니다. (프로그램이 먹통되지 않게만 했을 뿐 알고리즘이 돌아갈 때 메인스레드를 쓰는 GUI를 사용한다는 전제는 없었으니까요.)
무엇보다도 저는 아주 significant한 성능 저하나 문제 해결에 critical하게 방해가 되는 것이 아니라면, 가능하면 프로그래머가 편하게, 직관적으로 짤 수 있도록 하는 방향을 선호합니다. 이에 대한 관점은 사람마다 차이가 있을 수 있겠죠. 하지만 적어도 PS 프로젝트로 인공지능을 돌리는 데 있어서 저 정도의 성능 저하(가 있었다면)는 충분히 감수할 만한 가치가 있었다고 생각합니다. 그만큼 팀원들이 생소한 언어에서 AI에 편하게 접근할 수 있었고, 분명하게 용도가 분리된 클래스와 설계로 편하다는 얘기를 했었으니까요. (여러 명이 프로그래밍을 했기 때문에 서로가 서로의 코드를 모르는 채 완전하게 돌아가려면 클라이언트 기반을 짠 제가 팀원들이 다른 부분과 상호작용을 고려하지 않고 AI만 짤 수 있도록 하는 게 가장 좋겠죠.)
-
-
익룡ㅋㅋ 2006/12/19 22:56 # M/D Reply Permalink
으헉 ㅎㄷㄷ;;
이거 문제해결기법 그 과목인가요?
무서워라 ㅡㅡ