An attempt at IBM’s Ponder This (Feb 2010)

Ponder this is a collection of puzzles, with a new puzzle released every month. This month’s puzzle is supposedly a famous chess problem.

The site seems to be down right now. It may or may not be back up in the future, but if it isn’t, I think Google has it cached.

The problem is something like this:

White starts a chess game with 1. e4 . On the fifth move (10th ply), black’s knight captures white’s rook and delivers checkmate. Find the missing moves.

To clarify, the game goes something like this:

1. e4 ..
2. .. ..
3. .. ..
4. .. ..
5. .. NxR#

My attempt

I thought this problem as a problem for computers instead of for humans. So the problem now is to write a computer program to generate the solution (or a list of solutions). I used Java for the programming language.

Instead of implementing all the chess rules from scratch, I used Chesspresso as the chess library. It was obviously designed with efficiency in mind. And it’s written in pure Java.

Here are some basics on how Chesspresso is structured:

  • The two most important classes are Position and Move. The Game class is also fairly important, but I’m not using it here.
  • The Position class contains data about a particular board state. This includes where all the pieces are, and whose turn is it, and a few other things.
  • The Move class describes a single move. It contains data about its starting square, its destination square, which piece is moving, and some other things, but not much else. It’s very compact, and is normally used as a short instead of a class.
  • You really can’t do that much with a Move without its associated Position. After all, it fits in a short. A short in Java is only 16 bits, by the way.
  • Position objects are mutable. Even though the ImmutablePosition class exists, methods generally change existing Position objects instead of returning new ones. This is different from say, String or BigInteger.

The biggest problem I found with this library is that its documentation is fairly lacking. Although there are some javadocs for individual classes and methods, there is no manual on how the library is supposed to work on a large scale.

Fortunately there were a few examples, in the form of programs using the library.

While it was difficult to figure out how to do simple stuff (like creating a Move from a short), there are already functions that do more advanced things, like generating all possible moves from a given position.

So after playing a bit with my code, I came up with this:

import chesspresso.Chess;
import chesspresso.position.Position;
import chesspresso.move.Move;
import chesspresso.move.IllegalMoveException;

public class Main{

	static Position position;
	static String[] game;
	
	static final int MAX_PLY = 9;

	// Don't bother handling exceptions.
	public static void main(String[] args) throws Exception{
		// The initial position.
		position = Position.createInitialPosition();

		// Array of moves.
		game = new String[MAX_PLY + 1];

		// First move: e4.
		// Boolean input (third parameter) describes whether it's a capture.
		short firstmove = Move.getRegularMove(Chess.E2, Chess.E4, false);

		// Alter the position by making this move.
		position.doMove(firstmove);

		recurse();
	}

	// All the data is mutable and therefore is stored globally.
	// Calling this method should not change the state of the position
	// since any changes are eventually undone.
	static void recurse() throws IllegalMoveException {
		int ply = position.getPlyNumber();
		Move lastMove = position.getLastMove();

		// Record move.
		game[ply-1] = lastMove.getSAN();

		if(ply > MAX_PLY){

			// Check if we've found a position where a black knight captures
			// a white rook with checkmate on the fifth move.
			if(position.isMate() && lastMove.isCapturing()
				&& lastMove.getMovingPiece() == Chess.KNIGHT
				&& position.getPiece(lastMove.getToSqi()) == Chess.ROOK){

				// We found it, now print the sequence of moves.
				for(int i=0; i<ply; i++)
					System.out.println(game[i]);
				System.out.println();
			}
			return;
		}

		// Recurse all the possible next positions.
		short[] nextMoves = position.getAllMoves();

		for(short thisMove : nextMoves){
			// Make the move, recurse, and undo the move.
			position.doMove(thisMove);
			recurse();
			position.undoMove();
		}
	}
}

If you want to run this, save the code as Main.java. You’ll need the Chesspresso jar file (can be downloaded), I’ll call it chesspresso.jar. The following commands compiles and runs it:

javac -cp .;chesspresso.jar Main.java
java -cp .;chesspresso.jar Main

The code should work.

There is, however, one small problem. I somewhat underestimated the size and computational complexity of the calculation.

The number of chess positions grows very quickly. Because there are nine unknown moves, and using an estimate of 20 possible moves from every position, we would have 20^9 \approx 512,000,000,000 games by the end of the ninth half-move.

I can evaluate about 100,000 positions every second with my average computer, so that many positions would take me about 1422 hours, or around 2 months.

Of course if I really wanted to calculate this, I could run it on a supercomputer, or distribute the task across many computers, or more likely, make the program save its state and run it over a couple of months. It’s definitely feasible, but pointless since the solution is already available on the internet.

Apparently someone has already done this (see the last response).

So even though my program wasn’t able to solve the problem, I think I still learned something in the attempt.

One Response to An attempt at IBM’s Ponder This (Feb 2010)

  1. Anonymous says:

    thanks very much for this! It’s very hard to find an actual example of how to use the chesspresso library

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

Follow

Get every new post delivered to your Inbox.

Join 71 other followers

%d bloggers like this: