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

The answer requires coordinated strategy and internal communications

Saturday 20 February 2016 18:27
Comments
Prisoners can see the hats lined up in from of them but  cannot look at the hats behind them or at their own
Prisoners can see the hats lined up in from of them but cannot look at the hats behind them or at their own

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.

Register for free to continue reading

Registration is a free and easy way to support our truly independent journalism

By registering, you will also enjoy limited access to Premium articles, exclusive newsletters, commenting, and virtual events with our leading journalists

Please enter a valid email
Please enter a valid email
Must be at least 6 characters, include an upper and lower case character and a number
Must be at least 6 characters, include an upper and lower case character and a number
Must be at least 6 characters, include an upper and lower case character and a number
Please enter your first name
Special characters aren’t allowed
Please enter a name between 1 and 40 characters
Please enter your last name
Special characters aren’t allowed
Please enter a name between 1 and 40 characters
You must be over 18 years old to register
You must be over 18 years old to register
Opt-out-policy
You can opt-out at any time by signing in to your account to manage your preferences. Each email has a link to unsubscribe.

By clicking ‘Create my account’ you confirm that your data has been entered correctly and you have read and agree to our Terms of use, Cookie policy and Privacy notice.

This site is protected by reCAPTCHA and the Google Privacy policy and Terms of service apply.

Already have an account? sign in

By clicking ‘Register’ you confirm that your data has been entered correctly and you have read and agree to our Terms of use, Cookie policy and Privacy notice.

This site is protected by reCAPTCHA and the Google Privacy policy and Terms of service apply.

Register for free to continue reading

Registration is a free and easy way to support our truly independent journalism

By registering, you will also enjoy limited access to Premium articles, exclusive newsletters, commenting, and virtual events with our leading journalists

Already have an account? sign in

By clicking ‘Register’ you confirm that your data has been entered correctly and you have read and agree to our Terms of use, Cookie policy and Privacy notice.

This site is protected by reCAPTCHA and the Google Privacy policy and Terms of service apply.

Join our new commenting forum

Join thought-provoking conversations, follow other Independent readers and see their replies

Comments

Thank you for registering

Please refresh the page or navigate to another page on the site to be automatically logged inPlease refresh your browser to be logged in