Guitar Pro - The Musician's IDE
October 18, 2009

Guitar Pro ScreenshotI've been using Guitar Pro pretty regularly for the past 3 years to compose some of my music. It was originally designed to be a guitar tab editor, but it's pianists and violinists would find themselves right at home as well. It's pretty convenient, but I often find myself complaining about some little thing that Visual Studio has that Guitar Pro could really benefit from. This is coming from a programmers perspective, but these would make very good features in an "Advanced" menu.

  • Commenting: Commenting is by far my most sought after feature in Guitar Pro, though admittedly commenting a music track would add a lot more complexity. Normally when I want to save a riff for later, I put it at the far end of the track, meaning by the time I'm finished with the song, I'll have 5 or 6 snippets that don't really belong anywhere but "comments".
  • Batch Modify and/or Find and Replace: I can't count how many times I've wanted to a do a pattern match or a find and replace on my guitar tracks. As it stands, there's a lot of manual (see: repetitive) that labour involved in laying down a track. It's a matter of adding nice (even vim like) commands that would really speed up that process.
  • Export to MP3 Rendering: Guitar Pro features a rendering library for guitar, bass and drums called "Realistic Sound Engine" or RSE as an alternative to MIDI playback. The quality is usually pretty nice (though there a few volume inconsistencies with the MIDI player that drive me insane), however that's no "real" way to export sounds rendered in it. I put "real" in quotes because there does exist a Export to WAV option that would do essentially what I want, however it just tries to record the output of your sound card. This can be problematic since some sound cards don't support recording their output. What I'm looking for is real FL Studio style rendering that has no sound card in between it and the resulting MP3.

Guitar Pro does get a lot of things right though. It does have a few nice keyboard shortcuts, such as C to copy the current note to the end of the measure, Insert to add a rest before the current note with the same value as the note, CTRL-Insert to add a measure before the current measure, P for palm mute and I for 'let ring'. It also supports pasting multiple times with a variety of options (insert, paste over and add to the end of the score). Guitar Pro also uses numbers for the drum parts which are easily memorized. The built-in scales and chords are also nice when I'm having musician's block.

There are a few alternatives out there: Power Tab, which is free, and TablEdit. Hopefully the pressure of competition and the release of Guitar Pro 6 will add some of these features! They can all learn a lesson from IDE's to improve musician productivity.

music guitar pro

Writing a bitboard chess engine
March 15, 2009

I've shifted my focus a little and am currently writing a bitboard based chess engine. Bitboard based engines aren't quite as straight forward as array based chess engines, but they offer benefits in both move generation and board evaluation. The idea is to represent the board in a series of 64 bit integers, as in the following sample board structure:

#define BITBOARD unsigned long long

typedef struct {
    /* colours */
    BITBOARD white_pieces;
    BITBOARD black_pieces;

    /* white pieces */
    BITBOARD white_pawns;
    BITBOARD white_knights;
    BITBOARD white_bishops;
    BITBOARD white_rooks;
    BITBOARD white_queens;
    BITBOARD white_kings;

    /* black pieces */
    BITBOARD black_pawns;
    BITBOARD black_knights;
    BITBOARD black_bishops;
    BITBOARD black_rooks;
    BITBOARD black_queens;
    BITBOARD black_kings;
} BOARD;

The nice thing about bitboards is that one has access to a multitude of information through simple (and fast!) bitwise operations (AND, OR, NOT, XOR and shifts). Bitboards have a really high information density, and are easily manipulated on 64 bit machines. In fiasco, I'm using a little endian bitboard representation (that is, A1 is the 0th bit, or 2^0, A7 is the 7th bit or 2^7, B1 is the 8th bit or 2^8 and H8 is the 63rd bit or 2^63).

A sample default board representation might be:

/* colours */
BITBOARD white_pieces = 0xFFFFLLU;
BITBOARD black_pieces = 0xFFFF000000000000LLU;

/* white pieces */
BITBOARD white_pawns    = 0xFF00LLU;
BITBOARD white_knights  = 0x42LLU;
BITBOARD white_bishops  = 0x24LLU;
BITBOARD white_rooks    = 0x81LLU;
BITBOARD white_queens   = 0x8LLU;
BITBOARD white_kings    = 0x10LLU;

/* black pieces */
BITBOARD black_pawns    = 0xFF000000000000LLU;
BITBOARD black_knights  = 0x4200000000000000LLU;
BITBOARD black_bishops  = 0x2400000000000000LLU;
BITBOARD black_rooks    = 0x8100000000000000LLU;
BITBOARD black_queens   = 0x800000000000000LLU;
BITBOARD black_kings    = 0x1000000000000000LLU;

Move generation of knights and kings are trivial with bitboards (well they're simple with arrays too, but still faster here). One simply has to precompute an array of possible knight or king moves from each square, and do a simple array look up to find possible move locations. For example:

BITBOARD knight_moves[64] = {
0x20400LLU, 0x50800LLU, 0xA1100LLU, 0x142200LLU,
0x284400LLU, 0x508800LLU, 0xA01000LLU, 0x402000LLU,
... };

So for example, if I wanted to find the moves for a piece at A1 (which is the 0th bit if you recall), I would look up knight_moves[0], which is 0x20400LLU in base-16. Translated to binary, this is 10 00000100 00000000, meaning the knight at A1 can access the pieces at C2 and B3.

Right now I'm working on implementing rotated bitboard move generation, which allow me to generate moves of sliding pieces in a loop-less (bitwise) fashion. Dr. Robert Hyatt has a great paper on the subject, which is a must-read for any potential bitboard based chess engine author. Most of the top engines today are bitboard based, such as Rybka, Crafty and Glaurung, and I hope this approach proves beneficial in Fiasco ;).

programming chess

The layout of a chess engine
March 08, 2009

Chess is said to be a game of perfect information, meaning that all the information is visible to both sides at all times. This allows a computer to play chess by searching the game tree for the best possible move. Thus a simple chess engine is composed of three major parts that define how it plays:

  1. A move generator
  2. An evaluation function
  3. A search function

The same basic components are present in any game of perfect information, such as checkers, connect 4, tic tac toe.

Move Generator

A move generator is capable of producing all legal chess moves given a particular board representation. This function is needed by the search to produce moves in order to traverse the game tree (more on this later). It's critical that this part of the chess engine be very fast as it's going to be called perhaps millions of times for a single move.

There's a lot of information to take into account in this part as well, such as castling information, captures, en passant, 50 move rule, double jumps and promotions. In TSCP, Tom uses a 'bits' component in his move structure to store such information, as follows (from defs.h):

/* This is the basic description of a move. promote is what
 piece to promote the pawn to, if the move is a pawn
 promotion. bits is a bitfield that describes the move,
 with the following bits:

 1    capture
 2    castle
 4    en passant capture
 8    pushing a pawn 2 squares
 16    pawn move
 32    promote

 It's union'ed with an integer so two moves can easily
 be compared with each other. */

typedef struct {
    char from;
    char to;
    char promote;
    char bits;
} move_bytes;

Bitwise operations such as the union are fast and compact, making for a good storage medium. It can also be expanded on really easily -- if we wanted to add a boolean field for something else, we could just union 64 with the bits character without affecting 1 - 32. Neat eh?

Usually chess engines contain a 'pseudolegal' move generator which builds a list of moves based on basic piece movements. From there the moves are then pruned based on their legality, i.e., can't move somewhere if your king is in check, castling through check, etc.. More on this in another post.

The Evaluation Function

The evaluation function is exactly what it sounds like. It looks at a board state and gives it a score -- typically positive if the board favours white and negative for black. It's essentially the source of chess knowledge for your engine. Simple evaluation functions can be constructed by tallying the pieces values for each side, i.e. 9 for the queen, 5 for the rook, 3 for the bishop and knight and1 for the pawn. More complex evaluation functions contain positional information such as the number of attacked squares per side, control of the center, doubled up pawns. It's also imperative that you make the evaluation function as fast as possible, for the same reasons as the move generator.

The Search Function

As I've said before, the search function searches the game tree and returns the best possible move. How does it do this? It employs the move generator to generate all possible moves from a position, then recursively calls the search function again on each of the newly created positions, decreasing the depth each time until it reaches a node where the depth is zero; from there it returns the evaluated board (depth is defined as the number of total turns the game tree searches, so 6 would be three moves by white and three moves by black below the current board position). That's probably really hard to understand right now (it was hard to write), so it might be a little easier with some pseudocode:

function minimax(node, depth)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    else
        let α := -∞
        foreach child of node      { evaluation is identical for both players }
            let α := max(α, -minimax(child, depth-1))
        return α

(taken from http://en.wikipedia.org/wiki/Minimax) This algorithm is called minimax. The reason it's called minimax is that it tries to maximize the possible score for white at one search depth, and minimizing the score for white at the next. This allows us to grab move which leads to the best possible score for white (or black) at the end. It's basically a bruteforce to search all possible positions for the best one. Now this isn't very efficient is it? There are a lot of faster search algorithms out there, I'll just name a few for reference:

  • Alpha beta pruning, which allow us to grab the same principle variation as with the minimax search algorithm. It does so in a much quicker manner by introducing the concept of "pruning" in that if a certain score is absolutely terrible after a search, it causes a cutoff where it stops search that branch of the tree. This is heavily dependent on move ordering. In this best case scenario, it allows for a sqrt() speedup compared to minimax, and in the worst case scenario, it's just as good as the minimax.
  • Negascout, which has been shown to speed up chess searches by ~10%. It's essentially the same as the principal variation search for all practical purposes.
  • MDT(f) -- which is proven to be very fast, but is heavily dependent on transposition tables (more on this later too)
  • SSS* -- also dependent on transposition tables I believe.
  • Aspiration Windows, which allow for a more selective pruning of the search tree.

There's a whole lot more I want to add here: Quiescence Search, Transposition tables, etc, but that should be fine for now. I highly suggest you check out my links page for sites that can provide a better explaination that my own.

Happy Chessing.

programming chess