| Part of a series on |
| Puzzles |
|---|
 |
Induction puzzles are logic puzzles, which are examples of multi-agent reasoning, where the solution evolves along with the principle of induction.[1][2]
A puzzle's scenario always involves multiple players with the same reasoning capability, who go through the same reasoning steps. According to the principle of induction, a solution to the simplest case makes the solution of the next complicated case obvious. Once the simplest case of the induction puzzle is solved, the whole puzzle is solved subsequently.
Typical tell-tale features of these puzzles include any puzzle in which each participant has a given piece of information (usually as common knowledge) about all other participants but not themselves. Also, usually, some kind of hint is given to suggest that the participants can trust each other's intelligence — they are capable of theory of mind (that "every participant knows modus ponens" is common knowledge).[3] Also, the inaction of a participant is a non-verbal communication of that participant's lack of knowledge, which then becomes common knowledge to all participants who observed the inaction.
The muddy children puzzle is the most frequently appearing induction puzzle in scientific literature on epistemic logic.[4][5][6] Muddy children puzzle is a variant of the well known wise men or cheating wives/husbands puzzles.[7]
Hat puzzles are induction puzzle variations that date back to as early as 1961.[8] In many variations, hat puzzles are described in the context of prisoners.[9][10] In other cases, hat puzzles are described in the context of wise men.[11][12]
- ^ Stuhlmüller, A.; Goodman, N.D. (June 2014). "Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs". Cognitive Systems Research. 28: 80–99. CiteSeerX 10.1.1.361.5043. doi:10.1016/j.cogsys.2013.07.003. S2CID 7602205.
- ^ Lucci, Stephen; Kopec, Danny (2015). Artificial Intelligence in the 21st Century. Stylus Publishing, LLC. ISBN 978-1-944534-53-0.
- ^ Tagiew, Rustam (2008). "Simplest Scenario for Mutual Nested Modeling in Human-Machine-Interaction". KI 2008: Advances in Artificial Intelligence. Lecture Notes in Computer Science. Vol. 5243. Springer. pp. 364–371. doi:10.1007/978-3-540-85845-4_45. ISBN 978-3-540-85844-7.
- ^ Fagin, Ronald; Halpern, Joseph Y.; Moses, Yoram; Vardi, Moshe Y. (March 1999). "Common knowledge revisited". Annals of Pure and Applied Logic. 96 (1–3): 89–105. arXiv:cs/9809003. doi:10.1016/S0168-0072(98)00033-5. S2CID 59551.
- ^ van der Hoek, Wiebe; van Ditmarsch, Hans (2007). Dynamic epistemic logic. Springer. ISBN 978-1-4020-5838-7.
- ^ "Google Scholar "Muddy Children Puzzle"". scholar.google.com. Retrieved 11 February 2020.
- ^ Fagin, Ronald; Halpern, Joseph Y.; Moses, Yoram; Vardi, Moshe (2004). Reasoning about knowledge. MIT Press. ISBN 978-0262562003.
- ^ Hardin, Christopher; Taylor, Alan D. (2008). "An introduction to Infinite Hat Problems" (PDF). Mathematical Intelligencer. 30 (4): 20–25. doi:10.1007/BF03038092. S2CID 24613564. Archived from the original (PDF) on 2012-04-05.
- ^ "The Prisoners' Hats – Puzzles And Riddles". www.puzzlesandriddles.com.
- ^ "Prisoners and Hats Puzzle". CrazyforCode. 13 August 2013.
- ^ "Robots pass 'wise-men puzzle' to show a degree of self-awareness". techxplore.com.
- ^ Leite, João (2005). Computational Logic in Multi-Agent Systems: 5th International Workshop, CLIMA V, Lisbon, Portugal, September 29–30, 2004, Revised Selected and Invited Papers. Springer Science & Business Media. ISBN 978-3-540-28060-6.