Can you solve the '100 hat riddle' used by Google in job interviews?

The answer requires coordinated strategy and internal communications

Prisoners can see the hats lined up in from of them but cannot look at the hats behind them or at their own (Jakob Foerster)

A riddle used during job interviews for Google has proven to be no problem for artificial intelligence.

A team from the University of Oxford, Canadian Institute for Advanced Research and Google’s DeepMind created an AI called “deep distrubted recurrent Q-networks” to tackle the “100 hats riddle”.

The authors of the research paper say their findings could pave the way in solving other multi-agent communication problems.

Speaking to The Independent, Jakob Foerster, one of the authors behind the findings said: “The results show that we can reformulate tasks, which are made to be challenging for humans, as communication based AI problems and that our extension of existing algorithms can successfully solve these kind of challenges.”

Co-author Yannis Assael added: "Our work paves the way towards a new class of multi-agent communication problems.

“We believe that the challenge now is to gain deeper understanding of the communication protocols that arise and to see what other real applications we can solve with this approach."

In the riddle, 100 prisoners stand in line, one in front of the other, each wearing either a red hat or a blue hat.

Every prisoner can see the hats of the people in front but not their own hat, or the hats worn by anyone behind.

A prison guard, starts at the back of the line and asks each prisoner the colour of their hat. If they answer correctly, they will be pardoned, if they get it wrong, they’ll be executed.

Before lining up, the prisoners are allowed to collectively come up with a strategy. What should they do?

The AI's best strategy resulted in 99 of the prisoners definitely surviving and the one remaining prisoner having a 50% chance of survival.

For this to happen, the first prisoner to speak will say “blue”, if the number of blue hats he sees in front of him is even, or “red” if he sees an odd number.

This information, coupled with the responses other prisoners have already given and the hats in front is enough to work out what colour hat is on your head.

In this case, everyone except the first prisoner will definitely answer correctly.