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}
\]

17 comments:

  1. I did the math and calculated the total number of positions in a backgammon game. It is a stagering:
    3458085312432494932095

    or
    three sextillion ,
    four hundred fifty eight quintillion ,
    eighty five quadrillion ,
    three hundred twelve trillion ,
    four hundred thirty two billion ,
    four hundred ninety four million ,
    nine hundred thirty two thousand ,
    ninety five

    ReplyDelete
  2. Hi Daan.

    I would like to reprint this article in my backgammon magazine, Bibafax. Would you kindly give your permission?

    You can checkout my references at www.backgammon-biba.co.uk.

    Michael Crane
    info@backgammon-biba.co.uk

    ReplyDelete
  3. Daan, since the above comment I have formatted your content into my magazine and I would like to send you a pdf so that you can preview it before (hopefully) giving your permission.

    Please email me and I will send it by return.

    Regards.

    Michael

    ReplyDelete
  4. Yesterday, while I was at work, my cousin stole my iphone and tested to see
    if it may survive a twenty five foot drop, just so she can be quite a youtube
    sensation. My ipad by apple is now broken and she's 83 views. I understand that is completely off topic but I had to fairly share it with some one!

    Here is my weblog ... real estate articles

    ReplyDelete
  5. I am regular reader, how are you everybody? This article posted at this site is
    genuinely good.

    Stop by my blog post

    ReplyDelete
  6. Hi there Dear, are you really visiting this website regularly, if so then
    you will definitely get pleasant knowledge.

    Feel free to visit my blog post; lacasitamariadelaesperanza.org

    ReplyDelete
  7. Do you mind if I quote a couple of your articles as
    long as I provide credit and sources back to your webpage?

    My blog site is in the very same niche as yours and my users would really benefit from
    some of the information you present here.
    Please let me know if this ok with you. Thanks a lot!


    Feel free to surf to my web page ... educate online

    ReplyDelete
  8. Undeniably consider that that you stated. Your favourite reason seemed to be at the
    internet the simplest thing to take into accout of.
    I say to you, I definitely get irked even as other folks think about worries that they just don't recognize about. You controlled to hit the nail upon the highest and outlined out the entire thing without having side-effects , other folks can take a signal. Will likely be again to get more. Thank you

    Here is my page electrical engineering news

    ReplyDelete
  9. Hi great blog! Does running a blog similar to this take a massive amount
    work? I have virtually no expertise in computer programming but I was hoping to start my own blog in
    the near future. Anyway, should you have any ideas or tips for new blog
    owners please share. I understand this is off subject but I just wanted to
    ask. Thanks a lot!

    my website; http://moodle.cephuelva.org

    ReplyDelete
  10. It's awesome to visit this website and reading the views of all colleagues concerning this post, while I am also keen of getting experience.

    Also visit my web page; Health food News

    ReplyDelete
  11. Hi to all, the contents present at this
    web site are in fact remarkable for people experience, well, keep up the good work
    fellows.

    Look into my homepage: entertainment news today

    ReplyDelete
  12. After looking into a handful of the blog posts on your site,
    I really like your technique of blogging. I saved it
    to my bookmark webpage list and will be checking back in the near future.
    Please check out my web site too and let me know how you feel.



    Have a look at my web site; http://clickbank-tribune.com/

    ReplyDelete
  13. An impressive share! I have just forwarded this onto a friend who has
    been conducting a little research on this.

    And he actually ordered me breakfast due to the fact that I found
    it for him... lol. So let me reword this.... Thank YOU for the meal!
    ! But yeah, thanx for spending the time to discuss this topic here on your
    blog.

    my website: Home Articles

    ReplyDelete
  14. excellent issues altogether, you simply received a emblem new reader.
    What would you suggest about your publish that you just made a
    few days in the past? Any sure?

    Also visit my weblog; Apple Decor

    ReplyDelete
  15. It's going to be end of mine day, however before finish I am reading this great piece of writing to increase my knowledge.

    Here is my homepage Outdoor Lounge Furniture

    ReplyDelete
  16. I blog frequently and I seriously thank you for your information.
    This great article has really peaked my interest. I will take a note of your website and keep checking for new information
    about once per week. I subscribed to your RSS feed as well.


    Here is my web page New Business

    ReplyDelete
  17. There is also a Catholic priest that fights by throwing dark daggers
    that bring to mind the concept of sacrificial blades.
    Take an friends on top of your head to head, as well go online, and
    also play other predators. While fighting a titan, if you knock off his first energy bar, you can ride the titan's back.

    The Playstation network is like Xbox Live, a marketplace
    online to purchase games,cheats,maps and many other items.
    Imagine all the money you could save using the
    generator. I used the Maximus option mentioned
    and its lightning fast, secure (Ive tried it and it works
    very well), and convenient. India keeps on nurturing an enormous pool of engineers with stupendous technical skills that believe in creative and ingenious thinking to bring revolutions within the technology sector.


    Feel free to surf to my web page: code psn gratuit

    ReplyDelete