Recommended data format for describing the rules of chess

Question

I'm going to be writing a chess server and one or more clients for chess and I want to describe the rules of chess (e.g. allowable moves based on game state, rules for when a game is complete) in a programming language independant way. This is a bit tricky since some of the chess rules (e.g. King Castling, en passent, draws based on 3 or more repeated moves) are based not only on the board layout but also on the history of moves.

I would prefer the format to be:

• textual
• human readable
• based on a standard (e.g. YAML, XML)
• easily parsable in a variety of languages

But I am willing to sacrifice any of these for a suitable solution.

My main question is: How can I build algorithms of such a complexity that operate on such complex state from a data format?

A followup queston is: Can you provide an example of a similar problem solved in a similar manner that can act as a starting point?

Edit: In response to a request for clarity -- consider that I will have a server written in Python, one client written in C# and another client written in Java. I would like to avoid specifying the rules (e.g. for allowable piece movement, circumstances for check, etc.) in each place. I would prefer to specify these rules once in a language independant manner.

Answer 1

Let's think. We're describing objects (locations and pieces) with states and behaviors. We need to note a current state and an ever-changing set of allowed state changes from a current state.

This is programming. You don't want some "meta-language" that you can then parse in a regular programming language. Just use a programming language.

Start with ordinary class definitions in an ordinary language. Get it all to work. Then, those class definitions are the definition of chess.

With only miniscule exceptions, all programming languages are

• Textual
• Human readable
• Reasonably standardized
• Easily parsed by their respective compilers or interpreters.

Just pick a language, and you're done. Since it will take a while to work out the nuances, you'll probably be happier with a dynamic language like Python or Ruby than with a static language like Java or C#.

If you want portability. Pick a portable language. If you want the language embedded in a "larger" application, then, pick the language for your "larger" application.

---

Since the original requirements were incomplete, a secondary minor issue is how to have code that runs in conjunction with multiple clients.

1. Don't have clients in multiple languages. Pick one. Java, for example, and stick with it.

2. If you must have clients in multiple languages, then you need a language you can embed in all three language run-time environments. You have two choices.

   • Embed an interpreter. For example Python, Tcl and JavaScript are lightweight interpreters that you can call from C or C# programs. This approach works for browsers, it can work for you. Java, via JNI can make use of this, also. There are BPEL rules engines that you can try this with.

   • Spawn an interpreter as a separate subprocess. Open a named pipe or socket or something between your app and your spawned interpreter. Your Java and C# clients can talk with a Python subprocess. Your Python server can simply use this code.

Answer 2

Edit: Overly wordy answer deleted.

The short answer is, write the rules in Python. Use Iron Python to interface that to the C# client, and Jython for the Java client.

Answer 3

This is answering the followup question :-)

I can point out that one of the most popular chess servers around documents its protocol here (Warning, FTP link, and does not support passive FTP), but only to write interfaces to it, not for any other purpose. You could start writing a client for this server as a learning experience.

One thing that's relevant is that good chess servers offer many more features than just a move relay.

That said, there is a more basic protocol used to interface to chess engines, documented here.

Oh, and by the way: Board Representation at Wikipedia

Anything beyond board representation belongs to the program itself, as many have already pointed out.

Answer 4

There's already a widely used format specific to chess called Portable Game Notation. There's also Smart Game Format, which is adaptable to many different games.

Answer 5

I would suggest Prolog for describing the rules.

Answer 6

Drools has a modern human readable rules implementation -- https://www.jboss.org/drools/. They have a way users can enter their rules in Excel. A lot more users can understand what is in Excel than in other tools.

Answer 7

What I've gathered from the responses so far:

For chess board data representations:

See the Wikipedia article on chess board representations.

For chess move data representations:

See the Wikipedia article on Portable Game Notation and Algebraic Chess Notation

For chess rules representations:

This must be done using a programming language. If one wants to reduce the amount of code written in the case where the rules will be implemented in more than one language then there are a few options

1. Use a language where an embedable interpreter exists for the target languages (e.g. Lua, Python).
2. Use a VM that the common languages can compile to (e.g. IronPython for C#, JPython for Java).
3. Use a background daemon or sub-process for the rules with which the target languages can communicate.
4. Reimplement the rules algorythms in each target language.

Although I would have liked a declarative syntax that could have been interpreted by mutliple languages to enforce the rules of chess my research has lead me to no likely candidate. I have a suspicion that Contraint Based Programming may be a possible route given that solvers exist for many languages but I am not sure they would truly fulfill this requirement. Thanks for all the attention and perhaps in the future an answer will appear.

Answer 8

To represent the current state of a board (including castling possibilities etc) you can use Forsyth-Edwards Notation, which will give you a short ascii representation. e.g.:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Would be the opening board position.

Then to represent a particular move from a position you could use numeric move notation (as used in correspondence chess), which give you a short (4-5 digits) representation of a move on the board.

As to represent the rules - I'd love to know myself. Currently the rules for my chess engine are just written in Python and probably aren't as declarative as I'd like.

Answer 9

I would agree with the comment left by ΤΖΩΤΖΙΟΥ, viz. just let the server do the validation and let the clients submit a potential move. If that's not the way you want to take the design, then just write the rules in Python as suggested by S. Lott and others.

It really shouldn't be that hard. You can break the rules down into three major categories:
- Rules that rely on the state of the board (castling, en passant, draws, check, checkmate, passing through check, is it even this player's turn, etc.)
- Rules that apply to all pieces (can't occupy the same square as another piece of your own colour, moving to a square w/ opponent's piece == capture, can't move off the board)
- Rules that apply to each individual piece. (pawns can't move backwards, castles can't move diagonally, etc)

Each rule can be implemented as a function, and then for each half-move, validity is determined by seeing if it passes all of the validations.

For each potential move submitted, you would just need to check the rules in the following order:

1. is the proposed move potentially valid? (the right "shape" for the piece)
2. does it fit the restraints of the board? (is the piece blocked, would it move off the edge)
3. does the move violate state requirements? (am I in check after this move? do I move through check? is this en passant capture legal?)

If all of those are ok, then the server should accept the move as legal…