MS. Pac Man Jang Su-Hyung

Contents MS.Pacman 소개 A* 알고리즘 FSM, Rule Based Neural Network 기타 연구 이론 FSM, Rule Based 관련연구 참고코드 Neural Network 참고 코드 기타 연구 고스트 팀 훈련 Influence Map 구현 환경, 시연

Pacman 캐릭터로 1982년 미국 에니메이션 쇼 제작 8명의 개발 인원으로 15달에 걸쳐 개발 토루 이와타니 개발 아케이드 게임 역사상 가장 성공적인 게임 300000 대의 PacMan 게임기 생산 1억불의 수익 개발사 남코 Pacman 캐릭터로 1982년 미국 에니메이션 쇼 제작 8명의 개발 인원으로 15달에 걸쳐 개발 소프트웨어 4명, 하드웨어 4명

250의 회사로부터 라이선스 취득 400 여개의 제품으로 생산 경제학 용어로 등장 범용적 게임을 목적 간단한 조작방식 여성, 어린이들이 대상 간단한 조작방식

격자의 형태 로쪼개진 환경에서의 경로 탐색 이동 가능한 모든 방향으로 탐색 주변 위치는 어디서 왔는지 기억

비연속적 이동 지점마다 표시 : 노드 F = G + H F 가 가장 작은 방향 선택 F : 예상 총거리

A* 의 약점

FSM (finite-state machine) 유한한 개수의 상태들로 구성된 하나의 간단한 기계 상태 – 하나의 조건 (예) 문이 열린 상태, 문이 닫힌 상태, 문이 잠긴 상태, 문이 잠기지 않은 상태 하나의 입력을 받고 그에 의거해서 현재 상태로부터 다른 어떤 상태로 전이(transition)하는 식으로 작동 어떤 상태를 현재 상태로 만들 것인지 판단하는 간단한 (또는 복잡한) 상태 전이 함수

FSM [S1] 의 상태 : 몬스터는 주위를 돌아다니고 있다

FSM [S1] 의 상태 : 주인이 휴식상태이므로, 펫은 주인의 주위를 돌아다니고 있다. 0은 이 상태의 반복

FSM S -> right R S -> left L S -> up U S -> down D R -> right R R -> left L R -> up U R -> down D R -> pause P R -> right R -> left R -> up R -> down R -> pause L -> right R L -> left L L -> up U L -> down D L -> pause P L -> right L -> left L -> up L -> down L -> pause U -> right R U -> left L U -> up U U -> down D U -> pause P U -> right U -> left U -> up U -> down U -> pause D -> right R D -> left L D -> up U D -> down D D -> pause P D -> right D -> left D -> up D -> down D -> pause P -> right R P -> left L P -> up U P -> down D P -> pause P P -> right P -> left P -> up P -> down P -> pause

FSM S R L U D P r l u d p S = Start R = Right L = Left U = Up D = Down P = Pause r = right l = left u = up d = down p = pause

FSM An Evaluation of the Benefits of Look-Ahead in Pac-Man Thomas Thompson, Lewis McMillan, John Levine and Alastair Andrew

FSM Learning to Play Using Low-Complexity Rule-Based Policies: Illustrations through Ms. Pac-Man István Szita András Lorincz

FSM

FSM

Reference Code Rule Based FSM

Neural Network Evolving a Neural Network Location Evaluator to Play Ms. Pac-Man Simon M. Lucas Evaluating each possible next location Neural Network Maximum two layers Weight matrix mapping the input plus bias

Reference Code NEAT

Training Ghost

Influence Map An Influence Map Model for Playing Ms. Pac-Man Nathan Wirth and Marcus Gallagher

Influence Map

Base Environment http://cswww.essex.ac.uk/staff/sml/pacman/PacManContest.html Java Image Detector, Simulator, Game

Question