solitaire
and maths

2011–11–06

I’ve always loved solitaire, so when I could combine that love with maths and computing—well you know where I’m going with this…

By the way if you are using IE you may need to hit F5 to see the diagrams.

in the beginning…

I was originally going to call this article, “solitaire and group theory”, and perhaps I should have stuck with that; but the obsession grew and things got out of hand. Situation normal for me.

First off, let me state that I haven’t come up with a single original insight into solitaire—cleverer people than I have studied it—I wasn’t expecting to discover something that they’d missed. So what you have here is a synthesis of various things that I’ve come upon elsewhere and a series of gaming tips from someone who is [all too] familiar with the game.

This is also a part one—I’m still beavering away at it and, who knows? I may come up with something. However for now let’s set the scene…

I wrote the above about a year ago, although I never posted it. I’m still hacking away at the problem, no closer to a solution but with some better tools and some new ideas.

some housekeeping

Let’s do some housekeeping, so that we may discuss my faults using the same language. [I’m assuming that you are familiar with group theory and the proof that I was ‘unhappy’ with.]

There are many kinds of solitaire boards, we will get to them, for now will will concentrate on the English in standard position. Here is the solution [well one of them.]

Solution
 0123456
0•••
1•••
2•••••••
3••• •••
4•••••••
5•••
6•••
  1. [1,3]→[3,3]
  2. [2,5]→[2,3]
  3. [0,4]→[2,4]
  4. [0,2]→[0,4]
  5. [3,4]→[1,4]
  6. [0,4]→[2,4]
  7. [5,4]→[3,4]
  8. [4,6]→[4,4]
  9. [2,6]→[4,6]
  10. [4,3]→[4,5]
  11. [4,6]→[4,4]
  12. [4,1]→[4,3]
  13. [6,2]→[4,2]
  14. [6,4]→[6,2]
  15. [3,2]→[5,2]
  16. [6,2]→[4,2]
  17. [1,2]→[3,2]
  18. [2,0]→[2,2]
  19. [4,0]→[2,0]
  20. [2,3]→[2,1]
  21. [2,0]→[2,2]
  22. [4,3]→[2,3]
  23. [2,3]→[2,1]
  24. [2,1]→[4,1]
  25. [4,1]→[4,3]
  26. [5,3]→[3,3]
  27. [3,4]→[1,4]
  28. [3,2]→[3,4]
  29. [4,4]→[2,4]
  30. [1,4]→[3,4]
  31. [3,5]→[3,3]

The trick, if it can be said to be so, is block-removal; play through this position. [Although this is a slightly unusual block-removal; it involves a horizontal move across row 1.]

Block-removal
 0123456
0•••
1•••
2
3•
4•
5
6
  1. [0,2]→[2,2]
  2. [0,4]→[0,2]
  3. [3,2]→[1,2]
  4. [0,2]→[2,2]
  5. [1,4]→[1,2]
  6. [1,2]→[3,2]
  7. [4,2]→[2,2]

clump & non-clump

Once you’ve mastered block-removal it’s pretty easy to solve the basic game. What you need to do is to play for a clump. This is my personal term, an example of which is given below [playing for a [4,2] finish]:

Clump
 0123456
0
1•••
2•••••
3•• ••
4•••••
5•••
6•
  1. [4,3]→[4,0]
  2. [4,0]→[4,2]
  3. [6,3]→[4,3]
  4. [4,4]→[4,6]
  5. [2,4]→[4,4]
  6. [5,4]→[3,4]
  7. [2,5]→[4,5]
  8. [4,6]→[4,4]
  9. [2,2]→[0,2]
  10. [1,4]→[1,2]
  11. [0,2]→[2,2]
  12. [3,1]→[3,3]
  13. [3,3]→[1,3]
  14. [2,1]→[2,3]
  15. [5,2]→[3,2]
  16. [1,3]→[3,3]
  17. [4,3]→[2,3]
  18. [4,4]→[2,4]
  19. [2,4]→[2,2]
  20. [2,2]→[4,2]

This position has an interesting property which we will deal with when we come to Groups and Solitaire.

The above is a slight cheat on my part: a cheat because I didn’t know which single-peg I was going to end up with; slight because I chose the clump [almost] at random and I was fairly sure that I could play it to a single-peg solution. I knew, intuitively, that there was such a solution. I could also play quite a few moves without worrying too much about the consequences because the clump retained the right shape.

Let’s look at another position, an example of a non-clump:

Non-clump
 0123456
0
1•
2••••
3•
4•
5••
6
  1. [2,0]→[2,2]
  2. [2,6]→[4,6]
  3. [4,6]→[4,4]
  4. [5,2]→[5,4]
  5. [5,4]→[3,4]
  6. [3,4]→[1,4]
  7. [1,4]→[1,2]
  8. [1,2]→[3,2]

To me it wasn’t obvious that the start position could be played to a single-peg finish, and changing it, even slightly, means that it can’t be solved. But it does have less wiggle-room—there aren’t a great many moves that you can make. It would be easier for a computer to search for the solution than it would be for the clump.

In the clump position I relied upon having a good shape only for so long, at a certain point I needed to analyse the position to see that I could reach a out-shape where I knew that I could get to a single-peg finish.

This is the tip-point—the moment when you need to change from making moves on principal and start having to do a concrete analysis. In practice a certain amount of thinking ahead is always needed, but often it’s only of the order of two or three moves.

Such behaviour is hard to programme.

solitaire & computers

Since M255, where I programmed a player using BlueJ, I’ve worked off-and-on on various incarnations of the beast. For the last month I’ve been building yet another. Over time I’ve got…I was going to say better but that isn’t right—I’ve aquired more knowledge about the problem domains. For there is more than one domain.

Developing a programme to play any non-trivial game is non-trivial. There are a few ways that we might tackle the problem, I intend to try quite a few. The above suggests one approach—if I could mathematically define clumpiness and spot the tip-point…

For now I’m going to go off and do a bit more work on ‘the beast’.

Next time I’ll look at Group Theory and solitaire which is of some interest.