Hledání min (Minesweeper)

Napište AI, která hraje hledání min.

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

Hledání min

Hledání min je logická hra s mřížkou políček, z nichž některá obsahují skryté „miny“. Kliknutím na políčko s minou mina vybuchne a hráč prohraje. Kliknutím na „bezpečné“ políčko, tedy bez miny, se odhalí číslo udávající počet sousedních políček s minou. Sousedem je políčko vzdálené o jedno políčko vlevo, vpravo, nahoru, dolů nebo diagonálně.

V této hře 3 × 3 například tři hodnoty 1 označují, že každé z těchto políček má právě jedno sousední políčko s minou. Čtyři hodnoty 0 označují, že každé z těchto políček nemá žádnou sousední minu.

Z těchto informací může logicky uvažující hráč usoudit, že v pravém dolním políčku musí být mina a v levém horním mina není. Jen v takovém případě by číselné popisky ostatních políček byly správné.

Cílem hry je označit, tedy určit, každou minu. V mnoha implementacích včetně této lze minu označit pravým kliknutím na políčko, případně kliknutím dvěma prsty podle počítače.

Výroková logika

Cílem projektu je vytvořit AI schopnou hrát hledání min. Připomeňme si, že agenti založení na znalostech se rozhodují tím, že zvažují svou znalostní bázi a odvozují z ní závěry.

Jedním způsobem reprezentace znalostí AI o hře je přiřadit každému políčku výrokovou proměnnou. Ta je pravdivá, pokud políčko obsahuje minu, jinak nepravdivá.

Jaké informace má AI k dispozici? Věděla by o každém kliknutí na bezpečné políčko a viděla by jeho číslo. Uvažujte následující desku, kde bylo odhaleno prostřední políčko a ostatní jsou pro účely vysvětlení označena písmeny.

Jaké informace nyní máme? Zdá se, že víme, že jedno z osmi sousedních políček obsahuje minu. Můžeme proto zapsat logický výraz jako níže, který označuje, že některé ze sousedních políček je mina.

Or(A, B, C, D, E, F, G, H)

Ve skutečnosti ale víme více, než tento výraz říká. Výše uvedená logická věta vyjadřuje, že alespoň jedna z osmi proměnných je pravdivá. Můžeme však tvrdit něco silnějšího: víme, že pravdivá je právě jedna z osmi proměnných. Tím získáme větu výrokové logiky podobnou té níže.

Or(
    And(A, Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), B, Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), C, Not(D), Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), D, Not(E), Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), E, Not(F), Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), F, Not(G), Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), G, Not(H)),
    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), H)
)

To je docela složitý výraz! A přitom vyjadřuje pouze význam hodnoty 1 v políčku. Kdyby políčko obsahovalo 2, 3 nebo jinou hodnotu, mohl by být výraz ještě delší.

Také kontrola modelů by se u tohoto typu úlohy rychle stala výpočetně nezvládnutelnou: na mřížce 8 × 8, kterou Microsoft používá pro začátečnickou úroveň, bychom měli 64 proměnných, a tedy 2^64 možných modelů ke kontrole. To je příliš mnoho, aby je počítač vypočítal v rozumném čase. Pro tuto úlohu potřebujeme lepší reprezentaci znalostí.

Reprezentace znalostí

Místo toho budeme každou větu ve znalostech AI reprezentovat jako níže.

{A, B, C, D, E, F, G, H} = 1

Každá logická věta má v této reprezentaci dvě části: množinu cells na desce, kterých se věta týká, a číslo count udávající, kolik z těchto políček obsahuje miny. Výše uvedená věta říká, že z políček A, B, C, D, E, F, G a H obsahuje minu právě 1.

Proč je tato reprezentace užitečná? Mimo jiné se dobře hodí pro určité typy odvozování. Uvažujte hru níže.

Ze znalosti čísla v levém dolním políčku můžeme vytvořit větu {D, E, G} = 0, která říká, že z políček D, E a G obsahuje minu právě 0. Intuitivně z ní lze odvodit, že všechna tato políčka musí být bezpečná. Obecně tedy vždy, když má věta count rovný 0, víme, že všechna její cells musí být bezpečná.

Podobně uvažujte hru níže.

Naše AI by vytvořila větu {E, F, H} = 3. Intuitivně lze odvodit, že E, F i H jsou miny. Obecně vždy, když je počet cells roven count, víme, že všechna cells této věty musí být miny.

Obecně chceme, aby se věty týkaly pouze cells, o nichž dosud není známo, zda jsou bezpečná, nebo obsahují miny. Jakmile tedy zjistíme, zda políčko obsahuje minu, můžeme věty aktualizovat, zjednodušit je a případně vyvodit nové závěry.

Pokud například AI zná větu {A, B, C} = 2, nemáme zatím dost informací k závěru. Pokud ale zjistíme, že C je bezpečné, můžeme C z věty zcela odstranit a zbude nám {A, B} = 2. To nám mimochodem umožní vyvodit nové závěry.

Stejně tak pokud AI zná větu {A, B, C} = 2 a zjistíme, že C je mina, můžeme z věty odstranit C a snížit count, protože C bylo minou započítanou do tohoto počtu. Dostaneme {A, B} = 1. Je to logické: pokud dvě z políček A, B a C jsou miny a víme, že C je mina, pak z A a B musí být minou právě jedno.

Pokud chceme být ještě důvtipnější, můžeme použít ještě jeden typ odvozování.

Uvažujte pouze dvě věty, které by AI znala z horního prostředního a dolního prostředního políčka. Z horního prostředního získáme {A, B, C} = 1. Z dolního prostředního získáme {A, B, C, D, E} = 2. Logicky pak můžeme odvodit novou znalost: {D, E} = 1. Pokud dvě z A, B, C, D a E jsou miny a pouze jedna z A, B a C je mina, pak právě jedno z D a E musí být druhou minou.

Obecně kdykoli máme dvě věty set1 = count1 a set2 = count2, kde set1 je podmnožinou set2, můžeme vytvořit novou větu set2 - set1 = count2 - count1. Projděte si výše uvedený příklad, abyste porozuměli, proč to platí.

Pomocí této reprezentace znalostí tedy můžeme napsat AI agenta, který bude shromažďovat znalosti o desce a doufejme vybírat políčka, o nichž ví, že jsou bezpečná!

Začínáme

• Stáhněte výchozí kód z https://cdn.cs50.net/ai/2023/x/projects/1/minesweeper.zip a rozbalte jej.
• V adresáři projektu spusťte pip3 install -r requirements.txt, abyste nainstalovali potřebný balíček Pythonu (pygame), pokud ho již nemáte nainstalovaný.

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

Projekt má dva hlavní soubory: runner.py a minesweeper.py. minesweeper.py obsahuje veškerou logiku samotné hry i AI, která ji hraje. runner.py je již implementován a obsahuje celý kód grafického rozhraní. Až dokončíte všechny požadované funkce v minesweeper.py, měli byste pomocí python runner.py být schopni hrát hledání min nebo nechat svou AI hrát za vás!

Otevřeme minesweeper.py a podíváme se, co je připraveno. Soubor definuje tři třídy: Minesweeper, která zajišťuje průběh hry; Sentence, která reprezentuje logickou větu obsahující množinu cells a count; a MinesweeperAI, která na základě znalostí odvozuje, jaké tahy provést.

Třída Minesweeper je již kompletně implementována. Každé políčko je dvojice (i, j), kde i je číslo řádku od 0 do height - 1 a j číslo sloupce od 0 do width - 1.

Třída Sentence bude reprezentovat logické věty ve tvaru popsaném ve výchozích informacích. Každá věta obsahuje množinu cells a count udávající, kolik z nich jsou miny. Třída má také funkce known_mines a known_safes, které určují, zda o některých políčkách věty víme, že jsou miny nebo bezpečná. Obsahuje také funkce mark_mine a mark_safe pro aktualizaci věty při získání nové informace o políčku.

Třída MinesweeperAI nakonec implementuje AI hrající hledání min. Sleduje několik hodnot. self.moves_made obsahuje množinu všech políček, na která se již kliklo, aby je AI nevybírala znovu. self.mines obsahuje množinu všech známých min. self.safes obsahuje množinu všech známých bezpečných políček. self.knowledge obsahuje seznam všech objektů Sentence, o nichž AI ví, že jsou pravdivé.

Funkce mark_mine přidá políčko do self.mines, aby AI věděla, že je minou. Projde také všechny věty v knowledge AI a každé oznámí, že políčko je mina, aby se věta mohla odpovídajícím způsobem aktualizovat, pokud o této mině obsahuje informace. Funkce mark_safe dělá totéž pro bezpečná políčka.

Implementace zbývajících funkcí add_knowledge, make_safe_move a make_random_move je na vás!

Specifikace

Dokončete implementace tříd Sentence a MinesweeperAI v minesweeper.py.

Ve třídě Sentence dokončete implementace known_mines, known_safes, mark_mine a mark_safe.

• Funkce known_mines má vrátit množinu všech políček v self.cells, o nichž víme, že jsou minami.
• Funkce known_safes má vrátit množinu všech políček v self.cells, o nichž víme, že jsou bezpečná.
• Funkce mark_mine má nejprve ověřit, zda cell patří mezi políčka obsažená ve větě.
  • Pokud cell ve větě je, funkce ji má aktualizovat tak, aby v ní cell již nebylo, ale aby věta zůstala logicky správná při znalosti, že cell obsahuje minu.
  • Pokud cell ve větě není, není třeba nic dělat.
• Funkce mark_safe má nejprve ověřit, zda cell patří mezi políčka obsažená ve větě.
  • Pokud cell ve větě je, funkce ji má aktualizovat tak, aby v ní cell již nebylo, ale aby věta zůstala logicky správná při znalosti, že cell je bezpečné.
  • Pokud cell ve větě není, není třeba nic dělat.

Ve třídě MinesweeperAI dokončete implementace add_knowledge, make_safe_move a make_random_move.

• add_knowledge má přijmout cell reprezentované jako n-tice (i, j) a jeho count a aktualizovat self.mines, self.safes, self.moves_made a self.knowledge všemi novými informacemi, které AI dokáže odvodit, pokud ví, že cell je bezpečné políčko s count sousedními minami.
  • Funkce má označit cell jako jeden z již provedených tahů ve hře.
  • Funkce má označit cell jako bezpečné políčko a aktualizovat také všechny věty obsahující cell.
  • Funkce má podle hodnot cell a count přidat do znalostní báze AI novou větu uvádějící, že count sousedů políčka cell obsahuje miny. Do věty zahrňte pouze políčka s dosud neurčeným stavem.
  • Pokud lze podle některé věty v self.knowledge označit další políčka jako bezpečná nebo jako miny, funkce to má udělat.
  • Pokud lze podle některých vět v self.knowledge odvodit nové věty pomocí metody podmnožin popsané ve výchozích informacích, mají se také přidat do znalostní báze.
  • Pokaždé, když změníte znalosti AI, může být možné odvodit nové závěry, které dříve odvodit nešlo. Pokud je to možné, zajistěte přidání těchto nových závěrů do znalostní báze.
• make_safe_move má vrátit tah (i, j), o němž je známo, že je bezpečný.
  • Vrácený tah musí být známý jako bezpečný a nesmí už být proveden.
  • Pokud nelze zaručit žádný bezpečný tah, funkce má vrátit None.
  • Funkce nemá měnit self.moves_made, self.mines, self.safes ani self.knowledge.
• make_random_move má vrátit náhodný tah (i, j).
  • Tato funkce se zavolá, pokud bezpečný tah není možný: když AI neví, kam táhnout, vybere tah náhodně.
  • Tah nesmí být již provedený.
  • Tah nesmí směřovat na políčko, o němž je známo, že je minou.
  • Pokud žádný takový tah neexistuje, funkce má vrátit None.

Nápověda

• Důkladně si přečtěte výchozí informace, abyste porozuměli reprezentaci znalostí v této AI a tomu, jak může odvozovat závěry.
• Pokud si nejste jistí v objektově orientovaném programování, může vám pomoci dokumentace tříd v Pythonu.
• Některé běžné operace s set najdete v dokumentaci množin v Pythonu.
• Při implementaci known_mines a known_safes ve třídě Sentence zvažte: za jakých okolností víte jistě, že políčka věty jsou bezpečná? Za jakých okolností víte jistě, že jsou minami?
• add_knowledge vykonává mnoho práce a pravděpodobně bude zdaleka nejdelší funkcí, kterou pro tento projekt napíšete. Pomůže implementovat její chování postupně po jednotlivých krocích.
• Pokud chcete, můžete ke kterékoli třídě přidat nové metody, neměli byste však měnit definice ani argumenty existujících funkcí.
• Když AI spustíte například kliknutím na „AI Move“, nebude vždy vyhrávat! V některých případech bude muset hádat, protože nemá dost informací pro bezpečný tah. To je očekávané. runner.py vypíše, zda AI provádí tah, který považuje za bezpečný, nebo náhodný tah.
• Při procházení množiny ji neměňte. Mohlo by to vést k chybám!

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/minesweeper

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

style50 minesweeper.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/minesweeper
   

   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/minesweeper.

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