python

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

I created a new repository in Github with my personal boilerplate to CreateJS. This boilerplate includes:

  • A simple server written in Python using the Flask web framework, you will need them to run the server;
  • A simple html page initializing the CreateJS libraries and jQuery;
  • The last release of jQuery;
  • A folder structure containing: assets, core, data, models, scenes, and systems;
  • Core files containing some useful objects for your games;

I will keep these files updated as much as I can.

For those who don’t know, a boilerplate is a “template project” that you can use to start a new work. The template includes files, folders and the structure of the project. If you are happy user of Sublime Text, you can install the Nettuts + Fetch plugin to add this (or other ones) boilerplate automatically.

You can access the repository and propose changes, access:

https://github.com/renatopp/createjs-boilerplate

Read more

In my opinion, knowing the tools you work and knowing how to set them up to operate together is an important step to keep yourself productive, efficient and mentally healthy =). In this post I will talk a little bit about the tools I am currently using to develop my games.

I’m sharing the essential items of toolbelt and I hope some of the programs I cite here can be useful for you. Notice that, all tools of this list can be used in any OS, such as Windows, Linux and Mac.

Programming Tools

As a programmer, I think the core of my work tools is Sublime Text 3, a powerful, beautiful, fast, elegant, awesome, demigod editor that I use to write code, texts, notes, and anything else. Sublime has several built-in addictive features that make you love the editor, such as the multi selection, the distraction free mode, the command palette and the plugin system. Sublime Text 3 costs USD $70, however, it is free for evaluation (you will see a notification to buy it, occasionally, but it is far from being a problem).

With Package Control, you can easily add new plugins to Sublime, just press ctrl+shift+p to open the command palette, chose the install package option and select the plugin you want to install. My must-have plugins:

  • Dictionaries: it adds a lot of dictionaries (press F6 to use the spell check). This package is pretty useful for people who write common texts, documentation, code comments, in English or other 28 languages. In fact, I am writing this post in Sublime right now and using this plugin.
  • Nettuts + Fetch: an awesome plugin that let you add remote files or complete boilerplates to your project folder. Just press ctrl+shift+p to open the command palette, type “fetch” and select the target file or package you want and they will be automatically added to your project. It is highly recommended, specially if you have a common structure that you use in several projects. It is also useful to add common libraries automatically, such as jQuery or normalize.css.
  • Sidebar Enhancements: adds a lot of options to the sidebar menu (when you press the right mouse button on sidebar files or folder). With this plugin you can delete, open, run and copy files and folder, and much more. It is a must have that can be useful for all cases.

I use the default theme, Monokai, which can be seen at the image below, but you can add more themes with package control. I made just a few changes on the default configuration: I have added two rulers lines to the columns 0 and 80, and set the translation of tabs to spaces to true.

Sublime Text 3 - Screenshot

I am a Python guy, and I use this language to help me in practically any project or task that I do, such as to create a simple web server to run my CreateJS projects. I am using Python 2.7 provided by Anaconda. Anaconda is a super package for scientific computing which includes a python distribution within a lot of useful libraries, such as Numpy, Scipy, Matplotlib, and Flask.

Flask is a Python micro-framework for web development that I use to create simple web servers when I need one. This is the case for several HTML5 game engines, such as the CreateJS. For example, you can create a basic web server with this:

from flask import Flask
from flask import render_template
app = Flask(__name__)
@app.route("/")
def index():
    return render_template('index.html')
if __name__ == "__main__":
    app.run(debug=True, port=5051)

Image Editing

For image editing I basically use Inkscape and Gimp, two powerful open source programs that some people may hate, but I love them.

Inkscape is a vector graphics editor similar to Corel Draw or Illustrator, and uses the Scalable Vector Graphics (SVG) format natively. Inkscape has a lot of features and an intuitive interface, great for noobies and pros.

GIMP is an image editor that replaces the Photoshop. With GIMP you can use plugins, brushes, patterns and other components that were originally destined to Photoshop, without spend any money. It is constantly updated by community and also has a lot of features and an intuitive interface.

Audio Editing

At this moment, I don’t have any tool for create musics or sound effects, but for general audio edition I use Audacity. I can’t really say anything about Audacity because I rarely use it and when I do, it is just for simple tasks.

Other Tools

Git is my choice of version control system. It is easy to use and hard to messing things up. I use Github to host my open projects and Bitbucket for my private ones.

Dropbox is essential, sometimes I use three different computers and I don’t want to sync my code with Git before I finish some feature of fix some bug. All my projects are in the dropbox folder, thus, I can save a file in my Desktop and open it in my Notebook without any effort from my part.

Finally, I use Firefox and Chrome to test my web games. I don’t really care about IE.

Read more