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

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 b^d noduri, avem b * 1 * b * 1 ..., deci b^d/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