Thursday, July 29, 2010

Counting Backgammon End Positions

In this blog I will count the number of end positions in backgammon.

Recently I picked up backgammon again. But I could not put my mathematical mind to rest. I got interested in the question of how many end positions backgammons has.
In order to count the number of positions I will introduce the following terminology. The number of stones you own in the end position will be denoted by $$m$$. The number of points used available is $$n$$. $$o$$ is the number of stones owned by the opponent, which occupy $$p$$ points of the available $$n$$.
So in the following example, playing as black, the following equalities apply $$m=8,\,n=6,\,o=2,\,p=1$$.

Let's look at a special case first. Lets assume we have a contact-less end position. So $$o=0$$. I will proof that the number of backgammon end positions with $$m$$ stones and $$n$$ points is

$m + n - 1 \choose m$

To see this equality, study the following diagram, which corresponds with the figure above if you ignore the opponent stones:

Every dot corresponds with a stone. Every bar with the division between points. A moments reflection will bring the insight that every diagram of this kind corresponds to a backgammon end position and vice versa, every backgammon end position can be described by such a diagram. This proofs the stated equality.

With the result of this special case we can answer the main question: How many backgammon end positions exist with $$m$$ stones distributed over $$n$$ points of which $$p$$ are occupied by $$o$$ opponent stones? This number is exactly

${n \choose p} {o - 1 \choose o - p} {m + n - p - 1 \choose m}$

The proof of the above equality comes from the following insight. The opponent stones are distributed over $$p$$ points. there are $$n \choose p$$ ways of picking the occupied points.
For a point to be occupied it must at least contain one opponent stone. So of the $$o$$ opponents stones, we can freely distribute o - p opponent stones over $$p$$ points. This is the special case we counted already, so this can be achieved in $${(o-p) + (p-1) \choose o - p} = {o - 1 \choose o - p}$$ ways.
This brings us to the final factor. It represent the $$m$$ stones which should be distributed over the remaining $$n-p$$ points. Again this is given by our preliminary result of $${m + n - p - 1 \choose m}$$ ways. This proofs the stated result.

In conclusion: the number of backgammon end point positions with $$m$$ stones distributed over $$n$$ points of which $$p$$ are occupied by $$o$$ opponent stones equals

${n \choose p} {o - 1 \choose o - p} {m + n - p - 1 \choose m}$

Null Object Pattern

In this post I will summarise the Null Object Pattern.

The null object pattern is a means to forgo null checks. The following example will be used to explain how the null object pattern can be used to reach this goal.

public Person getPerson()
{
return person;
}

public void showName()
{
Person person = getPerson();
String name = "unknown";
if (person != null)
{
name = person.getName();
}
System.out.println("name: " + name);
}


In my opinion a few there are thing wrong with this code.

• Different call flow. Because of the null check there are two possible paths through this code. If this is the only point at which this occurs, it would not be a big problem. But
• Caller is responsible. The caller is made responsible to check if the returned value is correct. By placing the burden at the callers side probably means a lot of duplicate boilerplate code in checking for null values.
• Error prone. You only have to forget the null check once and it will blow up in your face with a NullPointerException.

The null object pattern is a means to remedy these points. In the following example I refactored the original code.

class UnknownPerson extends Person
{
@Override
public String getName()
{
return "unknown";
}

}

public Person getPerson()
{
if (person == null)
{
return new UnknownPerson();
}
return person;
}

public void showName()
{
Person person = getPerson();
System.out.println("name: " + person.getName());
}


With the introduction of the UnknownPerson all the mentioned problems are solved.

• Same call flow. The calling code does not have to differentiate between a null value and a legitimate value
• Callee is responsible. The callee is now responsible to check if the returned value is defined. By placing the burden at the callee side there is a single check so no duplication of code. So
• Less error prone. Because the null check is in a single location there are less oppertunities for making a mistake.

This summarises the null object pattern.

Saturday, July 24, 2010

Introduction to Software Development - Part 2

In this blog I will outline the second instalment of the introduction to software development I had with a friend of mine.

In a previous post I told the story of introducing software development to a friend. In this second run, we took on a little project to hone our developing skills.

We looked into Mancala. It is a game in which stones get sown around the board. The exercise was meant to develop a feel for architecture.

We had a lot of discussion about responsibilities. Which object should be responsible for a certain task? I think that the question of responsibility is a very good to get your bearing while developing an application.

In the subsequent meeting we will finish this little project.

Fresh Install

In this blog I will outline the pieces of software I would install if I would be doing a fresh install of a computer. It is mainly written for a personal reference.

First of all, the operating system. I started using Ubuntu about three years ago and I really like it. So the primary software will the operating system, and it will be Ubuntu.