Note de curs, clasele 11-12, 1 martie 2013

From Algopedia
Revision as of 18:16, 1 March 2013 by Cata (talk | contribs) (Created page with "== Minimax, alpha-beta == * arbore de joc: nodurile sunt poziții, muchiile sunt mutări * trebuie să știm să generăm și să efectuăm mutări * de fapt este un graf: repet...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Minimax, alpha-beta

  • arbore de joc: nodurile sunt poziții, muchiile sunt mutări
  • trebuie să știm să generăm și să efectuăm mutări
  • de fapt este un graf: repetiții, transpoziții
  • poate fi redus prin simetrii, rotații
  • X și 0: arbore de joc simplu, (26K poziții după eliminarea simetriilor)
  • șah: arbore uriaș, nu mai poate fi evaluat complet
  • tăiem arborele când nu mai avem timp și evaluăm cu o funcție statică
    • material (pion 1, cal 3, ...)
    • pozițional (structura pionilor, pion trecut, pion pe linia a 7-a, rege expus)
  • numiți și arbori și/sau (sau pentru primul jucător, și pentru al doilea)
  • minimax
    • cu aceasta putem scrie un program care să ne bată
    • exemplu: colossus pe ZX Spectrum, procesor de 3,5 MHz, 48 kB de memorie
    • tehnic vorbind, e nevoie de o carte de deschideri, oricât de bună ar fi euristica statică
  • principal variation
  • negamax (pentru jocuri de sumă 0)
  • alpha-beta
    • exemplul cu cutiile: î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.
  • dacă ordonarea mutărilor este perfectă, în loc de bd noduri, avem b * 1 * b * 1 ..., deci bd/2 noduri
    • deci reducem factorul de ramificare la sqrt
    • la șah: 6 mutări în loc de 36
    • echivalent, dublăm adâncimea pe care o putem analiza
  • ajută dacă putem genera mutările una câte una (căci poate nu sunt toate necesare)
  • încă ne oferă informație perfectă
  • dorim să testăm mutările bune primele, pentru ca toate celelalte să genereze un cut-off
  • iterative deepening
    • pierde câtva timp, dar nu mult (exemplu: d = 6, b = 10 => 123,456/111,111 = 11% în plus
    • circa 1/b în plus în general
    • în schimb, ajută la ordonarea mutărilor (=> pruning), ceea ce îi permite să analizeze mai multe noduri
    • poate fi oprit oricând, ceea ce este bine pentru temporizare
  • quiescent search
    • problema: capturează un pion cu dama sau lasă dama în priză pe ultimul nivel
    • îmbunătățește valoarea alpha-beta, dar cere timp
    • evaluează capturile cele mai avantajoase primele (generatorul de mutări trebuie să permită asta)
  • contempt factor: care este un scor bun pentru remiză?
    • pozitiv pentru adversar, negativ pentru mine (dar poate fi și invers)
  • killer move heuristic (if applicable)
  • alpha-beta și transpoziții:
    • chei Zobrist (un fel de fingerprint pe 64 de biți)
    • zobrist[piesă][culoare][pătrat] pentru toate piesele, + o valoare în plus când negrul este la mutare
    • este utilă pentru că este incrementală (ușor de gestionat între mutări)
    • în tabela hash trebuie stocată adâncimea, valoarea și dacă a existat un cutoff
    • tabela hash este utilă și pentru stocarea PV (cea mai bună mutare), carte de deschideri etc.
  • repetiții: pot fi de dorit (șah etern) sau de evitat (dacă nu știu să dau mat cu un turn)
    • repetițiile pot apărea la poziții deja jucate sau poziții în arborele alpha-beta
    • dacă pur și simplu acord scorul de remiză unei poziții repetate, algoritmul poate face mutări nenaturale
    • o soluție este să acordăm scorul de remiză doar la a doua repetiție, dar algoritmul poate depăși cele 50 de mutări, poate juca „enervant” pentru un om
  • null move: căutare la D - 2 fără nicio mutare, înainte de a căuta mutările propriu-zise
    • nu se aplică bine la zugzwang
  • strategii de pondering: construiesc tot arborele, sau presupun una sau mai multe mutări
  • PV search (între alpha și alpha + 1, căci pariez că am găsit deja cea mai bună mutare a mea)
    • circa 10% eficiență
    • numită și Negascout

Problemă de logică

  • Monty Hall