Coding Challenge #56 - Chess

This challenge is to build your own chess program. The game chess has held a fascination for many people for hundreds of years, so much so that the first automated chess playing machine, “The Mechanical Turk” was built in 1770!

However, The Turk was a fraud. There was in fact a human player hidden inside the machine who was operating it. This artificial artificial intelligence inspired the name for Amazon’s crowdsourcing market place; Amazon Mechanical Turk .

The idea was copied a few times, then in 1941 real algorithmic attempts to play chess began and soon afterwards chess became considered a big challenge for AI. This lead to a focus on developing ‘AI’ to play chess and ultimately to IBM developing Deep Blue .

Deep Blue was the first computer based chess player to win a game against a world champion in 1996 and subsequently the first to win a match in 1997. It’s estimated that Deep Blue cost around 10 million USD to develop! It wasn’t exactly portable either, being a supercomputer that took up two full server cabinets!

If You Enjoy Coding Challenges Here Are Two Ways You Can Help Support It

1. Refer a friend or colleague to the newsletter. ??
2. Buy one of my courses that walk you through a Coding Challenge.

The Challenge - Building A Chess Game

In this coding challenge we’ll build a chess game. It’s a challenge you could do with a web-based UI, a desktop or mobile UI or even a terminal based UI. The choice is yours.

What makes this an interesting challenge is the complexity of a game of chess. It’s widely agreed that to play well you need to be thinking at least five moves ahead. Doesn’t sound much, but with 30 legal moves per piece, there are a quadrillion possibilities to consider. If you could evaluate 10 million possibilities a second, it would take three years to evaluate them all!

Chess is a great testing ground for your data structure and algorithm skills. Here’s why it’s so key.

1. Picking the right data structure to represent the board is crucial to the performance of the move generation and evaluation. Often bitboards are used to represent the board and Huffman encoding is used to compact data for long-term storage (you can learn move about Huffman encoding in the build you own compression tool challenge).
2. Chess programs usually consider the possible chess moves as a game tree, the root being the initial state of the game and every node representing a game state. The next move to make is normally determined by examining the tree. In theory if you generate the entire tree you can ‘solve’ the game. But these tree’s get big fast, for example the simple games tic tac toe ends up with 255,168 leaf nodes!
3. So selecting the right algorithm(s) to explore the tree with a key to making a move in a reasonable amount if time - we don’t want to wait weeks or months between moves!

Some algorithms to explore are minmax, alpha-beta pruning , and Monte Carlo tree search .

Continued...

The steps for the rest of this Coding Challenge are detailed on the website as Build Your Own Chess Game .

Share Your Solutions!

If you think your solution is an example of the developers can learn from please share it, put it on GitHub, GitLab or elsewhere. Then let me know via Twitter or LinkedIn or just post about it and tag me.

Request for Feedback

I’m writing these challenges to help you develop your skills as a software engineer based on how I’ve approached my own personal learning and development. What works for me, might not be the best way for you - so if you have suggestions for how I can make these challenges more useful to you and others, please get in touch and let me know. All feedback greatly appreciated.

You can reach me on Twitter , LinkedIn or through SubStack.

Thanks and happy coding!

John