이 경기의 목적은 MS Pac-Man(이하 미스팩맨) 게임을 위한 최고의 소프트웨어 컨트롤러를 제공하는 것이다. 크게 보면 3가지 정도의 이유에서 계산지능, 머신러닝, 그리고 대부분의 AI 분야에 있어서 큰 도전이라고 볼 수 있다.

1. 4마리의 무작위적인 움직임을 보이는 유령
2. 67 msec 라는 짧은 응답시간
3. 게임 엔진으로 부터 참고할만한 환경 정보를 얻기 어려움

일반적인 팩맨 게임과 달리 미스팩맨은 비 결정적인 게임이고, 때문에 일반적인 사람의 경우에도 더 어렵게 느껴지는 편이다. 이러한 게임을 위한 AI 플레이어를 개발하는 것이 정확히 어느정도나 어려운지는 아무도 알 수 없다. 기존의 아케이드 버전에서 사람이 세운 세계 기록은 933,580 점인데, 이 기록을 깰 수 있는 소프트웨어 컨트롤러를 만들어낼 수 있다면 대단한 성과를 거둔 것으로 볼 수도 있겠다.

미스팩맨 경기는 인공지능 워크샵에서 컴퓨터 기반 플레이어들의 능력을 시험 할 것이다. 이 워크샵에서는 특히 계산 지능 방법으로 문제를 해결하려는 플레이어들에게 관심을 두고 있지만, 어떠한 형태의 알고리즘이라도 경진 대회에 참여 할 수 있다.

이 게임의 상호작용 방식은 스크린 캡쳐된 정보에 기반하여 이루어 진다. 게임 윈도우를 캡쳐하여(초당 15회 정도) 그 정보를 분석하고, 이것에 정수로 된 방향을 입력해줌으로써 작동한다.

미스팩맨 게임은 그 이름에서 알 수 있듯이 사용자가 컨트롤 할 팩맨의 성별이 여성인 게임이다. (머리 위에 빨간색 리본을 달고 있다.) 게임 화면은 하얀색 알약과 벽, 그리고 4마리의 색이 서로 다른 유령이 미스팩맨을 잡기 위해 돌아다니고 있다. 그리고 이따금씩 랜덤하게 맵 상에 과일이 나타나는데 이 과일을 먹게 되면 추가점수를 얻을 수 있다. 또 알약중에 그 크기가 다른 알약과 다른 4가지 알약이 있는데, 이 알약을 미스팩맨이 먹게 되면 일정 시간동안 유령들을 습격할 수 있으며, 이 시간에 많은 유령을 습격하면 습격할 수록 더 많은 점수를 얻을 수 있다. 하지만 일반적인 상태에서 유령과 만나게 되면 주어진 생명이 하나씩 줄어들게 되고 이 생명을 모두 소비하게 되면 게임오버가 된다.

한 스테이지의 클리어 조건은 맵상에 존재하는 알약을 미스팩맨이 모두 먹었을때 끝나게 되며, 1만점의 점수를 얻을 때 마다 한 개의 생명을 더 얻을 수 있다.

경진대회에서 우승자를 가려내는 방법은 간단하다. 게임을 세 번까지 도전하여 최고 점수를 달성한 프로그램이 우승자가 되는 방식이다. 경진대회에 이용될 게임 버전은 두가지 인데, 어느것을 사용하여도 상관 없다. 하나는 위의 스크린샷에 나오는 마이크로소프트 리벤지 오브 아케이드의 Ms Pac-Man 게임이며, 또 하나는 웹 버전의 게임으로 http://www.webpacman.com/ 에서 Ms Pac-Man 게임을 선택하면 된다.

경진대회에 나가게 될 프로그램은 게임 윈도우의 화면 픽셀을 여러번 캡쳐하고 키보드 이벤트를 Ms Pac-Man을 제어하기 위해 발생 시켜야 한다. 하지만 게임의 속도가 현저하게 느려지게 한다거나 하는 일을 하게 된다면 대회에서 실격당하게 된다.

참가방법은 완성된 소프트웨어와 그 소프트웨어를 어떻게 실행하여야 하는지, 그리고 어떤 방식으로 작동되는지를 간단하게 서술한 문서를 함께 첨부하여 Simon Lucas(sml@essex.ac.uk)에게 메일로 전송하면 된다.

올해 IEEE CIG 2011 Ms Pac-Man 경진대회의 참가 엔트리에 이름을 올릴수 있는 마감기한은 7월 31일 까지이다. 이 기한까지 작성된 엔트리 중에서 가장 좋은 성적을 낸 5팀이 결승을 치르게 된다.

우승자를 가려내는 방법은 아주 단순하다. 정해진 횟수만큼 게임을 실행시켜서 가장 높은 점수를 내는 팀이 우승을 거머쥐게 된다. 제출된 컨트롤러들은 결승이 치뤄지기 전에 각각 10번씩 게임을 플레이하고 이들 중에 가장 높은 점수를 낸 다섯개의 팀이 결승을 치르게 된다

결승에서도 5개의 팀이 3번씩 게임을 플레이하고 모두 합쳐 13개의 플레이 동안에 가장 높은 점수를 낸 팀의 컨트롤러가 우승을 차지하게 된다.

공평한 채점을 위해서 프로그램이 수행될 머신은 다음과 같다. 모든 컨트롤러는 MacOS나 bootcamp를 이용하여 Window 7이 설치된 Mac Book Pro에서 구동될 것이다. 때문에 가급적이면 작성된 프로그램을 테스트 할때 비슷한 환경에서 해보는 것을 권장한다. 게임의 버전은 마이크로소프트 리벤지 오브 아케이드의 Ms Pac-Man 또는 Webpacman을 사용하게 된다.

위에서도 언급 하였지만 기본적인 상호작동 방식(스크린캡쳐)만 똑같다면 그 어떤 알고리즘을 이용해서 그 어떤 프로그램을 작성하여도 상관없다. 다만 주의해야할 점은 프로그램으로 인하여 게임의 속도가 현저하게 느려지게 된다면 실격되므로 주의하여야 한다.

CIG에서 제공하는 소프트웨어 툴 킷은 JAVA로 작성된 것과 C#으로 작성된 두가지 버전이 있다. JAVA로 작성된 것은 게임의 두가지 버전 어느것을 사용하더라도 문제가 없으며 C# 툴 킷은 마으크로소프트 리벤지 오브 아케이드의 MS Pac-Man을 사용하여야 한다.

이 대회에 참여하기 위해서 반드시 이렇게 제공되는 소프트웨어 툴킷을 사용하여야 한다는 제약조건은 없다. 1에서 소개한 기본적인 규칙만 지켜진다면 자유롭게 자신만의 프로그램을 작성하여도 된다.

하지만 이미지 프로세싱에 대한 기본적인 정보나 지식이 많지 않다면 아무것도 준비되지 않은 상태에서 처음부터 프로그램을 작성한다는 것은 쉽지 않은 일이다. 때문에 CIG에서 제공하는 두가지 소프트웨어 툴킷과, 2010년에 경진대회에서 우승을한 Pambush 3 팀의 프로그램을 소개하고자 한다.

위의 스크린샷은 CIG에서 제공한 JAVA 툴킷을 사용하여 MS Pac-Man을 플레이 하는 화면이다. 게임 윈도우를 제외하고 두가지 창이 존재하는데, Extracted 윈도우는 스크린 캡쳐를 통해 필요한 정보를 추출하고 그것을 보이는 그림이고, 화살표 모양이 있는 상단의 윈도우는 현재 발생된 키보드 이벤트를 보여준다.

이 JAVA 툴킷을 원만하게 구동시키기 위해서는 MsPacInterface 코드 내부의 게임이 실행될 창의 좌표 정보를 넣어주어야 한다. 또 당신의 컴퓨터에서 표현되는 4마리 유령의 색을 RGB 코드로 입력해주어야 하기 때문에 유용한 시작점으로는 적절하지 않다고 볼 수 있다.

구동 방법은 Ms Pac-Man 윈도우 위치 및 유령의 색깔 코드를 맞추어주고 게임을 실행시켜놓은 상태에서 MsPacInterface의 새 인스턴스를 시작하면 된다

java pacman.MsPacInterface

화면 조정을 위해 MsPacInterface의 Code 일부분을 수정할 필요가 있다. 아래 코드는 그 부분을 일부 발췌해놓은 것이다.

// change these to suit your screen position
static int left = 530;
static int top = 274;

툴킷에서 제공되는 컨트롤러는 굉장히 단순한 컨트롤러로, 미스팩맨의 위치로부터 가장 가까운 알약을 찾아 그 알약을 향해서 이동하는 방식이다. 아래 코드는 Agent.java의 일부를 발췌하여 놓은 것으로 Move와 eval 메소드를 보여준다.

public int move(GameState gs) {
  // let's say we move towards the
  // simple controller that tries to move towards the nearest power pill
  // set up a rogue value for the move, and a large value for the closest pill
  move = -1;
  double best = 100000;
  for (int i = 0; i < dirs.length; i++) {
    if (d[i] > 12) {
      tmp.set(cur);
      tmp.add(vDirs[i]);
      // System.out.println(i + "\t " + eval(tmp, gs));
      if (eval(tmp, gs) < best) {
        move = i;
        best = eval(tmp, gs);
      }
    }
  }
  if (move < 0) {
    System.out.println("Move error: " + move);
  }
  // the +1 is to map the move into a range of joystick actions
  // where '0' is centre position
  move += 1;
  return move;
}

public double eval(Vector2d pos, GameState gs) {
  if (gs.closestPill != null) {
    return pos.dist(gs.closestPill);
  } else {
    return 0;
  }
}

이미지 프로세싱에 대한 부분의 프로그래밍을 따로 하지 않고 새로운 Controller의 개발에만 집중하고 싶다면 툴킷을 다운로드 하여 미스팩맨을 직접적으로 컨트롤하여 키보드 이벤트를 발생시키는 부분만을 수정하면 된다.

툴 킷 다운로드 : http://cswww.essex.ac.uk/staff/sml/pacman/pac.zip

위의 그림은 http://www.codeplex.com/MsPacmanAI 에서 얻을 수 있는 C# kit를 이용하여 게임이 구동되는 장면이다. 게임을 실행시키고 Initialize 버튼을 누르게 되면 자동으로 화면에서 게임 윈도우를 찾아 그 위치를 옮기고 스크린 캡쳐를 통해 정보를 추출하여 윈도우에 그 정보를 표시하는 방식으로 진행된다.

프로그램 내부에 컨트롤러로 사용될 클래스를 미리 작성해 두면 프로그램을 수정하지 않고 간단하게 시험해보고 싶은 컨트롤러를 선택할 수 있고, 일일이 게임 윈도우의 위치나 유령의 색을 지정해줄 필요가 없기 때문에 C#에 익숙한 사람이라면 JAVA 툴 킷 보다 훨씬 쉽게 접근 할 수 있을 것으로 생각 된다.

다음은 Visual Studio 2008을 이용하여 제공된 툴 킷의 프로젝트 파일을 실행한 모습이다. PacmanAI 부분에 있는 여러 가지 컨트롤러의 버전을 수정하는 것도 가능하고, 원한다면 새로운 컨트롤러를 작성하여 추가하여도 된다. 새로운 컨트롤러를 작성하여 추가해주기만 하면 MsPacmanController 윈도우에서 간편하게 선택하여 테스트 해볼 수 있다.

실행 시키는 것도 간단하다. 위의 그림과 같은 방법으로 MsPacmanController의 인스턴스를 시작해주기만 하면 제어를 위한 윈도우 창이 생기게 되고, 그 윈도우 창을 조작하여 미스팩맨과 연동시켜주면 된다.

ICE Pambush 3는 2009년 경진대회에서 우승을 차지한 팀이다. JAVA에 기반하여 프로그램을 작성하였으며, 기존에 CIG에서 제공하는 JAVA 툴 킷의 스크린 캡쳐 부분을 수정하여 자동으로 게임 윈도우를 감지하기 때문에 CIG에서 제공하는 툴과 다르게 윈도우의 위치를 지정해주거나 유령의 색 코드를 맞추어줄 필요가 없어 굉장히 간편하다.

2009년 ICE Pambush 3 의 Document : http://cswww.essex.ac.uk/staff/sml/pacman/cig2009/ICEPambush3/ICE%20Pambush%203.pdf

ICE Pambush 3의 핵심 전략을 간략하게 소개하자면, 만약 유령과 적당한 거리를 유지한 상태에서 현재 Power pill(큰 알약)이 미스팩맨의 근처에 있다면 “습격 모드” On 하는 방식을 사용한다. 즉, 큰 알약의 주변에서 유령이 가까이 오기를 기다리고 있다가 유령이 근접하면 큰 알약을 먹고 유령을 먹어치워버린다. 그 이외에도 A* 알고리즘에서 현재 상황에 따라 두가지 버전의 다른 DFS(Depth First Search)를 사용하는 등의 특징이 있으나 여기서는 자세히 다루지 않겠다.

C# 대신 JAVA를 사용해서 경진 대회에 참여를 하고 싶다면 이 ICE Pambush 3 팀의 코드를 시작점으로 잡는 것도 하나의 좋은 방법이 될 수 있겠다. 위에서 소개한 C# 툴 킷의 경우에는 게임을 따로 시작해두지 않아도 자동으로 프로그램이 게임을 시작하게 하지만, 이 ICE Pambush 3의 프로그램은 게임을 자동으로 시작하지 않기 때문에 직접 시작 해주어야 한다

다음은 2009년, 2010년에 개최된 경진대회의 우승팀과 그에 대한 정보를 살펴 볼 수 있는 페이지이다. 함께 제출될 문서는 어떻게 작성되어야 하는지, 그리고 우승팀들은 어떤 전략을 사용하였는지 참고하는데 많은 도움이 될 것이다.

http://cswww.essex.ac.uk/staff/sml/pacman/CIG2010Results.html

http://cswww.essex.ac.uk/staff/sml/pacman/CIG2009Results.html

아래의 Link는 PacManContest에 대한 공식 자료이다. 지금 읽고 있는 이 문서도 공식 자료의 대부분을 참고하여 작성되었다.

http://cswww.essex.ac.uk/staff/sml/pacman/PacManContest.html

아래 File은 Competition에서 사용 될 수 있는 두가지 게임 버전 중 하나인 마이크로소프트 리벤지 오브 아케이드이다. 내부에 포함된 Reg 파일을 추가시켜주고, Game 폴더의 ROA를 실행시킨 후 MS Pac-Man을 선택하면 된다

roa.zip

1. ICE Pambush 3 (Hiroshi Matsumoto, Takashi Ashida, Yuta Ozasa, Takashi Maruyama,
and Ruck Thawonmas Intelligent Computer Entertainment Laboratory Department of Human
and Computer Intelligent, Ritsumeikan University ruck [at] ci.ritsumei.ac.jp 30 August 2009)
2. Evolution Strategy for Optimizing Parameters in Ms Pac-Man Controller ICE Pambush 3
(Ruck Thawonmas, Senior Member, IEEE and Takashi Ashida 2010)
3. IEEE CIG 2011 Ms Pac-Man Competition
(http://cswww.essex.ac.uk/staff/sml/pacman/PacManContest.html)