Compiling the sources

My precious...

Blockem sources have been compiled in both GNU/Linux and Windows, however it should compile in every platform where GTKmm has been ported. There is an official bunch of GTKmm installers for lots of Linux flavours and other operative systems here.

GNU/Linux

Compiling blockem in a linux environment is "almost" straight away, you'll need to have the g++ compiler and the gtkmm-2.4 and libxml2 libraries for developers:

• libglademm-2.4 dependency was removed in 0.2.0, so you will need that library if you are planning to compile a version of blockem older than 0.2.0.
• libxml2 dependency has been added in version 0.3.0, so if you are planning to compile an older version there is no need to install this library.

All in all, the process to install these libraries differs depending on the type of linux you are using:

• In debian based systems, like Ubuntu, open a terminal and run sudo apt-get install g++ libgtkmm-2.4-dev libxml2-dev
• If your Linux is not debian-based, Google will help you to find and install those libraries. They are prety common and should be available for your platform

Once your system has those requirements covered, it is ready to compile and install the package:

1. Download the latest tarball from the download page
2. Uncompress it: tar -zxf blockem-x.y.z.tar.gz
3. cd into the new directory: cd blockem-x.y.z
4. Set up the compile environment and compile the sources: ./configure && make
5. Install it in your system sudo make install
6. That's it. Blockem is now installed in your system. Open up a terminal and runblockem

Windows

There is a precompiled binary in the download page, but if you still want to compile the sources in this platform here's the HOWTO I wrote when I compiled it for the first time.

• First of all you'll need to install the MinGW environment in your windows machine. Have a look at: http://www.mingw.org/wiki/HOWTO_Install_the_MinGW_GCC_Compiler_Suite
• You'll also need the port of the GTKmm library for windows. Have a look at: http://live.gnome.org/gtkmm/MSWindows/
• The following list of packages is needed for the MinGW environment:
  • gtkmm-win32-devel-2.16.0-4.exe
  • gcc-c++-4.4.0-mingw32-bin.tar.gz
  • gcc-c++-4.4.0-mingw32-dll.tar.gz
  • gcc-core-4.4.0-mingw32-bin.tar.gz
  • gcc-core-4.4.0-mingw32-dll.tar.gz
  • gmp-4.2.4-mingw32-dll.tar.gz
  • mpfr-2.4.1-mingw32-dll.tar.gz
  • libiconv-1.13.1-1-mingw32-dll-2.tar.Izma
  • w32api-3.14-mingw32-dev.tar.gz
  • MSYS-1.0.11.exe
  • mingwrt-3.18-mingw32-dev.tar.gz
  • mingwrt-3.18-mingw32-dll.tar.gz
  • binutils-2.20.1-2-ming232-bin.tar.gz
  • make-3.81-20090914-mingw32-bin.tar.gz
• From version 0.2.4 blockem has support for internationalization, (uses gettext for that matter). These are the packets you need to install in your MinGW environment ot be able to compile blockem in win32 with full support for internationalization
  • gettext-0.17-2-msys-1.0.13-bin.tar.lzma
  • gettext-0.17-2-msys-1.0.13-dev.tar.lzma
  • libintl-0.17-2-msys-dll-8.tar.lzma
  • libgettextpo-0.17-2-msys-dll-0.tar.lzma
  • libtermcap-0.20050421_1-2-msys-1.0.13-dll-0.tar.lzma
  • libexpat-2.0.1-1-msys-1.0.13-dll-1.tar.lzma
  • libiconv-1.13.1-2-msys-1.0.13-dll-2.tar.lzma
• libintl is not included in the packets above because compiling the app against the libintl version included in MinGW is giving errors at linking time: main.o:main.cpp:(.text+0x191b): undefined reference to '__printf__' To prevent this from happening you have to pass a few options to the configure script to force the app to compile against the gettext library included in the package. Pthreads should also be disabled since having them on produces a lot of linker errors when blockem is linked against the libintl library. Libintl can be built without pthread support without any problem, and blockem will still have 2 threds because they are gthreads instead of pthreads.So, to summarise, after setting up your environment correctly you will have to run the configure script like this: ./configure --with-included-gettext --disable-threads
• Now, once the configure script has been run, the app is ready to be compiled using the command 'make', but before you do it you've got to bear in mind localization in win32 is different from GNU Linux systems. To force blockem to be shown in a specific language (obviously, a language that blockem has already been translated into) you just have to run from a terminal (this example will load blockem translated into Spanish): $ LANG=es_ES.UTF-8 blockem If no LANG variable is set when you run blockem, the app will retrieve the system's one, wich is English if your Windows system was originally installed in English, or Spanish, etc.
• But not everybody runs blockem from the MinGW terminal (actually, almost nobody does). When an application compiled by MinGW is run by the usual double-click of your mouse, GTK retrieves the system default language In win32, but it cannot be set as easily as in Linux if you want to change the language. So a decission had to be made on how blockem will be handling languages on win32 platforms. Right now there is a call to putenv in main.cpp. It sets the LANG environment variable to pick which language blockem will run with. It retrieves the value from a configuration .xml file located at ${path-to-blockem-dir}/etc/blockem.conf between the tags: <language></language> If blockem can't find that file at startup it creates a default one (in the former path) with the value "en_UK" and launches the application in English (localised to the UK). If you set the language to something you can't understand simply remove this config file and blockem will start up in English next time.

Mac OS X

Nobody (that I am aware of) has ever tried to compile block'em for Max OS X. If you have an interest in compiling block'em for this platform you should satisfy its dependencies first, this is: gtkmm-2.4 and libxml2.

• gtkmm-2.4: There is a a fink package to install gtkmm on MacOS X here
• libxml2: You can find binary versions of this library for Mac OS X here

Once you have all the necessary dependencies installed in your system (plus the C++ compiler) block'em should compile easlily, though it hasn't been tested yet!

Other

Block'em should compile in every platform where GTKmm and libxml2 work. There are libraries for a few different systems already, but if you are extremely interested you could try to compile them by yourself before doing so with block'em.

• You can find GTKmm precompiled for quite a lot of different systems and platforms here
• There are links to binaries for Solaris and Mac OS X here (the official libxml2 website)

Translate block'em

The limits of my language mean the limits of my world

Block'em uses gettext to show every sentence in different languages (you can read more about gettext here). Using gettext means that translating block'em is a matter of going through a set of sentences written in English translating each one of them into a different language (or localise them to your region, English from New Zealand for instance)

Block'em is available in the following languages so far:

• English (UK)
• Spanish (Spain)

If you wish to translate block'em into a different language, please contact me. I will send you a .po file with the set of sentences used by the latest version of block'em. You can go trhough all the sentences editing the file manually or using applications such as poedit.

You could also generate your own .po file without my help, simply using GNU autotools with the source code. In the coming days I will try to write a tutorial about how to do it by yourself. Anyway, I would appreciate it if you send your translation back to me so I could ship it with all downloadable files.

Artificial Intelligence in block'em

Fasten your seatbelts. It's going to be a bumpy night

Artificial intelligence is the main reason why this project was started in the first place. The aim at the very beginning was creating a smart blokus player to be used in one of the several blokus games we used to play whenever the 4th player was missing.

Later on, once the project was started, we realised a smart blokus player in a 4 player game is, firstly, much more complicated to develop, and secondly, much harder to prove to be smart, due to the nature of the 4-players blokus game. If you ever played a blokus game I am sure you have noticed 4-players blokus is not a fully strategical game but more of a psychological one, since you can get ganged up by the other 3 players.

However, 1 vs. 1 games are purely strategical: you are responsible for your moves and you have to play against only one opponent. This is the main reason why the project changed at the early stages into a 1vs1 game AI player (human vs. human games were added later on).

Of course, this doesn't mean I don't want the AI engine to be extended to cover the 4-player game too. In fact, I would love it, since as I have already said, it was the reason why this whole thing was started in the first place. For the moment, 4 player games (where all players are human) have been added to blockem in 0.3.2.

For whoever is interested in this part of block'em, the following sections explain the main parts of the AI, and how you can extend it if you are interested. There is a plain text version of all this info in the source package, in the "doc/" directory. Happy reading!

Writing AI for 1vs1 games

It's alive! It's alive!

To understand the Artifical intelligence (AI) used in Blockem, a few terms must be understood first:

• Game tree (from wikipedia) is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position.
• Minimax (from wikipedia) is a decision rule used in game theory (...) for minimising the possible loss while maximising the potential gain
• Alpha-beta prunning (from wikipedia) It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm

As you could have guessed, Blockem AI is based on the MiniMax algorithm with alpha-beta prunning, to reduce the number of nodes in the search tree ensuring the same result as it would be got with MiniMax.

The big deal about the Minimax-alphabeta algorithm is the evaluation function, which gives a numeric value to a specific configuration of the game. In block'em the configuration of the game is defined by the board, the moving player and the opponent, so the C++ interface of the evaluation function was decided to be: int32_t EvalFunction( const Board &a_board, const Player &a_playerMe, const Player &a_playerOpponent);

Inside a class called Heuristic (in heuristic.h) there's a typedef which defines exactly this interface: class Heuristic { /* ... */ typedef int32_t (*EvalFunction_t) (const Board &, const Player &, const Player &); /* ... */ };

You can easily write a new heuristic and make it available in the blockem GUI. The following explanation applies to blockem version 0.2.0 or higher, where the process of adding new heuristics had been improved and simplified.

1. Implement a function that suits the 'EvalFunction' Interface. A very obvious one (though too simple) might be based on the number of squares each player managed to allocate on the board: int32_t SimpleEvalFunction( const Board &a_board, const Player &a_playerMe, const Player &a_playerOpponent) { int32_t squaresMe = 0; int32_t squaresOpponent = 0; int32_t rv = 0; for (uint8_t rowCount = 0; rowCount < a_board.GetNRows(); rowCount++) { for (uint8_t columnCount = 0; columnCount < a_board.GetNColumns(); columnCount++) { if (a_board.IsPlayerInCoord(rowCount, columnCount, a_playerMe)) { squaresMe++; } else if (a_board.IsPlayerInCoord(rowCount, columnCount, a_playerOpponent)) { squaresOpponent++; } } } rv += squaresMe; rv -= squaresOpponent; return rv; } If we take the former heuristic as the base, we can slightly improve its performance taking into account also the nucleation points. The following code is the heuristic called "Simple" in the configuration dialog. It assigns twice as much of importance to create a new nucleation point than removing one from the opponent. You could easily adapt this heuristic to something that is only focused on stopping the opponent, or vice-versa. Note that there are a few functions defined in rules.h that might help you out to write a powerful evaluation function (things like IsThisANucleationPoint, and so on...) int32_t SimpleEvalFunction( const Board &a_board, const Player &a_playerMe, const Player &a_playerOpponent) { int32_t squaresMe = 0; int32_t squaresOpponent = 0; int32_t rv = 0; for (uint8_t rowCount = 0; rowCount < a_board.GetNRows() ; rowCount++) { for (uint8_t columnCount = 0; columnCount < a_board.GetNColumns(); columnCount++) { if (a_board.IsPlayerInCoord(rowCount, columnCount, a_playerMe)) { squaresMe++; } else if (a_board.IsPlayerInCoord(rowCount, columnCount, a_playerOpponent)) { squaresOpponent++; } } } rv += squaresMe*4; rv += a_playerMe.NumberOfNucleationPoints()*2; rv -= squaresOpponent*4; rv -= a_playerOpponent.NumberOfNucleationPoints(); return rv; }
2. All the available heuristics are added to an array defined in the Heuristic class called m_heuristicData. This array is defined in heuristic.h as: /// pointer to the heuristic calculator function typedef int32_t (*EvalFunction_t)(const Board &, const Player &, const Player &); /// types of heuristic. If you add a heuristic here you MUST add a proper description /// to Game1v1Config in the constructor using a Game1v1Config::sHeuristicConfig_t typedef enum { e_heuristicStartCount = 0, // this element must be always 0 and must be at the start e_heuristicInfluenceArea = e_heuristicStartCount, e_heuristicInfluenceAreaEastwood, e_heuristicNKWeightedv1, e_heuristicCentreFocused, e_heuristicSimple, e_heuristicRandom, e_heuristicCount, // stores the amount of heuristics. Must be always at the end } eHeuristicType_t; /// heuristic data to be used in the heuristics config array typedef struct { eHeuristicType_t m_type; EvalFunction_t m_evalFunction; const char* m_name; const char* m_description; } sHeuristicData_t; static const sHeuristicData_t m_heuristicData[e_heuristicCount]; At the top of heuristic.cpp the list of available heuristic is instantiated. Note that all strings are defined inside a call to N_(). This call tells the translation engine (gettext) to mark the string as translatable. This must be done in your brand new heuristic to ensure its description is translated by the i18n team. const Heuristic::sHeuristicData_t Heuristic::m_heuristicData[e_heuristicCount] = { {e_heuristicInfluenceArea, Heuristic::CalculateInfluenceAreaWeighted, N_("Influence Area"), N_("Uses the influence areas that a user's pieces create on the board to determine the quality of a move") }, {e_heuristicInfluenceAreaEastwood, Heuristic::CalculateInfluenceAreaWeightedEastwood, N_("Mr. Eastwood"), N_("Modified version of \"Influence Area\". When in doubt it will try to block you out") }, {e_heuristicNKWeightedv1, Heuristic::CalculateNKWeightedv1, N_("NK weighted"), N_("The more Nucleation points the better. NK points are more important in the middle of the board at the beginning") }, {e_heuristicCentreFocused, Heuristic::CalculateCentreFocused, N_("Centre focused"), N_("It has a tendency to create nucleation points over the centre of the board") }, {e_heuristicSimple, Heuristic::CalculateSimple, N_("Simple"), N_("Takes into account only the amount of squares of the deployed pieces") }, {e_heuristicRandom, Heuristic::CalculateRandom, N_("Random"), N_("Random heuristic. Evaluation function returns a random value so any heuristic can be checked against it") }, }; To add a brand new Heuristic in a function called, for example, "MyCustomisedHeuristic", first of all you must add an entry in the eHeuristicType_t enum in heuristic.h /* ... */ typedef enum { e_heuristicStartCount = 0, // this element must be always 0 and must be at the start e_heuristicInfluenceArea = e_heuristicStartCount, /* ... */ e_heuristicRandom, e_heuristicMyCustomisedHeuristic, // <-- Your brand new heuristic e_heuristicCount, // stores the amount of heuristics. Must be always at the end } eHeuristicType_t; /* ... */ And then add it to the m_heuristicData array at the top of heuristic.cpp. Don't forget to write the all strings inside the call to the N_() function. const Heuristic::sHeuristicData_t Heuristic::m_heuristicData[e_heuristicCount] = { /* ... */ {e_heuristicRandom, Heuristic::CalculateRandom, N_("Random"), N_("Random heuristic. Evaluation function returns a random value so any heuristic can be checked against it") }, {e_heuristicMyCustomisedHeuristic, // as defined in eHeuristicType_t in heuristic.h Heuristic::MyCustomisedHeuristic, // pointer to the heuristic function you wrote N_("MyCustomised"), // Name of the heuristic. It'll be used in the GUI N_("This is my brand new...") // Description of your heuristic. It'll also be used in the GUI } };
3. Save all the changes, recompile blockem and your heuristic will be magically available to be selected in the "new Game" and the "configuration" menu. You will be able to test your new heuristic against the "random" one, or try to beat it playing blockem in a 1vs1 game.

Depth of the search tree

It is not length of life, but depth of life

The depth of the search tree is set by default to 3, unless the player has less than 14 pieces left. The depth of the search tree defines how many pieces are "virtually" put down by the minimax algorithm to test how good a specific move is. Depth 3 means minimax will put down a piece of the player whose move is being calculated, then it will put down a piece of the opponent (normally the human user) and finally another piece of the player whose move is being calculated. Once this is done, the evaluation function is calculated and the value returned is used to "tag" this particular move. That set of 3 moves which maximises the minimax algorithm at the end of the whole process is picked as winner, and the move returned by the minimax algorithm will be the corresponding first move of the set.

Minimum depth possible is 1, where no futurising is done. Evaluation function is calculated after putting down just one piece by the user whose move is being calculated. Depth 5 means 3 pieces of the "computer" player and 2 of the "human" will be placed on the board before the evaluation method is run.

Depth can also be set to an even number. It is discouraged though, because better results have been observed using an odd number. This is due to the fact that an odd number maximises the current user, instead of trying to minimise the opponent.

Obviously, the deeper you calculate the search tree, the better. But if the search tree is too big (for instance: there are too many pieces left) computing a new depth for the search tree will be very expensive in time, which is very bad for the user experience.

Let's use an example to explain how important it is to pick a sensible value for the\ minimax algorithm: At the beginning of the game each player has 21 pieces left. Since placing this 1st piece on the board has different rules than the rest of the pieces, let's assume both players put down the simplest of the pieces, the baby piece (1 square). It has 4 nucleation points (corners).

If we set up the minimax algorithm to calculate with depth = 1 it will call the evaluation function once per allowed movement in each nucleation point, that might be, roughly, 90 different configurations (20 pieces + rotated pieces + mirror pieces + rotated and mirrored pieces...) multiplied by 4 nucleation points equals 360 times. In reality it's even worse, because some pieces can be put down more than once with the same configuration in the same nucleation point (for instance, think of how many different ways you can place a the cross piece next to a baby piece)

Let's assume there will be always around 360 different possibilities (as I said it is even worse, there are several ways to deploy a piece in a nucleation point, and normally there are more than only 4 corners). Assuming this beautiful world of "only 360", the next depth in the search tree will be 360 * 360 = 129,600 (360 new configuration per each old possibility), and the following one (depth 3), will be 360*360*360 = 46,656,000!!!

The reality is that things are not really that bad. The alpha-beta prunning used in block'em takes care of lots of different useless branches of the search tree before they are calculated, but this example shows why you must use the depth parameter with a lot of care.

Improving performance of the heuristics

I feel the need - the need for speed!

As it is described in the wikipedia about the alpha-beta prunning, "Further improvement can be achieved without sacrificing accuracy, by using ordering heuristics to search parts of the tree that are likely to force alpha-beta cutoffs early, For example, in chess, moves that take pieces may be examined before moves that do not".

To improve speed in the Block'em implementation of the alpha-beta prunning, bigger pieces are always checked before smaller ones (they are more likely to be better as an important part of the evaluation function must be the amount of squaresd deployed on the board). They are checked in inverse order as they are defined in ePieceType_t enum in src/piece.h, so pieces in that enum are sorted from worse to better (from less likely to do a good move to more likely):

/// @brief available blockem pieces typedef enum { // pieces are described here from less complex to more complex. This ordering might // be used in a minimax algorithm to try to prune out useless branches early // using the alphabeta prunning e_minimumPieceIndex = 0, e_1Piece_BabyPiece = e_minimumPieceIndex, e_2Piece_TwoPiece = 1, e_3Piece_LongPiece = 2, /* ... */ e_5Piece_SafPiece = 18, e_5Piece_WPiece = 19, e_5Piece_Cross = 20, e_numberOfPieces = 21, e_noPiece = 22, } ePieceType_t;

Another design step was made to trim out possibly useless branches of the search tree. It sacrifices a bit of accuracy assuming no 4,3,2 or 1 square pieces are put down before the 6th move. Obviously Assume makes an ass out of u and me, but sometimes assumptions must be made. A constant has been defined in game1v1.cpp (MIN_5SQUARE_PIECES_AT_START) which describes how many 5-square pieces will be put in-a-row before even considering to put a 4,3,2 or 1 square piece on the board.

Computing speed has been also improved using tools as gprof to understand where the biggest amount of computing was being spent. It doesn't mean it's perfect though. Pieces are at the moment described as arrays of coordinates, while describing them as pure bits in a uint32_t (or uint64_t) would improve calculation speed (at least that is what I think). There is an entry in the TODO list to add this feature to block'em, in case you are interested in having a look.

Also, the calculation algorithm is not multithreaded, though building up a search tree looks like a good (and relatively easy) thing to be multithreaded. This feature is also present in the TODO list I mentioned above.