Example code

Let me demonstrate the potential problems of the default encoding settings with the following example code:

1
2

data = File.read('test.txt')
puts data.gsub(/Example/, 'Coding')

1

Example with ❤

Now when I connect to a server with that code installed via SSH from my Mac, everything works perfectly fine:

1
2
3
4

$ ruby example.rb
Coding with ❤
$ echo $?
0

But when I connect from a Windows machine to the same server and do the same thing, I end up with a different result:

1
2
3
4
5

$ ruby example.rb
example.rb:2:in `gsub': invalid byte sequence in US-ASCII (ArgumentError)
        from example.rb:2:in `<main>'
$ echo $?
1

Behind the scenes

When you connect to a server via SSH, modern clients send environment variables to pass on your local locale settings. You can see this once you enable the debug output of your SSH client:

1
2
3
4

debug1: Sending environment.
debug1: Sending env LC_ALL = en_US.UTF-8
debug1: Sending env LANG = en_US.UTF-8
debug1: Sending env LC_CTYPE = en_US.UTF-8

If these variables are omitted, you end up with a default locale, which in my case was a non-unicode version of en_US.

The same problem will emerge if your script is executed as a cron job: The cron daemon normally also ends up with the systems default locale settings.

Explicit encoding to the rescue

When you are reading data from a file, you should always explicitly define the encoding you expect the file to be in:

1
2

data = File.read('test.txt', encoding: 'UTF-8')
puts data.gsub(/Example/, 'Coding')

This way you end up with portable code that executes in a predictable way independent of environment settings. Just make sure to specify the encoding your application uses for file handling in your documentation.

The same concepts apply to other programming languages as well. Java’s java.io.FileReader for example is completely useless because it does not allow you to state the encoding manually:

The constructors of this class assume that the default character encoding and
the default byte-buffer size are appropriate. To specify these values yourself,
construct an InputStreamReader on a FileInputStream.

A little while ago, I released an extension that adds a nifty feature to Twitch (Twitch is the video streaming platform for games that was acquired by Amazon last year for $970 million): ReChat for Twitch.

Twitch does not only allow users to see live video streams but also records them so that users can watch them later. The one thing you miss out on when you watch a recorded stream is the chat. This is where ReChat comes into play: ReChat allows you to see the recorded chat messages as if it was a live stream.

Indexing chat messages

Since Twitch does either not record chat messages or at least not make them available through their API, I was forced to build my own indexing system.

Luckily, Twitch’s custom built chat server does not only come with an HTTP front-end, but is also reachable via IRC. IRC, in contrast to the proprietary HTTP chat interface of Twitch, is a well documented and quite simple standard (RFC 1459) and was therefore the natural choice to connect to Twitch chat.

I chose to write the indexing daemon in JavaScript and run it with Node.js. It’s event-driven architecture and the non-blocking I/O seems like a perfect fit for an application that waits on numerous connections for incoming chat messages.

For the storage backend, I chose to go with Elasticsearch. Not only does Elasticsearch a good job at indexing hundreds of documents per second, it also is easily scalable and blazingly fast at finding documents. Every chat message is represented by a JSON document consisting of the actual message, the sender, the chat room, and a timestamp.

Browser extension

Since all modern browser (probably even Internet Explorer 12) feature a JavaScript powered extension interface, writing cross-browser extensions has never been easier. The main difference between the browsers is how you have to provide metadata (e.g. manifest.json for Chrome, package.json for Firefox, …) and the API to access bundled resources.

All of the browser extension’s source code is available on GitHub.

Search API

The ReChat search API consists of a basic Sinatra web application that talks to Elasticsearch, a threaded Puma that acts as application server, and an nginx as reverse proxy.

Based on the unique Twitch video ID, the web application fetches video time information via Twitch API, searches for the matching chat messages in the Elasticsearch index and serves them in chunks with pagination.

Aggregations

Elasticsearch has some nifty aggregation features to analyze the data available. Maybe some sort of statistics page would be a nice addition? It could for example feature a visual representation of the most frequent words (some common english words filtered out):

Basic setup

Uninstall rvm:

1

rvm implode

Install rbenv and ruby-build:

1
2
3

brew update
brew install rbenv
brew install ruby-build

Remove RVM initializers from your .bash_profile and instead add rbenv:

1

eval "$(rbenv init -)"

Restart your shell (or re-source .bash_profile).

Now you can start installing Ruby versions:

1
2
3
4

rbenv install 1.9.3-p194
rbenv install 1.9.3-p429
rbenv install 2.0.0-p195
rbenv rehash  # Rehash rbenv shims (run this after installing executables)

Gemsets

If you used RVMs project-specific gemsets and would like to continue to do so, I recommend installing rbenv-gemset. Be sure to install an up-to-date version to support loading .ruby-gemset files (instead of just .rbenv-gemsets files):

1

brew install rbenv-gemset --HEAD

If you already migrated from .rvmrc to .ruby-version (and .ruby-gemset), this setup is 100% compatible with rvm. If not, now is the time to do so: .ruby-version contains the Ruby version (like 1.9.3-p429) while .ruby-gemset contains the name of the gemset (like casino). You can delete .rvmrc afterwards.

Pow

If you are using Pow, add this to your ~/.powconfig:

1

export PATH=$(rbenv root)/shims:$PATH

I will use some Ruby for the example code, but the principles are the same in all other programming languages (at least the ones I know).

Exception as in exceptional

Exceptions should be used for situation where a certain method or function could not execute normally. For example, when it encounters broken input or when a resource (e.g. a file) is unavailable. Use exceptions to signal the caller that you faced an error which you are unwilling or unable to handle. The exception is then passed to the caller who has the chance to either handle the exception or pass it on (chain-of-responsibility).

1
2
3
4
5
6
7
8

def update(identifier)
  unless @data.has_key?(identifier)
    raise UnknownIdentifierError, "Identifier '#{identifier}' is not registered"
  end
  # ...
  raise TimeoutError, "Timeout while connecting to server '#{server}'."
  # ...
end

Don’t use exceptions for your normal application flow. Take a look at the following example:

1
2
3
4
5
6
7
8
9

def handle_client_input(input_stream)
  input_stream.each_line do |line|
    if line =~ /^hello$/i
      # ...
    elsif line =~ /^quit$/i
      raise ClientQuitEvent, "Client is about to disconnect."
    end
  end
end

In this example we use an exception to signal the caller that the client disconnected by sending a quit command. Something that will happen in every normal use case of this method. There are multiple reasons why you should not do this:

1. Exceptions are not designed for this. Developers using this API or reading through the source code will be confused. It looks like a failure scenario but it’s just some sort of flow control.

2. Exceptions are hard to follow. If you are using exceptions like this, you are using just another form of a goto statement. I don’t have to clarify why using goto is a bad idea, do I?

3. Exceptional exceptions? If you use exceptions for normal situations, how do you signal unusual situations?

4. Exceptions are slow. Because exception only rarely occur, performance is not a priority for the implementers of compilers nor the designers of the language. Throwing and catching exceptions is inefficient and many times slower than a simple check of a return value or a state field.

Don’t use exceptions to signal something completely normal. Don’t use exceptions to control your normal application flow. Use return values or state fields for flow control instead.

It’s all about the hierarchy

Another question that pops up frequently: What structure (hierarchy, inheritance, …) should I use for my own exceptions?

Exceptions should be as specific as possible. Especially if you are designing an API that will be used by third-party developers.

Your own exceptions should all inherit from a common exception in your namespace. And this exception class in turn should inherit from the standard library exception (e.g. StandardError in Ruby, Exception in Java).

1
2
3
4
5
6
7

module MyAwesomeModule
  class Error < StandardError; end
  class ClientError < Error; end
  class TimeoutError < ClientError; end
  class ParsingError < ClientError; end
  # ...
end

This allows the caller to decide which exceptions he would like to handle. If you don’t follow this advice, you might end up with an error design as broken as the one in Ruby’s Net::HTTP. Because there is no common error class, a caller willing to catch all module specific exceptions must list all possible exceptions that may occur:

1
2
3
4
5

begin
  response = Net::HTTP.post_form(...)
rescue Timeout::Error, Errno::EINVAL, Errno::ECONNRESET, EOFError, Net::HTTPBadResponse, Net::HTTPHeaderSyntaxError, Net::ProtocolError => e
  # ...
end

Be verbose

When throwing an exception, you should supply an error message describing what exactly went wrong. This is especially useful for logging and debugging.

1

raise MyAwesomeModule::ParsingError, "Character #{character} at position #{position} is not allowed"

The error messages are only intended for humans. They should not be used by the calling method to determine what probably went wrong.

tl;dr

Exceptions should be used to signal serious errors from which your method is unable or unwilling to recover. In a best case scenario, no exceptions should occur during the whole application flow.

Be sure to structure your exceptions and use a hierarchy to simplify exception handling for the caller.

Use the optional error message to supply additional debug information.

RubyCAS-Server

We didn’t have any knowledge in running a big Java web application, so we decided to use the RubyCAS-Server. Running and maintaining Ruby web applications was (and still is) our daily business.

After some weeks and months of usage, we encountered several bugs and shortcomings in RubyCAS-Server. What’s worse: RubyCAS-Server does not fully adhere the CAS standard. “No problem, it’s open source!”, you’re probably saying. That’s what we thought too… After looking through the source code, we almost cried: it’s a mess and not well tested. But we didn’t give up here and began to hack our changes in. We then opened issues and pull requests but did not get any feedback. Very frustrating! The project seemed dead to us.

CASino

That’s when we formed an organization (rbCAS) and decided to build our own Ruby on Rails based CAS server: CASino

It took us just a few weeks to implement basic CAS support. We had a clean code base, a responsive user interface and 100% compatibility with the CAS standard.

But we didn’t stop here; the clean and well-tested source code allowed us to go beyond the CAS standard and add features such as two-factor authentication and a session overview.

We also built a product page with an appealing documentation: Check out casino.rbcas.com to learn how to setup your SSO within minutes.

And that’s it? Of course not! We are still adding features to CASino. So make sure to follow the project on GitHub, report feature requests or ask questions in our IRC channel (webchat)

So here is my contribution: A domain model to give you an overview over the CAS entities as I know them until now.

The only thing not that intuitive to me was the whole linking progress as it was easy to lose track of what you already “deployed” to your local Pow installation.

Not anymore, Anvil to the rescue!

It adds a little menubar icon that gives you access to your Pow apps, allows adding new ones and lets you easily execute various Pow commands (start, stop, …). Finally a nice GUI for Pow! :)

I ended up writing my own Gem, which manipulates ActiveRecord::Base to hide the actual ID. Rails’s path functions still work as expected. The only thing I had to add to the actual project was the following line:

1
2
3

class User < ActiveRecord::Base
  encrypted_id key: '5gA6lgr5g3GOg7EOQ1caYQ'
end

I open sourced the project on GitHub (pencil/encrypted_id) and published it on RubyGems.org.

So when it is this bots turn, it will decide based on the scores:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

private Map<Integer, Move> scores = new HashMap<>();

private Move chooseMove() {
  Move bestMove = null;
  for (int i = 0; i < 9; ++i) {
      if (gameGrid.getField(i) == Field.EMPTY) {
          GameGrid possibleGrid = new GameGrid(gameGrid);
          possibleGrid.setField(i, playersField);
          int hashCode = possibleGrid.hashCode();
          if (!scores.containsKey(hashCode)) {
              scores.put(hashCode, new Move(hashCode));
          }
          Move move = scores.get(hashCode);
          if (bestMove == null || move.score > bestMove.score) {
              bestMove = move;
          }
      }
  }
  return bestMove;
}

We then have to save the performed moves, so that we later can set the score accordingly:

1
2
3
4
5
6
7
8
9
10
11
12

public void reset() {
  int score = 0;
  if (gameGrid.getWinner() == playersField) {
      score = 1;
  } else if (gameGrid.getWinner() != null) {
      score = -1;
  }
  for (Move move : performedMoves) {
      move.score += score;
  }
  performedMoves.clear();
}

That’s it! So the learning AI is even simpler than the Minimax bot.

Results

The question is: How good is this bot?

To measure this, I let the bot play against a really stupid bot (chooses always a random move). In the following screenshots: “Player 1” is the stupid bot, “Player 2” is the learning bot.

As you see, the learning bot is indeed smarter than a purely random but (as expected). Playing this 20.000 rounds took 15 minutes. Probably he would get even as good as the simulating bot (which has a winning rate of ~80% against the stupid bot but never loses) if he would be running/learning long enough.

Update 2012-09-16 19:41: After ~3.000 rounds, the learning bot achieved a 100% draw rate against the simulation bot. Yay! :)

Source Code

Once I finished refactoring the code, I will make my repository public on GitHub. In the meantime, you can download a playable version here: Simple Tic-tac-toe (Java 7 required)

When you did some SQL things back in the Java 6 days, you often ended up with something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

try {
  Connection con = createConnection();
  // do something
  Statement stmt = null;
  try {
    stmt = con.createStatement();
    ResultSet rs = stmt.executeQuery("SELECT ...");
    // do something with rs
    rs.close();
  } catch (SQLException e) {
    e.printStackTrace();
  } finally {
    if (stmt != null) {
      stmt.close();
    }
  }
} finally {
  con.close();
}

Now with Java 7, this got a lot easier and shorter:

1
2
3
4
5
6
7
8
9

try (Connection con = createConnection()) {
  // do something
  try (Statement stmt = con.createStatement();
       ResultSet rs = stmt.executeQuery("SELECT ...")) {
    // do something with rs
  } catch (SQLException e) {
    e.printStackTrace();
  }
}

Awesome!

If you want to write a class that supports this syntax, you may take a look a the AutoClosable interface.

So the first thing the bot does is generating all possible game endings based on the current situation. The resulting situations can be stored in a so called Game Tree:

To generate the game tree, we will use a RecursiveAction to speed things up:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class SimulationTreeNode extends RecursiveAction {
  private static int FORK_THRESHOLD = 6;
  SimulationTreeNode[] possibleMoves;
  private GameGrid gameGrid;

  /**
   * Last position set that let to the situation now
   */
  private byte chosenPosition;

  /**
   * Player who should act now
   */
  private Field activePlayer;

  protected boolean isComputersTurn() {
    return activePlayer == playersField;
  }

  @Override
  protected void compute() {
    if (gameGrid.getWinner() != null || gameGrid.countFreeFields() == 0) {
      return;
    }
    int freeFields = gameGrid.countFreeFields();
    possibleMoves = new SimulationTreeNode[freeFields];
    try {
      int counter = 0;
      for (byte i = 0; i < 9; ++i) {
        if (gameGrid.getField(i) == Field.EMPTY) {
          SimulationTreeNode child = new SimulationTreeNode(
              gameGrid, i, otherPlayer(activePlayer));
          possibleMoves[counter++] = child;
          if (freeFields < FORK_THRESHOLD) {
            child.compute();
          }
        }
      }
      if (freeFields >= FORK_THRESHOLD) {
        invokeAll(Arrays.asList(possibleMoves));
      }
    } catch (EngineException e) {
      e.printStackTrace();
    }
  }
}

Each SimulationTreeNode starts a new thread to generate all possible moves. If less then 6 free fields are left, no new threads are started (wouldn’t improve performance anymore). The generated sub-situations are stored in an array.

Now when it is the computers turn, it can build the game tree or search for the new situation in the existing game tree (after players move):

1
2
3
4
5
6
7
8
9
10
11

@Override
public int getNextMove() {
  if (simulationTree == null) {
    generateSimulationTree();
  } else {
    simulationTree = simulationTree.getChild(gameGrid.hashCode());
  }
  SimulationTreeNode move = simulationTree.getBestMove();
  simulationTree = move;
  return move.getPosition();
}

What should I do?

You may noticed the getBestMove call to the simulation tree. This method searches the best possible move. Often there are multiple moves with the same “score”. A random one is returned in that situation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public SimulationTreeNode getBestMove() {
  double bestScore = -1;
  List<SimulationTreeNode> bestMoves = new ArrayList<>();
  for (SimulationTreeNode child : possibleMoves) {
    if (child.getScore() > bestScore) {
      bestScore = child.getScore();
      bestMoves.clear();
    }
    if (child.getScore() == bestScore) {
      bestMoves.add(child);
    }
  }
  int index = randomGenerator.nextInt(bestMoves.size());
  SimulationTreeNode bestMove = bestMoves.get(randomGenerator.nextInt(index);
  return bestMove;
}

What does this “score” mean? The higher, the better: A defeat would be bad for us, so it has score -1. A draw would be OK, so it has score 0. Winning would be good, so it has score 1:

1
2
3
4
5
6
7
8
9
10
11
12
13

private byte calculateScore() {
  if (gameGrid.getWinner() == null) {
    if (gameGrid.countFreeFields() == 0) {
      return 0; // draw
    } else {
      // Magic happens here!
    }
  } else if (gameGrid.getWinner() == playersField) {
    return 1; // win
  } else {
    return -1;
  }
}

To calculate the score of situations which are not yet completed (no winner and still empty fields), we use the Minimax algorithm.

When it is the other players turn, we assume that he will try to do the best he can. So we must assume the lowest score of all possible moves for the situation. Because when we end up with that situation, the player could do this move that would hurt us.

When it is the computers turn, it will do the best it can. That’s why we can assume the highes score of all possible moves. Because when we end up with that situation, we may have a chance to do the move with that good score.

We end up with something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

private byte calculateScore() {
  if (gameGrid.getWinner() == null) {
    if (gameGrid.countFreeFields() == 0) {
      return 0; // draw
    } else {
      byte score = (byte) (isComputersTurn() ? -1 : 1);
      for (SimulationTreeNode child : possibleMoves) {
        if (isComputersTurn()) {
          // computer will move, so search for good choice
          if (child.getScore() > score) {
            score = child.getScore();
          }
        } else {
          // other player will move and tries to hurt us!
          if (child.getScore() < score) {
            score = child.getScore();
          }
        }
      }
      return score;
    }
  } else if (gameGrid.getWinner() == playersField) {
    return 1; // win
  } else {
    return -1; // defeated
  }
}

As the grid consists of 3x3 fields, we could go with a multidimensional array, where each field would store either a 0 (empty), 1 (X, player 1’s sign) or a 2 (O, player 2’s sign). But multidimensional arrays are difficult to serialize and you can’t do a simple pattern matching against them.

Integer to the rescue

This is why we will use an integer to store the grid. We need 3 different states per field, which we can store using 2 bits each. Given the 9 fields of the grid, we totally need 18 bits (doh, short is only 16-bit, so we will definitely need an integer). The actual bit position is calculated as: (x + (y * 3)) * 2

This makes it also very easy to reset the grid. We just need to set our integer back to 0.

Bitwise operators

Retrieving and setting the value of a field requires some bitwise operations. If we wanted to get the value of field (1, 1) (the center of the grid), we would start by calculating the bits’ position, using the formula above: position = (1 + (1 * 3)) * 2 = 8. That implies, we need bit 8 and 9 to get the actual value. To get this two bits, we will need a mask. The mask is generated by setting bit 8 and bit 9 (the desired bits) to 1: mask = 3 << position. Now we can do an AND to get the bits:

    00 00 01 00 10 10 00 00 01
AND 00 00 00 00 11 00 00 00 00
  = 00 00 00 00 10 00 00 00 00

We now shift the result again, to get the actual value (result >> position), which gives us a 2 decimal. Which is exactly what we expected, yay!

The resulting Java code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int getField(int x, int y) {
  int position = calcualteBitPosition(x, y);
  int mask = getMask(position);
  return (this.grid & mask) >> position;
}

private int getMask(int position) {
  int mask = 3 << position;
  return mask;
}

private int calcualteBitPosition(int x, int y) {
  int position = (x + y * 3) * 2;
  return position;
}

Come on, make a move!

Say we would like to replace the value of (1, 1) with an X (not a valid game move, but we’ll do it anyway). We would first erase the current value at the given position, using AND with the inverted mask from above:

    00 00 01 00 10 10 00 00 01
AND 11 11 11 11 00 11 11 11 11
  = 00 00 01 00 00 10 00 00 01

Then we would shift the desired value (X, therefore 1) to the desired position and do an OR:

    00 00 01 00 00 10 00 00 01
OR  00 00 00 00 01 00 00 00 00
  = 00 00 01 00 01 10 00 00 01

The resulting Java code:

1
2
3
4

public void setField(int x, int y, int value) {
  int position = calcualteBitPosition(x, y);
  this.grid = (this.grid & ~getMask(position)) | (value << position);
}

In this blog series, I’d like to document the development of a simple tic-tac-toe program. Once finished, I’ll release the source code on GitHub.

The program will support three different players:

Human Player: This one is obvious ;)

Simulating AI: A AI simulating all possible moves to find the ones guaranteeing either a win or a tie.

Learning AI: This one is the most interesting one: The only thing it knows is that it plays a turn based game and it can place X’s (or O’s) on a 3x3 grid. It doesn’t know the rules and it doesn’t know any strategies. Instead it will try to win by analyze it’s moves when the game finished.

I’ll use Java (7) as programming language but the principles are useable in any other language as well.

1
2
3
4
5

<span class="filesize">54788455578</span> <!-- 51.03 GiB -->
<span class="filesize">2322</span> <!-- 2.27 KiB -->
<script type="text/javascript">
  $('.filesize').fileSize(2, true);
</script>

Hope it’s of some use to you.

Setup

First you have to sign up for an Amazon AWS account. Then you create a bucket using the S3 Management Console. The name of the bucket should be the domain you’d like to use later (in this example it’s www.codinghell.ch).

By default, stuff stored in Amazon’s S3 cloud is only accessible to you. To change that, select the bucket and click on “Properties”. Next, click on “Add bucket policy” and add this code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

{
  "Version": "2008-10-17",
  "Statement": [
    {
      "Sid": "PublicReadForGetBucketObjects",
      "Effect": "Allow",
      "Principal": {
        "AWS": "*"
      },
      "Action": "s3:GetObject",
      "Resource": "arn:aws:s3:::www.codinghell.ch/*"
    }
  ]
}

Also in the properties pane, click on “Website” and enable the checkbox. Use index.html as “Index Document”. The domain part of the endpoint URL is what you should point your actual domain to (CNAME).

Deployment

To deploy the blog, we will use s3cmd. It’s available (or at least installable) in most Linux distributions and via Homebrew for OS X users. After you installed s3cmd, you have to configure it:

1

s3cmd --configure      # start the interactive configuration

Now every time you want to update the content stored on S3, you do the following:

1
2

rake generate
s3cmd sync --no-preserve --delete-removed --recursive public/ s3://www.codinghell.ch

1

 print 'Hello world!'

I finally managed to start my own blog. I will add random bits about ruby, software development in general, geek stuff but also personal thoughts. You can learn more about me and this blog in the about section of this website.

The blog is powered by Octopress, it’s using the darkstripes theme for the moment and it’s currently hosted at Amazon S3. I will try to build my own theme and setup a personal server when the time comes.