Does a winning strategy exist for Don't Break the Ice?

Question

Don't Break the Ice is a children's game, where players take turns using mallets to knock pieces of ice away from the playing field. The playfield is composed of a (6 x 6) grid of single square blocks, except for the 2x2 block that the skating bear is on.

The object of the game is to not break the ice and have the bear fall.

Is there an winning strategy? If so, for which player? Assumptions:

• Each player only knocks out one block of their choice.
• Blocks are 'sticky' and will cling to each other along any edge, and so:
• The game ends when the center 2x2 square has been disconnected from the exterior of the 6x6 square; that is, when there is no orthogonal (connected along the edges) path from any cell outside the 6x6 square to a cell in the interior of the central 2x2.

Answer 1

If I understand the game correctly, there should be a winning strategy for the player going last. If we first disregard the corners, then the bear will fall when the second last block is removed:

--X---
--X---
--BB--
--BB--
------
------

(or similar) Since the number of blocks is even, this block will be removed by the player going first. Now, there are two complication. First, the last block removed may include the corner:

-X----
-X----
-XBB--
--BB--
------
------

or

-X----
-XX---
--BB--
--BB--
------
------

Since the number of remaining blocks is now odd, the player going last would lose. Second, a block may fall due to being disconnected. As Steven notes, only four blocks can possibly fall this way. If an odd number of blocks fall, then the player going last will be the one to make the last move in the first setting.

However, both of these can easily be avoided by attacking the corner blocks first. Since it requires two moves to remove a corner block, the second player can always remove the corner block before the first can make it fall, and of course before all side blocks are removed. This ensures that the final position will be of the first kind, and thus that the player going first loses.

Answer 2

A few notes:

• There's very little point in bothering to remove blocks under the conditions specified for the simplified version; the only cells that can ever be removed by becoming isolated are the four cells diagonally (but not horizontally) adjacent to the central block. All the cells on outer 6x6 ring are, of course, always connected, and all of the rest but those four cells are connected to the inner 2x2 block.
• The four cells on the outer corners of the board can be ignored for connectivity purposes; there's no path through them that doesn't also touch another edge of the board. Thus, they effectively serve as 'pass' moves, a move that can be taken without affecting the board in any meaningful way. What's more, since the game is symmetric, if it's to one player's strategic advantage to pass then it's to the other player's as well; thus, a pass should always be followed by another pass. Since the passes come in pairs (4 total) then they have no meaningful effect on the gameplay either and can be ignored in computing the game's outcome; you might as well leave those cells empty from the beginning.
• These simplifications (along with a lot of transposition tables) put the game into eminently-analyzeable range. Since the 4 central cells can't be knocked out and the 4 outer-corner cells don't matter, there are effectively 28 cells whose state can meaningfully change; this means that the game has 2²⁸ positions in total. That's just 256M positions, and since you can store a position's value in a single bit, then you could actually hold the complete 'truth table' (this position is a winning or losing position) in just 32 megabytes. If you want to be fancy, you could even add an additional bit indicating whether the position is 'already lost' (i.e., whether it's connected or disconnected), doubling your storage but making things a bit easier.
• What's more, building that truth table is straightforward; the position with 0 bits on is impossible, so its value doesn't matter. All positions with one bit on are lost for whomever has just moved to them. From those you can compute the value of all positions with two bits on (or even more simply, just fill in the ones that aren't lost: the eight positions with one 'interior' cell and one adjacent 'exterior' cell on). From those, you can compute the value of all three-bit positions; etc. This wouldn't take more than a day to write and probably less than 5 or 10 minutes to run on any decently-powered modern machine, assuming the algorithms were done well.

If there are sufficient amounts of interest, I can try and put something together to find the final value, but it'll take me a day or two; it's also eminently possible that it could be solved with a quick case analysis, since 90% of the connectivity feels like a 'red herring' and (aside from the 'interior corner' cells) the problem is almost entirely a matter of knocking out either an interior cell or both the adjacent exterior and adjacent interior-corner cells. It ought to be analyzable as the sum of four 'mini-games', one for each of the four corners of the board (but be careful - in the standard parlance the game is misere and not normal, so normal nim-sums can't be applied to it).

Answer 3

In theory, an optimal strategy, in the sense of a Nash equilibrium, certainly must exist. However, based on the description of the game on Wikipedia, I see some difficulties in finding such a strategy in practice.

First, it appears the the game is non-deterministic, so the optimal strategy can only be optimal in a statistical sense — it cannot guarantee victory for any player. Second, the outcomes of different moves appear to depend on the physical properties of the blocks, which means that calculating the optimal strategy would first require developing an accurate model of the game physics, and then fitting the model to actual measurements.

(That's not completely impossible — for example, it has been done for Pass the Pigs, but that's a simpler example, since the pigs in Pass the Pigs don't really interact with each other much. In that respect, Don't Break the Ice seems closer to, say, Jenga.)

Finally, I'm not sure how consistent the physical properties of the game pieces are, or how likely they are to change over time due to age or wear. If the behavior of the pieces varies too much, a strategy calculated for one particular game set may not be optimal for another one.

All that said, however, it might still be possible to come up with a deterministic (or at least consistently non-deterministic) approximation of the game, and then analyse that approximation. I'm not familiar enough with the game in question to suggest what such an approximation might look like, though, except for some very crude features (e.g. that completely disconnecting the center from the edges of the playing field should surely be a losing move).

Answer 4

Given physics, it would seem like blocks wouldn't be sticky - but you can still predict when they will fall. Blocks will stay if they are in between (with a line of unbroken blocks) two blocks that are already confirmed to stay up (counting the edge)

For example, take this board.

----
--x-
---x
----

The two other "corner" blocks by the Xs would also fall, since they are not supported.

----
--xx
--xx
----

The rest of the blocks would stay, though. The rest of the board would stay up because of compression with the board edges.

----
--xx
--xx
x---

This block has been broken, now. However, nothing else will fall. I am going to mark stable blocks with an "s". These blocks are stable because they are held together by edges:

ssss
-sxx
-sxx
xs--

The rest of the blocks are also going to stay because they are held between edges and other stable blocks.

However, there is still a pretty simple winning strategy. Always break the ice block 180 degrees from what the first player played. The board will always remain symmetrical, and eventually you will get to some scenario like this.

xx-xxx
xx-xxx
xxBBxx
xxBBxx
xxx-xx
xxx-xx

Your opponent will be forced to break one of these chains, thus making the center fall.

You can never lose when doing this because of the symmetry. The central tile will only fall if it is not supported neither vertically nor horizontally. If you are breaking one of the tiles holding the center up (here shown as S tiles)

--SS--
--SS--
SSBBSS
SSBBSS
--SS--
--SS--

you would always break a side on the same axis that your opponent broke. You won't break stability in any axis because your opponent will first.

xxxSxx
xxxSxx
--BB--
--BB--
xxSxxx
xxSxxx

If your opponent breaks any of the S tiles, there will be no helpful force vertically.

xxxxxx
xxxxxx
--BB--
--BB--
xx-xxx
xx-xxx

The bottom two tiles are not providing any stability for the center because this stability only comes from compression, and the other side of that compression is broken. This means that when you remove the bottom two, you are not making the center less stable.

Knowing this strategy, however, doesn't mean you'll always win. You have to always be able to knock off only the block/blocks you want (which is skill, not strategy). I also haven't figured out what to do if you are going first and your opponent makes a mistake.