bitboard

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