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.

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.

• Development
  
  • Java
  • subversion
  • maven
  • eclipse
    

    with the following plug-ins:
    

    • Mousefeed
    • Subversive
    • qwickie
    
    
  • Squirrel
  
  
• Programming Languages
  
  • Prolog
  • Haskell
  • Smalltalk
  
  
• Usefull
  
  • BloGTK
  • gtk-recordMyDesktop
  • Gedit
    with the following plug-ins
    
    • Bracket Completion
    • Session Saver
    • Snippets
    • TabSwitch
    
    
  
  
• Interesting
  
  • Geogebra
  • Processing
  • Contect Free Art
  • Combinatorial Game Suite