Piškvorky (Tic-Tac-Toe)

Pomocí algoritmu Minimax implementujte AI, která hraje piškvorky optimálně.

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!

Začínáme

• Stáhněte výchozí kód z https://cdn.cs50.net/ai/2023/x/projects/0/tictactoe.zip a rozbalte jej.
• V adresáři projektu spusťte pip3 install -r requirements.txt, abyste nainstalovali balíček Pythonu (pygame), který projekt vyžaduje.

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

Tento projekt má dva hlavní soubory: runner.py a tictactoe.py. tictactoe.py obsahuje veškerou logiku hry a volby optimálních tahů. runner.py je již implementován a obsahuje celý kód grafického rozhraní hry. Až dokončíte všechny požadované funkce v tictactoe.py, měli byste pomocí python runner.py být schopni hrát proti své AI!

Otevřeme tictactoe.py a podíváme se na to, co je připraveno. Nejprve definujeme tři proměnné: X, O a EMPTY, které představují možné hodnoty polí herní desky.

Funkce initial_state vrací počáteční stav desky. V této úloze jsme desku zvolili jako seznam tří seznamů představujících její tři řádky. Každý vnitřní seznam obsahuje tři hodnoty, které jsou buď X, O, nebo EMPTY. Následují funkce, jejichž implementaci jsme nechali na vás!

Specifikace

Dokončete implementace player, actions, result, winner, terminal, utility a minimax.

• Funkce player má přijmout stav board a vrátit hráče, který je na tahu, tedy X nebo O.
  • V počátečním stavu hry hraje jako první X. S každým dalším tahem se hráči střídají.
  • Pokud je vstupem koncová deska, tedy hra již skončila, je přípustná libovolná návratová hodnota.
• Funkce actions má vrátit set všech akcí, které lze na dané desce provést.
  • Každá akce má být n-tice (i, j), kde i označuje řádek tahu (0, 1 nebo 2) a j políčko v daném řádku, na které se táhne (také 0, 1 nebo 2).
  • Povolené tahy zahrnují všechna políčka desky, v nichž dosud není X ani O.
  • Pokud je vstupem koncová deska, je přípustná libovolná návratová hodnota.
• Funkce result přijímá board a action a má vrátit nový stav desky, aniž by původní desku změnila.
  • Pokud action není platnou akcí pro danou desku, program má vyvolat výjimku.
  • Vrácený stav má odpovídat desce, která by vznikla, kdyby hráč na tahu provedl na původní vstupní desce tah do políčka určeného vstupní akcí.
  • Původní deska musí zůstat nezměněna: Minimax bude během výpočtu potřebovat zvažovat mnoho různých stavů desky. Prostá změna políčka v samotném board proto není správnou implementací funkce result. Před změnami pravděpodobně budete chtít vytvořit hlubokou kopii desky.
• Funkce winner má přijmout board a vrátit vítěze, pokud existuje.
  • Pokud vyhrál hráč X, funkce má vrátit X. Pokud vyhrál hráč O, funkce má vrátit O.
  • Vyhrát lze umístěním tří vlastních značek do souvislé vodorovné, svislé nebo diagonální řady.
  • Můžete předpokládat nejvýše jednoho vítěze. Žádná deska tedy nebude mít současně tři značky v řadě u obou hráčů, protože by to byl neplatný stav desky.
  • Pokud hra nemá vítěze, protože ještě probíhá nebo skončila remízou, funkce má vrátit None.
• Funkce terminal má přijmout board a vrátit booleovskou hodnotu označující, zda hra skončila.
  • Pokud hra skončila, protože někdo vyhrál nebo jsou všechna políčka obsazena bez vítěze, funkce má vrátit True.
  • Pokud hra stále probíhá, funkce má naopak vrátit False.
• Funkce utility má přijmout koncový stav board a vrátit užitek této desky.
  • Pokud vyhrál X, užitek je 1. Pokud vyhrál O, užitek je -1. Pokud hra skončila remízou, užitek je 0.
  • Můžete předpokládat, že utility bude volána pro board pouze tehdy, když terminal(board) je True.
• Funkce minimax má přijmout board a vrátit optimální tah pro hráče, který je na této desce na tahu.
  • Vrácený tah má být optimální akce (i, j) z povolených akcí na desce. Pokud je více tahů stejně optimálních, je přípustný kterýkoli z nich.
  • Pokud board představuje koncovou desku, funkce minimax má vrátit None.

U všech funkcí přijímajících board můžete předpokládat platnou desku: seznam obsahuje tři řádky a v každém jsou tři hodnoty X, O nebo EMPTY. Poskytnuté deklarace funkcí, tedy pořadí ani počet jejich argumentů, neměňte.

Až budou všechny funkce správně implementovány, měli byste být schopni spustit python runner.py a hrát proti své AI. Protože při optimální hře obou stran piškvorky končí remízou, nikdy byste AI neměli porazit. Pokud ale sami nebudete hrát optimálně, může porazit ona vás!

Nápověda

• Pokud chcete funkce testovat v jiném souboru Pythonu, můžete je importovat například řádkem from tictactoe import initial_state.
• Do tictactoe.py můžete přidat další pomocné funkce, pokud jejich názvy nekolidují s názvy funkcí nebo proměnných, které již v modulu existují.
• Alfa-beta prořezávání je volitelné, ale může zrychlit běh vaší AI!

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

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

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

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

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