Clarence Hann

Building a Chess in C# – Bitboard Data Structure – Part 1

What you will learn from this article series:

  • What is a Bitboard Data Structure?
  • Why do I wanna use this Data Structure anyway?
  • How can I easily implement a chess with this Bitboard Data Structure?

So without further ado, let’s answer the first question:

What is a Bitboard Data Structure?

It is a board representation for Chess that makes your AI faster, compared to a “duh” and easy-to-think-of solution: 2D array. Why? Others have already explained. Below are the external readings.

https://www.chessprogramming.org/Bitboards

https://en.wikipedia.org/wiki/Bitboard

Why do I wanna use this Data Structure anyway?

Because it makes your chess engine cooler with its better performance, and its added difficulty to implement compared to a 2D array data structure. It can make you outstanding in an AI class assignment, or look awesome on your portfolio if you make a Chess game with a Bitboard Data Structure.

How can I easily implement a chess with this Bitboard Data Structure?

Simple. Follow this article and its series.

Wait, before you leave and think of it as another clickbait, I want you to know the purpose of this article is for YOU to be able to implement a Bitboard Chess engine at the end, without being bored along the away. Source code will be provided as well so Let’s delve into this fun learning process!

Part 1: How does Bitboard work

TLDR: Each square is a yes or no. There are 64 of them. So a 64-bit chunk (an Int64 in C#) is called a “Bitboard”. It is an answer to a query such as “For each square, is there a white king?”, “For each square, is there a black piece?”. In order to represent the same board information as a 2D array data structure, one Bitboard doesn’t cut it. But 12 Bitboards can.

Don’t know what I’m saying? Partly understand but wanna know more? Please feel free to read the following:

Chess has 64 squares. Each square can have 2 states: has a thing, and has nothing. For example, suppose there’s a classroom of 64 students, I ask each of them a question, do you have a white king? But I let them write “yes” or “no” on a paper, and pass around the class. So after each student has written their answer on the paper, it will look like this (suppose there’s only one white king):

  • no
  • no
  • no
  • no
  • yes
  • no
  • ….
  • no

If we denote the word “no” as number 0, and the word “yes” as number 1, it can be seen as this:

All the other squares are 0 because their answers are “no, I don’t have a white king”. While the square who has a white king says “yes. I do have a white king”.

If we rearranging these 0s and 1s into a single line, from a1 to h1, then a2 to h2… until a7 to h7 then a8 to h8, it will look like something like this:

00000000 00000000 00000000 00000000 00010000 00000000 00000000 00000000

I believe you’ve got it by now. This 64-bit chunk can answer questions such as “Where is the white king or the board?”, “Where are the white pawns on the board?”, “Where are all the black pieces?”. And each answer to those questions is a 64-bit chunk, which in C# can be a number of type Int64.

Another example just in case:

“What are all the black pieces?”

If this time we list from h8 to a8, then h7 to a7, etc. until h2 to a2, h1 to a1, then the 64-bit chunk would be like this:

01110001 11001011 10110010 00000000 00000000 00000000 00000000 00000000

with the rightmost digit being a1, and the leftmost digit being h8.

This way of representation (h8 to a8, h7 to a7 … a8 to a1) is what we will use in this blog. Why? Well, it seems everybody is using this representation so why not? 🙂 Plus, the CS experts at the University of Wisconsin–Madison suggest it has a “mathematical advantage” to arrange the 64 squares in this way. Extra reading time! http://pages.cs.wisc.edu/~psilord/blog/data/chess-pages/rep.html

Ok at this point, I suggest you scroll up to read the “TLDR” part again and see if this time you totally get it. Especially, the sentence in the end:

In order to represent the same board information as a 2D array data structure, one Bitboard doesn’t cut it. But 12 Bitboards can.

Why? Because a bitboard can only tell you if a square has a thing. It can’t tell you what is that thing. But since there are 2 sides in Chess: Black and White. And 6 classes for each side: King, Queen, Rook, Knight, Bishop and Pawn. So if I know whether a square has a stuff for each type of it, I have the information of the whole board.

(To Be Continued…)

Leave a Reply

Your email address will not be published. Required fields are marked *