Computed Values with RxJS and @ngrx/store
July 25, 2016

Cross-post from the Rangle.io blog.

Introduction

@ngrx/store is a popular store architecture for Angular 2. It promotes one-way data binding for components:

  • Components subscribe to updates from the store
  • Components dispatch events to the store
  • Reducers receive dispatched events and modify the store data structure
  • …and repeat.

We’ve used @ngrx/store on several Angular 2 projects at Rangle. @ngrx/store was built specifically for Angular 2 and leverages the wonderful JavaScript Reactive Extensions library (RxJS). This allows updates to the store to be consumed as observable streams in our components. We’ve previously written how Observables are central to Angular 2.

@ngrx/store in principle is very similar to Redux and the concepts should be familiar to someone with knowledge of Redux. Most Redux best practices have an equivalent in @ngrx/store and we’ll be covering one of those today: computed values.

Reselect with Redux

First let’s contrast with the best practices in Redux. Reselect is a selector library for Redux. Selectors are memoized functions used to compute derived values from the store. Being memoized implies values are only computed when the inputs to the selector function change. With Reselect, we don’t need to put computed values in the store. We can instead store the minimal state and recompute derived data only when necessary. We’ve covered this topic recently in an article titled Improving React and Redux performance with Reselect.

We can achieve a similar effect with @ngrx/store using built-in RxJS’s methods. I’ll illustrate on an example application.

Example Application

The examples below use the following monotonically increasing counter store instrumented into an Angular 2 TypeScript application:

counter.reducer.ts

import {ActionReducer, Action} from '@ngrx/store';

export const counter: ActionReducer<number> = (state: number = 0, action: Action) => {
  switch(action.type) {
    case 'INCREMENT':
      return state + 1;
    default:
      return state;
  }
};

bootstrap.ts

import {bootstrap} from '@angular/platform-browser-dynamic';
import {App} from './app';
import {provideStore} from '@ngrx/store';
import {counter} from './reducers/counter';

bootstrap(App, [provideStore({counter})]);

Note: The examples in this blog post can be found on Plunker.

Computed values with RxJS

In the examples below we’ll be selecting a value from the store and performing an operation on it. We need the store instance to do this, which can be added to a component through Angular 2’s dependency injection. The instance of the store is technically a BehaviorSubject which inherits the methods from Observable.

select shares the same performance characteristics as Reselect, as it uses the distinctUntilChanged operator on the observable it returns (see here). This effectively memoizes any subscribers to select, similar to Reselect.

Map

For computing a value from the most recent store data, we can combine @ngrx/store’s select method with RxJS’s map operator. map will receive the latest value from the store and apply a transformation to it, similar to JavaScript’s map. In my experience map is the most common operation used when computing values from the store.

import {Component} from '@angular/core';
import {Store} from '@ngrx/store';
import {Observable} from 'rxjs/Observable';
import {IStore} from './store.interface';
import 'rxjs/Rx';

@Component({
  selector: 'power',
  template: `
  <div>
    <h2>Power (map example)</h2>
    <ul>
      <li>2<sup></sup> = </li>
    </ul>
  </div>
  `
})
export class PowerComponent {
  counter$: Observable<number>;
  power$: Observable<number>;

  constructor(private store: Store<IStore>) {
    this.counter$ = this.store.select('counter');
    this.power$ = this.counter$.map((value) => Math.pow(2, value));
  }
}

Scan

RxJS’s scan operator is similar to reduce in JavaScript, except reduce acts on arrays while scan acts on streams. Streams differ from JavaScript arrays in that values are added to them over time. They are not operated on entirely at once. scan allows us to operate on all values of a stream over time and return a singular value. This value is updated when new values are added to the store. Here we’ll use scan to compute the factorial of the counter in the store:

import {Component} from '@angular/core';
import {Store} from '@ngrx/store';
import {Observable} from 'rxjs/Observable';
import {IStore} from './store.interface';
import 'rxjs/Rx';

@Component({
  selector: 'factorial',
  template: `
  <div>
    <h2>Factorial (scan example)</h2>
    <ul>
      <li>! = </li>
    </ul>
  </div>
  `
})
export class FactorialComponent {
  counter$: Observable<number>;
  factorial$: Observable<number>;

  constructor(private store: Store<IStore>) {
    this.counter$ = this.store.select('counter');
    this.factorial$ = this.counter$.scan((acc, value) => acc * value);
  }
}

Selecting across keys

You’ll notice in our previous examples computed values were based on one key from our store (through select('keyName')). What if we want a value derived from multiple store keys?

We can pass @ngrx/store’s select a function, allowing us to select arbitrary subsets of store data instead of a single key. For example, if our store also had a name key and we wanted to grab them both, we could do the following:

this.counterAndNameSelect$ = this.store.select((state) => {
  return {
    counter: state.counter,
    name: state.name
  };
});

Additionally, RxJS allows us to combine multiple streams into one by using the combineLatest operator. This can be used as alternative to passing select a function. This is equivalent to the select above:

this.counterAndNameCombine$ = this.store.select('counter')
  .combineLatest(this.store.select('name'), (counter, name) => {
    return {
      counter,
      name
    };
  });

Use with Angular 2

Angular 2 treats RxJS streams as first class citizens. Observable’s can be leveraged directly in HTML templates by using Angular’s async pipe. In our components, we can save Observables as public values and access them in our templates without having to manually subscribe. This is the approach we followed in the above examples.

Resources

@ngrx/store puts the full power of RxJS is as your disposal! I’ve only shown as few ways this power can be harnessed. For more information on @ngrx, Redux and RxJS, see the following resources:

Thanks to the support squad at Rangle.io, namely Evan Schultz and Cosmin Ronnin for reviewing this.

programming ngrx rxjs redux

Artifact Deployment via Google Drive
July 13, 2016

The Twelve-Factor App is a set of best practices for building web applications. Every project I build adheres to the principles laid out at the above website and I highly recommend internalizing them if you’re a full stack developer or in dev ops.

One of the key points is “dev/prod parity”: minimal difference between development, staging and production environments. For staging and production, the best practice is produce an artifact (typically an archive of everything needed to run your application, including dependencies) during your build step and deploy the same artifact to both environments. Deployment of a single artifact with its dependencies guarantees all platforms are running the exact same code, they only differ in configuration.

It’s common to see Amazon S3 used for artifact hosting, particularly if the app is also deployed on Amazon EC2. While S3 is cheap, it’s not free :). In my quest to build a completely free web application stack, I’ve built a way to use Google Drive as the artifact host. This blog post will break down how to upload your artifact to Google Drive from a Continuous Integration (CI) tool.

Continuous Integration (CI)

My CI tool of choice is Shippable. Shippable is similar to CircleCI or TravisCI (in fact it supports the .travis.yml format verbatim!), however it’s free for private repos for BitBucket and GitHub. I use it primarily with BitBucket for a one-two punch of free code hosting and CI.

Google Drive

Interaction with Google Drive is done through prasmussen/gdrive, a command line Google Drive client written in Go. It supports most platforms (Windows, Linux, Mac OS X, *BSD). It is single binary, meaning it’s easily bundled with our application.

The Magic

Shippable works by reading the steps in shippable.yml. Here’s an example shippable.yml for a NodeJS project:

node_js:
  - 6.2.1
language: node_js
env:
  global:
    - secure: [OMITTED]
script:
  - npm run test
  - NODE_ENV=production npm run deploy
after_script:
  - ./bin/upload.sh

This implicitly runs npm install loading dependencies from our package.json, runs our tests and builds the final artifact. Once that is all completes successfully, the after_script step is run. This is where the magic happens. In our project we’ve defined a shell script (./bin/upload.sh) that archives the app (and node_modules) and uploads to Google Drive. Here it is:

#!/bin/sh
FIXED_BRANCH=$(echo $BRANCH | sed 's/\//-/g')
ARCHIVE=$REPO_NAME-$FIXED_BRANCH-$(date +%Y-%m-%d_%H_%M_%S)-$COMMIT.tar.bz2
echo "Creating archive $ARCHIVE"
tar cfj $ARCHIVE dist
FILESIZE=$(stat -c%s "$ARCHIVE")
echo "Finished archive (size $FILESIZE), starting Google Drive upload"
./bin/gdrive upload --refresh-token $GDRIVE_REFRESH_TOKEN --parent $GDRIVE_DIR "$ARCHIVE"
echo "Finished Google Drive upload"

This script uses the prasmussen/gdrive binary ./bin/gdrive. Download the appropriate gdrive binary for your build system and put it in your bin folder in your project.

There are a number of environment variables used in the above script. Some are exposed by Shippable automatically (see Configure Your Build - Using environment variables) and some we will need to provide ourselves. I’ll go into detail explaining each one:

  • $BRANCH: Git branch name.
  • $FIXED_BRANCH: File system safe version of the git branch name – replaces / in the branch name with a - using sed. This may not make the branch name 100% safe, but / is the most common character in git branch names that is invalid in file names.
  • $REPO_NAME: Repository name.
  • $COMMIT: Commit hash for the latest commit in the branch.
  • $ARCHIVE: Artifact filename. It is a concatenation of $REPO_NAME, $FIXED_BRANCH, a datetime and $COMMIT.
  • $FILESIZE: Filesize in bytes of the artifact archive
  • $GDRIVE_REFRESH_TOKEN: Google Drive OAuth2 refresh token. This is a persistent authentication key used by the Google Drive client. We need to provide this!
  • $GDRIVE_DIR: Google Drive parent directory ID. We need to provide this!

There are two keys we need to provide to make this work. How do we get them and how to we let our build process know about them?

Google Drive Refresh Token

Download the prasmussen/gdrive binary for your system and run the following command.

$ ./gdrive list
Authentication needed
Go to the following url in your browser:
https://accounts.google.com/o/oauth2/auth?access_type=offline&client_id=...

Enter verification code: ...
Id                             Name                                       Type   Size      Created
0B1h7GlNyl9MaSnNMY0RRWW5PREU   app-client-feature-...3689705bfe.tar.bz2   bin    8.0 MB    2016-07-11 22:25:17
0B1h7GlNyl9MaWE8ybFk1SjROMWc   app-server-master-2...34b0e75e79.tar.bz2   bin    16.3 MB   2016-07-11 22:22:59

It will ask you to authenticate at a Google URL. Go to the URL, login with your Google Account, permit the app to view/edit your Google Drive files and copy/paste the verification code you’ve received back into the command line prompt.

Notice that when you run ./gdrive list a second time it no longer prompts you for authentication. This is because the client has cached your OAuth2 access tokens and refresh tokens in the file ~/.gdrive/token_v2.json:

{
  "access_token": "...",
  "token_type": "Bearer",
  "refresh_token": "...",
  "expiry": "2016-07-13T11:47:00.424973987-04:00"
}

Make note of your refresh token for later.

Google Drive Folder ID

Go to Google Drive and navigate to the folder where you wish artifacts to be uploaded. Copy the ID from the URL bar.

Google Drive folder URL bar

Encrypted Environment Variables

Shippable has this nifty feature that lets you provide encrypted environment variables to your build environment. On Shippable navigate to Your Project -> Settings -> Encrypt.

Encrypt

Here we can encrypt the two environment variables we need, $GDRIVE_REFRESH_TOKEN and $GDRIVE_DIR:

Environment Variables

Copy the secure value to your shippable.yml. Shippable holds the secret key to the encrypted phrase so only they can decrypt it on build. That should be all you need to get your project artifact uploaded to Google Drive on every successful build!

Deployment with Ansible

Ansible uses a similar deployment script, ./bin/download.sh. This will connect to your Google Drive, read the contents of your $GDRIVE_DIR and find the most recent artifact that matches. It will then download this artifact to a /tmp folder locally.

#!/bin/sh
ARGS=("$@")
TMP_DIR=/tmp
PROJECTS="app-server"
BRANCHES="master"
GDRIVE_DIR="..."
GDRIVE_REFRESH_TOKEN=${ARGS[0]}
GDRIVE_BIN=./bin/gdrive

GDRIVE_OUTPUT=$($GDRIVE_BIN --refresh-token "$GDRIVE_REFRESH_TOKEN" list -q "name contains '$PROJECT-$BRANCH-'" --order "name desc" -m 1 --no-header --name-width 0)
IFS='   ' read -a GDRIVE_FIELDS <<< "$GDRIVE_OUTPUT"
$($GDRIVE_BIN --refresh-token "$GDRIVE_REFRESH_TOKEN" download --path "$TMP_DIR" --no-progress -f "${GDRIVE_FIELDS[0]}" >/dev/null 2>&1)
echo "${GDRIVE_FIELDS[1]}"

Below is the ansible task that runs ./bin/download.sh, downloads the artifact locally, uploads it to your server, unarchives it and starts the service! Variables such as the gdrive_refresh_token are stored in Ansible’s encrypted vault.

- name: Download latest release from Google Drive
  register: gdrive_downloads
  local_action: shell ./bin/download.sh "{{ gdrive_refresh_token }}"
  become: false

- name: Copy app-server artifact {{ gdrive_downloads.stdout_lines[0] }}
  copy: src={{ temp_dir }}/{{ gdrive_downloads.stdout_lines[0] }} dest={{ common_deployer_home }}

- name: Unarchive app-server
  unarchive: src={{ gdrive_downloads.stdout_lines[0] }} copy=no dest={{ common_deployer_home }}

- name: start app-server
  service: name=app-server state=started

Moving Forward

This approach emphasizes a moving-forward mentality: code deployed is always the latest from the master branch. To “rollback” code, you can simply issue a git revert on an erroneous commit, push it up, wait for this commit to be build and uploaded, and then redeploy. In emergencies the logic in ./bin/download.sh can be modified locally to return older artifacts.

That’s it!

There you have it. I’ll leave the rest of the Ansible deployment script as an exercise to the user, but the core idea of uploading and downloading artifacts to Google Drive has been demonstrated.

Upshot

Once this build flow is established, I’ve found it to be a remarkably stable way of doing deployment. Deploys are simple, fast and reproducible. There is no fetching dependencies on the server. When combined with Google Drive, Shippable, Bitbucket and Amazon EC2’s free tier, this is a complete free web application stack that follows Twelve-Factor best practices.

Happy deploying!

devops

Building a Chat Bot for Fun and Profit
May 18, 2016

This blog post is based on a lunch and learn talk I gave at Rangle.io on May 13, 2016.

On April 16th, 2016 Telegram unveiled their “$1,000,000 to Bot Developers. For free.” challenge. Developers were incentivized by a chance to win $25,000 USD to build novel, interesting bots on Telegram’s platform. Telegram is not the only major chat platform to embrace bots. Slack, Whatsapp, Facebook, Kik, Skype all have well developed bot APIs with bots ranging from image and video search, games to weather, sports and translation.

There’s no shortage of bot ideas out there and many developers are building them. This got me thinking. How hard would it be to build a bot anyway? What separates a bot from a command line REPL? This blog post details my journey to find out.

What is a bot?

Let’s start with a definition:

A computer program designed to simulate conversation with human users, especially over the Internet.

- Google

Okay. A bot is supposed to simulate conversation, so what makes a conversation in bot-land? Conversations are:

  • Message based
  • Realtime
  • Intelligent (contextual)

Therefore we must give our bot all of these qualities. It must have a brain, or at the very least be able to make intelligent assertions about incoming data.

How to make an intelligent bot?

State machines! State machines allow you to give the bot context. Incoming messages can set the bot in a state that lets it know what to expect of the next message.

What are state machines?

Another definition, a state machine (otherwise known as a finite-state machine) consists of:

  • An initial state or record of something stored someplace
  • A set of possible input events
  • A set of new states that may result from the input
  • A set of possible actions or output events that result from a new state

Simple finite state-machine

Above is an example of a simple finite-state machine. At any time it is in one state of a set of known finite states. From each state are defined transitions to other states.

Operations: Commands vs. Actions

For our bot, there are two types of operations. Here’s the lexicon we’ll be using:

  • Commands are global top-level chat operations. They begin with a “/” and can be run at any time in the conversation lifecycle.
  • Actions are contextual responses. They are handled by a specific function for each state.

The flowchart below shows the message parsing logic for commands and actions:

Commands vs. Actions in flowchart form

Now that we have the basics, let’s build a bot!

We’re going to be building Expense_Bot, a single-entry accounting bot. This bot will allow you create accounts and log transactions such as income and expenses to those accounts through a chat based interface. We’re going to be using Node.js and some database (pick your poison: MongoDB, RethinkDB, /(My|Postgre)?SQL(lite)?/) for this exercise.

Commands

Let’s define a set of commands for our chat bot:

/start - Returns this list of commands
/newaccount - Create a new account
/accounts - List accounts
/transaction - Log transaction (expense or income)
/history - List previous transaction history
/charts - View a chart image summary of your expenses and income
/spreadsheet - Download full data
/delete - Delete a transaction (expense or income)
/deleteaccount - Delete an account
/deleteall - Delete all info Expense_Bot knows about you
/cancel - Cancel current operation

For our example we’re going to go through the /newaccount workflow and build a conversation.

States

States are constants string literals defined as follows:

const STATES = {
  NONE: 'NONE',
  NEW_ACCOUNT_TYPE: 'NEW_ACCOUNT_TYPE',
  NEW_ACCOUNT_NAME: 'NEW_ACCOUNT_NAME',
  NEW_ACCOUNT_INITIAL_BALANCE: 'NEW_ACCOUNT_INITIAL_BALANCE'
};

Data structures

I’m going to define a set of data structures to hold our commands and actions.

const commands = {
    help: function* (msg) {
        // output help message
    },
    newaccount: function* (msg) {
        // start new account
    };
};

const actions = {
    [STATES.NONE]: function* (msg) {
        // NONE state launches commands ^
    },
    [STATES.NEW_ACCOUNT_INITIAL_BALANCE]: function* (msg) {
        // Validates response is a number
        // Transition to NEW_ACCOUNT_TYPE
    }
    // ...,
    [STATES.NEW_ACCOUNT_TYPE]: function* (msg) {
        // Validates response is account type
        // Transition to NEW_ACCOUNT_NAME
    }
    // ...
};

Entry Point

All messages are triaged by an entry point. I’m using ES6 generators to leverage the yield keyword and create co-routines. These are asynchronous function calls that appear synchronous, with the value returned inline, eliminating the need for a callback. The bluebird promise library gives us Promise.coroutine(), a wrapper around generators that allows us to use yield to return the value of a promise. Errors that would normally be given to a .catch are raised, allowing us to use the traditional JavaScript error catching mechanism try { } catch (e) { }. Cool!

const Promise = require('bluebird');

const main = Promise.coroutine(function* (msg) {
  var state;

  if (msg.text.startsWith('/')) {
    state = yield createNoneState(msg);
  } else {
    var collection = yield State
      .orderBy({index: r.desc('createdAt')})
      .filter({telegramId: msg.from.id})
      .limit(1)
      .run();

    state = !collection[0] ? yield createNoneState(msg) : collection[0];
  }

  runAction(state, msg);
});

This parses the contents of the message. If it begins with a /, it creates a new State record in the database with a STATE of NONE. The idea is if the user is issuing a global command, its current context becomes invalid. The global command will then set them in a new state. If their message does not begin with a /, it must be a contextual response, so we retrieve their current state and direct them to the runAction function. This function looks like:

function runAction(state, msg) {
  const action = actions[state.state];

  if (!action) {
    bot.sendMessage('That action is not understood. Run /start to get the list of actions.');
    return;
  }

  Promise.coroutine(action)(state, msg);
}

This references the actions data structure above. In each handler we can do validation on the incoming response. So for example when the user is in the NEW_ACCOUNT_INITIAL_BALANCE, the following handler will be used:

const actions = {
    [STATES.NEW_ACCOUNT_INITIAL_BALANCE]: function* (state, msg) {
      const validNumber = DOLLAR_REGEX.exec(msg.text);
      if (validNumber && validNumber[1]) {
        // Transition them to new account
        yield new State({
          telegramId: msg.from.id,
          state: STATES.NEW_ACCOUNT_TYPE,
          meta: {,
            balance: validNumber[1]
          }
        }).save();

        bot.sendMessage(msg.from.id, `What type of account is it?`);
      } else {
        bot.sendMessage(msg.from.id, 'I cannot parse that number. Please enter an initial balance of the format $1234.56.');
      }
    }
    // ...
};

Conversation Example

Consider the following conversation with an accounting bot:

<robot> Hello, welcome to Expense_Bot!
<human> /newaccount
<robot> What is the initial balance for your new account?
<human> $750.00
<robot> What type of account is it?
<human> Savings
<robot> And finally what is the name of this account?
<human> Royal Bank
<robot> Great! New account "Royal Bank" created.

In the above example:

  • /newaccount is a command. At any time it can be run and interrupt the flow of the conversation because it is global.
  • $750.00 is an action. It only makes sense if the current state is expecting it. If you asked me “What is the initial balance for your new account?” and I responded $750.00, that conversation would make total sense. However if I walked up to you and said “$750.00” out of nowhere, you would have no idea what I’m talking about. This is the definition of context.

When parsing the second message from the human, the bot knew to expect a dollar figure. Why? When the human asked to create a new account (/newaccount), it put the bot into state NEW_ACCOUNT_AMOUNT. In our bot we can define a specialized handler for the NEW_ACCOUNT_AMOUNT state that will validate the next response (is it a dollar amount?), save any persistent data ({balance: 750.00}). After they submit a valid dollar figure, we ask the user what type of account this is and transition them to the NEW_ACCOUNT_TYPE state. After the process is done we save the new account record and transition the human back to the NONE state.

This transition of states and building of data is illustrated in the table below.

Current State Next State Incoming Message Data (after message)
NONE NEW_ACCOUNT_INITIAL_BALANCE /newaccount
{}
NEW_ACCOUNT_INITIAL_BALANCE NEW_ACCOUNT_TYPE $750.00
{
  balance: 750.00
}
NEW_ACCOUNT_TYPE NEW_ACCOUNT_NAME Savings
{
  balance: 750.00,
  type: 'Savings'
}
NEW_ACCOUNT_NAME NONE Royal Bank
{
  balance: 750.00,
  type: 'Savings',
  name: 'Royal Bank'
}

After the final step, the data is committed to the database as a new Account model. There you have it. The finite-state machine model of computing fits well with a conversation chat bot. This approach works well with transactional or wizard style bots that walk users through a number of steps. Now go write your own bot!

bots telegram nodejs

Optimizing Move Generation from 200K to 2.5M moves/s
January 06, 2016

Originally posted at http://ceruleanjs.joeyrobert.org/.

CeruleanJS has a pseudo-legal move generation algorithm. It generates all possible moves for a position (even ones that put the king in check or castle the king through check) and the full legality is tested during the addMove() function. This is because the move needs to be added before check detection can work. Fast move generation is key to a strong chess engine: the more moves you can generate and evaluate per second, the stronger it will be. This post is about my experiences optimizing CeruleanJS’s move generation.

At the start of this document, CeruleanJS was weighing in at a measly 200,000 moves/s on my MacBook Pro. Cerulean (the original C implementation) managed 20,000,000 moves/s in a single thread. CeruleanJS hopes to achieve this level of performance, the question is: can it?

Faster Piece List

A piece list is a cache of which board indices are occupied by which side. CeruleanJS has two piece lists, one for each white and black. Think of it as a way to optimize looping over all 64 squares. Instead we only need to loop over the pieces we’re generating moves for (maximum 32).

The first iteration of CeruleanJS contained a dead simple piece list implementation:

class PieceList {
    constructor() {
        this.indices = [];
    }

    push(index) {
        this.indices.push(index);
    }

    remove(index) {
        let reverseIndex = this.indices.indexOf(index);
        this.indices.splice(reverseIndex, 1);
    }
}

There’s a couple things wrong with this implementation. First, the indices array is set to an initial length of 0, so each push has to allocate more memory to store the new item. Second, removing an index is expensive. It requires a linear scan of the indices array to remove a specified index, which is O(n). Third, indices is spliced to remove the found index. This reduces the size of the array, but forces all values after reverseIndex to be shifted by one. I’m can’t speculate on the internals of the JS Array data structure, but this may cause a rewrite of up to 16 squares (again, O(n)). What data structure would allow quick creation and removal?

What if we implement a scheme such that when an index is removed, it is replaced by current last element in the list? A piece list only needs to contain at most 16 pieces. We can do the allocation for all 16 elements up front. Also, what if we maintain a reverse board array that maps board index to index in piece list? This would remove the linear scan needed to find the object to remove.

class PieceList {
    constructor() {
        this.indices = new Array(16);
        this.reverse = new Array(constants.WIDTH * constants.HEIGHT);
        this.length = 0;
    }

    push(index) {
        this.reverse[index] = this.length;
        this.indices[this.length] = index;
        this.length++;
    }

    remove(index) {
        this.length--;
        var reverseIndex = this.reverse[index];
        this.indices[reverseIndex] = this.indices[this.length];
        this.reverse[this.indices[reverseIndex]] = reverseIndex;
        this.indices[this.length] = undefined;
        this.reverse[index] = undefined;
    }
}

This allows for an O(1) piece list implementation for both adding and removing items.

Remove ‘let’ keyword in tight loops

The let keyword is a relatively new addition to ES6, which allows variables to be defined at the block level (for, if, while, do, switch, or { }). This is great for encapsulating variables in a for loop or if statement.

However when let is used two levels deep in nested for loops, all that variable allocation and deallocation can be expensive and can generate a lot of garbage.

The solution is to use a single variable declared outside of any loop and to modify this value as necessary. This trades off safety for performance, but resulted in a large performance increase for Cerulean :).

Switch expensive lookups from Objects to Arrays

A significant performance increase was noticed when two lookup objects were converted to arrays. These lookup objects were used in tight loops (generateMoves(), addMove(), subtractMove()) where the additional overhead of casting a value to a string was cost prohibitive.

Add history less

CeruleanJS uses an internal history array to restore unrecoverable information (i.e. information that cannot be inferred) during the subtractMove() function. Some examples of unrecoverable information are:

  • En passant
  • Castling
  • Half move clock
  • Zobrist keys (these are recoverable but are loaded from the history array for simplicity)

It makes sense for addMove() and subtractMove() to be exact inverses of each other, where addMove() pushes a new array to the history array, and subtractMove() pops this off. This however would generate an array for every move. As it turns out, at each node in the search tree, all subsequent moves share the same history. Therefore we only need to save to the history array once per move generation instead of once for every move in every move generation, saving dozens of array allocations.

Move as a 32-bit integer

This may seem obvious to other chess programmers, but using a single 32-bit integer to represent a move object is significantly faster than using an object-structure like an array. CeruleanJS initially used a simple array [from, to, promotion]. [] in JavaScript is short for new Array(), so in reality you’re doing a lot of object allocation. Integers create less garbage in this respect.

Cerulean’s move data structure is:

ORDER  BITS   CAP PRO TO      FROM
000000 000000 000 000 0000000 0000000
^ MSB                           LSB ^

This breaksdown to the following distribution:

  • 7 bits for FROM index
  • 7 bits for TO index
  • 3 bits for PROmotion piece (Q/R/B/N)
  • 3 bits for CAPtured piece (any or empty)
  • 6 bits for BITS (metadata)
  • 6 bits for ORDERing

This dense move structure requires less data to be saved on the board’s internal history array.

Have your move generator help you out

Your pseudolegal move generator has a lot of information about the move your generating. Is it a pawn move? Is it a capture? Is it a double push? Save this information in a metadata field in your move and base your addMove()/subtractMove() functions on it.

Originally CeruleanJS only passed in [from, to, promotion] and inferred all other information from the board state. This proved to add a lot of overhead to addMove()/subtractMove() when this information is available earlier in the pseudolegal move generator. For a capture for instance — you’d be essentially double checking that the board[to] is occupied by an opponent square: in generateMoves() and addMove().

CeruleanJS switched to a “bits” based addMove()/subtractMove() functions, where the “bits” flag in a move is used to switch() to specialized move for that bit type.

Pass moves array by reference

The move generator is a single function, generateMoves() loops over all pieces for a side and has a big switch statement for the piece we’re looking at (pawn, knight, bishop, rook, queen, king). This calls a bunch of other functions pawnMoves(), rookMoves(), etc.

Originally these functions returned a list which was concatenated to the main move list.

Instead of using concat, we can use a single move array that is passed by reference to all the sub functions (pawnMoves(moves), etc.), which then modify it. Using a single array with a mutable state that is passed by reference to other objects that modify it is considered bad practice almost anywhere that codes JavaScript. However, by doing this we reduce the amount of garbage arrays (and .concat()) created during the move generation process.

Use TypedArrays (Uint32Array) for Board and Piece List

This makes the lookup of board positions significantly faster. Roughly a 2x speed increase was noticed when switching to this. This is because less checks are required on item access in JavaScript.

An additional increase of 14% was seen switching from Arrays to Uint32Array in the PieceList.

Testing showed this would not be as advantageous for Move lists (due to the number Uint32Array allocations, which can be as large as 218 in one turn!). A possible optimization here is to use one move list per depth and maintain the list of preallocated move lists in the board. More testing is needed on this front.

Future Improvements

A number of other data structures in my application could be switched to TypedArrays, namely Zobrist keys, which are looked up frequently during the addMove()/subtractMove() cycle. However, this did not prove to be as beneficial since Zobrist keys are currently a multi-dimensional data structure. JavaScript only supports a 1 dimensional TypedArray and the multiplication required to generate the key look took away any possible speed improvements.

As a whole, these improvements gave a 10-15x speed boost for CeruleanJS, which clocks in at around 2,500,000 moves/s. The performance remains an order of magnitude slower than Cerulean in C (and 2 orders of magnitude slower then a well optimized state-of-the-art chess move generator), but it will suffice for a sufficiently strong JavaScript chess engine.

Until next time, happy chessing!

chess chess programming ceruleanjs

History of joeyrobert.org
June 22, 2015

Version 1 (2007 - 2009)

joeyrobert.org version 1

joeyrobert.org has long been my home on the web. Registered in 2007 prior to joining the University of Waterloo, joeyrobert.org was intended to document my entire university career. It had my courses outlined for all 5 years. I vigorously studied the Undergraduate Calendar and would post all documents related to my courses on it. It was written using PHP 4.3, with a blog component built using CuteNews and a custom built lifestream component pulling in feeds from my social media. The website was red, grey and white and fluid width on its main layout, but also featured themes including an nfo style with monospaced font and an ASCII art Anarchy symbol. This version remained online until sometime in 2009 when I got an unfortunate call from a faculty member of the Physics Department regarding the course materials I posted. I promptly took it down.

Version 2 (2010 - 2011)

joeyrobert.org version 2

This version was built with Ruby and Sinatra. It features a main page which highlights a few software projects I've worked on. This site was spawned around the time I began working on harmonyofchaos and so featured a number of Guitar Pro songs I had written (I typically use SoundCloud today for this purpose). I additionally built a lifestream and blogging engine admin interface using DataMapper and SQLite.

Version 3 (2012 - Present)

joeyrobert.org version 3

This version errs on the side of simplicity. Version 3 is a statically generated site built using Jekyll. The templating is Bootstrap 2.3.3, using a modified Ubuntu theme from Bootswatch with my own stylings. It features a left hand navigation with a responsive design -- the left hand menu appears above the content on lower-width viewports. The site is dated and the HTML minified on build using Rake and HTML compressor. Overall this workflow is simple and can be deployed to any static host.

Who knows what the future brings?

joeyrobert.org will always be a personal playground for webthings. I hope to keep iterating on it, but for now V3 meets my needs as a personal brand.

website history