How to enumerate targets for the Tower of London test?

Factual Questions
1

Disclaimer: As far as I can tell, the original version of the Tower of London cognitive test is in the public domain, so I’m hoping that I am not violating any copyrights here.

The Tower of London cognitive test uses a horizontal board with three vertical posts and 3 colored balls (red, green and blue in the original version) drilled to slide onto the posts. The posts from left to right can hold 3, 2 and 1 balls respectively. This is similar to the classic Tower of Hanoi puzzle, but the varying post heights changes the game. The original version has one example and 12 problems. In each case, the starting position of the balls is the same, the goal is to rearrange them with the minimum number of legal moves to match the given target arrangement. The rules are that you can only move the top ball from a post, and only place it on a different post with free space, and each such rearrangement counts as one move.

For the original version the start arrangement is:

X
R X
G B X

where X indicates a free space, and R, G and B are the three colored balls. The trial example, shown below, requires a minimum of 2 moves; first move the red ball to post 3, then the blue ball to post 1.

X
B X
G X R

I have been asked to create a web version of the test, and so I want to find a way to enumerate all of the possible minimum move targets (final arrangements) possible given the constraints described above, and this finally leads to my question.

What I plan to do is to create code to take any initial state and step through all of the possible new states that one legal move can produce. If any such resulting state has already occurred after any lower number of moves, then this state can be eliminated at the current move number because it is possible to reach it with fewer moves, and so fails the minimum number of moves criteria. For each of these 1 move states, I repeat the process and generate the set of 2 move states, and so on. The original version of the test only went up to 5 move targets, although later versions of the test have used higher move numbers.

Will this approach work as I think it should? I have done this by hand for the original version starting arrangement for up to 5 moves, and it appears to be working, but I would like to create code to take any start arrangement and any (reasonable) number of moves.

2

It seems to me there are a finite number of arrangements and so there are a finite number of moves to get there.

Is there any arrangement where it is impossible to get to from the starting position? I don’t think so, just quickly looking at it.

It’s a bit more complex than a standard combinatorial problem, but should be easy to solve.
First enumerate all collections of G,B,R,X,X,X.
Eliminate ones where X is lower than R,G,B on any pole.
Divide the resulting set by 3! ( =6) because all arrangements of the 3 X’s are the same.
Start:
R
G B X

for - - R in third column the only final arrangements are (LEAVING OFF BLANK LINES)
G X
B X R =easy: R to 2, G to 3, B to 1 gives BR-X-G; then G to 2, B to 2, R to 3 now X-BG-R so B to 2, G to 2 done.
A quick guess -I hope I’m still with it cognitively.

B X
G X R

B G R

G B R

X G
X B R

X B
X G R
Do the same for each of the other choices for column 3 - G,B,X.
There are 6 final combinations each where 3 is G or B same as above. Just rotate R, G, B values.
So 18 of these.
For 3 = X, first the pole 2 empty XX
R R B B G G
G B G R B R
B G R G R B

For 3=X and 1 on pole 2 - (hope this formats right) First is zero moves.

R R G G B B
GB BG BR RB RG RG
and, the formatting doesn’t work right…

For 2 on pole 2, 1 on pole one, just reverse the above configs.
R R G G B B
GB BG BR RB RG RG

So your approach will work, and when you have results for these 36 possible combinations, you have the full solution set.

it’s simply a top down (recursive?) tree of moves, and compare against the list above; when the tree reaches an arrangement that has already not been enumerated with less moves, that tree branch notes the new winning path. if the branch reaches a duplicate of what it has already found in this recursive path, that branch stops moving and goes up a to the next branch point.

3

I went ahead with my instincts and coded up the algorithm. There are 36 possible arrangements, the output of my code, run with the one starting arrangement as specified in the original version of the tests, does produce all of the remaining 35 arrangements as minimum move targets. An interesting result, which I should have predicted, is that there must be an upper limit to the number of moves, in the case of the trial I ran there are no 9 move minimum move targets, because by the time you reach 8 moves, you have ticked off all 36 arrangements.

Here are the results. I used string representations of the arrangements as follows:

XRG:XB:X is the initial state, with the red ball on top of the green ball on post 1, the blue ball on post 2 and post 3 empty. In the table bleow, at each move number, the resulting minimum move targets are listed in CSV form.

Moves Cases Targets
0 1 XRG:XB:X
1 4 XXG:RB:X,XXG:XB:R,BRG:XX:X,XRG:XX:B
2 4 XXX:RB:G,XXX:GB:R,XBG:XX:R,XXG:XR:B
3 6 XXR:XB:G,XXR:GB:X,RBG:XX:X,XBG:XR:X,XXX:GR:B,XXG:BR:X
4 4 XBR:XX:G,XGR:XB:X,XXB:GR:X,XXX:BR:G
5 6 GBR:XX:X,XBR:XG:X,BGR:XX:X,XGR:XX:B,XGB:XR:X,XXB:XR:G
6 5 XXR:BG:X,XXR:XG:B,RGB:XX:X,XGB:XX:R,XRB:XX:G
7 5 XXX:BG:R,XXX:RG:B,XXB:XG:R,GRB:XX:X,XRB:XG:X
8 1 XXB:RG:X
9 0

I haven’t tried any other starting arrangements, and I did not save the paths, or sequence of steps, taken by the algorithm, but this result suggests that similar results will be found for any of the 35 other possible starting states. What I did find is that there are some targets that have more than one possible set of minimum moves, although obviously the same number of moves. I’m going to add path tracking to the algorithm so that I can capture these many roads cases.

4

Me again. While I have answered my original question in that my brute force approach works, I’m still wondering if there isn’t a more elegant solution. When I was thinking about how I would modify the code to add tracking of the path(s) from start to target, it occurred to me that the Tower of London test can be represented a a graph, each of the 36 arrangements are the nodes and the vertices are then given by the possible results from each arrangement by making one move. However I don’t know enough about graph theory to know what I’d have to do next, once I had built the graph.

It seems to me that this would then become a variation on the traveling salesman problem in that the sets of minimum move targets reachable in N moves from any given start node are those that require traversing N distinct nodes with the restriction that no node can exist as an intermediate step in any path found for fewer than N nodes.

I’m hoping that someone out there with a better understanding of graph theory than me can provide some guidance…

5

It would seem to me that if you solve for the 36 optimal solutions for the 36 final results (well technically 35 if you don’t count the start), then basically keep a list of the sequences for each final target. As soon as subject departs from the optimal sequence, they are not correct. Count how many extra moves they make to get the correct answer, and that is their fail score.

I suppose the key to this is to ask whether there are final configurations with more than one shortest solution sequence - multiple paths? Then you allow for either path.

The trick with following the subject being tested is that you already know the final result he’s assigned, so you know what path(s) he must follow.

6

I should have provided more details on the TOL test. The journal article I’m using is R. Kirkorian, 1995, (PDF) wherein is described the original administration and scoring of the Tower of London test as devised by Shallice and McCarthy in 1988. The 12 (start arrangement, target arrangement) pairs are called problems, and the test subject is allowed up to three trials for each problem. In this original version, the test administrator records the moves made, and stops the trial if the set minimum number of moves is made without producing the target arrangement. Success on trial 1 is awarded 3 points, success on trial 2 is awarded 2 points, success on trial 3 is awarded 1 point, and failing all 3 trials is awarded 0 points. There is also a 60 second time limit for each trial, and making two illegal moves halts any trial. According to the description in the paper, an illegal move is one where the test participant tries to place a ball on an already full post. For my implementation I think that I will also count trying to put a ball back on the post it came from as illegal.

All of this is clear enough, and the Krikorian paper gives the 12 problem target arrangements and one 2 move practice example. As you can see, I don’t need to know if the test subject is following a valid solution path, only if after the specified minimum number of moves have they produced the target arrangement. It is more general curiosity on my part that lead to wondering what the total possible numbers of initial states and associated minimum move targets are for the test. From my fairly cursory searches on the TOL so far, there have been several variants created and used for research since Shallice and McCarthy’s original was published in 1988. One of my collaborators on this project is a research neuroscientist, it’s up to them to decide which version we are going to implement.

7
8

@DPRK, many thanks, I’ll check this out. Bonus points if you are a fan of The Witcher books/video game.

9

Following the link provided by @DPRK, I see that I have managed to re-invent a variation of his algorithm for finding the shortest-path tree for the problem posed by the Tower of London test.

I created a graph where the nodes are the 36 possible arrangements of the 3 balls on the 3 posts, and for each node found the associated edges (links to other nodes) for one move. This forms an undirected graph, since if a move can take you from node i to node j, then there is always a corresponding move that will take you from node j back to node i. The distance between every connected pair of nodes is 1 move. As an aside, each node can have from 2 to 4 edges.

Once I had the graph, finding the shortest path from any starting node to all of the other nodes was trivially easy, and my procedure also had the advantage of grouping the nodes by the number of moves (edges) required. I found that there are no 9 move results, because for every node, all of the shortest paths to the 35 remaining nodes have been found after 8 moves.

Here is a brief description of the procedure.

Create a graph with a node for the 36 possible arrangements and find each nodes edges.

Create an initially empty list to collect the nodes found at each move number.

For the starting node n, mark this node as visited, and optionally add it to the list as move 0.

Use the edges for node n to find the 1 move nodes, mark these as visited and add them to the list as 1 move nodes.

For each node found in the previous step, test their edges to see if they lead to nodes not yet visited, and if yes, mark them as visited and add these nodes to the list as 2 move nodes.

Increment the move number by 1 and then repeat the last step until no unvisited nodes are found.

Optionally, record the paths traversed for each of the shortest paths found.

Profit!

10

Also, can you simplify the graph by removing the difference between colours?

After all, there are essentially 3 identical graphs with colours rotated. XAD-XC-X as start is the same whether you use:
A=R,D=G,C=B or A= B,D=R,C=G etc.
You can take any arbitrary XOO-XO-X and substitute the colours you have to have at that instance.

Or is the start always the arrangement you mention in the first post?

11

@md-2000, I did consider this. When counting the number of possible arrangements, I grouped them into 4 cases as follows.

Case 1 is where all 3 balls are on post 1, but because the order of the colors matters, there are 3! such arrangements.

Case 2 is where there is one ball per post, so again there are 3! such arrangements.

Case 3 is where there are 2 balls on post 1 and the remaining ball is on either post 2 or 3, and the very similar Case 4 is where 2 balls are on post 2 and the remaining ball is on either post 1 or 3. Here, there are 3 x 2 ways of choosing the 2 balls on post 1 (or 2) and for each, two possible locations for the remaining ball, so for each of these cases we have 2 x 3! possible arrangements.

Thus there are 6 x 3! = 36 possible arrangements, because the order of the colors does matter, so for example XRG:XB:X is different from X:GR:XB:X.

I could have followed your suggestion, and done 1 shortest path search for each case, using indices like 1,2 and 3 instead of the colors, and then done a a series of 3! mappings like 1 - R, 2 = G, 3 = B, 1 = G, 2 = R, 3 = B and so on, to generate the complete list, but I’m not sure that this would have been faster because the algorithm I created is pretty efficient.

I had also thought about using the fact that, once I’d found the shortest path between say node i and node j, then the there is a path of the same length from node j to node i consisting of the opposite moves, and while this may not be the only such path of that length, it will be of the shortest possible length. This means that I could build a list of start - end nodes for each number of moves and use it to populate the list my algorithm builds, but it seems to me that the overhead in building such a list, and then checking it, actually adds steps to the algorithm and so would not save any time.

As for your final question, is the start arrangement always XRG:XB:X? In the original Shallice and McCarthy version of the Tower of London test, the answer is yes. However, as I’ve been investigating this I have read a few journal papers that address what TOL measures, and discussions of how to vary the test to make it a more sensitive diagnostic probe of different aspects of problem solving abilities. As I mentioned in a previous post, it will be up to someone else in the team to decide which version we will be implementing, but by happy chance, my curiosity about how to find these shortest paths will be directly applicable to the project, because amongst the parameters that appear to influence the sensitivity of these test variations are both the path lengths and the kind of moves required, and I’ve now got a complete listing for the Tower of London problem space, in a nice graph format.

12

There are always 3! equivalent cases. Suppose that you initially reported your results, with diagrams, in a black and white publication, and so instead of colors, marked the balls A, B, and C. Then a color publication republished your result, and asked which color each of those letters should be.

13

@Chronos, yes. There are 7 distinct cases so I could have limited myself to finding the shortest path trees for these 7 cases and then applied the 3! color mappings to the results. My algorithm requires on the order of N x (N-1) x E operations, where is N the number of nodes and E is the average number of edges per node (about 4.5 for the TOL graph). For N = 36 this gives about 5670 operations, for N = 7 it is only 189 operations. Had I thought of this before having carried out the process for all 36 nodes, I probably would have. Assuming that the color mappings require on the order of 3! * 7, we are still way ahead. When I said in my last post that I wasn’t sure @md-2000’s suggestion would save time, I hadn’t carried out this analysis. Clearly I was wrong. In my defense, by the time I saw that post, I’d already found the shortest tree paths for all 36 nodes and was too lazy to re-write the code.

14

Actually, on reflection, this is wrong. If I restrict the problem space to the 6 (sorry, my mistake typing 7 earlier) general ball arrangement cases, as compared to the 36 possibilities resulting from the 3 colors, the shortest path maps for the 6 node case cannot be simply scaled up to the 36 node case, for the obvious reason that there are 6 times as many nodes and roughly 6 times as many edges.

15

Given any starting state and any target state, you can map the problem exactly to the starting state where the balls are red, green, blue, in that order, and the ending state is the same permutation of the given ending state.

16

In terms of generating the possible states (nodes) you are correct, and this is how I created the representation of the Tower of London test as a graph. However, this will not work in mapping the shortest path trees between nodes in the graph unless you start with a graph with all 36 nodes. For the 6 node case the maximum length shortest path is 3 moves, while for the 36 node case it is 8. Adding nodes to a graph creates new paths and path lengths that simple permutations of the node colors does not.

I suspect that even if you could specify a process of expanding the nodes and paths from the 6 node case, the effort required would exceed that for starting with all 36 nodes, and I would insist on using the 36 node shortest path trees to validate the results.

17

Don’t know if it’s “polite” to quote myself, but I feel the need to clarify this a bit. @Chronos is absolutely correct (as was @md-2000 in an earlier post) that an efficient way to generate the 36 nodes, and their edges, is to start with the 6 states that arise from indistinguishable balls and then cycle through the 3! permutations for each to create the 36 3-colour nodes and their edges. But one cannot then create the shortest path trees for the indistinguishable balls case and then cycle through permutations to generate the shortest path trees for the 3-colour ball case.

Consider the 3 I.B (indistinguishable ball) starting case where 0 is no ball and 1 is ball

0
0 1
0 1 1

One of the two possible moves is to take the top ball on post 2 and move it to post 1

0
0 0
1 1 1

Now consider a 3-colour case where 1, 2 and 3 denote the colours.

0
0 1
0 2 3

The same move as before gives us

0
0 0
1 2 3

Now permute the colours by swapping 1 and 2

0
0 2
0 1 3

It now requires 6 moves to reach the 1 - 2 - 3 arrangement that only required 1 move before.

And if we make another permutation so we start with

0
0 2
0 3 1

It now requires 4 moves to reach the 1 - 2 - 3 arrangement

This is what I was trying to describe when I said that a permutation of the colours of the balls will not allow you to expand from the shortest path trees for the 6 node I.B. case to the shortest path trees for the 36 node 3-colours case.

18

I was never talking about indistinguishable balls.

Right, let’s call this “test 1”.

And call this “test 2”.
But you permuted only the starting state, not the final state. The six moves it takes in test 2 is the same six moves it would take to get from the test 1 starting spot to the state
0
0 0
2 1 3
.

19

@Chronos, I agree 100% with this. I think my problem here is that I have been assuming that you were suggesting that it is somehow possible to create the shortest tree paths for the 36 node graph representing the Tower of London by first generating the shortest tree path for a subset of the nodes, and then using a permutation operation on this subset shortest tree path to generate the shortest tree path for the complete set of nodes.

20

Right, you need to find the paths from 6 starting positions, to all 36 ending positions (or equivalently, from 36 starts to 6 ends), and permute it from there. Just going from 6 positions to 6 positions isn’t enough. That’s still a sixfold reduction of the total problem size, though, which is nothing to sneeze at (if I were doing it by hand, I’d much prefer to work out 216 cases, than 1296 ones).