Github repo for the TU-Berlin "Project AI - Symbolic Artificial Intelligence" course.
Implementation of a Alpha-Beta Search Chess AI using the bitboard representation, built with Python/ Cython.
The final goal of this project is to implement a Chess Engine using Alpha-Beta Search and further improve on its strength and efficiency. In this case, a chess variation called "King Of The Hill" has been chosen, wherein players win based on classic chess conditions, or by reaching the center of the chess board with their king.
Milestone I - Basic Chess Engine: (done)
- Board representation and chess logic
- Dummy AI, able to play games using random moves
- Benchmarking
- Simple evaluation function
- Time management
Milestone II - Simple AI: (done)
- Minimax
- Alpha-Beta Search
- Simple Move-Sorting and Iterative Deepening
Milestone III - Advanced AI: (done)
- Principal Variation Search
- Better Move-Sorting, Evaluation function, etc.
- Quiescence Search
- Monte Carlo Tree Search
Milestone IV - Optimized AI: (current)
- Connection to Game Server
- Testing, Optimizing, Bug-fixing
Ahead of the project, our team discussed tools to use for our implementation, factoring in our experiences and programming backgrounds. Based on the consensus that most of us had used python in the past, and its ease of legibility and flexibility in terms of computing and web packages, we decided to base our implementation on it.
Although its benefits mentioned before, some drawbacks, such as computational speed and restricted use of unsigned data types, were obvious. As such, part of our code relies on Cython, which is capable of compiling Python into C/C++ modules.
Using Python also opens up possibilites for further milestones, where the chess engine will have to communicate with a web server for matches and have a graphical user interface, both of which can be done with a rudimentary Django/React/HTML/CSS server implementation or as a client with a PyQt front-end.
After several research and team discussions, we came to the conclusion, to implement Bitboards in our Chess AI, instead of Mailbox (Arrays). We found out, that investigating, if the King is exposed into a check, after a move has been made, is a very time consuming task.
Mailbox uses a so called "if square attacked" function, to calculate the attacked squares of the chessboard. This process causes a significant loss in performance.
Bitboards on the other hand, operate with "pre calculated attack tables". The "magic Index" is implemented to reference these pre calculated attack tables, in order to obtain the data, of the attacked sqaures on the chessboard. This leads to a significant increase in performance, as a simple lookup is used, instead of real time calculations.
So far our implementation computes attack maps for sliding pieces on the fly, instead of using magic bitboards. This is due to ease of implementation and testing, but will be changed in future updates.
- Chess Programming Wiki - The "beacon of light" in chess programming and our implementation so far.
- Fast Chess Move Generation With Magic Birboards - Great article which helps so understand how magic bitboards function.
- Chess Engine Playlist - Wes Doyle - Playlist of livestreams where Wes Doyle implements a chess engine using arrays. Interesting for Python specific ways of solving chess problems and entertaiment purposes.
- Konstantin Hasler
- Cedric Braun
- Raul Nikolaus