Rytíři a lháři (Knights)

Napište program pro řešení logických hádanek.

Kdy úkol dokončit

Do 2027-06-30T23:59:00+00:00

Jak získat pomoc

1. Ptejte se prostřednictvím Ed!
2. Ptejte se prostřednictvím kterékoli z komunit CS50!

Výchozí informace

V roce 1978 vydal logik Raymond Smullyan knihu logických hádanek „What is the name of this book?“. Mezi jejími hádankami byla skupina, kterou Smullyan nazval „Knights and Knaves“, tedy rytíři a lháři.

V hádance s rytíři a lháři platí následující: každá postava je buď rytíř, nebo lhář. Rytíř vždy říká pravdu: pokud rytíř vysloví nějakou větu, tato věta je pravdivá. Lhář naopak vždy lže: pokud vysloví nějakou větu, tato věta je nepravdivá.

Cílem hádanky je podle vět vyslovených jednotlivými postavami určit, zda je každá z nich rytíř, nebo lhář.

Uvažujme například jednoduchou hádanku s jedinou postavou A. A říká: „Jsem zároveň rytíř i lhář.“

Logicky můžeme usoudit, že kdyby byl A rytíř, musela by tato věta být pravdivá. Víme však, že pravdivá být nemůže, protože A nemůže být zároveň rytíř i lhář: každá postava je buď jedním, nebo druhým, ale nikdy obojím. Můžeme tedy dojít k závěru, že A musí být lhář.

Tato hádanka byla jednodušší. S více postavami a větami mohou být hádanky složitější! Vaším úkolem je určit, jak je reprezentovat pomocí výrokové logiky, aby je za nás mohla vyřešit AI používající algoritmus kontroly modelů.

Začínáme

• Stáhněte výchozí kód z https://cdn.cs50.net/ai/2023/x/projects/1/knights.zip a rozbalte jej.

Porozumění výchozímu kódu

Podívejte se na logic.py, který si můžete pamatovat z přednášky 1. Nemusíte rozumět celému souboru, všimněte si však, že definuje několik tříd pro různé typy logických spojek. Tyto třídy lze vkládat do sebe, takže výraz jako And(Not(A), Or(B, C)) představuje logickou větu, podle níž symbol A není pravdivý a symbol B nebo symbol C je pravdivý. „Nebo“ zde označuje nevylučovací, nikoli vylučovací disjunkci.

Připomeňme si, že logic.py obsahuje také funkci model_check. model_check přijímá znalostní bázi a dotaz. Znalostní báze je jediná logická věta: pokud známe více logických vět, můžeme je spojit výrazem And. model_check rekurzivně zvažuje všechny možné modely a vrátí True, pokud dotaz ze znalostní báze vyplývá, jinak vrátí False.

Nyní se podívejte na puzzle.py. Nahoře jsme definovali šest výrokových symbolů. AKnight například představuje větu „A je rytíř“, zatímco AKnave představuje větu „A je lhář“. Podobně jsme definovali výrokové symboly také pro postavy B a C.

Následují čtyři znalostní báze knowledge0, knowledge1, knowledge2 a knowledge3, které budou obsahovat znalosti potřebné k odvození řešení hádanek 0, 1, 2 a 3. Všimněte si, že každá je zatím prázdná. Zde přichází váš úkol!

Funkce main v tomto puzzle.py prochází všechny hádanky. Pomocí kontroly modelů a znalostí pro každou hádanku určuje, zda je každá postava rytíř, nebo lhář, a vypíše všechny závěry, k nimž algoritmus dokáže dojít.

Specifikace

Přidejte do znalostních bází knowledge0, knowledge1, knowledge2 a knowledge3 znalosti potřebné k řešení následujících hádanek.

• Hádanka 0 je hádanka z výchozích informací. Obsahuje jedinou postavu A.
  • A říká: „Jsem zároveň rytíř i lhář.“
• Hádanka 1 má dvě postavy: A a B.
  • A říká: „Oba jsme lháři.“
  • B neříká nic.
• Hádanka 2 má dvě postavy: A a B.
  • A říká: „Jsme stejného druhu.“
  • B říká: „Jsme různých druhů.“
• Hádanka 3 má tři postavy: A, B a C.
  • A říká buď „Jsem rytíř“, nebo „Jsem lhář“, ale nevíte kterou z těchto vět.
  • B říká: „A řekl: ‚Jsem lhář.‘“
  • B pak říká: „C je lhář.“
  • C říká: „A je rytíř.“

V každé z uvedených hádanek je každá postava buď rytíř, nebo lhář. Každá věta vyslovená rytířem je pravdivá a každá věta vyslovená lhářem je nepravdivá.

Po dokončení znalostní báze úlohy byste měli být schopni spustit python puzzle.py a zobrazit řešení hádanky.

Nápověda

• Pro každou znalostní bázi budete pravděpodobně chtít zakódovat dva typy informací: (1) informace o struktuře samotné úlohy, tedy informace dané definicí hádanky s rytíři a lháři, a (2) informace o tom, co postavy skutečně řekly.
• Zvažte, co znamená, když postava vysloví větu. Za jakých podmínek je věta pravdivá? Za jakých podmínek je nepravdivá? Jak to můžete vyjádřit logickou větou?
• Pro každou hádanku existuje více znalostních bází, které vypočtou správný výsledek. Snažte se zvolit bázi, která co nejpřímočařeji převádí informace v hádance, místo abyste logické uvažování prováděli sami. Zvažte také, jak lze informace vyjádřit co nejstručněji.
  • Například nastavení knowledge0 = AKnave pro hádanku 0 by vedlo ke správnému výstupu, protože z vlastního uvažování víme, že A musí být lhář. Bylo by to však proti smyslu úlohy: cílem je nechat uvažování na vaší AI.
• K dokončení této úlohy byste neměli potřebovat a ani nemáte jakkoli upravovat logic.py.

Testování

Pokud chcete, můžete po nastavení check50 ve svém systému spustit následující příkaz pro ověření správnosti kódu. Není to povinné; můžete úkol jednoduše odevzdat podle kroků na konci specifikace a stejné testy se spustí na našem serveru. V každém případě kód také sami zkompilujte a otestujte!

check50 ai50/projects/2024/x/knights

Následujícím příkazem zkontrolujte styl svého kódu pomocí style50.

style50 puzzle.py

Jak úkol odevzdat

1. Navštivte tento odkaz, přihlaste se účtem GitHub a klikněte na Authorize cs50. Poté zaškrtněte políčko udělující týmu kurzu přístup k vašim odevzdaným pracím a klikněte na Join course.
2. Nainstalujte Git a volitelně nainstalujte submit50.
3. Pokud máte nainstalovaný submit50, spusťte

   submit50 ai50/projects/2024/x/knights
   

   Jinak pomocí Gitu odešlete práci do https://github.com/me50/USERNAME.git, kde USERNAME je vaše uživatelské jméno GitHub, do větve pojmenované ai50/projects/2024/x/knights.

Práce by měla být ohodnocena do pěti minut. Pak můžete na https://cs50.me/cs50ai zobrazit aktuální postup!