Done in groups of three over two weeks.
We first designed the Chess Board through UML diagram, then implemented the chess board rules.
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 :
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.
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.
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 :
We learned a lot about chess board representations and AI algorithms by reading chess programming.
+33 6 09 34 62 27