Clasele 11-12 lecția 3 - 2 oct 2015: Difference between revisions

From Algopedia
Jump to navigationJump to search
No edit summary
 
(No difference)

Latest revision as of 12:56, 6 October 2015

Prima oră

Teoria jocurilor

Astăzi am discutat noțiuni introductive din teoria jocurilor și am văzut cum se calculează strategia optimă de câștig în jocurile imparțiale.

Un joc este imparțial dacă pentru orice stare a jocului ambii jucători au aceleași mutări la dispoziție.

Astfel, pentru orice stare a unui joc imparțial putem asocia o valoare de adevăr care spune dacă jucătorul aflat la mutare în acea stare are sau nu strategie sigură de gâștig indiferent de mutările ulterioare ale adversarului.

Regulile jocului vor defini cel puțin o stare ca fiind câștigătoare sau pierzătoare. Iar pe baza valorilor de adevăr asociate acestor stări va trebui să stabilim valoarea de adevăr ale tuturor celorlalte stări ale jocului. Pentru aceasta vom folosi următoarea formulă:

Câștig[stareCurentă] = !(Caștig[stareViitoare1] && Caștig[stareViitoare1] && ... && Caștig[stareViitoareK])

unde:
Câștig[stare] = valoarea de adevăr asociată stării stare
stareViitoareI = mulțimea stărilor în care jucătorul aflat la mutare
                 în starea stareCurentă poate aduce jocul printr-o singură mutare

Interpretarea acestei formule este:

  • dacă, indiferent de mutarea pe care o va face, jucătorul curent va duce jocul într-o stare câștigătoare (pentru adversar) atunci starea curentă este pierzătoare (va pierde / nu are strategie optimă de câștig);
  • dacă există cel puțin o mutare prin care jucătorul curent va duce jocul într-o stare pierzătoare (pentru adversar) atunci starea curentă este câștigătoare (va câștiga / are cel puțin o strategie optimă de câștig).

1282 - Game Tree

Se dă un arbore cu rădăcină. Cei joi jucători pornesc din rădăcină și aleg alternativ pe care dintre fiii nodului curent să coboare în arbore. Toate frunzele au asociată o valoare:

  • +1 - victorie pentru primul jucător;
  • 0 - remiză;
  • -1 - victorie pentru cel de-al doilea jucător.

Se cere să se spună care va fi deznodământul jocului dacă cei doi jucători aplică o strategie optimă.

A doua oră

În a doua oră am aplicat formula de calcul prezentată în prima oră pentru un joc cu un număr exponențial de stări (Coins (Infoarena)). Mai exact, am asociat fiecărei stări a jocului un număr întreg care, scris în baza 2, are următoarea interpretare: fiecare bit de 1 corespunde unei căsuțe pe care se află un galben și fiecare bit de 0 corespunde unei căsuțe libere.

În esență, problema ne cere să calculă valorile de adevăr asociate elementelor unei mulțimi de cel mult 100000 de stări date.

Soluția este să calculăm valoarile de adevăr asociate tuturor celor 222 stări posibile ale jocului și apoi să răspundem la fiecare dintre întrebările date în O(1).

Implementarea soluției

Primul lucru pe care trebuie să-l stabilim este modul de codificare al stărilor jocului în întregi. Vom vedea ulterior că implementarea este mai ușoară atunci când căsuțelor din stânga le corespund biții cei mai puțin semnificativi.

int galben;
int stare = 0;
int cost = 0;
for(int j = 0; j < 22; ++j){
  scanf("%d", &galben);
  stare = stare ^ ((1 << j) * galben);
  cost += galben;
}

În pasul următor vom încerca să calculăm (recursiv) valoarea de adevăr asociată unei stări.

bool castigatoare(int stare, int depth = 0) {
  /*
  for (int i = 0; i < depth; ++i) {
    printf("  ");
  }
  printf("%d\n", stare);//*/
  bool raspuns = true;
  if ((stare & (stare + 1)) != 0) {
    int i;
    int ultimul0 = -1;
    for (i = 0; i < 22; ++i) {
      if (stare & (1 << i)) {
        if (ultimul0 != -1) {
          int nouaStare = stare ^ (1 << ultimul0) ^ (1 << i);
          raspuns &= castigatoare(nouaStare, depth + 1);
        }
      } else {
        ultimul0 = i;
      }
    }
    raspuns = !raspuns;
  }
  return raspuns;
}

Problema cu această metodă este că timpul de execuție devine exponențial în numărul de stări. O optimizare facilă ar fi memoizarea, care ar face ca timpul de execuție să devină liniar în numărul de stări. Deși complexitatea acestei abordări este bună, nu o vom folosi deoarece un algoritm iterativ are constanta per operație mult mai mică.

Folosindu-ne de observația că putem calcula valoarea de adevăr a unei stări dacă știm valoarea de adevăr a tuturor stărilor care au asociat un număr strict mai mic decât numărul asociat stării curente putem calcula aceste valori iterativ, în ordine, de la 0 la 222 - 1 astfel:

bool Castigatoare[1 << 22];

for (int stare = 0; stare < (1 << 22); ++stare) {
  bool raspuns = true;
  // ...
  // calculează răspunsul pentru stare în baza valorilor din array-ului Castigatoare
  // ...
  Castigatoare[stare] = raspuns;
}

Temă

Pentru data viitoare veți avea de rezolvat următoarele probleme: