Emergent behavior from simplicity: Modeling chess

I like to doodle during meetings – it helps me pay attention. Recently, though, it ended up turning into a one-person design session for modeling a chess game. The goal – on paper – was to make a system that, with as low a degree of complexity as possible, would allow a chess game between two players to be carried out. All chess rules would be enforced, so that only valid moves would be possible. Three days later, I have a working chess program that you can play on the command line with a graphical interface. How did that happen? And what does this demonstrate on an abstract level?

The concrete implications of the program I’ve written are very clear: I am a nerd. There’s not a whole lot to add to that, so let’s move on. To whet your appetite, here are some screenshots from the current command line version of the game:

Starting a game.

Making a move. As you can see above, you can scroll up to see old moves.

What a sissy you are, black! He resigned without hardly putting up a fight.

The more abstract implications are interesting, because they demonstrate something that I really love thinking and talking about, much to the chagrin of fellow man in general: emergent behavior in complex systems that results from simple rules. Complexity from simplicity. The fact that this can happen is probably what makes chess so popular, but it’s also the reason things like molecules, bacteria and multicellular organisms are popular, or at least abundant.

How do you program chess in a few train rides? My free-time programming takes place on the train commute to work and back, so I force myself to keep it simple, which might seem hard when you’re talking about chess.

I used two tricks to decrease the complexity and increase the maintainability and adaptability of my code – all of which were necessary for this project. If you add up the hours I programmed it in, you come to with less than 7, and sometimes I realized that I had to change things I’d already implemented to make other things possible. The whole thing boils down to a few guiding principles that are in no way new, but were very fun to observe here in action:

Build from the bottom up

In chess, a lot of decisions have to be made at every turn. Whose turn is it? What pieces can I move? Am I in check? Can the piece I chose really move there?

All of these decisions are made by a person when a game of chess is played with a board and people and all of those things. So a first step could be to try to program a player who can analyze the situation, find all of the pieces that could be moved, and then move them. Don’t program like that, you’ll produce tons of code that you’ll never want to touch again.

Instead, divide up each decision into smaller decisions. Make them as simple as possible. The complex behavior you are trying to produce will be more robust if it emerges from smaller pieces of behavior that can be quite simple. Think of an ant colony: the behavior of the ant colony as a whole emerges, without any kind of central coordination whatsoever, from the behavior of thousands and thousands of ants which actually aren’t smart at all. They don’t even know much about what the other ants are doing, and yet they manage to work quite well together.

In my chess game, the players know what board they’re playing on and what pieces they have. They don’t know whether it’s their turn or not, they aren’t aware of what moves their pieces are allowed to perform. In fact, they don’t even know where their pieces are on the board, nor do they know enough about the pieces to set up the board at the beginning of the game.

Players receive instructions – presumably from a human – that contain the start position and end position of a move. Everything they do after that is just poking around in the dark, but it works. How?

First, they pass the instructions they’ve received on to the chessboard they’re associated with. The chessboard knows both players – and nothing else about them – and blocks the player if he’s trying to move out of turn. Then the chessboard looks up the positions the player is interested in. If both positions are valid, the chessboard passes the command on to the starting position.

Each position is also somewhat intelligent. It knows what chessboard it’s associated with and it knows its immediate neighbors. It also knows if there’s a piece standing on it – you kinda notice that kind of thing. So the position check if it has a piece and, if it doesn’t, it complains. If it does, it passes the command to its piece.

The piece takes a look at the player requesting the move and checks whether it belongs to that player. If it doesn’t, it complains. If it does, takes a look at the moves it’s allowed to make. If the goal position in the command is legal, it goes there. If it’s not, the piece complains.

So there you have it. That’s pretty much the essence of how the game works. Of course there’s more to it, but that wraps up most of the complexity and is enough to get a game going without any soecial rules, like casting, en passant or pawns turning into queens.

All of those rules, though, are implemented too – according to the same principle. Keep things simple, make decisions as locally as possible, and separate logic into as many smaller chunks as possible.

Keep it abstract

As I mentioned before, all the stuff I programmed was dumb. The player’s dumb – he knows what pieces he has and what chessboard he’s playing on, but he doesn’t even know where the pieces are and he doesn’t know anything about the rules of chess. He just tries things out and hopes he doesn’t get yelled at. It’s a rather touching self portrait, if you ask me. Not that anybody’s asking.

But the player can’t feel too bad. The chessboard only knows the players and the positions, but not the pieces, so it always has to ask the positions for the pieces. And the pieces only know what moves they can make, and even that is formed by asking the pieces about the possible positions and the possible pieces on top of them. “Is there a position here? And does it have a piece on it?” is the question they’re always asking, and they ask the poor positions, which don’t even really understand why.

This is nice and divided up into digestible pieces, but it could neglect something important: abstraction.

See, each piece does basically the same thing: Moving a certain number of squares in a certain direction. So you can program each pieces’ legal moves individually, but you definitely won’t be done in less than 7 hours.

The chess pieces in my program are all subclasses of a single superclass, and that superclass can do a few things that, in turn, each chess piece can do, because it inherits those capabilities from the superclass. This is pretty basic object orientation, and the relationship is obvious, so I won’t get into it . What’s interesting is the movement that they all have in common.

As I said before, almost every piece moves in a certain direction for a certain number of squares. They differ for each piece, but if you take the part that they all have in common – moving in a direction for a certain number of squares – you can implement that in a more generalized fashion, so that you only have to tell each piece what directions it can move in and how far. The rest of the work is taken care of for you by the more abstract movement method.

That’s how I implemented the movement for my pieces, which meant that I needed a little bit longer for the method implementing the abstract movement logic. This was more than compensated for by the fact that the method allowed me to write the movement logic for queens, bishops, kings and rooks in about two minutes total afterwards, and a good part of the pawns’ movement logic in about the same time. Special cases, like castling, en passant and knight movement took a little longer, but at least they were special cases. If I hadn’t abstracted the common part of the logic in the beginning, I would have needed that much time for each piece, writing basically the same code, again and again and again.

Worry about visualization at the end

Of course my main goal was to produce software that can validate and execute legal chess moves – I mean, haven’t we all dreamed of doing that at one time or another? We have, right? Guys?

But of course you also want to be able to play the game too. If I would have started with the user interface first, it might have been harder to pull the functionality out of the interface. As it is, I made an interface at the very end and just hooked it up to the logic controlling the pieces, board, etc.

Who cares? Well, I do, so there. This way, if I decide to abandon the beautiful text interface the game has now, I will only have to write a new interface. It won’t matter if it’s a web interface, or a window, or a way of sending he moves automatically to a 3D printer. The logic won’t have to change – the interface just has to access it.

So that’s how to write chess in seven hours! If you’re interested in playing it or using the library for your own devious purposes, it’s available for use on PyPI or for development on Github. Knock yourself out.

Advertisements
About

My name’s Daniel Lee. I’m an enthusiast for open source and sharing. I grew up in the United States and did my doctorate in Germany. I've founded a company for planning solar power. I've worked on analog space suit interfaces, drones and a bunch of other things in my free time. I'm also involved in standards work for meteorological data. Now I work for the German Weather Service on improving forecasts for weather and renewable power production.

Tagged with: , ,
Posted in Uncategorized
One comment on “Emergent behavior from simplicity: Modeling chess
  1. Nancy Wills says:

    You. Are. So Weird.
    Haha – just kidding. You are actually quite brilliant. And weird.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

From the archive