Algorithm needed for solving building-blocks problem.

Question

Consider the following scenario:

1. We have a number of sequential building blocks (e.g. 12 building blocks, ordered from 1 to 12), distributed randomly (but not necessarily equally) on a number of builders (e.g. 3 builders).
2. The builders are required to work in order and start building the wall from block number 4, both ways; down to block number 1 or up to block 12.
3. Each builder doesn't have any knowledge about what block numbers the other builders may have, though he knows how many.
4. Builders must try to finish first by preventing others from making their moves. They should not pass and have to place a block, if they can. Any builder who finishes all his blocks first will be granted the highest reward, then the second, and so on...

Can we predict who will finish first, second and last? Is there any algorithm the builders should follow to get their work done first?

The following is a practical example of the problem:
Let us say:

builder 1 has: b2 b5 b8 b9
builder 2 has: b1 b11
builder 3 has: b3 b4 b6 b7 b10 b12

builder 1, and builder 2 will have to wait for builder 3 to place b4.
builder 3 will place b4, and gives his place back to builder 1.

wall: b4

builder 1 will have to put up b5, as there are no other options for him.

wall: b4 b5

builder 2 will follow, but he cant place his blocks, he will have to wait for b2 or b10.
builder 3 now have two options: b3 or b6, he must choose the one which help him finish first.

wall: b4 b5 b6

builder 1 has nothing to do, he'll pass his turn to builder 2.
builder 2 is still waiting for the installation of b2 or b10.
builder 3 will have to place b7.

wall: b4 b5 b6 b7

builder 1 now will place b8.

wall: b4 b5 b6 b7 b8

builder 2 is still waiting patiently...
builder 3 is forced to put down b3, as there are no other options, he was hoping that builder 2 may place b9... but his hope faded!

wall: b3 b4 b5 b6 b7 b8

builder 1 is totally in charge now, and feeling very happy! but he is confused! after thinking he decided that b2 may allow him to keep preventing a larger number of blocks, which in turn increases his chance.

wall: b2 b3 b4 b5 b6 b7 b8

builder 2 says: finally! some action! and places b1.

wall: b1 b2 b3 b4 b5 b6 b7 b8

builder 3 lost his hope on becoming first!
builder 1 now will install his final block and go home with the biggest reward!

wall: b1 b2 b3 b4 b5 b6 b7 b8 b9

builder 2 will wait...
builder 3 sadly places b10
builder 2 places b11 and goes home with the second reward...

Any known algorithm for solving such problems?

Answer 1

At first glance, a player's strength is a function of the range spanned by his highest and lowest blocks. In your example game, we can see that Builder 1 completely dominates Builder 2.

Builder 1:            2 ----------- 9   
Builder 2:          1 ----------------- 11
Builder 3:              3 --------------- 12

Start position:           ^^

Since the game starts on b4, the most important pieces are at the high end. For example, Builder 3 has b3, which prevents 2 other moves (b2 and b1); however, this isn't very decisive. Block b3, in its ability to prevent b2 and b1, is only as powerful as b5, which prevents b6 and b7.

The real power lies on the right side of the diagram above. This means that games with the initial starting ranges depicted above will usually finish like this: Builder 1, Builder 2, and then Builder 3.

As for player strategy, here's an admittedly speculative guideline: hold on to your most powerful pieces, meaning those that prevent the largest number of moves by other players. In this strategy, every piece you hold can be assigned a score based on the number of other moves it prevents.

For example, suppose the wall is at b3-b4-b5 and that you hold b2, b6, and b9. You can play either b2 or b6. How do you value your pieces?

b2 score = 1 (prevents b1)
b9 score = 3 (prevents b10, b11, b12)
b6 score = 2 (prevents b7, b8)

Note that b6 does not get credit for preventing b10 and higher, because b9 is doing that job (Matthieu M. also makes this point). In this scenario, you should prefer to play b2 first because it exposes you to the least risk of another player finishing.

Other answers have raised interesting ideas about not wanting to prevent your own progress, suggesting that you should play b6 first. But I don't think there is anything to be gained by accelerating the movement toward b9. You want to delay b9 as long as possible, because it's the piece that gives you the most insurance (from a probabilistic point of view) of preventing other players from finishing.

Update:

I wrote a Perl simulation to test a few simple player strategies. I'm starting to wonder whether player strategy is irrelevant. I tried the following: (a) pick the highest block; (b) pick the lowest block; and (c) my recommended strategy of picking the safest block (the one that prevents the most moves by others). I evaluated the strategies by awarding 3 points for 1st place, 2 for 2nd, and 1 for 3rd. None of these strategies performed consistently better (or worse) than random selection.

Certainly, one can concoct scenarios where a player's choice affects the outcome. For example, if the blocks are distributed like this, player 3 will get either 1st or 2nd place.

b1  b2  b3  b4  b5  b6  b7  b8  b9  b10  b11  b12
2   1   3   1   3   2   2   2   2   2    2    2

However, from a probabilistic point of view, this variation in outcome can be simplified to the following: player 3 will win unless he picks a the block adjacent to a player who has only one block remaining. In other words, the precise outcome is a coin toss.

So here's the question: Can anyone provide a scenario with an outcome that is neither foreordained nor a coin toss? I tried for about 15 minutes and then got bored.

Answer 2

@FM is right - the more pieces you block of your enemies, the better the move is. However, there is another part to the strategy that is not being considered there.

Consider if you have B3, B7, and B11. Suppose that B3 and B7 are currently both legal moves. (You are in a reasonably good position. Because you have neither B12 or B1, you cannot come third.)

Choosing B3 means that you are only opening up B1 and B2, so it is the best move under FM's strategy.

However, by not placing B7, you are delaying the eventual play of B10, which is necessary for you to win. B7 is probably a better move.

Answer 3

Since I don't have had the precisions yet, let's start with the (reasonable) assumption that if you can play then you have to. It's nice to prevent the game to be stuck.

Because of the rules, you have 0, 1 or 2 moves possible. You can only choose when you are in a 2 moves solution.

1. Decision Tree

Like many games, the easiest way to see what happens is to trace a tree of all possible moves and then explore this tree to make your decision. Since there is not much decision taking place, the tree should not be that big.

For example, consider that we are in the state:

wall = [3, ..., 8]
b1 = [2,9]
b2 = [1,11]
b3 = [10,12]

And it's b1 turns to play.

b1[2] -> b2[1] -> b3[] -> b1[9] (1st) -> b3[10] -> b2[11] (2nd) -> b3[12]
 or
b1[9] -> b2[] -> b3[10] -> b1[2] (1st) -> b2[1] -> b3[] -> b2[11] (2nd) -> b3[12]
                                           or
                                          b2[11] -> b3[12] (2nd) -> b2[1]

So basically we have 2 choices in the part of the tree.

1. b1 gets to choose between 2 and 9
2. b2 gets to choose between 1 and 11

We can summarize the consequences of a choice by listing the positions the players will get, obviously in an unbiased party each player choose in order to get the best position.

So, let's express a reduced version of the tree (where we only show the choices):

b1[2] -> [1,2,3]
b1[9] -> b2[1] -> [1,2,3]
b1[9] -> b2[11] -> [1,3,2]

Now we can apply a reduced view, based on a given player.

For b1, the tree looks like:

[2,9] -> [1,1] (both are equivalent)

For b2, it looks like:

[1,11] -> [2,3]

For b3, there is never a choice...

2. Possible outcomes

Of course, the players don't get this tree, since they don't know what the others have, but it gives you, as an observer, the possibility to study the various possible outcomes, at different stages of the party.

Note for example that on this subtree, we have 2 choices, the second being conditional on the first. If we have Pi(x in {x,y}) express the probability that player i choose x when facing a choice between x and y, then we can express the probabilities of each outcome.

P([1,2,3]) = P1(2 in {2,9}) + P1(9 in {2,9}) * P2(1 in {1,11})
P([1,3,2]) =                  P1(9 in {2,9}) * P2(11 in {1,11})

3. Players Strategy

From what we can see here, it appears that the best strategy is to try and block as many pieces as possible: ie when choosing between 1 and 11, you'd better play 1 because it does not block anyone while 11 blocks 1 piece. However this only works when you are down to 2 pieces.

We need something a bit more generic for the case when you actually have a list of pieces.

For example, if you hold {3, 9, 11} and the wall is [4, ..., 8] which should you pose ? Apparently 3 blocks less pieces than 9, but 9 blocks one of your own pieces!

Personally, I would go for 9 in this case, because I will need to place my 11 anyway and 11 blocks less pieces than 3 (with 3 I have a chance of terminating first, with 11 it's less likely...).

I think I can give a score to each piece in my hand, depending on the number of pieces they block:

3 -> 2
9 -> 1
11 -> 1

While is 9 attributed only 1 ? Because it only blocks 10 since I hold the 11 :)

Then I would play first the piece of the lowest score (if I have a choice).