## 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.

### 2 Responses 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

2. John Doe says:

So this was a while ago, but I was trying to modify your code slightly to learn chesspresso and I’m a bit confused about this line:
“…&& position.getPiece(lastMove.getToSqi()) == Chess.ROOK)…”

Given that we’ve found our solution, wouldn’t the getPiece method always return KNIGHT on this square, since the position is the final (checkmate) position?

Thanks.