Amazing story of co-operation amongst ants

Ant on leafImagine that you are an ant living happily in your colony hidden between two rocks. One day a big dog runs over the rocks and dislodges one, breaking up your nest and leaving you and your fellow ants exposed and without a home.

What strategy do you follow to be able to survive when this happens?

You look around and, although it is risky, you know that you need to be one of the ants to go out and look for a new nest site.

You leave your damaged nest and bravely step out into the sunshine, you are looking for another crevice between rocks that will be an ideal site for a new nest. Other brave ants are also leaving the nest to search out a new site.

You find a new site and look around. Would this make a good nest? You check out whether it is the right size, how many openings it has, whether there are already any dead ants here and then run back to the nest.

When you get back you wait for some other ants to join you before you head back to the nest you have found to show them the potential site. The key to the strategy is that you wait longer if you have found a poor site and less time if you have found a good site.

The ants that follow you to the potential site also make a judgement of how good it is and return to the nest. They then wait for some other ants to join them, again waiting longer for a poor site and less time for a good one.

Once you have shown your site to others then you look around the damaged nest and find another ant who takes you to a different potential site. You then judge this site and head back to the nest once again.

Very quickly a lot of ants are making judgements about different sites. You meet up with another ant and go to look at another site. The ant that you are with now had only just arrived back in the old nest before he headed out again, you must be going to a good site.

When you arrive you find that the new site is packed with ants. You sense that there are enough ants here for this to be the place to make the new nest. Everyone else senses the same thing and you all go back to fetch the main brood of ants who are protecting your queen.

By working together the ants are able to quickly check out a lot of new sites and identify the best one for a new nest.

The strategy works because the ants wait less time to go back to a good site which means that ants are arriving there more often then they are arriving at a poor site. An ant coming from a good site will go back there almost immediately taking other ants with him. One coming from a poor site might wait a minute before going back, in that time a lot more ants will have returned to the good site. After a while a lot more ants end up at the good site, which is then selected.

Amazingly this co-operative behaviour is really how some ants work when then need to find a new nest site.

I wonder if it has any applications to crowd-sourcing solutions to problems?

 

Image courtesy of sweetcrisis / FreeDigitalPhotos.net

Posted in Science, Uncategorized | Tagged , , , | Comments Off on Amazing story of co-operation amongst ants

Keyboards, kids and game theory

ID-100117391The last few months have been a really exciting time for me because my daughter has just started at school. It is amazing to see how quickly kids learn new things once they are at school.

She is learning her letters and also learning to write. I guess they have to learn to write but as an adult I hardly write anything any more, everything I do is typed on a keyboard of one sort or another.

This got me thinking about how early a child should learn to type and then whether even that will be worth doing if the method of inputting changes in the next 10-15 years. Maybe we’ll move on to something beyond keyboards, or maybe we’ll move away from QWERTY keyboards to something else.

How do we know that we are teaching our kids something that will really be useful for them in the future?

It is possible that we won’t be using keyboards in the future, but if we are they will almost certainly be QWERTY ones – because of game theory.

Although the QWERTY keyboard is by far the best known layout of the keys there are other options available. One of the best known alternatives is the Dvorak keyboard which puts the most commonly used keys on the middle line of keys which then minimizes the amount of finger movement that is required to type. It is arguably a better layout than the standard QWERTY keyboard.

But choosing a keyboard layout is really a big co-ordination game. If I decide to change to the Dvorak keyboard because I think it is better then I can change my own computers but every other keyboard I come across in my day will still be a QWERTY one so I will need to be able to type on both which will be harder work.

If everyone changed to Dvorak then we would all be better off but whilst the vast majority stay with QWERTY it is better to stay with that, even if it is a slightly worse layout.

A new product has to be significantly better if it is to break into a market where it is better for everyone to be using the same product. Another example is with social networks. A challenger to Facebook has to be good enough to convince enough people to change even though at first not all their friends will be on the new network. Once the new product reaches a tipping point then take up will be quick but getting to the tipping point can be nearly impossible.

Image courtesy of imagerymajestic / FreeDigitalPhotos.net

Posted in Game theory | Tagged , , , | 2 Comments

Nim game solution

I have previously worked out a solution to Nim which is a simple game of strategy.

The game is played by two players who each take turns to pick up matches from two separate piles. The rules allow a player to take any number of matches from one of the piles when it is their turn. The winner is the player that takes the last match. This post explains the winning strategy.

This version of Nim is quite easy to work out the correct strategy for but there are versions where things get more difficult.

What about a game where there is one pile of matches and the first player can take can any number of matches up to one less than the total. For moves after that each player can only take a number of matches that is less than, or equal to, the number that was taken by the other player in their previous turn.

So if player one takes two matches then player two can take one or two. If player two then takes one, then player one can only take one match in their next turn. Each turn from then on will be to take only a single match.

If there are an odd number of matches in the pile then the solution is easy. Player one takes one match which leaves an even number of matches. Player two is only allowed to take one match since they cannot take more than their opponent took on the previous turn. This leaves an odd number of matches again. This game continues until player one take the final match and wins.

So the more interesting case is when there is an even number of matches in the pile. No player wants to leave an odd number of matches in the pile otherwise the other player will just take one and then each player will only be able to take one match each turn until the player that left an odd number of matches in the pile loses. This means that we know that player one’s first move must be to take an even number of matches, and he must take fewer than half the matches. If he takes more than half then player two will simply take all the remaining matches to win.

Looking at some examples should start to show the pattern.

We know that player one wins if there are an odd number of matches. Looking at the even numbers:

Start with 2 – player one must take one, player two then takes the last one to win. Player two wins

Start with 4 – player one loses if he takes an odd number so he must take two, player two then takes the final two and wins. Player two wins

Start with 6 – player one must take two to have a chance as it is the only even number less than half of six. This leaves four and is the case above, player two can take one or two and either way they lose. Player one wins

Start with 8 – player one must take two again which gives the same as starting with six but with player two to play so: Player two wins.

Start with 10 – If player one takes four then six are left and, as above, player two wins. But if player one takes two then eight are left, following the logic above, Player one wins.

Start with 12 – Player one takes four and will win. Player one wins

Start with 14 –  Player one takes six and will win. Player one wins

Start with 16 – Player one cannot bring the number down to eight again otherwise player two will take all the eight remaining matches and win. Player one must take a number less than eight, we know that odd numbers will lose, and taking two, four or six leaves the cases above for 10,12 and 14 but we know that whoever goes first with a pile of 10, 12 or 14 will win, so Player two wins

We can now see the pattern and the strategy

Player two wins when the pile contains a number of matches that is a power of two (2, 4, 8, 16, etc) and player one wins otherwise. The winning strategy is to reduce the pile to a power of two that is more than half the remaining pile.

More complicated games can still be worked out by working up from the simplest cases.

Posted in Game theory, Uncategorized | Tagged , , , | Comments Off on Nim game solution