Jenga

[LaserGuy]

Played this game with my son the other day and it got me thinking about strategy...

Jenga consists of a tower of rectangular blocks. Each level of the tower has three blocks in it, forming a square. The blocks on the next level up are rotated by 90 degrees, and so on. Suppose that the tower is 12 levels high, with 36 bricks total.

Version 1:
Two players take turns removing blocks from the tower until it falls over. The tower will fall over if the middle block + either of the side blocks are removed. So valid positions for any given layer are |||, |X|, X||, ||X, X|X. This will hold even on the very top layer.

Assuming both players play perfectly, is it possible for either player to devise a strategy that will guarantee a win?


Version 2:
When a piece is removed, it added to the top of the tower to either fill in the layer or create a new one. In adding to a new layer, players must add bricks in valid positions (ie. you have to put the middle block in first, then you can add the sides or add a new layer).

Assuming both players play perfectly, is it possible for either player to devise a strategy that will guarantee a win?


My solution to version 1:

Spoiler:

The first version seems fairly straightforward. You need to be the person to make the last legal move. Player 1 wins if there are an odd number of legal moves played, Player 2 wins if there are an even number of legal moves played. Since there are an even number of levels, it looks to me like Player 2 always wins this version, just by repeating whatever Player 1 does on a different level.

I think there ought to be a solution to version 2, but I haven't worked through the variations yet.

[Soupspoon]

For an "Ideal Jenga", the mathematical solution dominates (akin to the game of Nim) and unless the number of blocks (thus opportunities for removals and hence new layers) is specifically atuned towards making the optimal Player 1 first turn an unattainable 'null move', a 'perfect' play would seem to be in control of the first player and their actual choice of first move such that they then force Player 2 to make moves that Player 1 can always complement (e.g. always respond to a centre-removal with another centre-removal, an edge-removal with the countering edge-removal, or maybe contrariwise). I haven't modelled this is in full, and certainly haven't modelled Version 2 play where extracted blocks are, on every third occasion, forced to be placed so as to be part of an asymmetrical tower-cap over a possibly asymmetrical 'depleted tower' beneath.

But in a real game of Jenga, there's an added complication that (in all versions I've played, from tabletop to 'giant' version) the blocks seem to be deliberaely cut to loose tolerances. You know the feeling of when you want to remove a centre-block, or an edge block opposite an already removed edge, but due to slight differences in height, that block will not freely push or pull out of the stack.

When choices become scarce, you know that you've tried tapping several blocks subtly, at first, to test them. And then with cautious but increased percusiveness you persist with one or maybe a couple of the possibilities to try to do a 'tablecloth removing' manouever, aiming to whip the block out (usually in stages), hoping that the inertia of its vertically neighbouring blocks overcomes the friction between them enough not to cwuse catastrophe.

As such, the idealised strategy is likely to hit upon the stubborn central block, when central-blck removal is strategically called for, and ditto with edges, and you may wish to abandon the optimal removal rather than risk causing your own calamity, and hope that the opponent feels similarly constrained (or inadvertently accomodating) in not then choosing the idealised countermeasure to your weakness of choice and seizing (almost) certain victory from the jaws of inevitable defeat by you.


But I shall ponder the specifics of the Idealised Version 2 game. It sounds like an interesting problem. (Also for a number of players, albeit in strict rotation, other than two!)

[Soupspoon]

I have pondered, but not yet implemented beyond a form of 'statefulness', my analysis of Ideal Jenga. I'll put what I have down here before I put things aside for the night, and I know I won't have time to continue until late tomorrow at the earliest.

Forgive the likely non-standard notation, but hopefully it is self explanatory enough.

Define superstates S, A, B and C as having four explicit metrics across them all, and each representing a fifth metric implictlly.

S ('starting state') has 11 'Threes' (full 'floors', assuming a total of 36 blocks, excluding the top layer), zero 'Pairs' (floors with two adjacent blocks, one a centre, but one missing edge), zero 'Splits' (two edge blocks remain, separated by a missing central block), and zero 'Singles' (a solitary central block, both edges removed previously). Implicitly, S has 3 'Tops' (blocks on the top whole layer that cannot be legally removed in a turn). For setups of other than 36 blocks, adjust the Threes and the assumed Top number appropriately, naturally, and potentially the entry-point marked*, below.

It does not matter what order the Threes, Pairs, Splits and Singles are stacked, assuming theoretical maximum mathematical stability for our purposes.

For states with 3 Tops (S*|C) three changes may be possible:
If Threes>0, a centre block may be removed. Change Threes-1, Splits+1 (implicitly, Top=4, a full layer and a solo block) and state=>A
If Threes>0, an edge block may be removed. Change Threes-1, Pairs+1 (implicitly, Top=4) and =>A
If Pairs >0, a second-edge may be removed. Change Pairs-1, Singles+1 (Top=4) and =>A

A slightly repetitious version for the 4 Top state (A):
If Threes>0, a centre block may be removed. Change Threes-1, Splits+1 (Top=5, a full layer and a two more blocks) and state=>B
If Threes>0, an edge block may be removed. Change Threes-1, Pairs+1 (Top=5) and =>B
If Pairs >0, a second-edge may be removed. Change Pairs-1, Singles+1 (Top=5) and =>B

And repeat (with modifications! ) for the 5 Top state (B):
If Threes>0, a centre block may be removed. Change Threes-1 then re-add one so actually unchanged, Splits+1 (implicitly, Top=6-3, a new full layer, the previous one now replenished the Threes count) and state=>C
If Threes>0, an edge block may be removed. Change Threes-1+0=unchanged, Pairs+1 (implicitly, Top=6) and =>C
If Pairs >0, a second-edge may be removed. Change Threes+1, whilst Pairs-1, Singles+1 (Top=6) and =>C

The cycle S=>{A=>B=>C=>...} repeats until there are no valid moves (Threes=Pairs=0, Splits and Singles and Tops are all that remain), at which point a loss is forced. There is a finite 'net' of gameplay (always a loss of Threes, across each full cycle of three moves, whether that is one or two of them; Splits and Singles, meanwhile, irrevocably accumulate at the same combined rate(?)) and there may well be a single Nimesque strategy applicable in a game of N playes that one player can use every Nth turn to avoid loss or N-1 players must use to force the remainng playet to take the loss or possibly somewhere inbetween. For arbitrary or specific N, to be determined.

[SirGabriel]

My solution to version 1:

Spoiler:

The first version seems fairly straightforward. You need to be the person to make the last legal move. Player 1 wins if there are an odd number of legal moves played, Player 2 wins if there are an even number of legal moves played. Since there are an even number of levels, it looks to me like Player 2 always wins this version, just by repeating whatever Player 1 does on a different level.

Except that there has to be a rule against removing blocks from the top layer, otherwise the ideal game (and probably most actual games) wouldn't end until every single block had been removed from the tower. Which means that

Spoiler:

there are only 11 layers that can be touched. So Player 1 can guarantee victory by first removing the middle block from any layer other than the top (leaving 10 playable layers) and then following the strategy you gave.

[Qaanol]

In real-physics Jenga, there is an added constraint that the *center of mass* for *the entirety of the top n levels* must always be located above the remaining blocks in the next level down.

In particular, if the left-hand block has been removed somewhere, then there is a limit on how many right-hand blocks parallel to and above it can be removed while the left-hand blocks remain.

The specific effect of this constraint depends on the width and mass of the blocks, and how far out the side blocks are placed.

[Tirear]

Version 1:
Two players take turns removing blocks from the tower until it falls over. The tower will fall over if the middle block + either of the side blocks are removed. So valid positions for any given layer are |||, |X|, X||, ||X, X|X. This will hold even on the very top layer.

Assuming both players play perfectly, is it possible for either player to devise a strategy that will guarantee a win?

Spoiler:

Suppose there is only one untouched layer. The player can remove a side piece, which will leave the layer with a single move, or the player can remove the middle piece, which will leave the layer with no moves. Since there are no real choices left, this will determine who wins the game. In order to prevent your opponent from getting the last layer, you will want to avoid touching the second to last layer. If whoever touches the second to last layer loses, you are now effectively playing N-2 layer jenga. By induction, 12 layer jenga is equivalent to 0 layer jenga, and as such the first player will always lose twenty dollars and my self respect be defeated.

FAKEEDIT: modified for word filters

[SirGabriel]

Spoiler:

Suppose there is only one untouched layer. The player can remove a side piece, which will leave the layer with a single move, or the player can remove the middle piece, which will leave the layer with no moves. Since there are no real choices left, this will determine who wins the game. In order to prevent your opponent from getting the last layer, you will want to avoid touching the second to last layer. If whoever touches the second to last layer loses, you are now effectively playing N-2 layer jenga. By induction, 12 layer jenga is equivalent to 0 layer jenga, and as such the first player will always lose twenty dollars and my self respect be defeated.

Spoiler:

Again, you're ignoring the fact that it is illegal to remove any blocks from the top layer. 12 layers means 11 playable layers, which by your logic is equivalent to 1 playable layer, meaning the first player will always win.

[Soupspoon]

In particular, if the left-hand block has been removed somewhere, then there is a limit on how many right-hand blocks parallel to and above it can be removed while the left-hand blocks remain.

If two adjacent blocks are left, after removal of the opposite edge-block, that layer's CoG is at the ⅓ point, i.e. the edge of the middle block (with near enough idealised blocks and stack alignment). No matter how many lop-sided (alternating with perpendicularly stacked layers) pairs there are, their contribution to the stack CoG goes no further over than this

Take into account the intervening layers (however so depleted, all stretch the full width, their CoG being entirely central in the same axis) the consistently edge-depleted stack (doubly depleted, even, in both axes) is moved firmly onto the centre-third of any lower stack and even if that's oppositely edge-removed, it can safely suport the contrary layers above it.


The prime exception might be if in the 'remove and place on top' version of the game you don't start a fresh layer with the centre, but with an edge. One solitary top edge block has a CoG at the ¹/₆th point of its layer, which could be enough to move the CoG (of an arbitrary stack segment below) across the ⅓ point above a current/imminent missing edge.

I think. ICBW.

[Derek]

I was just thinking about this today (after watching professional Melee and Street Fighter players play Jenga, what a world we live in today). I searched google for "Jenga" and "nim" and of course this forum would show up on the first page.

Anyways, for version 1 of the ideal game (which is all that I'm concerned with), it can easily be seen to be equivalent to a game of Nim where every pile starts with 2 stones. For a Jenga tower with N levels, the Nim game has N-1 piles. If you remove the middle block from a Jenga row, you remove two stones from the corresponding Nim pile. If you remove a side block from a Jenga row, you remove 1 stone from the corresponding Nim pile. An empty Nim pile corresponds to a Jenga row from which no more blocks can be removed. From this analysis we can easily see that a Jenga tower with an odd number of levels, the second player wins by mirroring the first player's moves (note that this means if he removes a first side block, the first player should remove a first side block, likewise for removing a second side block). For a Jenga tower with an even number of levels, the first player wins by removing the middle block from any level, the playing as above.

For version 2, the Nim game is modified by adding a new pile of 2 stones after every third move. I'm still thinking about this version, it's much harder, but I think it should be possible to inductively solve it, but the induction step might be 6 moves long, which is a pain to analyze.

[skeptical scientist]

Take into account the intervening layers (however so depleted, all stretch the full width, their CoG being entirely central in the same axis) the consistently edge-depleted stack (doubly depleted, even, in both axes) is moved firmly onto the centre-third of any lower stack and even if that's oppositely edge-removed, it can safely suport the contrary layers above it.

Agreed

The prime exception might be if in the 'remove and place on top' version of the game you don't start a fresh layer with the centre, but with an edge. One solitary top edge block has a CoG at the ¹/₆th point of its layer, which could be enough to move the CoG (of an arbitrary stack segment below) across the ⅓ point above a current/imminent missing edge.

Yes. But this consideration only prevents the remove-left-block move from a level when the level is full, in which case you can substitute the mathematically equivalent remove-right-block move. So I don't think center-of-gravity considerations affect the outcome of the game.

However, none of you seem to be considering moves like this, which totally alters the mathematics.

[heuristically_alone]

The looks on their faces brought me so much joy.

Has anyone played Dread? It is a RPG where you use jenga instead of rolling dice.

[lordofthesnails]

This version 2 puzzle is wonderful. I've always been curious about this and I've never been able to get my head round it, so I stuck it into Excel. I can now see who wins for each state of the Jenga tower and the correct move in each case, but I can't see the pattern

Certainly something mathsy(???) is being balanced out as we go, I'd love someone to post exactly what it is.

There are some complications over what we're calling the "top" layer, but:
If you are allowed to take from any complete layer only (including the top, if it's complete), then this follows my nim-with-a-new-row-added-every-3-turns model. In that case...

Spoiler:

Number of complete rows to start - winner (player 1 [moves first] or 2 [moves second])
01-1
02-2
03-1
04-1
05-2
06-1
07-1
08-2
09-1
10-1
11-2
12-1
13-1
14-2

I'd take a middle piece first

If we can't take anything from the top row, regardless of whether it has 1,2 or 3 blocks on it, I think it's:

Spoiler:

Number of total rows - winner (player 1 [moves first] or 2 [moves second])
01-2 (you instantly lose)
02-1
03-1
04-2
05-1
06-1
07-2
08-1
09-1
10-2
11-1
12-1
13-2
14-1

Again, I'd take a middle piece first

If no strategies are forthcoming, I'll play some games against my spreadsheet and see if I can come up with one, but it feels a bit backwards when we have all the pieces of the puzzle.

[Derek]

The rules of Jenga are that there must be a complete row above the one you are taking from. This means that at the start of the game you can draw from any row except the top, and that row does not become accessible until the after the third move.

I believe this amounts to an off-by-one error in your analysis.

[lordofthesnails]

Thanks Derek, indeed it's just 1 less row from my first example, so

Spoiler:

going second wins

So here's the situation, can anyone see what's going on?

Spoiler:

I've taken out a lot of the duplicates, "pairs mod 3" was nice to take out a lot of lines. I've sort of grouped "takeable threes" mod 3 together with colours where they match, but couldn't simplify the table thanks to that pesky zero row. I'm still not 100% convinced I haven't made a mistake, but I can't fault anything by spot checking.

I've circled our jenga case, 11 threes with zero outstanding pairs, and 3 untouchable (aka 0) on top
With the first 4 blocks of colours and some understanding of how different moves jump you around this table, you could beat anyone by trying to place them on a '2' after your turn. This will always be possible if you're on a '1'.

...there must be an easier rule to link that all together.

[Shufflepants]

For anyone considering physical versions of the game with perfect play, for a level that is supported by a single block in the middle, it is possible to knock that block out of the way and have the top part fall onto the bottom part without toppling over leading to the possibility of an infinite game.

[Sableagle]

OP misses out the rules that the blocks must be removed from below a complete layer and that the topmost layer must be completed before another layer can be added above it, so you can't just turn the top three from side-by-side to a vertical stack.

In practice, due to blocks being 3.00x1 but not quite 3.00000000000000 x 1 and do players not setting them exactly "in position" on top, the tower can develop quite a lean and yes, it is possible to have XX| as a layer with a big tower balancing on it.

The people who used to do trips with the Guide Dogs' Adventure Group took various games with them for the down-time between end-of-hike and dinner or between dinner and bed or while in harbour or whatever, and as well as braille cards they got a Jenga set.

Then they got another Jenga set.

They hadn't lost any of the bricks from the first set. They'd just run out of legal moves (excluding that snatch move, which would be harder to do on a stack of singles anyway) too many times. They doubled the height of the tower just to make it interesting.