Projekt 4 — Nim

Napiš AI, která se pomocí posilovaného učení sama naučí hrát Nim.

$ python play.py
Playing training game 1
Playing training game 2
Playing training game 3
...
Playing training game 9999
Playing training game 10000
Done training

Piles:
Pile 0: 1
Pile 1: 3
Pile 2: 5
Pile 3: 7

AI's Turn
AI chose to take 1 from pile 2.

Kdy úlohu dokončit

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

Jak získat pomoc

1. Ptej se prostřednictvím Ed!
2. Ptej se v kterékoli komunitě CS50!

Východiska

Ve hře Nim začínáme s několika hromádkami objektů. Hráči se střídají: hráč na tahu odebere libovolný nezáporný počet objektů z jedné neprázdné hromádky. Kdo odebere poslední objekt, prohraje.

Poznámka překladatele: Původní anglické zadání zde uvádí „any non-negative number“, tedy nezáporný počet, což zahrnuje i nulu. Jde o nepřesnost původního slovního popisu: platný tah hry Nim odebírá kladný počet objektů, alespoň 1, z jedné neprázdné hromádky. Překlad původní věty výše je zachován; tato poznámka objasňuje pravidlo a nemění dodaný kód ani ostatní požadavky projektu.

Dokážeš si představit jednoduchou strategii: pokud zbývá jediná hromádka se třemi objekty a jsi na tahu, nejlépe odebereš dva a necháš protivníkovi třetí, poslední. Při více hromádkách se strategie podstatně komplikuje. V projektu vytvoříme AI, která se strategii naučí posilovaným učením. Opakovaným hraním proti sobě a učením ze zkušenosti časem zjistí, které akce provádět a kterým se vyhnout.

Konkrétně použijeme Q-learning. Pro každou dvojici (state, action) se učíme číselnou hodnotu odměny. Akce vedoucí k prohře má odměnu −1, akce vedoucí k prohře protivníka odměnu 1 a akce pokračující ve hře okamžitou odměnu 0, ale také určitou budoucí odměnu.

Jak stavy a akce vyjádříme v Pythonu? Stav Nimu jsou aktuální velikosti všech hromádek. Například [1, 1, 3, 5] znamená 1 objekt v hromádce 0, 1 v hromádce 1, 3 v hromádce 2 a 5 v hromádce 3. Akce je dvojice celých čísel (i, j) znamenající odebrání j objektů z hromádky i. Akce (3, 5) tedy odebere 5 objektů z hromádky 3. Použitím na [1, 1, 3, 5] dostaneme [1, 1, 3, 0], stejný stav s nyní prázdnou hromádkou 3.

Základní vzorec Q-learningu je níže. Kdykoli ve stavu s provedeme akci a, můžeme upravit Q(s, a) podle něj:

Q(s, a) <- Q(s, a) + alpha * (nový odhad hodnoty - starý odhad hodnoty)

alpha je rychlost učení, tedy míra, v níž nové informace oceňujeme vůči dosavadním. new value estimate je součet odměny za aktuální akci a odhadu všech budoucích odměn hráče. old value estimate je dosavadní hodnota Q(s, a). Používáním vzorce po každé nové akci se AI postupně učí, které akce jsou v jednotlivých stavech lepší.

Začínáme

• Stáhni dodaný kód z https://cdn.cs50.net/ai/2023/x/projects/4/nim.zip a rozbal jej.

Porozumění zadání

Nejprve otevři nim.py. Obsahuje třídy Nim a NimAI a funkce train a play. Nim, train i play už jsou implementované, zatímco v NimAI musíš doplnit několik funkcí.

Třída Nim definuje pravidla hry. V __init__ si všimni seznamu hromádek, aktuálního hráče 0 nebo 1 a vítěze, pokud existuje. available_actions vrací množinu dostupných akcí ve stavu. Například Nim.available_actions([2, 1, 0, 0]) vrátí {(0, 1), (1, 1), (0, 2)}, protože lze odebrat 1 či 2 objekty z hromádky 0 nebo 1 objekt z hromádky 1.

Další funkce určují průběh hry: other_player určí protivníka daného hráče, switch_player předá tah protivníkovi a move provede akci v aktuálním stavu a předá tah.

Třída NimAI definuje AI učící se Nim. V __init__ začíná prázdným slovníkem self.q. self.q uchovává naučené Q hodnoty mapováním dvojic (state, action) na čísla. Ačkoli state obvykle představujeme seznamem, seznam nemůže být klíčem slovníku Pythonu. Při získávání a nastavování self.q proto použijeme stav jako tuple.

Chceme-li například Q hodnotu pro stav [0, 0, 0, 2] a akci (3, 2) nastavit na -1, napíšeme:

self.q[(0, 0, 0, 2), (3, 2)] = -1

Každý objekt NimAI má také hodnoty alpha a epsilon, používané pro Q-learning a volbu akce.

Hotová funkce update přijímá stav old_state, provedenou akci action, výsledný stav new_state a okamžitou odměnu reward. Provede Q-learning: získá aktuální Q hodnotu stavu a akce voláním get_q_value, určí nejlepší možné budoucí odměny pomocí best_future_reward a z obou upraví Q hodnotu pomocí update_q_value. Tyto tři funkce musíš implementovat.

Poslední nedokončenou funkcí je choose_action, která vybere akci pro daný stav, buď hladově, nebo epsilon-hladovým algoritmem.

Třídy Nim a NimAI využívají funkce train a play. train spustí n simulovaných her proti sobě a vrátí natrénovanou AI. play natrénovanou AI přijme a umožní člověku hrát proti ní.

Specifikace

V nim.py dokonči get_q_value, update_q_value, best_future_reward a choose_action. V každé funkci můžeš předpokládat, že state je seznam celých čísel a action dvojice celých čísel (i, j), hromádky i a počtu objektů j.

get_q_value přijme state a action a vrátí odpovídající Q hodnotu dvojice stav–akce.

• Q hodnoty uchovává slovník self.q. Klíče self.q mají tvar (state, action), kde state je tuple velikostí všech hromádek v pořadí a action tuple (i, j) označující hromádku a počet.
• Pokud dvojice nemá ve self.q Q hodnotu, vrať 0.

update_q_value přijme stav state, akci action, dosavadní Q hodnotu old_q, aktuální odměnu reward a odhad budoucí odměny future_rewards. Podle vzorce Q-learningu upraví Q hodnotu této dvojice.

• Vzorec Q-learningu připomínáme: Q(s, a) <- old value estimate + alpha * (new value estimate - old value estimate).
• alpha je rychlost učení přiřazená objektu NimAI.
• Starý odhad je současná Q hodnota dvojice stav–akce. Nový odhad má být součtem aktuální odměny a odhadované budoucí odměny.

best_future_reward přijme state a podle údajů self.q vrátí nejlepší možnou odměnu z dostupných akcí v tomto stavu.

• U akce, která pro daný stav dosud není v self.q, předpokládej Q hodnotu 0.
• Pokud nejsou dostupné žádné akce, vrať 0.

choose_action přijme state a volitelný příznak epsilon, zda má použít epsilon-hladový algoritmus, a vrátí dostupnou akci v daném stavu.

• Je-li epsilon False, funkce má vybrat hladově nejlepší dostupnou akci, tedy nejvyšší Q hodnotu; neznámá Q hodnota je 0.
• Je-li epsilon True, použij epsilon-hladový algoritmus: s pravděpodobností self.epsilon vyber náhodnou dostupnou akci, jinak nejlepší dostupnou.
• Má-li stejnou Q hodnotu více akcí, lze vrátit kteroukoli z nich.

V nim.py neupravuj nic kromě funkcí určených zadáním. Můžeš přidat pomocné funkce a importy standardní knihovny Pythonu, případně numpy či pandas, pokud je znáš, ale žádné jiné moduly třetích stran. Pro vlastní testování můžeš upravit play.py.

Tipy

• Je-li lst seznam, volání tuple(lst) převede lst na tuple.

Testování

Chceš-li vyhodnotit správnost kódu, můžeš po nastavení check50 spustit následující příkaz. Není to povinné: při odevzdání podle kroků na konci zadání proběhnou stejné testy na našem serveru. V každém případě kód také sama zkompiluj a otestuj!

check50 ai50/projects/2024/x/nim

Následujícím příkazem vyhodnotíš styl kódu pomocí style50.

style50 nim.py

Jak odevzdat

1. Otevři tento odkaz, přihlas se účtem GitHub a klikni na Authorize cs50. Pak zaškrtni souhlas s přístupem učitelů k odevzdaným pracím a klikni na Join course.
2. Nainstaluj Git a případně nainstaluj submit50.
3. Pokud máš nainstalované submit50, spusť

   submit50 ai50/projects/2024/x/nim
   

   Jinak pomocí Gitu odešli práci do https://github.com/me50/USERNAME.git, kde USERNAME je tvoje jméno na GitHubu, na větev ai50/projects/2024/x/nim.

Práce by měla být ohodnocena do pěti minut. Svůj postup pak můžeš sledovat na https://cs50.me/cs50ai!