Note de curs, clasele 9-10, 22 mai 2014

From Algopedia
Jump to: navigation, search

Arbori de joc și metode de evaluare

Introducere

Terminologie:

  • În această lecție, prin joc vom înțelege un joc între doi jucători, numiți Alb și Negru, care mută alternativ. Albul mută primul.
  • În general, vom da exemple din jocul de șah, dar nu numai.
  • O mutare este o pereche de semimutări (engl. ply / plies), una a albului și una a negrului.

Cum scriem un program care să joace un joc? La modul general, programul trebuie să „înțeleagă” și să respecte regulile jocului. Concret, avem nevoie de trei lucruri:

  1. să reprezentăm corect informațiile despre o poziție;
  2. dintr-o poziție, să generăm corect lista de mutări legale;
  3. când este rândul nostru, să alegem mutarea care pare cea mai bună.

În această lecție, vom discuta mai mult despre (3) și numai în limita timpului despre (1) și (2).

O poziție este starea jocului la un moment dat. Pentru șah, acesta constă din:

  • poziția pieselor pe tablă;
  • partea care este la mutare;
  • informații despre ce rocade mai pot face albul și negrul;
  • pionul care poate fi capturat en passant, dacă există;
  • numărul de semimutări efectuate de la ultima captură sau împingere de pion;
  • opționale: numărul semimutării, istoricul partidei (pentru regula repetiției), valorile cronometrelor.

Exemple

X și 0

X și 0 prezintă un (minim) interes didactic deoarece numărul total de poziții este foarte mic. Clar, el nu depășește 39 ≅ 20.000. În fapt, multe din aceste poziții sunt ilegale (albul sau negrul au câștigat deja, numărul de piese albe/negre este incorect etc.). Dacă eliminăm și rotațiile și simetriile, rămân 765 de poziții unice[1].

Suma 15

Jocul se joacă cu 9 cărți dintr-un pachet (de la A la 9 de cupă). Pe rând, fiecare jucător alege o carte din cele rămase. Dacă, la un moment dat, un jucător deține 3 cărți cu suma 15, el câștigă. Dacă după cele 9 mutări niciun jucător nu are suma 15, jocul se termină remiză. Care este strategia optimă?

Quarto

Dintre miile de jocuri de gândire, îl menționez și pe acesta, pentru că implică biți și puteri ale lui 2. :-) Vezi http://www.lifeishao.com/quarto/ .

Arbori de joc

Cu o reprezentare a tablei și cu un generator de mutări putem scrie un algoritm care să joace legal. El va ști să mute la întâmplare și să valideze mutările adversarului, dar cam atât. Cum alegem mutări cât mai bune?

Cum aleg oamenii mutări cât mai bune? Printr-o combinație de

  • cunoaștere a teoriei, care dă niște principii foarte generale: regele nu trebuie expus, piesele trebuie puse în poziții avantajoase etc.
  • analiză a poziției rezultate: avantajul material este important, lanțurile rupte de pioni sunt rele, perechea de nebuni este bună
  • experiență în poziții identice sau similare: carte de deschideri, analiza partidelor altor jucători
  • dar mai ales, analiza arborescentă, care ia în calcul răspunsurile adversarului, răspunsurile noastre la acele răspunsuri etc.

De aici decurge conceptul de arbore de joc, construit dintr-o poziție dată. (imagine) În practică, el este un graf, deoarece pot exista repetiții (1. Nc3 Nc6 2. Nb1 Nb8) și transpoziții (1. d4 d5 2. c4 / 1. c4 d5 2. d4).

Pentru jocuri ca X și 0 (sau Suma 15, dacă încă nu v-ați prins), arborele de joc poate fi explorat complet, deci putem juca jocul perfect. Pentru șah, numărul de poziții legale este estimat la 1047, iar mărimea arborelui la 10123 noduri[2]. De aceea, recurgem la o combinație de:

  1. evaluare arborescentă, la o adâncime dată de timpul de gândire permis, nivelul de joc dorit etc.;
  2. funcție statică de evaluare a unei poziții, numită și euristică, pe care o aplicăm în frunzele arborelui.

Pentru un arbore de joc, vom face referire la adâncimea lui, d, și la factorul de ramificare, b. Factorul de ramificare este numărul mediu de mutări posibile dintr-o poziție, care la X și 0 este 4, iar la șah (estimat) 35.

Evaluarea statică

Funcția de evaluare statică atribuie unei poziții o valoare între -∞ (negrul câștigă) și +∞ (albul câștigă). Valoarea arată cât de bine stă albul. Pentru șah, este natural ca evaluarea să depindă de valoarea cumulativă a pieselor: dacă albul are un cal în plus, valoarea ar putea fi +3. La aceasta se adaugă și informații poziționale: dominarea centrului, regele bine adăpostit, structură bună de pioni etc.

Algoritmul Minimax

(imagine cu un exemplu de arbore de joc)

Presupunând că am decis să tai arborele de joc la 6 semimutări în adâncime și că am atribuit valori statice tuturor frunzelor, cum propag acele valori spre rădăcină? Dacă toate frunzele ar avea valori +∞ și -∞, atunci propagarea este ușoară: albul câștigă un nod dacă oricare dintre fii are valoarea +∞ și pierde un nod dacă toți' fiii au valoarea -∞. Un astfel de arbore se numește arbore și/sau.

La modul general,

  • un nod în care albul este la mutare are valoarea egală cu maximul valorilor fiilor;
  • un nod în care negrul este la mutare are valoarea egală cu minimul valorilor fiilor.

Algoritmul este:

function minimax(nod, adâncime, jucător) {
  if (adâncime = 0 sau nodul este o poziție terminală) {
    return evaluareStatică(nod);
  }

  if (jucător == ALB) {
    scor = -∞;
    mutări = genereazăMutări(nod);
    for (m in mutări) {
      nod2 = mută(nod, m);
      scor = max(scor, minimax(nod2, adâncime - 1, NEGRU);
    }
  } else {
    scor = +∞;
    mutări = genereazăMutări(nod);
    for (m in mutări) {
      nod2 = mută(nod, m);
      scor = min(scor, minimax(nod2, adâncime - 1, ALB);
    }
  }

  return scor;
}

Acest algoritm, pe hardware-ul de azi, e suficient ca să bată orice jucător amator de șah. Tehnic vorbind, este nevoie și de o carte de deschideri, oricât de bună ar fi euristica statică. Altfel, la începutul partidei, toate mutările par la fel de promițătoare.

Din algoritmul Minimax se naște ideea de variantă principală: acea cale din arbore pe care ne așteptăm să o urmeze jucătorii în practică. Ea duce din fiecare nod spre acel fiu care are valoare egală cu a nodului.

Algoritmul Negamax

Putem aduce o îmbunătățire de stil programului de mai sus, ca să nu mai duplicăm cod. În loc să dăm valori pozitive pentru alb și negative pentru negru, modificăm evaluarea statică să dea valori pozitive pentru partea la mutare și negative pentru adversar.

function negamax(nod, adâncime, jucător) {
  if (adâncime = 0 sau nodul este o poziție terminală) {
    return evaluareStatică(nod);
  }

  scor = -∞;
  mutări = genereazăMutări(nod);
  for (m in mutări) {
    nod2 = mută(nod, m);
    scor = max(scor, -negamax(nod2, adâncime - 1, -jucător);
  }

  return scor;
}

Folosim aici două proprietăți: una matematică, anume max(a,b)=-min(-a,-b), și una a jocului de șah, anume că are sumă zero: o poziție este exact cu atât mai bună pentru mine cu cât este mai rea pentru adversar.

Alpha-beta

Alpha-beta este o metodă de a tăia bucăți mari din arborele minimax, fără a le mai evalua, garantând însă că valoarea finală a nodului-rădăcină este aceeași.

Să considerăm următorul experiment. În urma unui pariu pierdut, un prieten trebuie să-mi dea un obiect. Dar regula este că obiectele sunt grupate în diverse cutii. Eu aleg cutia din care vreau să primesc un obiect, iar prietenul alege obiectul pe care mi-l dă din acea cutie.

Desigur, maximul pe care îl pot obține se determină cu algoritmul minimax: voi alege cutia care maximizează valoarea minimă a obiectelor. Dar nu este nevoie să examinez toate obiectele pentru a afla această valoare. Să presupunem că în prima cutie obiectul minim are valoarea 5. Dacă în a doua cutie primul obiect examinat are valoarea 4, pot ignora tot restul cutiei, deoarece obiectul minim din acea cutie va fi cel mult 4.

Așadar, atunci când un nod X își evaluează fii, dacă primul fiu Y1 are valoarea v, și dacă al doilea fiu Y2 are un fiu de valoare < v, evaluarea lui Y2 poate fi oprită instantaneu, deoarece valoarea lui este sigur mai rea decât a lui Y1.

Asignăm fiecărui nod două valori: α este scorul minim de care albul este asigurat, iar β este scorul maxim de care negrul este asigurat.

function alphabeta(nod, adâncime, α, β, jucător) {
  if (adâncime = 0 sau nodul este o poziție terminală) {
    return evaluareStatică(nod);
  }

  if (jucător == ALB) {
    scor = -∞;
    mutări = genereazăMutări(nod);
    for (m in mutări și α < β) {
      nod2 = mută(nod, m);
      α = max(α, alphabeta(nod2, adâncime - 1, α, β, NEGRU);
    }
    return α;
  } else {
    scor = +∞;
    mutări = genereazăMutări(nod);
    for (m in mutări și α < β) {
      nod2 = mută(nod, m);
      β = min(β, alphabeta(nod2, adâncime - 1, α, β, ALB);
    }
    return β;
  }
}

Sau, în varianta cu Negamax:

function negamax(nod, adâncime, jucător) {
  if (adâncime = 0 sau nodul este o poziție terminală) {
    return evaluareStatică(nod);
  }

  mutări = genereazăMutări(nod);
  for (m in mutări și α < β) {
    nod2 = mută(nod, m);
    α = max(α, -negamax(nod2, adâncime - 1, -β, -α, -jucător);
  }

  return min(α, β);  // β se mai numește și „fail hard”
}

Ordonarea mutărilor

Alpha-beta ajută mult și dacă mutările sunt evaluate într-o ordine aleatoare. Totuși, dacă am reuși să evaluăm întâi mutarea cea mai bună, atunci toate mutările următoare ar fi rapid tăiate din arbore. Desigur, nu știm a priori care este mutarea cea mai bună -- tocmai asta încercăm să aflăm. Dar dacă am reuși, atunci:

  • pe nivelurile pare toate cele b mutări trebuie evaluate;
  • pe nivelurile impare doar prima mutare trebuie evaluată.

Astfel, pentru un arbore de adâncime d, în loc să evaluăm b^{d} noduri, vom evalua doar b^{{d/2}}={\sqrt  {b^{d}}} noduri. Cu alte cuvinte, alpha-beta ne permite să dublăm adâncimea de căutare a arborelui! Echivalent, putem să ne gândim la factorul de ramificare pentru șah ca fiind {\sqrt  {35}}\approx 6.

Cum îmbunătățim ordonarea mutărilor? Aici există nenumărate trucuri, dintre care amintim:

  • Generarăm mutările într-o ordine preferențială, de exemplu capturile înaintea non-capturilor.
  • Generăm mutările una câte una, căci poate nu ne sunt toate necesare.
  • Reținem, pe fiecare nivel din alpha-beta, cea mai promițătoare mutare, numită și killer move. Dacă ea este legală în contextul dat, o evaluăm prima.
  • Evaluăm arborele iterativ (iterative deepening) și reținem, în fiecare nod, cea mai bună mutare produsă de căutarea anterioară. Aceasta este o strategie bună și pentru gestiunea timpului.

În limita timpului

  • reprezentarea tablei: bitboards
  • generarea mutărilor: exemple pentru pioni, cai
  • carte de deschideri
  • tabele de final: analiză retrogradă, simetrii, Nalimov, DTM / DTC, noutăți teoretice despre KQvKR
  • proof number search, alte jocuri rezolvate
  • gestiunea timpului
  • pondering
  • probleme de orizont, quiescent search

Referințe

  1. Vezi http://en.wikipedia.org/wiki/Tic-tac-toe
  2. Vezi http://en.wikipedia.org/wiki/Game_complexity