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