Things I learned coding a chess game

As I alluded to in my bitboard rant a little while ago, I’ve been working on a chess game in my own time. I’ve had a few realisations while I’ve been building it, which I thought I’d share.

Realisation 1: You don’t always need objects

Coming up through uni in Java and spending a large chunk of my professional life using OOP languages, I often found myself reaching for a struct in golang. On noticing how great the bitboard solution was, I started rethinking how I define my types.

The obvious example is how I define my piece colours

type Colour bool

const (
  White Colour = true
  Black Colour = false
)

Or, something a little less obvious, I use a uint8 to represent my pieces. Doing it this way, I can apply a mask of 0x80 to get the colour of a piece and use go’s iota to quickly put the different types into place.

type Piece uint8

const NullPiece Piece = 0

const (
	WhitePawn Piece = 1 + iota
	WhiteRook
	WhiteKnight
	WhiteBishop
	WhiteQueen
	WhiteKing
)

const (
	BlackPawn Piece = 0x81 + iota
	BlackRook
	BlackKnight
	BlackBishop
	BlackQueen
	BlackKing
)

// Colour gets the colour of a piece
func (p Piece) Colour() Colour {
	return (0x80 & p) == 0
}

I think this was probably my biggest epiphany and really showed me how amazingly simple you can make some things by picking the right tool

Realisation #2: Unit tests are your friend when doing something like this

Something I read while I was trying to figure out where to start was a lot of people saying “test everything”, and I very quickly realised what they meant. I spent about 2 hours tracking something down very early on, and decided to try to push for around 80% testing coverage outside of the UI rendering code. Everything to do with the rules of chess has a unit test at the moment, I need some more around my move expansion and board evaluation functions.

Something I also realised writing these tests is that it helped increase my understanding of my own code. My board functions are all together in a file of about 1000 lines, making it a bit difficult to navigate unless you know what you’re looking for, so knowing that file inside out and having readymade examples to help me remember how to use those functions has been a huge help.

Realisation #3: It’s really difficult to find issues in a search algorithm

I did an AI course when I was in uni, so search is something I was already vaguely familiar with. Something I was not aware of, though, was how difficult it was to be able to manually diagnose an unexpected move, the search spaces are huge and makes it really difficult to be able to break at the right point and step through the execution.

The first problem I encountered was that the computer just kept picking the first move it generated. A typical game would be

NG3 H5
RG1 H4
RH1 G5
RG1 G4
...

I recognised this as the move generation going from H1->A8 pretty quickly, but it took me a while to figure out where the problem was, mostly that I wasn’t setting the best guess correctly.

But there have been repeated cases where I’ve seen this same behaviour. I implemented alpha-beta pruning to cut down on my search space and started seeing this happen again. Tracking down why that was occurring took me around 6 hours this time.

I’ve certainly been cut down to size, this wasn’t something I was ever “good” at, but I thought I could struggle through it. On the plus side, it means I’ve got something new to learn, which is always a fun proposition.

Realisation #4: I know how to play chess, but I had no idea how to explain it

One less programming related, but I still have some of the trophies I won playing chess in school, so I would say I’m at least an ok, if rusty, chess player.

Communicating how I think about a board position, though, had me completely stumped. For example, material calculation is easy:

1. Pawns are reasonably expendable early on
2. Bishops and Knights are worth roughly the same
3. Rooks are worth roughly twice a bishop or knight
4. Queens are worth roughly twice a rook

But how do you communicate pawn structure? How about knight outposts? Controlling the centre?

What about something useful but not particularly important, like putting a rook on an empty file?

This is not easy to explain, so I’ve been reading a lot of “how to play chess” type books trying to figure out how to encode that into a series of evaluation functions. A lot of it boils down to “how can I turn this into a bitmask”, but it’s still something (which now seems really obvious) that I hadn’t really anticipated needing to think about.

Realisation #5: Hard problems are fun

Though chess engines are something that’s been written about extensively, it’s something that people still shy away from because it’s a lot of work to get something even reasonably competent.

After I started doing a little bit every night, it took me about two weeks to get a player that would even make random moves within the rules of the game. I now have something that plays really badly after another week, and I can see easily myself running down a deep rabbit hole for another 6 months getting something competitive.

But it’s been addictive. Every time I do some work on it, the AI gets just a little bit smarter, or I shave a small amount of time off the move calculation. And I’m actually enjoying myself doing it.

Conclusion

I think this has been an ideal project to pick up at home. It’s giving me a good deal of new things to learn, and I find myself losing hours to it quite easily.