A Chess Game playable through console input/output in C++

Features

• Chess Board Rules (based on bitboard representation)
• Pgn Loader
• Pgn Generator
• AI (based on Minimax + alpha-beta pruning) as dynamic library
• Dynamic library loader to compete 2 differents AI

Done in groups of three over two weeks.

We first designed the Chess Board through UML diagram, then implemented the chess board rules.

The Chess Board Representation

We choosed a bitboard representation which is focused on pieces and not squares. There is a bitboard of position for each piece type and each color.

Let see an example :

• the pawn :
  • The bitboard of position: At the start of the game we will have 8 pawns which means if we are white 0xFF00 or 65280 in decimal.
  • For the moves either go ahead or eat are done by shifting the bitboard of position to see where we can go, through a new bitboard of position. Then we just need to apply over the supperposition of all the black pieces' bitboards to see if we can go there or not, and these are just bitwise operations which are very fast.

The Minimax algorithm

We made the AI based on the Minimax algorithm. It builds a tree with the root as the current state of the game and process each movement possibility to find every possible future states.

Then using some evalution function we based on pieces' mobility, king's safety, etc., we compute an evaluation of the leaves. Depending on which color the AI play, it brings back to the father's node the smaller son's evaluation if it is the opponent that just played, otherwise it brings back the bigger one.

But imagine you are playing chess, one thing you are going to do is to look for good moves not only for this turn, but also for the next one, and the next next one, but you never look at each possibilities for one turn as they are so much that are just not viable to play.

There are around 10120 possible moves in chess, it is often compared to the number of atoms in the observable universe which is less than 1081. But the number of viable moves is much smaller.

As for our AI we don't want to compute all of these moves that aren't viable, this is where Alpha-Beta pruning comes.

The Alpha-Beta Pruning optimization

It's very simple, each time you compute states from a level in your tree you also compute the evalution of these nodes, and since you can see which nodes are the best ones, you can choose which sons you are going to compute and earn a lot of time to process deeper trees.

What's next ?

We had only two weeks to do this project, and we had another project at the same time, so it was short and we didn't do any other optimization.

But we had few ideas in mind :

• Use of threads.
• Use of openings' reference to earn time in the beginning of the game and do a viable move in every case.
• Use of endings' reference for the same reason than openings but to be sure to checkmate the opponent in some special cases.

Resources

We learned a lot about chess board representations and AI algorithms by reading chess programming.