Programming

For all my academic works, experiments, personal projects, tests or any other problems that I can solve by writing a program, I try to use Python. Well, Python is my main language and after 6 years of experience with it, I can say that I love this language. More yet, I’m only passionate for coding today because of it. Python is an easy language to learn and to program, intuitive and clear. Everything you can do with other languages, you can do in Python with half effort and double love. It has several useful builtin libraries and a lot of epic frameworks, being used for web development, scientific computing, networking and in several other areas. But and for games?

There are several frameworks used for game development, and I will talk about some of them here. Notice that, my focus is on 2D game development and does not mention any 3D engines.

Pygame is the most known engine for Python and it is a binding for the C++ SDL 1.x. The community of Pygame is huge and there is a lot of tutorials out there, and, like SDL, Pygame is very mature and stable. The downside is, Pygame is slow as hell and provides a poor support to hardware acceleration, making it nearly impossible to run a heavy game on old computers. I feel that it is pretty hard to optimize the code and when I do it, several other problems occurs such as tearing and unstable fps. Despite the community size, Pygame is rarely updated (the last release is from 2009).

Pyglet is the alternative to Pygame. It is built upon opengl and it is a lot faster than Pygame. The Cocos2D engine was created as a framework upon Pyglet. The problem is, Pyglet is unstable, with a lot of problems, mainly on Mac OS. The community is nearly zero, it is poor documented and is also rarely updated (with less activities than Pygame).

Any other library using Pygame and Pyglet (such as Spyral, Ignifuga and Cocos2D) have the same problems already cited.

Pygame and Pyglet are the main option for game dev in Python, but there is also an opengl binding called PyOpenGL, which can be used to low level development. As far as I known, there is no promising library using it as basis.

Together with all problems already cited, there is the difficult to distribute a python game. You can use py2exe or cx_freeze to do so, but is pretty easy to do the reverse engineering and access the complete code and resources. Moreover, games are heavy applications in all senses and require a lot of optimization to run fast (at least 30fps), and this scenario is for C++. The slow speed is inherent to the Python and is not really a problem for most of the applications, including scientific computing, but for games is a real concerning.

The only real use for Python in commercial games today is as a script language, and even this is more rare to see.

Read more

In my Ph.D. program, every student must sign in into the “Teaching Practice” course. In this course, we have to help the teacher on his undergrad class, making lectures, evaluating the practical projects, etc. In this semester, the undergrad students had to implement a minimax search to play chess and I was in charge of developing the game to be the basis for them, so they can focus on the AI problem.

This chess game is not actually Chess, it is a simplified mini-game called Pawn Battle. In this mini-game you can set up the board with all the chess pieces, except the king. To win a Pawn Battle game, a player must promoted one of its pawns or eliminate all opponent’s pawns.

The project, called liac-chess, can be found on github and it is open to contributions.

liac-chess

The biggest difficult in programming a chess game is to develop the artificial intelligence. You must choose the right algorithms and data structures, and they must be well developed in order to achieve a reasonable performance in computation speed and play well the game.

This precaution about the algorithms and data structures is necessary due to the amount of possible states in a chess game. The chess game has a average branching factor of 35. This means that, for each configuration of the board, there are, in average, 35 possible movements. So to compute 2 movements ahead, there are 35^2 (1225) possible positions, and to 5 movements there are 35^5 (52,521,875), to 10 movements there are 35^10 (2,758,547,353,515,625) possible states!

I write here some conclusions about how to represent the board, to generate the piece movements, and how to search the best state, given my experience developing a bot for liac-chess. Everything about chess programming, including what I’m writing here, you can find on the site http://chessprogramming.wikispaces.com/, which is a specialized wiki for chess programming. Highly recommended.

Board Representation

The first challenge when programming a chess game is to decide how you will represent the game board. This choice will imply how you will generate the moves for each piece and how you will evaluate the state. Besides the board itself, you also need additional information about the game, e.g., the en passant position, whom is the turn, etc.

You can represent everything in the good and old oriented object style, with a game class that includes the board as a matrix of pieces, and other values. This is the easiest way to implement the AI, and will work, at least for a few number of states (in my computer, this can reach 4 movements ahead, approximately 1,500,625 states, in 3 or 4 seconds).

For a high-level AI bot, this implementation is pretty rough. You need more efficiency. I think, the best option here is the bitboard representation, which is relatively easy to implement and very fast to use.

In the bitboard representation you use a bitarray, containing 0 or 1, with 64 positions, one for each board cell. You will have several bitboards to present the board, e.g., for the black bishops, white knights, etc., as you can see on the image below.

bitboardThe great advantage of the bitboard is that you can use bitwise operator on it, this include flipping, mirroring and rotating the board. If you use a bitboard to store, for example, all position that the black queen can attack, you can also verify if the queen can attack some piece by a simple AND operation. Here you can see a lot of information about general setwise operations that you can apply to bitboards.

Move Generation

There is a lot of techniques to implement the generation of moves in the chess, depending heavily on the board representation. The move generation is the slowest part on the AI process, so it must be carefully implemented and tested.

Specifically to the bitboard representation, you can use the ray or line techniques, where you trace a ray/line in some direction and store all cells below this ray/line. By storing these cells on a bitboard, you can perform the operations commented on the “Board Representation”.  Check it out this link and this other.

Searching The Best State

The search algorithm is the main component of a chess AI, and is – again – essential to choose, implement and test a good algorithm. For games like chess (zero-sum games), the minimax is the most common algorithm by far. In general all algorithms for this kind of game is based on the minimax, such as its compact version, the negamax.

A simple and efficient way to search the best state is by using the negamax algorithm using the alpha-beta pruning. The alpha-beta can reduce significantly the search space, allowing the algorithm to evaluate more movements ahead than it would be possible by only the negamax algorithm.

There are other techniques you can apply in order to enhance the search speed, for example the transposition table and the iterative deepening.

Another feature you may need is to run the search in a separated thread and stop it when necessary. For example, the default time limit per move on liac-chess is 5.9, more than that you receive an infraction (with 5 infractions you lose the game). Thus, given a time limit, you can stop the search and perform the best move that the algorithm founded so far.

State Evaluation

An evaluation function computes how much a given board configuration is good. Notice, that “good” is an abstract term on chess, due to its complexity, so the evaluation is high based on heuristics. The heuristics used in the evaluation are the main component to generate good and natural moves.

You can evaluate several aspects of the game, e.g., the material evaluation (how much pieces each player have), the positional evaluation (how good is the position of the pieces), among other things.

There are several studies trying to identify how important each kind of piece is, take a look at this table. In general, we know that: a bishop is equal (or slightly better) to knights; two bishops, or two knights, or one bishop and one knight are better than one rook; one bishop, one knight and one rook is better (or equal) than a queen.

A piece can have a more or less value depending on the condition of the board, for example, a pair of bishops is better than a bishop and a knight. There is a lot of heuristics for the piece evaluation, implement what you think is the most important for your bot.

For the positional evaluation you can use predefined matrices within the values for each piece relative to each board cell (called piece-square tables).

Conclusions

Developing liac-chess was a fun experience, I’ve learn a lot of computer chess =].

Notice that, you won’t find any AI bot on the project page, only a random bot that we used as baseline to the student’s bots. I don’t know if a will share my bot, because the liac-chess is being used by the undergrad class and it is important that they program it itself.

What I can is that, I only used the piece values for material evaluation and the piece-square tables for positional, together with a negamax search and alpha-beta pruning. My bot had great performance, winning almost every game against the students bots (it loose 1 game and tied some ones).

I failed on the representation and move generation, using a matrix to store the pieces and a bad implementation of the Ray attack. Using the time limit as 5.9 seconds, I could only compute 4 movements ahead.

Read more

jscramble logo

I was looking for what HTML5 game developers do to protect their source codes. Coincidentally, Emanuale Feronato made post last week about JScrambler, which seems to be the state-of-the-art of free tools in protection for  Javascript codes.

Protecting your code is important for several reasons. Javascript is an interpreted client-side language, which means that the browser of the final user will read the code and execute it to run the game, and this same code can be accessed by the user simply looking in the page source code.

Now, suppose that your code is neither minified or obfuscated. In this case, the final user will see the exactly the lines you wrote. With this, he can: copy and modify all components of your game with the minimum effort and re-distributed as a completely new one; hack your code to submit scores without even playing your game; among other undesirable things.

Notice that, as Javascript runs in client-side, there is no real way to avoid the user to see your code and to stop him to try to decode it. But, you can make your code as harder as possible to decode. This is what JScrambler do, makes your code hard to read, to copy, to modify, and to redistribute without your permission.

Look at the following example. The code below is a function that merges two different objects, just like jQuery do:

(function() {
    
    "use strict";

    var merge = function() {
        var obj, name, copy,
            target = arguments[0] || {},
            i = 1,
            length = arguments.length;

        for (; i < length; i++) {
            if ((obj = arguments[i]) != null) {
                for (name in obj) {
                    copy = obj[name];

                    if (target === copy) {
                        continue;
                    }
                    else if (copy !== undefined) {
                        target[name] = copy;
                    }
                }
            }
        }

        return target;
    };

window.merge = merge;
}());

Using JScrambler you get:

var I2Y={'n':function(Y,R){return Y!=R;},'g':function(Y,R){return Y===R;},'H':function(Y,R){return Y!==R;},'d':(function(J){return (function(N,G){return (function(k){return {I:k};})(function(W){var V,j=0;for(var M=N;j<W["length"];j++){var e=G(W,j);V=j===0?e:V^e;}return V?M:!M;});})((function(S,Z,v,U){var O=26;return S(J,O)-U(Z,v)>O;})(parseInt,Date,(function(Z){return (''+Z)["substring"](1,(Z+'')["length"]-1);})('_getTime2'),function(Z,v){return new Z()[v]();}),function(W,j){var B=parseInt(W["charAt"](j),16)["toString"](2);return B["charAt"](B["length"]-1);});})('6i2bf2j20'),'t':function(Y,R){return Y<R;}};(function(){var h=I2Y.d.I("fe3d")?"use strict":"merge",z=I2Y.d.I("a6")?null:function(){var R=I2Y.d.I("b2")?"H":"target";var A=I2Y.d.I("f1")?"length":"g";var c=I2Y.d.I("8858")?null:"length";var p=I2Y.d.I("b331")?"target":"n";var E=I2Y.d.I("2c3")?"t":"obj";var P=I2Y.d.I("abf8")?"target":"length";var L=I2Y.d.I("dcf")?null:1;var s=I2Y.d.I("74")?0:null;var X,o,l,b=arguments[s]||{},q=I2Y.d.I("36")?L:"length",T=I2Y.d.I("cbb4")?"obj":arguments[P];for(;I2Y[E](q,T);q++){if(I2Y[p]((X=arguments[q]),c)){for(o in X){var w=function(Y){l=Y[o];};w(X);if(I2Y[A](b,l)){continue;}else if(I2Y[R](l,undefined)){var D=function(Y){b[o]=Y;};D(l);}}}}return b;},u=function(Y){var R="merge";window[R]=Y;};h;u(z);}());
Read more

EaselJS is a Javascript library that allows the programmer to work on html canvas in an easy way. It means that EaselJS abstracts the low level API of the canvas element and provides classes, structures and functions to manipulate visual elements.

Before starting the examples and the talk about the Easel modules, let’s set up the html file which will be used as basis throughout this post. Create a file called easel.html and copy the following code:

<!DOCTYPE html>
<html>
<head>

<script src="http://code.createjs.com/easeljs-0.7.1.min.js"></script>

<script>
    function init() {
        var canvas = document.getElementById('canvas')
        var stage = new createjs.Stage(canvas);
        // CODE HERE!
    }
</script>
</head>
<body onLoad="init();">

<canvas id="canvas" width="600" height="300">alternate content</canvas>

</body>
</html>

 The Basics

EaselJS provides a whole architecture to control the objects that will be used at our games. The following list explains a bit of each one of the core components of this architecture.

  • EventDispatcher: the EventDispatcher class provides the structure for managing queues of events listeners and dispatching events. All components of EaselJS inherit from this class, thus, any component can handle events such as mouse clicks, drags, etc. For example, you can register a callback function to the ‘click’ event of a Bitmap object, causing the callback to be called whenever the user clicks that Bitmap.
  • DisplayObject: is the base class for all visual element, exposing properties such as position, rotation, scale and transparency. It means that, you can manipulate the position, rotation and other display properties of any object that draws something at the screen.
  • Container: The Container inherit from DisplayObject and provides methods to group other DisplayObjects. Using Containers, you can create hierarchy of visual objects and manipulate them together. For example, if you have a container within 3 images and move the container to the left, all the three images will be moved to the left too.
  • Stage: the Stage is the root level of the DisplayObject hierarchy, thus, if you want to show an object in canvas you need to add this object to the stage.

After adding objects to stage, you need to call the stage “update” method, otherwise the canvas will be redraw and you won’t see any change. All examples below show how to use it.

Working with Shapes

A Shape object stores a group of vector graphics that are created directly by the canvas element. Each shape has a Graphics instance which is the interface to the canvas drawing system. Check the example below.

var shape = new createjs.Shape();
shape.graphics.beginFill('#99f');
shape.graphics.drawRect(0, 0, canvas.width, canvas.height);

shape.graphics.beginFill('#33f');
shape.graphics.beginStroke('black');
shape.graphics.drawCircle(canvas.width/2, canvas.height/2, 50);

stage.addChild(shape);
stage.update();

Notice how the graphics instance does the hard work. The beginFill function sets the filling color for the next drawings while beginStroke sets the stroke color. The Graphics object provides several functions for the drawing itself, take a look at the official documentation to see how drawRect, drawCircle and other directives work.

Working with Texts

With Text objects you can draw… texts! But just plain texts, not HTML-formatted ones. EaselJS allows you to change the color, alignment, size, font, wrapping and others settings of Text objects, check the official documentation to know more:

var text = new createjs.Text('Hello, World!', '32px Arial', '#53f');
text.textAlign = 'center';
text.x = canvas.width/2;
text.y = canvas.height/2;

stage.addChild(text);
stage.update();

Working with Bitmaps

With Bitmap objects you can display an image, canvas or video (the HTML elements) into the canvas. You can instantiate the Bitmap object using the HTML element explicitly or passing a string, as shown in the example. Notice that, the first lines of the code below is a bit different from the examples above, that is because I am using a external resource (the image ‘assets/html5.png’) and we can use it before the browser totally load it. This process is automated by PreloadJS.

img = new Image();
img.src = 'assets/html5.png';
img.onload = function(event) {
    var bitmap = new createjs.Bitmap('assets/html5.png');
    bitmap.x = canvas.width/2 - bitmap.image.width/2;
    bitmap.y = canvas.height/2 - bitmap.image.width/2;

   stage.addChild(bitmap);
   stage.update();
}

Consult the documentation to know more about bitmaps:

 Working with SpriteSheets

A sprite sheet is a group of several images combined into a single larger file, e.g.:Bubbles Sprite SheetYou can also define animations using sprite sheets as shown in the example.

EaselJS provides the SpriteSheet class to handle this kind of image.  The SpriteSheet object requires some configuration to work, such as the size of each frame and the sequence of animations, check the documentation for a detailed description of each property:

img = new Image();
img.src = 'http://static.guineashots.com/tutorials/easeljs/assets/bubbles.png';
img.onload = function(event) {
    var data = {
        framerate: 10,
        images: [img],
        frames: {width:64, height:64, regX:32, regY:32},
        animations: {
            'explode': [0, 10],
        }
    }

    var spritesheet = new createjs.SpriteSheet(data);
    var animation = new createjs.Sprite(spritesheet, 'explode');
    animation.x = canvas.width/2;
    animation.y = canvas.height/2;

    stage.addChild(animation);

    createjs.Ticker.addEventListener("tick", update);
    function update(event) {
        stage.update();
    }
}

The SpriteSheet only represents the sequence of images, to see them as isolated images or animations you need a Sprite.

Notice that, in the last lines of example, I register a function “update” to the “tick” event, so it will be called every frame by Easel. In this function I call the stage update so it can redraw the canvas and show each frame of our animation.

Other Tutorials

To learn more about EaselJS, follow the official tutorials:

Read more

Almost all games needs to record certain information about the player progression. For example, you may want to have a local leaderboard to track the player best results of each round, or the story progression, or the name of the player, etc. Sometimes is interesting to record these kind of information even after the user closes the browser and turn off the computer, thus, the next time a user comes back to your game, the progression is saved there.

HTML5 provides a feature for this kind of offline storage, called Local Storage. The concept is similar to cookies: you have a key-value storage system and you can write or read information locally with it. It is really basic, all you have to do is:

localStorage['key'] = 'value'

and you have an information stored in the user computer. The user can close the browser and turn off the computer but when he or she opens you game again, the information ‘key = value’ is still there.

The problem is when the browser does not support the HTML5 Storage feature. When this is the case, you need to use a third party library for offline storage, store the information into some server, or don’t save the information at all. The third option is the easier (if storing information is not essential), because you don’t have to change all your code, just define a stub localStorage object and the life goes on.

A beautiful way to detect if browser supports localStorage or any other HTML5 feature is using the Modernizr library. Thus, you can add the following verification to your code:

if (!Modernizr.localstorage) {
    window.localStorage = {};
}

Take a look at http://html5demos.com/storage to see an example.

Read more