Laying out the Foundations

A look into Chess complexity

As a self-made game developer who has participated in the industry for a couple of years, making a game is easier each time I commit to a new project. That’s why, at first, the task of developing a chess videogame using JavaScript didn’t appear as much of a challenge. Indeed, chess presumably has very simple rules that most people can quickly understand after playing a few games.

However, as I got deeper into the world of chess programming, I realized I was fooled by the apparent simplicity of the game. Programming a chess game is considered an arduous coding exercise in the chess community.

In my opinion, the main reason why this happens is because chess rules create what’s called “emergent gameplay”. Emergent gameplay occurs when simple mechanics generate complex situations. This complexity is not necessarily described by the rules of the game. Also, most of the times it isn’t intentionally designed by the game developer. Complexity emerges when the game mechanics interact with each other.

The best example of this behavior is portrayed in the zero-player game “The Game of Life” created by the British mathematician John Horton Conway. From a set of 4 simple rules, you can create complex dynamical structures, even a functional running computer.

Conway’s Game of Life
Conway’s Game of Life. Taken from [5]

Chess is another example of emergent gameplay. The rules are pretty straightforward: you have 6 easy-to-remember movement patterns and you just need to make sure your king is not put in a tight spot. However, there are a lot of intricate additional rules and edge cases that emerge from these rules. Pinned pieces are an example of this. Taking into account all of these situations makes chess challenging to replicate.

But, the fact that it is difficult is what makes it interesting and exciting. So let’s dive right into it.

Useful resources

It is a good idea to surf the web and look for what’s been made before as a starting point for our own journey. Some of the web resources I’ve found useful are:

  • Chess Programming Wiki: As the name implies, it is the Wikipedia of chess programming. You can find tons of helpful information about programming a chess engine, including heuristics, algorithms, general chess theory, etc. [1]
  • Game Dev Chess Programming Series: A short six-part blog series about all you need to know to program a chess engine. There are interesting articles about game design if you are into that. [2]
  • Introduction to an Advanced Java Chess Engine Tutorial Series: A YouTube video series that shows a complete implementation of a chess engine using Java. It goes into various advanced topics, but we’ll use it to code the move generation module of the game. [3]
  • Code Complete by Steve McConnell: An incredible book about best practices when developing software. As we’ll discuss later, creating a robust, bug-free, high-quality codebase is essential to avoid pitfalls during the development process and make our game extensible in case we want to add functionality later. [4]

Development route

Every masterpiece needs a plan. Here’s some of the steps will take to create our own masterpiece.

Upstream Activities

Before running right into coding, debugging, testing, and smashing our heads against the keyboard, we need to take a step back and analyze how we are going to structure our code. A common mistake programmers make, at any expertise level, is dealing directly with the nuts and bolts of the implementation without thinking about what they are trying to accomplish. Everyone feels this way, even myself. It’s ten times more entertaining to code an algorithm that solves a difficult problem than it is to spend hours writing boring design documents. However, projects that fail to pay proper attention to this phase are doomed to become impossible to manage in the long run.

whats your problem green
When programmers don’t plan their code. Taken from [6]

Why are upstream / preparation activities important? Code Complete gives an awesome analogy to describe it [4]. The author compares developing software with building a house. When you want to build a house, you have to carefully plan out how it’s going to be constructed from its foundations to the final building. You need to list the features your house will have, create a blueprint of the architecture, decide which materials and resources to use, choose the order to build it, and design how each room will be connected to others by water pipes and electrical wiring.

In the same way, when you develop software, you must determine the features it will offer to satisfy the customer’s needs, define the code’s general architecture, choose your resources (algorithms, data structures, design patterns, etc.), decide the order to integrate the different modules of the program so it doesn’t fall apart midway through, and design how each module will be separated from the others and how they will communicate to work together and reach the end functionality.

Also, the bigger your house is, the more planning you need to do. It is not the same to plan for building a bird’s house as it is for building a skyscraper. In this case, each one decides how big they want their chess program to be and how much time is spent on planning it.

Alt text
Programming is the same as building. Taken from [7]

Game Implementation

As stated in [1], two fundamental components of a chess program are board representation and move generation.

Board representation refers to how the chessboard is stored in data inside the computer. The board representation we choose will play a huge role in how we access information about the state of the game and how we can manipulate that state depending on player input. Therefore, it is important to choose a versatile yet simple representation so these tasks don’t become troublesome.

Move generation is the part of the program that calculates every legal move for any given board configuration. By board configuration I mean the way pieces are placed in the board. This module needs to be aware of all the rules on how pieces are allowed to move. It needs to consider tricky rules like castling and en passant captures. And surely it needs to ensure that every move doesn’t risk King’s safety. As we mentioned earlier, when these rules interact with each other, complexity arises. For example, imagine a game where an en passant capture is possible, but performing that capture will leave the king in check. Not only do you need to evaluate that all of the specific conditions of the en passant capture are met, but also you have to evaluate if that capture leaves an opening for any rival piece to capture the king. That’s why move generation is the real challenge when programming chess.

So, as the first step, we’ll be focusing on getting these two elements right because this is the backbone of the rest of the program. It is crucial to make sure our move generation behaves correctly every single time. This involves creating a testing framework that assesses the correctness of our code and pinpoints errors and bugs. A common technique used in chess programming is called perf testing, but we’ll discuss that later. Apart from doing perf testing, we’ll implement our own testing functions that assess every single piece of code.

After doing the hard work, we’ll be dealing with two important parts of the game: the user interface and handling player input. As we’ll talk later, compartmentalizing these tasks in their own modules and decoupling them from the program backbone brings multiple advantages.

Finally, all these modules will come together to create the game loop. The game loop is the sequence of actions that are most repeated in the game and make up the essence of the gameplay.

The Bottom Line

To summarize, this is the route we’ll follow to develop our chess program:

  1. Upstream activities
  2. Board representation
  3. Move generation
  4. Testing
  5. Player Input
  6. User interface
  7. Game Loop

References