GA 알고리즘 Google Chrome의 Dinosaur 게임

GA 알고리즘 Google Chrome의 Dinosaur 게임

Google Chrome의 Dinosaur 게임을 GA 알고리즘과 접목하여 게임을 학습하는 program이 있습니다.

Google Chrome은 브라우저(Browser)에서는 네트워크의 연결이 끊어지게 되면, Dinosaur 게임을 시작할 수 있습니다.

브라우저 내의 공간을 클릭하면 게임을 시작할 수 있습니다. 게임의 목표는 사용자가 키보드 입력을 이용하여 게임 속 공룡이 장애물(선인장)을 뛰어넘거나, 몸을 구부려 장애물(익룡)을 피해 먼 거리를 가는 것입니다. 게임은 거리를 통해 점수를 매깁니다. 여기서 유전 알고리즘을 접목하여 게임에서 최대한 높은 점수를 매기도록 훈련을 진행됩니다.

프로젝트는 Node js를 통해 개발이 되어 있으며,, Synaptic(Neural Network 라이브러리)과 RobotJs(픽셀을 읽고, 키를 작동하는 라이브러리)를 사용하였습니다. 작동 방식은 기본적으로 Google Chrome과 연동되어 Dinosaur 게임의 UI를 픽셀과 색으로 구분하여 GAME이 끝난 여부를 알 수 있습니다. 또한 RobotJS를 이용해 사용자의 입력없이 코드에 따라 위아래 키 입력 신호를 보내어 게임을 조작할 수 있습니다. 또한 사용자에게 현재 세대의 염색체와 적합도 함수를 보여주고, 염색체를 저장할 수 있는 UI를 제공하도록 개발하였습니다.

네트워크 입력 가시화 UI에서 각각의 막대는 센서를 의미합니다. 첫 번째 센서(Distance)는 거리 센서입니다. 두 번째 센서는 크기(Size)로 장애물의 크기입니다. 세 번째 센서는 속도(Speed)로 게임이 진행되는 속도입니다. 게임은 시간이 지날수록 속도가 증가하게 됩니다. 네 번째 센서는 활성함수(Activation)로 신경 네트워크의 출력 값입니다. 게임 상태 UI에서는 현재 게임 상태와 적합도(장애물을 넘을 때 마다 1씩 증가)와 학습 중인 염색체와 세대 수를 보여줍니다. 유전자 상태 UI에서는 게임에서 할 수 있는 행동을 나타내며, 기본적으로 점프(위)/숙임(아래)/가만히 있음(키 누르지 않음)이 있습니다.

유전자 알고리즘에서 학습해야할 유전자를 생각해봐야합니다. 게임에서 중요한 정보는 센서입니다. 우리는 공룡과 장애물 사이의 거리에 대한 정보를 얻을 수 있습니다. 이것은 우리가 언제 뛰어야 할지 결정하기 때문에 중요한 정보입니다. 센서에는 또한 장애물의 크기도 사용됩니다. 장애물의 크기에 따라 점프가 끝나기 전이나 후에 점프를 결정할 수 있습니다. 다른 요인은 속력입니다. 게임은 점수를 많이 획득할수록 공룡의 움직이는 속도가 빨라집니다. 따라서 3개의 센서(거리, 크기 및 속도)로 게임은 단순화할 수 있습니다. 게임은 또한 공룡이 할 수 있는 유일한 행동을 가지고 있는데 점프하거나 몸을 구부리는 것입니다. 그것은 키보드의 상/하 키가 있습니다.

입력과 출력에 대해 연결/맵핑하는 정말 좋은 방법인 신경망과 유전알고리즘을 접목하여 학습을 시킬 수 있습니다. 구성한 신경망은 염색체(DNA)처럼 변형할 수 있습니다. 염색체는 정보가 있는 유전자로 이루어져 있어, 지시 사항을 가지고 있습니다. 이 프로젝트에서는 12개의 염색체를 이용해 무작위로 시작합니다. 염색체는 일련의 정보이며, 정보가 있는 많은 작은 부분이 있습니다.

센서에서 입력을 지속적으로 신경망에 적용하고, 출력을 키에 맵핑하여 게임을 테스트합니다. 다음 세대로 우수한 염색체를 결정하기 위한 적합도 함수는 장애물을 많이 뛰어 넘은 횟수입니다. 적자생존의 법칙에 따라 적합도가 가장 높은 두 개의 염색체를 가져와 교차를 진행합니다. 또한 염색체의 돌연변이를 위해 12개의 유전자 중 임의의 위치에 있는 값을 무작위로 변경합니다. 새로 생성된 염색체를 다음 세대에 넣고 반복으로 진행합니다. 다음은 인공신경망과 유전 알고리즘에 따라 학습을 진행 중인 그림입니다.

학습을 진행하는 동안 첫 세대부터 장애물에 계속 부딪히며 20세대 이상부터는 점프를 진행하며 우수한 유전자를 선택해 교차와 돌연변이 알고리즘에 따라 다음 세대에 전달합니다. 150세대까지는 총 12시간이 걸렸으며, 150세대에서는 높은 게임 결과의 성적을 보여 주었습니다.

Code

-`index.js` : 다른 javascript 파일을 묶어줍니다.

-`Scanner.js` : RobotJs 라이브러리 위의 기본 추상화 레이어로 화면을 읽습니다. 또한 일부 유틸리티 함수가 있습니다.

-`UI.js` : UI 관리를위한 전역(global) 범위를 가지며 화면을 초기화하고 업데이트합니다.

-`GameManipulator.js` : 센서(senseor)를 읽고 출력을 적용하는 데 필요한 모든 코드가 있습니다. 또한 게임 포인트를 계산하고 게임 상태를  콜백(callback) / 리스너(listener)를 실제 구현으로 트리거합니다.

- Learner.js : 유전자 알고리즘의 핵심 구현입니다.

ROBOTJS

http://robotjs.io/

ROBOTJS에는 예제에서 볼 수 있듯이 사용자의 입력(키보드, 마우스)를 입력 받을 수 있습니다.

index.js

관련 파일을 import 합니다.

var robot = require('robotjs');

var GameManipulator = require('./GameManipulator');

var Learner = require('./Learner');

var Scanner = require('./Scanner');

var UI = require('./UI');

GameManipulator(조작) 를 초기화합니다.

// Robotjs를 설정합니다.

robot.setMouseDelay(1);

// 게임을 초기화합니다.

GameManipulator.findGamePosition();

// 게임을 찾습니다.

if (GameManipulator.offset) {

// 센서의 시작점(감지가 올바르게 되는지)을 디버그하기 위해서는 다음의 라인의 주석을 해제합니다.

// robot.moveMouse(GameManipulator.offset[0]+GameManipulator.sensors[0].offset[0],

//    GameManipulator.offset[1] + GameManipulator.sensors[0].offset[1]);

  robot.moveMouse(GameManipulator.offset[0], GameManipulator.offset[1]);

} else {

  console.error('FAILED TO FIND GAME!');

  process.exit();

}

UI와 Learner(유전 알고리즘 GA, 신경망 NN)을 초기화합니다.

// UI 초기화

UI.init(GameManipulator, Learner);

// Learner 초기화

// 유전알고리즘(Genetic Algorithm)와 신경망(Neural Network))

Learner.init(GameManipulator, UI, 12, 4, 0.2);

// 게임의 상태와 센서를 읽어 들이는 것을 시작합니다.

setInterval(GameManipulator.readSensors, 40);

setInterval(GameManipulator.readGameState, 200);

Scanner.js

게임 화면에서 해당 픽셀의 색상(rgb)과 위치를 확인합니다.

// screen의 사이즈 너비(width)와 높이(height)

var screenSize = robot.getScreenSize();

// Indexes

var X = 0;

var Y = 1;

// Create the "class" wrapper

var Scanner = {};

현재 검색 위치에 대해 screen의 밖에 있는 지 확인합니다.

// 지금 현재 위치가 screen의 밖에 있는지 확인합니다. 밖에 있다면 검사할 필요가 없습니다.

// screen의 너비(width)와 높이(height) 보다 크다면 밖에 있는 점이므로 true를 리턴합니다.

Scanner.isOutOfBound = function (pos) {

  if ( pos[X] < 0 || pos[Y] < 0 ||

    pos[X] >= screenSize.width ||

    pos[Y] >= screenSize.height) {

    return true;

  }

  return false;

}

위치를 스크린에 크기로 제한합니다.

// x, y의 좌표 위치를 스크린(screen)를 벗어나지 않도록

// screen의 너비(width)와 높이(height) 보다 큰 경우 경계의 -1로

// 0보다 작다면 위치를 0으로 이동합니다.

// 위치를 제한합니다.

Scanner.makeInBounds = function (pos) {

  if (pos[X] < 0) {

    pos[X] = 0;

  }

  if (pos[X] >= screenSize.width) {

    pos[X] = screenSize.width - 1;

  }

  if (pos[Y] < 0) {

    pos[Y] = 0;

  }

  if (pos[Y] >= screenSize.height) {

    pos[Y] = screenSize.height - 1;

  }

  return pos;

}

시작으로부터 변동량만큼 움직이고 일치하는 색을 찾을 때까지 진행합니다.

// 시작 [X, Y]와 DELTA [dx, dy]가 주어진다면,

// 맵 "start"로부터 delta(변동량)만큼 포지션을 더하여,

// matchinColor를 찾을 때까지, 또는 isOutOfBounds를 통해 맵의 밖으로 나갈 때까지 진행합니다.

Scanner.scanUntil = function (start, delta, matchColor, inverted, iterLimit) {

  var color, current, iterations = 0;

  //  makeInBounds를 호출해 screen 안에 있는 좌표로 clone 합니다.

  current = Scanner.makeInBounds([start[X], start[Y]]);

  if (delta[X] == 0 && delta[Y] == 0) {

     return null;

  }

  while (!Scanner.isOutOfBound(current)) {

     // 현재 위치 픽셀(pixel)의 색을 가져옵니다.

     color = robot.getPixelColor(current[X], current[Y]);

     // Color가 일치할 경우

     if (!inverted && color.toString() == matchColor) {

       return current;

     }

 

    // 뒤집힌 모드일 경우 Color의 색이 같지 않아야 한다.

     if (inverted && color.toString() != matchColor) {

        return current;

     }

     current[X] += delta[X];

     current[Y] += delta[Y];

     iterations++;

     if (iterations > iterLimit) {

       return null;

     }

  }

 return null;

};

자세한 코드는 github.com(https://github.com/KimJeongChul/IAMDinosaur)을 참고해주세요