03 Adversarial

Jak hledat řešení, když někdo hraje proti nám. Minimalizace soupeřova zisku. Jak prořezat strom, abychom lépe viděli.

Po tomto cvičení student

• rozumí Minimax algoritmu a umí jej na malých úlohách simulovat;
• chápe $\alpha-\beta$ prořezávání a umí jej na malých úlohách simulovat, umí určit, které větve není třeba prohledávat, umí nastavit takové pořadí expanze jednotlivých větví, aby se dalo prořezat co nejvíce (nebo co nejméně) větví;
• rozumí zadání druhé povinné úlohy Reversi.

• $\alpha,\beta$, jak sestrojit optimální řazení uzlů
• kolik dokážeme (jak velký prostor) ušetřit pomocí $\alpha-\beta$ prořezávání za předpokladu optimálního řazení uzlů.
• představení reversi

• $\alpha,\beta$ kvíz, jak sestrojit optimální řazení uzlů
• Zadání dostanete na cvičení

• vysvětlení $\alpha,\beta$ prořezávání na příkladu
• $\alpha, \beta$ online: Ukázka řešení 1, Ukázka řešení 2
• Analýza složitosti a-b-analysis.pdf

• Představení úlohy Reversi
• Úkol: naprogramovat hráče Reversi, viz. Specifikace
• Vysvětlení turnajů

• Začněte pracovat na 2. povinné úloze 2. Reversi. Deadline v BRUTE.