5
\$\begingroup\$

To give a bit of a background, I'm organizing a small session about reinforcement-learning, specifically Q-learning, to a group of high school students in the following month to give them a glance into the kind of opportunities waiting for them to tackle in this amazing field of AI and Computer Science. Just a small stint to motivate them, to be honest :)

I hence seek the guidance of this wonderful community (that is you!) to judge the understandability and the readability of my code which I had drafted some time ago. The code which follows is predominantly written in basic JavaScript and since it's targeted for a set of audience who aren't completely comfortable with most of the modern paradigms, I would like to keep it as simple as possible. I've tried to document the code heavily covering potentially all important cases in layman terms to make it more clear. You can see the effect of the code in action here: https://nileshsah.github.io/reinforcement-learning-flappybird/ (you just need to tap the game to start and then leave it alone for the computer shall learn to play it by its own). The complete repository for the game and the algorithm can be found here.

I do realize that it's a bit too much of a code to review (around 300 lines) but if in the process you get to learn something new then oh well, I guess it'll be a win-win situation for both of us :) Please take your time and share your thoughts regarding "which part of the code is hard to comprehend and how I can improve it".

Sharing the code: https://github.com/nileshsah/reinforcement-learning-flappybird/blob/master/js/brain.js

/**
 * The file contains solely the Q-learning model for training our flappy bird.
 * It takes input from the environment such as the position of the flappy bird,
 * the tubes etc and responds back with the appropriate action to take.
 * 
 * Author @nellex
 */


/**
 * The Q-table forms the heart of the Q-learning algorithm. Maintained for our
 * agent Flappy bird, the table represents the state-action function, i.e. the
 * relationship between a set of states (S) and the set of actions (A) =>
 * Q[S,A]. For a given state 's' and a given action 'a', Q(s,a) denotes the
 * expected reward of doing the action 'a' in the state 's'.
 * 
 * In our learning model, the state of the environment is defined by: 
 * (1) speedY: The speed of the flappy bird in the Y-axis, i.e. by what rate the
 * bird is going up or falling down
 * (2) tubeX: The X-coordinate of the next incoming tube, i.e. how far the next 
 * tube is from the flappy bird 
 * (3) diffY: We define the ideal position from which the flappy bird should pass 
 * through to be the very middle of vertical space between the two tubes. The 
 * parameter 'diffY' denotes the difference between the Y-coordinate of the flappy 
 * bird to the Y-coordinate of our ideal passage position, i.e. how down below or 
 * above our flappy bird is from where it should pass from the tube.
 */
var Q_table = {};

/** 
 * The action set comprises of: 
 * (1) Stay: Take no action, and just go with the flow of the gravity 
 * (2) Jump: Push the flappy bird upwards
 */
var actionSet = {
  STAY : 0,
  JUMP : 1
};

/**
 * Defining the parameters for our Q-learning model, 
 * (1) Learning rate, alpha: Ranging between [0,1], it determines how quickly should 
 * the flappy bird override it's old learned actions with the new ones for the 
 * corresponding state
 * (2) Discount factor, gamma: Used for determining the importance of future reward. 
 * 
 * In our game, if the flappy bird fails to clear the tube, the action which it 
 * took recently previously will be penalized more than the action which it took 10 
 * steps ago. This is because it's the recent actions which has a more influence on 
 * the success of the bird.
 */
var gamma = 0.8; // Discounted rewards
var alpha = 0.1; // Learning rate

// Frame buffer for mainting the state-action pairs in the current episode
var frameBuffer = [];

// Number of frames in the current frame buffer
var episodeFrameCount = 0;

// Flag to determine if the current episode is still ongoing or is completed by
// maintaing an index to the next incoming tube
var targetTubeIndex;

// The tube which the bird must clear next
var targetTube;

// To maintain the count on the number of trials
var trials = 0;

/**
 * Function to lookup the estimated Q-value (reward) in the Q-table for a given
 * state-action pair
 * @param {*} state State of the environment as described above
 * @param {*} action The action to be taken
 */
function getQ(state, action) {
  var config = [ state.diffY, state.speedY, state.tubeX, action ];
  if (!(config in Q_table)) {
     // If there's no entry in the given Q-table for the given state-action
     // pair, return a default reward score as 0
     return 0;
  }
  return Q_table[config];
}

/**
 * Function to update the Q-value (reward) entry for the given state-action pair
 * @param {*} state The state of the environment
 * @param {*} action The action taken for the given state
 * @param {*} reward The reward to be awarded for the state-action pair 
 */
function setQ(state, action, reward) {
  var config = [ state.diffY, state.speedY, state.tubeX, action ];
  if (!(config in Q_table)) {
    Q_table[config] = 0;
  }
  Q_table[config] += reward;
}

/**
 * Function responsible for selecting the appropriate action corresponding to
 * the given state The action which has a higher Q-value for the given state is
 * 'generally' executed 
 * @param {*} state 
 */
function getAction(state) {
  // Why always follow the rules? Once in a while (1/100000), our flappy bird
  // takes a random decision without looking up the Q-table to explore a new
  // possibility. This is to help the flappy bird to not get stuck on a single
  // path.
  var takeRandomDecision = Math.ceil(Math.random() * 100000)%90001;
  if (takeRandomDecision == 0) {
    console.log("Going random baby!");
    // 1 out of 4 times, it'll take a decision to jump
    var shouldJump = ((Math.random() * 100 )%4 == 0);
    if (shouldJump) {
        return actionSet.JUMP;
    } else {
        return actionSet.STAY;
    }
  }

  // Lookup the Q-table for rewards corresponding to Jump and Stay action for
  // the given state
  var rewardForStay = getQ(state, actionSet.STAY);
  var rewardForJump = getQ(state, actionSet.JUMP);

  if (rewardForStay > rewardForJump) {
    // If reward for Stay is higher, command the flappy bird to stay
    return actionSet.STAY;
  } else if (rewardForStay < rewardForJump) {
    // If reward for Jump is higher, command the flappy bird to jump
    return actionSet.JUMP;
  } else {
    // This is the case when the reward for both the actions are the same In
    // such a case, we determine randomly the action to be taken Generally, the
    // probability of jumping is lower as compared to stay to mimic the natural
    // scenario We press jump much less occasionally than we let the flappy bird
    // fall
    var shouldJump = (Math.ceil( Math.random() * 100 )%25 == 0); 
    if (shouldJump) {
        return actionSet.JUMP;
    } else {
        return actionSet.STAY;
    }    
  }
}

/**
 * Function responsible for rewarding the flappy bird according to its
 * performance One thing to note here is that we found the behaviour of our
 * Flappy Bird to be highly episodic. As soon as your flappy bird clears one
 * obstacle, we terminate our episode there and then and reward it postively A
 * new episode is then started for the next obstacle i.e. the next tube which is
 * treated completely independent from the previous one
 * 
 * We reward the flappy bird at the end of an episode, hence we maintain a frame
 * buffer to store the state-action pairs in a sequential order and decide upon
 * the reward to be awarded for that state-action on the completion of the
 * episode
 * @param {*} reward The amound of reward to be awarded to the Flappy Bird
 * @param {*} wasSuccessful Determines if the reward to be awarded should be
 * negative or positive depending upon if the episode was completed successfully
 * or not
 */
function rewardTheBird(reward, wasSuccessful) {
  // Minumun number of frames to be maintained in the frame buffer for the
  // episode (for maintaining the state-action sequecne tail)
  var minFramSize = 5;
  // Tolerable deviation from the ideal passage position between the tubes in px
  var theta = 1;

  var frameSize = Math.max(minFramSize, episodeFrameCount);

  // Iterate over the state-action sequence trail, from the most recent to the
  // most oldest
  for (var i = frameBuffer.length-2; i >= 0 && frameSize > 0; i--) {
    var config = frameBuffer[i];
    var state  = config.env;
    var action = config.action;

    // The reward for the state is influenced by how close the flappy bird was
    // from the ideal passage position
    var rewardForState = (reward - Math.abs(state.diffY));

    // Determine if the reward for given state-action pair should be positive or
    // negative
    if (!wasSuccessful) {
      if (state.diffY >= theta && action == actionSet.JUMP) {
        // If the bird was above the ideal passage position and it still decided
        // to jump, reward negatively
        rewardForState = -rewardForState;
      } else if(state.diffY <= -theta && action == actionSet.STAY) {
        // If the bird was below the ideal passage position and it still decided
        // to not jump (stay), reward negatively
        rewardForState = -rewardForState;
      } else {
        // The bird took the right decision, so don't award it negatively
        rewardForState = +0.5;
      }
    }

    // Update the Q-value for the state-action pair according to the Q-learning
    // algorithm Ref: https://en.wikipedia.org/wiki/Q-learning
    var futureState = frameBuffer[i+1].env;
    var optimalFutureValue = Math.max(getQ(futureState, actionSet.STAY), 
                                      getQ(futureState, actionSet.JUMP));
    var updateValue = alpha*(rewardForState + gamma * optimalFutureValue - getQ(state, action));

    setQ(state, action, updateValue)
    frameSize--;
 }
 // Allocating reward is complete, hence clear the frame buffer but still try to
 // maintain the most recent 5 state-action pair Since the last actions taken in
 // the previous episode affects the position of the bird in the next episdoe
 frameBuffer = frameBuffer.slice(Math.max(frameBuffer.length-minFramSize, 1));
 episodeFrameCount = 0;
}

/**
 * Function to negatively reward the flappy bird when the game is over
 */
function triggerGameOver() {
  var reward =  100;
  rewardTheBird(reward, false);
  console.log( "GameOver:", score, Object.keys(Q_table).length, trials );

  // Reset the episode flag
  targetTubeIndex = -1;
  episodeFrameCount = 0;
  trials++;
}

/**
 * This function is executed for every step in the game and is responsible for
 * forming the state and delegating the action to be taken back to our flappy
 * bird
 */
function nextStep() {
  // If the game hasn't started yet then do nothing
  if (gameState != GAME)
   return;

  // Logic to determine if the Flappy Bird successfully surpassed the tube The
  // changing of the targetTubeIndex denotes the completion of an episode
  if (birdX < tubes[0].x + 3 && (tubes[0].x < tubes[1].x || tubes[1].x + 3 < birdX)) {
    targetTube = tubes[0];
    if (targetTubeIndex == 1) {
      // The target tube changed from [1] to [0], which means the tube[1] was
      // crossed successfully Hence reward the bird positively 
      rewardTheBird(5, true);
    }
    targetTubeIndex = 0;
  } else  {
    targetTube = tubes[1];
    if (targetTubeIndex == 0) {
      // The target tube changed from index [0] to [1], which means the tube[0]
      // was crossed successfully Hence reward the bird positively
      rewardTheBird(5, true);
    }
    targetTubeIndex = 1;
  }

  // We'll take no action if the  tube is too far from the bird
  if (targetTube.x - birdX > 28) {
    return;
  }

  // Else, we'll form our state from the current environment parameters to be
  // ingested by our algorithm
  var state = {
    speedY: Math.round(birdYSpeed * 100),
    tubeX: targetTube.x,
    diffY: (targetTube.y+17+6) - (birdY+1)
  };

  // Query the Q-table to determine the appropriate action to be taken for the
  // current state
  var actionToBeTaken = getAction(state);

  // Push the state-action pair to the frame buffer so what we can determine the
  // reward for it later on
  var config = {
    env: state,
    action: actionToBeTaken
  };  
  frameBuffer.push(config);
  episodeFrameCount++;

  // Delegate the action to our flappy bird
  if (actionToBeTaken == actionSet.JUMP) {
    birdYSpeed = -1.4;
  } else {
      // For stay action, we do nothing but just let the bird go down due to
      // gravity
  }  
}

Finally, thank you so much for your valuable time. You guys are way too awesome! :)

| improve this question | | | | |
\$\endgroup\$
3
\$\begingroup\$

Review

This review has grown a little beyond a review as I have enjoyed playing with Q_learning. Take what you can, if anything, from the review and modifications I have made.

The majority of changes (suggestions only) are aimed at increasing performance, with the learning mode getting 10,000+ frames per 60th second by decoupling the rendering from the game play, and some performance oriented techniques in the Q learning code.

A suggestion. Because of the extra throughput it seems like the logical extension to apply the learning technique to the learning functions.

Style and code quality

  • Use constants for constants.
  • Spaces between operators.
  • Don't repeat code, use functions to take the place of repeated code.
  • Use block scope declarations (let, const) when variable's intended scope is only the block.
  • Use ternaries to reduce code size and improve readability
  • Always delimit blocks with currlies. Eg bad... if (gameState != GAME) return; good... if (gameState !== GAME) { return; }
  • Remove redundant code, it is just noise and reduces overall readability.

    Examples

    • rewardForState = +0.5; should be rewardForState = 0.5;.
    • (targetTube.y + 17 + 6) - (birdY + 1) becomes (targetTube.y + 22 - birdY)
    • } else {} is just }
  • Try to avoid truthy evaluations and use strict equality and inequality. In other words avoid == and !=, use === or !==. They also come with a very slight performance gain.

  • Don't add redundant clauses to statements.

    For example you have

    if (rewardForStay > rewardForJump) {
        return actionSet.STAY;
    } else if (rewardForStay < rewardForJump) {
        return actionSet.JUMP;
    } else {
        var shouldJump = (Math.ceil(Math.random() * 100) % 25 == 0);
        if (shouldJump) {
            return actionSet.JUMP;
        } else {
            return actionSet.STAY;
        }
    }
    

    The else's are redundant. Could be written as

    if (rewardForStay > rewardForJump) { return actionSet.STAY }
    if (rewardForStay < rewardForJump) { return actionSet.JUMP }
    if (Math.random() < (1 / 25)) { return actionSet.JUMP  }
    return actionSet.STAY;
    

Problem

There is a slight problem in getAction when the very slim chance of a random action, the chance of a jump is vanishingly small (somewhere near 1 in 2.3e15) var shouldJump = ((Math.random() * 100 )%4 == 0) I think you want shouldJump = Math.floor((Math.random() * 100) % 4) or for a 1 in 4 odds you can use shouldJump = Math.random() < (1 / 4);

Aulturnatives

Map more suited to the task.

You can use a Map for the Q_table

const createQ = (state, action) => `${state.diffY},${state.speedY},${state.tubeX},${action}`;

function getQ(state, action) {
    const q = Q_table.get(createQ(state, action));
    return q === undefined ? 0 : q.value;
}
function setQ(state, action, reward) {
    const key = createQ(state, action);
    const q = Q_table.get(key);
    if(q === undefined){
        Q_table.set(key, {value : reward});
    }else {
        q.value += reward;
    }
}

Changes to frameBuffer

In rewardTheBird the variable frameSize seems to have no purpose. I removed it. I also removed the frameBuffer.splice at the end of the function in favour of frameBuffer.shift after adding to the frameBuffer in nextStep. To compensate I change the min frame buffer size to 15 (you had 5) and it seams to get better results. (Counted number of steps to get a high score of 200)

Seeded random

Playing with the learning algorithm I found it hard to compare different settings as the random game varied too much and the environmentStatic = true did not provide a good testing environment.

To provide a consistent yet random environment you can use a seeded random number. Javascript does not have such so in the example I added a seeded pseudo random. I did not add it to the learning functions.

Performance

Changes to increase performance (learning frame time)

Decouple rendering

You can decouple the rendering from the game play as rendering is the slowest part. As the game logic is relatively simple, avoiding the rendering lets you get a decent amount of learning frames per second.(on my machine I run it at an easy 600,000 learning frames a second without even starting up the cooling)

Object pool for frameBuffer

You are creating and deleting these object a lot, so the pool provides a quicker way to create the object, using old frameBuffer objects if available.

A better hash

Your hash function for each state was just Array.toString on var config = [ state.diffY, state.speedY, state.tubeX, action ]; Q_table[config] = value; which you did each time you wanted a particular state.

Turns out that all four variables can fit into 25 bits. By packing the state into 32bits you can simplify some of the lookups and store the hash in the frameBuffer so you don't need to recreate it each time you check past states.

Changing a hash state from JUMP, to STAY only requires the bottom bit to be flipped.

Flappy game

I also had a look at the rest of the code.

In the game the rendering of the playfield renderToScale is very slow and can be done very quickly as follows

context.globalCompositeOperation = "copy";
context.drawImage(context.canvas, 0, 0, 32, 32, 0, 0, 32 * scale, 32 * scale);
context.globalCompositeOperation = "source-over";

However that is not really needed as you can scale the canvas using the style attributes.

context.canvas.width = 32;
context.canvas.height = 32;
context.canvas.style.width = 32 * scale + "px";
context.canvas.style.height = 32 * scale + "px";
canvas.style.imageRendering = "pixelated";  // to prevent bilinear smoothing

The collision test was also a little slow (a good solution for more complex interactions). As the bird is only 5 by 3 pixels and the tubes 6 pixels wide, the collisions can be done with a bit of binary math. This helps decouple the slow canvas interface from the game play. See example

Example

Hopefully I have not strayed too far from the original. The example code has most of the suggestions outlined above and some other changes.

Some original features are missing.

/**
 * For answer on codereview.stackexchange.com
 * The script forms the most basic 32x32 pixel gameplay for flappy bird, ideally developed for the #lowrezjam2014
 * challenge (http://jams.gamejolt.io/lowrezjam2014)
 * The script can be configured for various environmental parameters like gameplay speed, gravity, tubes position etc. 
 * 
 * Reference: https://codepen.io/sakri/details/gGahJ
 */


 
const flappyRenderer = (()=>{
    const playSize = {w : 32, h: 32};
    const spriteImage = new Image;
    spriteImage.src = "data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAACUAAABQCAYAAACecbxxAAACY0lEQVRoge2XPW4CMRCF5yooLeegpIw4SZp0dBF34DBIKSMOkKQJUgpyBuQUyYIZv/mx1wsGraXR4vXu+Jv3Zheg59e3cM3YbqbH+Dl8BiIiujYUEVEHtZvPwm4+C01AERF9LB+On5uAas6+uKdG+27Oviafvu1mGlq0L40WoOLRFFR8HKFGqLuFau7pa/I91SRUk/aJjb4/vB+D3xivea/xrkMotOElA9r38r0K14y4wVuC6sYI5YY6RkNQpzFC3TTU02Ya1vtF+AqrcMnP6/0iWUvAuoXH5QQ/EXZY16N16R4din8FoHmcULqO50Pnzs5bUNKmfBMNNlaFQ8HzfaG0Y7Q5ylkOhRTwHNnmIlSxfaVHL1SsWBEUUo5bADdKbZKvrWEfggIWovNZ9qH3x6VChvKoxNclJapCeY5oc+2zBO2ybwgobb0alKTCVaHQRpaCWjHZUJYtsGKhmVX1HpeTwKH+wUwr+LoEZdhHyXUaVIVIlIJWpfDqKAXJyYfW9CTIIm1eqUg7Ceopo4/cRRYUdkpUE4qYMuDcnUD16amL2uesEqqTqfZ5IiOycvWFou6GHraJeXrkqlZdTdX/Et4tlMs+5QvZhCrpKV6UWOCA/2ZUxYqg0BPHq+XrTvVs1a1fnkhyVGFGn/VTqkkodPMQUFXti5PB5AKUES6oM+UcCuW8JvBwvBI81dWByYBCm+ZA5heU+w85Xtd6SpubfdgHKq5SmqOeM/uwApQ6d0KdjwGUKoHyK8X955ta6/yI7onniWJsmEoZVoj3I8USpQaAUmEGhbKsQHMElWWfEtZ6n6BfqpBLl8a8BXQAAAAASUVORK5CYII=";
    const spriteArray = [
        {x:0, y:0, w:32, h:32},
        {x:0, y:31, w:35, h:1},
        {x:6, y:49, w:17, h:21},
        {x:6, y:32, w:21, h:17},
        {x:32, y:0, w:5, h:3}, 
        {x:32, y:3, w:5, h:3}, 
        {x:32, y:6, w:5, h:3},
        {x:0, y:32, w:6, h:44},
        {x:6, y:70, w:30, h:10},
        {x:32, y:9, w:5, h:9},
        {x:27, y:32, w:5, h:9},
        {x:32, y:32, w:5, h:9},    
        {x:27, y:41, w:5, h:9},
        {x:32, y:41, w:5, h:9},    
        {x:27, y:50, w:5, h:9},
        {x:32, y:50, w:5, h:9},    
        {x:27, y:59, w:5, h:9},
        {x:32, y:59, w:5, h:9},    
        {x:32, y:18, w:5, h:9},
    ];
    const ZERO_ASCII = "0".charCodeAt(0);
    const sprites = {
        bg: 0,
        ground: 1,
        instructions: 2,
        gameOver: 3,
        bird: 4,
        tube: 7,
        hiscore: 8,
        numbers: 9,
        drawIdx(name, idx, x, y) {
            const spr = spriteArray[sprites[name] + idx];
            ctx.drawImage(spriteImage,spr.x, spr.y, spr.w, spr.h, x, y, spr.w, spr.h);
        },
        draw(name, x, y) {
            const spr = spriteArray[sprites[name]];
            ctx.drawImage(spriteImage,spr.x, spr.y, spr.w, spr.h, x, y, spr.w, spr.h);
        },
        drawNumber(num, x, y) { // x,y is coord of top left of right most digit
            var i = num.length;
            var idx = sprites.numbers;
            while (i--) {
                const spr = spriteArray[num.charCodeAt(i) - ZERO_ASCII + sprites.numbers];
                ctx.drawImage(spriteImage,spr.x, spr.y, spr.w, spr.h, x, y, spr.w, spr.h);
                x -= spr.w;
            }
        }            
    };
    const canvas = document.createElement("canvas");
    canvas.width = playSize.w;
    canvas.height = playSize.h;
    const ctx = canvas.getContext("2d");
    const states = {
        HOME: 0, 
        GAME: 1, 
    }
    const API = {
        set state(stateObj) {
            sprites.draw("bg", 0, 0);
            sprites.draw("ground", -stateObj.tick % 3, playSize.h - 1);
            sprites.drawIdx("bird", stateObj.birdFrame % 3, stateObj.birdX, stateObj.birdY);
            if (stateObj.gameState === states.HOME) {
                sprites.draw("instructions",  playSize.w - spriteArray[sprites.instructions].w - 1, 1);
            } else {
                sprites.draw("tube", stateObj.tubes[0].x, stateObj.tubes[0].y);
                sprites.draw("tube", stateObj.tubes[1].x, stateObj.tubes[1].y);
                sprites.drawNumber("" + stateObj.score, playSize.w - 7, 2);
            }
        },
        draw(context, x, y, w, h) { // draws local 
            context.imageSmoothingEnabled = false;
            context.drawImage(canvas, x, y, w, h);
        },
    }
    return API;
})();
    






function flappy() {
    
    /* Collision maps 
       These are used to do pixel perfect collision that is a lot fater
       than getting pixeldata from the canvas which is stored in GPU memory.    
    */
    const birdMap = [ // As bin numbers for easy entry
        [0b11110, 0b01111, 0b00100],
        [0b01110, 0b11111, 0b00100],
        [0b01110, 0b01111, 0b10100],
    ];
    const tubeMap = [];
    {   /* block to scope the next two vars */
        const t0 = 0b0111100000;
        const t1 = 0b1111110000;
        tubeMap.push(...[t0, t0, t0, t0, t0, t0, t0, t0, t0, t0, t0, t0, t0, t0, t0, t1, t1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, t1, t0, t0, t0, t0, t0, t0, t0, t0, t0, t0, t0, t0]);
    }    
    const tubesDefaults = [
        { x : 48, y : 0 },
        { x : 67, y : 0 },
    ];
    const tubes = [{}, {}];
    const GAME_SIZE = 32;
    const FLAP_SPEED = -1.4;
    const TUBE_HEIGHT = 44;
    const TUBE_WIDTH = 6;
    const GRAVITY = 0.25;
    const BIRD_WIDTH = 5;
    const BIRD_HEIGHT = 3;
    const BIRD_START_Y = 14;
    const states = {
        HOME: 0, 
        GAME: 1, 
        GAME_OVER: 2, 
        HI_SCORE: 3,
    }
    var environmentStatic = false, hiScore=0, gameState, score, birdY,
        birdYSpeed, birdX = BIRD_WIDTH, birdFrame = 0, activeTube, 
        tick, gameState = states.HOME, seed = 0;
        
    /* Game (low) quality seeded random number */
    const seededRandom = (() => {
        var seed = 1;
        return { max : 2576436549074795, reseed (s) { seed = s }, random ()  { return seed = ((8765432352450986 * seed) + 8507698654323524) % this.max }}
    })();
    const randSeed = seed => seededRandom.reseed(seed | 0);
    const randSI = range => (seededRandom.random() % range) * Math.sign(range);   
    var rand = randSI;  
    
    function loop() {  // main game loop
        switch (gameState) {
            case states.HOME: 
                ticker();
                break;
            case states.GAME: 
                update();
                break;
            case states.GAME_OVER: 
                API.state = states.GAME;
                break;
            case states.HI_SCORE: 
                renderHiScore();
                break;
        }
    }
    function ticker() {
        tick += 1;
        birdFrame = (birdFrame + 1) % 3;
    }
    function update() {
        ticker();
        moveTubes();
        updateBirdGame();
        checkCollision();
    }        
    function checkCollision() {
        if (birdX === tubes[activeTube].x + TUBE_WIDTH) {
            score++;
        } else {
            const bMap = birdMap[birdFrame];
            for (const tube of tubes) {
                if (birdX + 5 > tube.x && birdX < tube.x + TUBE_WIDTH) {
                    const shiftBird = tube.x + BIRD_WIDTH - birdX;     
                    birdPos = birdY - tube.y;
                    if (((bMap[0] << shiftBird) & tubeMap[birdPos++]) ||
                       ((bMap[1] << shiftBird) & tubeMap[birdPos++]) ||
                       ((bMap[2] << shiftBird) & tubeMap[birdPos])) {
                        gameState = states.GAME_OVER;
                        if (score > hiScore) { hiScore = score }
                        API.state = states.GAME_OVER;  
                        break;                    
                    }
                }
            }
        }
    }
    function updateBirdGame() {
        birdY = Math.round(birdY + birdYSpeed);
        birdYSpeed += GRAVITY;
        if (birdY < 0) {
            birdY = 0;
            birdYSpeed = 0;
        } else if(birdY + BIRD_HEIGHT > GAME_SIZE) {
            birdY = GAME_SIZE - BIRD_HEIGHT;
            birdYSpeed = 0;
        }
    }
    function moveTubes() {
        activeTube = tubes[0].x < tubes[1].x ? 0 : 1;
        for (const tube of tubes) {
            tube.x --;
            if (tube.x <= -TUBE_WIDTH) {
                tube.x = GAME_SIZE;
                setTubeY(tube);
            }
        }
    }
    function setTubeY(tube) {
        if (environmentStatic) {
            tube.y = Math.floor(0.639 * (GAME_SIZE - TUBE_HEIGHT));
        } else {
            tube.y = rand(GAME_SIZE - TUBE_HEIGHT + 2);
        }
    }        
    const API = {
        states,
        initGame() { API.state = states.HOME },
        set state(val) {
            if (val === states.HOME || (gameState === states.GAME_OVER && val === states.GAME)) {
                randSeed(seed);
                tick = birdYSpeed = score = 0;
                birdY = BIRD_START_Y;
                Object.assign(tubes[0], tubesDefaults[0]);
                Object.assign(tubes[1], tubesDefaults[1]);
                setTubeY(tubes[0]);
                setTubeY(tubes[1]);
                
            }
            gameState = val;
        },
        set flap(val) { birdYSpeed = FLAP_SPEED },
        set static(val) { environmentStatic = val },
        get static() { return environmentStatic },
        set seed(seed) { 
            if (seed === undefined || seed === null) { 
                rand = range => Math.random() * range | 0;
            } else { 
                rand = randSI;
                randSeed(seed);
            }
        },        
        gameState(stateObj = {}) {
            stateObj.gameState = gameState;
            stateObj.tick = tick;
            stateObj.score = score;
            stateObj.birdY = birdY;
            stateObj.birdX = birdX;
            stateObj.birdYSpeed = birdYSpeed;
            stateObj.birdFrame = birdFrame;
            stateObj.hiScore = hiScore;
            if (stateObj.tubes === undefined) { stateObj.tubes = [{}, {}] }
            stateObj.tubes[0].x = tubes[0].x;
            stateObj.tubes[0].y = tubes[0].y;
            stateObj.tubes[1].x = tubes[1].x;
            stateObj.tubes[1].y = tubes[1].y;
            stateObj.activeTube = activeTube;
            return stateObj;
        },
        tick() { loop() }
    }
    API.state = gameState;
    API.tick(); // first tick to setup
    return API;
}

const QRLearn = (() => {
    const game = {}; // holds the game state
    var flappy; // reference to game API used to flap `flappy.flap = true` will flap 
    const Q_table = new Map();
    const actions = {
        STAY: 0,
        JUMP: 1
    };
    const settings = {
        GAMMA: 0.8,
        ALPHA: 0.1,
        THETA: 1,
        MIN_FRAME_SIZE: 15,
        STATE_REWARD: 0.5, // Could not think of a better name.
        GAME_OVER_REWARD: 100,
        Y_SPEED_SCALE: 100,
        JUMP_Y_SPEED: -1.4,
        RANDOM_ACTION_ODDS: 1/90001,
        RANDOM_JUMP_ODDS: 1/4,
        JUMP_ODDS: 1/25,
        tube: {
            CLEARANCE: 3,
            REWARD: 5,
            DISTANCE: 28,
            Y_OFFSET: 22,
        },
        HASH_MASK : 0b1111111111111111111111110,  // This mask is use to change the hash action
      //DIFY_MASK : 0b1111111000000000000000000,  // just for visual clarity of bit positions
      //SPEY_MASK : 0b0000000111111111100000000,
      //TUBE_MASK : 0b0000000000000000011111110,
    }
    const frameBuffer = [], framePool = [];
    var trials = 0;
    var targetTube;

    const randOdds = odds => Math.random() < odds;

    const createHash = state =>
        (((state.diffY + 32) & 0x7f) << 18) +        // 7 bits
        ((((state.speedY - settings.JUMP_Y_SPEED) * settings.Y_SPEED_SCALE) & 0x3ff) << 8) + // range is 0 to just under 512. 10 bits
        ((state.tubeX & 0x7F) << 1) + state.action;  // 7 bits and action 1 bit
        
    function getQ(hash) {
        const q = Q_table.get(hash);
        return q === undefined ? {value: 0} : q.value;
    }
    function getMaxQ(hash) {
        hash &= settings.HASH_MASK;
        const a = Q_table.get(hash);
        const b = Q_table.get(hash + 1);
        return Math.max(a === undefined ? 0 : a.value, b === undefined ? 0 : b.value);
    }
    function getH(hash, action) {
        hash = (hash & settings.HASH_MASK) + action;
        const q = Q_table.get(hash);
        return q === undefined ? 0 : q.value;
    }    
    function setQ(hash, Q) {        
        if (!Q_table.has(hash)) { Q_table.set(hash, Q)  }
    }
    function getAction(state) {
        if (randOdds(settings.RANDOM_ACTION_ODDS)) {
           //log("Going random baby!");
           return randOdds(settings.RANDOM_JUMP_ODDS) ? actions.JUMP : actions.STAY;
        }
        const rewardForStay = getH(state.hash, actions.STAY);
        const rewardForJump = getH(state.hash, actions.JUMP);
        if (rewardForStay > rewardForJump) {
            return actions.STAY;
        }
        if (rewardForStay < rewardForJump) {
            return actions.JUMP;
        }
        return randOdds(settings.JUMP_ODDS) ? actions.JUMP : actions.STAY;
    }
    function rewardTheBird(reward, wasSuccessful) {
        for (let i = frameBuffer.length - 2; i >= 0; i--) {
            const fb = frameBuffer[i];
            let rewardForState = reward - Math.abs(fb.diffY);
            if (!wasSuccessful) {
                if (fb.diffY >= settings.THETA && fb.action === actions.JUMP) {
                    rewardForState = -rewardForState;
                } else if (fb.diffY <= -settings.THETA && fb.action === actions.STAY) {
                    rewardForState = -rewardForState;
                } else {
                    rewardForState = settings.STATE_REWARD;
                }
            }
            const future = frameBuffer[i + 1];
            const optimal = getMaxQ(future.hash);
            const Q = getQ(fb.hash);
            const updateValue = settings.ALPHA * (rewardForState + settings.GAMMA * optimal - Q.value);
            Q.value += updateValue;
            setQ(fb.hash, Q)
        }
    }   

    function triggerGameOver() {
        rewardTheBird(settings.GAME_OVER_REWARD, false);
        //log("GameOver:", "Score " + game.score, "Rules " + Q_table.size, "Trials " + trials);
        targetTube = undefined;
        trials++;
    }
    function nextStep() {
        var state;
        if (game.gameState !== flappy.states.GAME) {
            return;
        }
        const t0 = game.tubes[0], t1 = game.tubes[1];
        const x0 = t0.x + settings.tube.CLEARANCE;
        const x1 = t1.x + settings.tube.CLEARANCE;
        if (game.birdX < x0 && (t0.x < t1.x || x1 < game.birdX)) {
            if (targetTube === t1) {
                rewardTheBird(settings.tube.REWARD, true);
            }
            targetTube = t0;
        } else {
            if (targetTube === t0) {
                rewardTheBird(settings.tube.REWARD, true);
            }
            targetTube = t1;
        }
        if (targetTube.x - game.birdX > settings.tube.DISTANCE) {
            return;
        }
        if(framePool.length > 0){
            state = framePool.pop();
            state.speedY = game.birdYSpeed;
            state.tubeX = targetTube.x;
            state.diffY = targetTube.y + settings.tube.Y_OFFSET - game.birdY;
        }else{
            state = {
                speedY: game.birdYSpeed,
                tubeX: targetTube.x,
                diffY: targetTube.y + settings.tube.Y_OFFSET - game.birdY,
            };
        }
        state.hash = createHash(state);
        state.action = getAction(state);
        state.hash = (state.hash & settings.HASH_MASK) + state.action;
        
        frameBuffer.push(state);
        if(frameBuffer.length >= settings.MIN_FRAME_SIZE){
            framePool.push(frameBuffer.shift());
        }
        if (state.action === actions.JUMP) {
            flappy.flap = true;
        }        
    }
    return {
        step() {
            flappy.gameState(game);
            if (game.gameState === flappy.states.GAME_OVER) {
                triggerGameOver();
            }
            nextStep();
        },
        set flappy(val) {
            flappy = val;
        }
    };
})();

const log = (...args) => { logEl.textContent = args.join(" ") }

const ctx = canvas.getContext("2d");

var started = false;
var framesPerTick = 1;
var stepsPerFrame = 1000;
var frameCount = 0;
var flap = false;
const gameState = {};
const game = flappy();
QRLearn.flappy = game;
game.gameState(gameState);
flappyRenderer.state = gameState;
flappyRenderer.draw(ctx, 0, 0, ctx.canvas.width, ctx.canvas.height);
var mode = "Play";
requestAnimationFrame(mainLoop);
playEl.addEventListener("click",() => {
    mode = "Play"
    stepsPerFrame = 0;
    framesPerTick = 4;      
    start();
});
learnFastEl.addEventListener("click",() => {
    mode = "Learn fast";
    stepsPerFrame = 10000;
    framesPerTick = 1;
    start();
});
learnEl.addEventListener("click",() => {
    mode = "Learn";
    stepsPerFrame = 1;
    framesPerTick = 1;   
    start();
});
seedEl.addEventListener("click",() => {
    const seed = Date.now();
    game.seed = seed;    
    log("Seeded random " + seed);
});
randEl.addEventListener("click",() => {
    game.seed = null;    
    log("Game random");
});
canvas.addEventListener("mousedown",() => {
    if (mode === "Play") {
       stepsPerFrame = 0;
       framesPerTick = 4;   
       flap = true;
       start();
    }
});
function start() {
   if (!started) {
       game.state = game.states.GAME;
       started = true;
   }
}
log("Game in seeded random mode");
function mainLoop() {
    frameCount ++;
    if (mode === "Learn" || mode === "Learn fast") {
        if (frameCount % framesPerTick === 0) {
            for (let i = 0; i < stepsPerFrame; i++) {
                game.tick();
                QRLearn.step();
            }
            game.gameState(gameState);
            flappyRenderer.state = gameState;
            highScoreEl.textContent = "Hi score " + gameState.hiScore;
        }
    } else {
        if (frameCount % framesPerTick === 0) {
            game.tick();
            game.gameState(gameState);
            flappyRenderer.state = gameState;
            highScoreEl.textContent = mode + " Best " + gameState.hiScore;
        }
    }
    flappyRenderer.draw(ctx, 0, 0, ctx.canvas.width, ctx.canvas.height);    
    if (mode === "Play") {
        if (flap) {
           game.flap = true;
           flap = false;
        }
    }    
    requestAnimationFrame(mainLoop);    
}
#canvas {
  width : 192px;
  height : 128px;
  image-rendering : pixelated;
}
body {
    user-select: none;    
    -moz-user-select: none;    
}
<input id = "playEl" type="button" value = "play"/>
<input id = "learnFastEl" title="Learn at 10,000 frames 60th sec" type="button" value = "learn fast"/>
<input id = "learnEl" type="button" value = "learn"/>
<input id = "seedEl" title="Use seeded random and reseed" type="button" value = "seed"/>
<input id = "randEl" title="Game totaly random" type="button" value = "rand"/>
<span id="highScoreEl"></span><br>
<canvas id="canvas" width="32" height="32"></canvas>
<div id="logEl"></div>

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ I literally don't have words to describe how amazed I am by the quality of your answer! This, in every sense, is nothing less than gold to me. Your suggestions regarding the fixes, using a seeded environment and decoupling rendering are really thoughtful. Moreover, I don't know how I can thank you for taking out extra time to review the rest of my code, your generosity exceeds limits. I don't have much background in JavaScript and hence could have never foreseen ways to optimize the game in the manner you've put forth - it's just incredible. \$\endgroup\$ – nellex Nov 4 '18 at 18:14
  • \$\begingroup\$ Also, it warms my heart knowing that you liked playing around with this hobby project of mine, and that it introduced you to the beautiful world of Q-learning :) I'll be implementing your suggested ideas over the coming week. Please feel free to contribute to this repository of mine as well, I'll feel honoured. \$\endgroup\$ – nellex Nov 4 '18 at 18:20
  • \$\begingroup\$ In the end, I just would like to know if the documentation for this project was sufficient enough to convey the idea behind Q-learning in a general way or is there still some scope for improvement? Thank you! \$\endgroup\$ – nellex Nov 4 '18 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.