Skip to content

Ziua 3 - Algoritmul MinMax

Algoritmul MinMax se folosește pentru a determina cea mai bună mutare într-un 0-sum game cu informație completă, perfectă și 2 jucători.

Slide-uri cu soluția și toți pașii algoritmului

Exemplu

Fie imaginea de mai jos:

img.png

Cât va fi valoarea din rădăcină după ce rulăm MinMax pe exemplul din imagine?

Informații generale

Date de intrare:

  • graful (nodurile, muchiile împreună cu costurile lor)
  • nodul din care începe căutarea (nodul-start)
  • un scop dat sub forma unei condiții pe care trebuie să o îndeplinească nodul căutat (se poate oferi chiar nodul propriu-zis, condiția fiind relația de egalitate cu acest nod). Vom numi mai departe nodul care îndeplinește condiția nod-scop
  • o estimare (euristică) a costului de la fiecare nod din graf la nodul (nodurile) scop.

Pașii algoritmului

Paşi:

  1. Generează arborele de joc până la stările scop sau o adâncime stabilită.

  2. Estimează scorul fiecărei stări terminale (frunză).

  3. Deplasează-te înapoi în arbore, de la nodurile frunze spre nodul rădăcină, determinând la fiecare nivel al arborelui valorile care reprezintă utilitatea (i.e. scorul) nodurilor aflate la acel nivel. Propagarea acestor valori la nivelurile anterioare se face prin intermediul nodurilor-părinte conform următoarei reguli:

    • dacă părintele este un nod de tip MAX, atribuie-i maximul dintre valorile fiiilor săi;
    • dacă părintele este un nod de tip MIN, atribuie-i minimul dintre valorile fiilor săi.

  4. Ajuns în nodul-rădăcină, alege pentru MAX mutarea care îl conduce către cel mai mare scor.

X și 0

Care este cea mai bună funcție de estimare a scorului pentru X și 0?

Soluție:

Vom considera estimarea scorului pentru simbolul X:

  • pentru fiecare simbol X aflat singur pe o linie / coloană / diagonală se adună 1 punct la scor
  • pentru fiecare 2 simboluri X aflate singure pe o linie / coloană / diagonală se adună 10 puncte la scor
  • pentru fiecare combinație de 3 X-uri în linie / coloană / diagonală se adună 100 de puncte
  • din acest scor se scade echivalentul pe 0

Pentru 0 estimarea este 0 minus estimarea pe X.

Exerciții

Rezolvă în Colab: MinMax

Exercițiul 1

Creează o clasă Nod care reține o stare a jocului. Poți porni de la clasa Nod explicitată în capitolul anterior.

Adaugă jucator_curent în constructorul clasei.

Salvează static simbolurile pentru MAX, MIN și spațiu GOL.

Adaugă următoarele funcții:

  • jucator_opus(self) -> returnează simbolul lui MAX dacă acum este starea lui MIN, simbolul lui MIN altfel;
  • scop(self) -> verifică dacă starea curentă e o stare scop. Dacă da, returnează simbolul câștigătorului sau 'remiză';
  • estimare(self) -> returnează estimarea scorului pentru starea curentă.

Poți folosi oricâte funcții ajutătoare.

# Rezolvă aici

Exercițiul 2

Aplică algoritmul MinMax pe X&0. Când rulezi codul algoritmul trebuie să lase utilizatorul să aleagă dacă vrea să joace împotriva computerului, computer vs computer sau player vs player. Pentru cazul player vs computer acesta va trebui să aleagă dacă vrea să înceapă jocul sau nu.

# Rezolvă aici