Note de curs, clasele 11-12, 1 martie 2013
From Algopedia
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