Block'd (Part 2)

Here's a more detailed follow-up on my original Block'd post with some practical advice for how you can get scores over 1,000,000 or so ('Marathon' mode). In order to get to a very high score (e.g. my high score is 100,410,143) you will need to learn to control boredom - above about level 40 or so you have effectively beaten the game and the rest is just rote play.
(My explanation of going so far is that I was interested to see if the high score would 'roll-over' correctly to 7 digits. My particular game - on my old Nokia phone - has some other glitches where it can screw up if you go over level 128, so there was *some* reason to believe that other issues may arise:-) )

As mentioned in the original post, the key strategy is to try and get the maximum points every 4th and 5th levels so you can maximize the number of 'wilds' that you have. Then, use these judiciously over the next few levels so that you have some available for the next big level.

So minimizing the overuse of 'wilds' can pay dividends. A few simple situations and how to handle them follow. These will probably only make sense if you either play the game, or have read the earlier post! And to use a chess analogy - this is kind of like learning the endgame positions so you can recognize how to win them, and which ones to avoid.

First, a simple case (see below). To clear this without losing lives you might think you should put a wild on the top right (red) block (to clear it and the yellow), then place a wild on the top left (red) block to clear the rest. However this has a simpler solution...just place a wild on the middle blue block and clear the bottom row, and then you can clear the two reds as they will be side by side.

Now that you've seen the general approach, here's a quiz. In all cases, how do you place the minimum number of 'wilds' in order to clear the level without losing lives.

1.      

2.     

3.    

Answers:
1. Just need 1 wild (on the white)
2. Just need 1 wild (on the bottom white)
3. Need 2 wilds (e.g. one on the right hand red, then one on the white)

And what you will have seen by now, is that you don't want to get a very simple end position like:

Since you need 2 'wilds' to clear this. Don't forget, you can place them both before clicking to clear. (e.g. place a wild on each of the green blocks then click to clear).

I probably won't do any more posts on Block'd, so my knowledge of the 'middlegame' strategies for 'Marathon' mode, as well as how to get high scores on the 'Speed' mode will probably be forever lost.

Nim (Part 2) - harder

So, how can you figure out the solution to the more complex 'nim' game? (See my previous post for info on the game).

It's actually amazingly simple (well - somewhat simple) but needs a bit of background in binary numbers to appreciate.

First, a reminder that a binary number is composed of a 'ones' column (the right-most digit in the number), then a 'twos' column, then a 'fours' column, etc, like below:

So this is 1 'four' plus 0 'two' plus 1 'one' = 5 (in decimal)

In decimal of course, we have the 'ones' column, 'tens' column, etc, like below:

And this would be 1 'hundred' plus 1 'one' = 101 (in decimal)

Now for the solution. All you do is write out the number of toothpicks in each pile in binary, one below the other. Then add up the columns to see whether each column is even (0, 2, 4, etc) or odd. Finally, if all column sums are even then we call the overall sum 'even'. Everything else will be 'odd'.

Two things that I will note (but not prove):
1. If the overall sum is 'even', then if you take 1 or more toothpicks from any pile you will make the overall sum 'odd'.
2. If the overall sum is 'odd', then there is always a way to take away from one pile so that you make the overall sum 'even'.

So if you can make the sum 'even' on your turn, you can also always do that on your next turn since your opponent will always make it 'odd' on their turn.

a) If you follow this strategy you will win the game where the last person to take a toothpick wins.

Here's an example with three piles of 3, 5 and 8 toothpicks respectively:

Pile 1 (3)	0	1	1
Pile 2 (5)	1	0	1
Pile 3 (8)	1	0	0
	Even	Odd	Even

If you take away 2 from pile 1 you change it from binary 011 to binary 001 and now the sum of all the columns is even. If you keep this up, you will always leave toothpicks in at least 2 piles until you force your opponent to take the second-last pile and you then take the last one.

b) If you are playing the more common version of nim where the person to take the last toothpick loses, then play as above until only one heap has a size of 2 or more. Then remove all toothpicks from the larger heap and you win.

Finally, if you are playing a version of the game where you can only take away up to 'k' toothpicks at a time, then first (in your mind) reduce the size of each heap modulo k + 1 (that is, remove all multiples of k + 1 until you just have a remainder that is between 1 and k). Assuming that you are playing the 'last person to take a toothpick loses' version, then:
- If this makes all the heaps of size zero just take k objects from one of the heaps.
-Otherwise, follow the above strategy 'a'.

This is just an intro to nim, but should be enough that the explanations you read elsewhere make sense (e.g. the wikipedia nim entry)

Nim (Part 1) - easy

Nim is "a game in which two players alternately take one or more objects from one of a number of heaps, each trying to take, or to compel the other to take, the last remaining object".

(This post looks at an 'easy' version of Nim and how to solve it. My next post looks at the solution to the harder variants.)

My first experience with Nim was the simple version ('easy') where you start with a pile of (say) 15 toothpicks. You are allowed to take away 1, 2 or 3 toothpicks in your turn and then it is the other player's turn. You continue taking turns until someone has to take the last toothpick (and they lose).

This type of game is pretty easy to analyze. You can see that if you leave your opponent 1 toothpick you win. And if you leave them 1+4 = 5 toothpicks you also win (since if there are 5 toothpicks and they take 'x', you just take '4-x' on your turn and that leaves 1...giving you the win). So the winning strategy is to leave your opponent with 1 + (some multiple of 4) in the pile. If the pile starts with 15 and you get to go first, take 2 (leaving 13 = 1 + 4(3)) and you are already in a winning position.

Finally, if you are allowed to take 'k' toothpicks on each turn, then just leave 1 + some multiple of (k+1) toothpicks and you win. (And if the rules are that you need to take the last toothpick yourself to win, then just leave 1 + some multiple of k.)

The next variant I had heard of (call it 'hard') extended this game to 3 piles. The version I played had piles of 3, 5 and 8. During your turn you can take 1, 2, or 3 toothpicks from any one pile. Again, the objective of the game was to leave your opponent with the last toothpick.

I'll leave the analysis of this to be a simple case of the 'hardest' case:

• you have any number of piles
• each pile has some number of toothpicks
• during your turn you can take any number of toothpicks from any one pile

What is the winning strategy?

I'll leave this to my next post...but it's actually a fairly easy(!) solution - if you're good at converting numbers to binary and then adding up columns to see if they are even or odd.

Block'd (Part 1)

Where to start? After the recent amazing games at the worlds (plus the huge timing scandal for the Marathon players) it has probably become the number one talked about game on the web!

Or not.

I found this game on my now almost antique Nokia 2720 (which has v1.3.2 of Block'd). It's challenging to play and I'm going to try and give a short overview - then encourage you to buy my old phone so that you can play it!

My version came out in 2008 and was from EA. I see that they now disavow any knowledge of the game (their 'Answer HQ' here). But there does seem to be a site where you can download it (http://java.mob.org/game/blockd.html) though I have no idea if it's a safe/valid/etc site.

There are two 'modes' that you can play: Speed and Marathon. I'll talk about Marathon mode here and possibly (if there's a huge response) continue on to Speed mode later.

Here's a screen shot of a typical screen (though at a high level). You have blocks of different colours (the game starts with just 3 colours, and works up to 6). If you click on a block that is touching 1 or more other blocks with the same colour, then you remove all 'n' blocks and get a score of n**2. When you no longer have any cases of 2 or more blocks of the same colour touching you then lose a number of 'lives' equal to the number of blocks remaining. If you get rid of all blocks on a level you get a bonus of 1000*(level) points (i.e. 5000 points for level 5).

The last thing to talk about is the 'Wild' blocks. You start with 3 and can work up to 9 (like above) as you get one for each 10,000 points. When you place a 'wild' block it joins the block you place it on with the others around it and allows you to build a large connected area with different colours. This is important because if you clear 3 areas of 5 blocks each (for example) you will get 3*(5*5)=75 points. If you clear 1 area of 15 blocks though, you will get 1*(15*15)=225 points. So it pays to develop large areas and then clear them!

I will modestly claim the World Record Block'd Marathon score (for my particular version of course, and if necessary, restricted to areas not including others who have a higher score). And the key tactics?

• In the first 5 levels, work up to getting 9 wild blocks. Specifically, on levels 4 and 5, use the 'lightning' and 'multiplier' blocks (oh yeah, I forgot to mention them...lightning extends the number of blocks by 1 in each direction around the base area of blocks, and the multiplier multiplies your score by whatever value it has).and wild blocks to get a big score. See also this totally unrelated video by IanStig.
• You shouldn't use wild blocks on levels 1-3 unless you need one to, say, finish the level or avoid a big penalty. On the early levels it's usually more important to keep the wild blocks for use on levels 5, 10, 15, etc (the levels where you also get 3 lightning and 3 multipliers)
• The most difficult part to get through is probably around levels 25-30. Once you get past that you are getting 30,000+ points per level completed, which gets you 3 new wild blocks
• Work on those fundamentals! (stand with your feet just more than shoulder-width apart, knees slightly flexed, etc - though that may be other sports)

So much more detail I could give...ask me about my upcoming book. (And possibly see part 2 of this post)