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

From Algopedia
Jump to: navigation, search

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