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

From Algopedia
Revision as of 17:08, 28 May 2014 by Cata (talk | contribs) (Tabele de final (endgame tablebases - EGTB))

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Ora trecută am vorbit despre algoritmii minimax, alpha-beta, diverse optimizări la alpha-beta și puțin despre reprezentarea tablei folosind bitboards.

Proof-Number search

Alpha-beta se aplică bine în jocul de mijloc. Spre final, însă, arborele de joc devine suficient de mic încât să poată fi rezolvat. Consecințele unui pion pierdut în jocul de mijloc nu devin evidente pentru încă 60-80 de semimutări sau chiar mai multe. În finalul jocului, orizontul se apropie, iar un avantaj material poate fi convertit într-o promoție sau chiar în mat. În aceste situații, aplicăm algoritmul PN, care caută mai agresiv liniile câștigătoare.

O altă situație unde PN bate alpha-beta sunt jocurile unde evaluarea statică este grea. Dacă situația materială nu este un indiciu bun al balanței de putere, atunci evaluarea statică trebuie să judece o poziție bazându-se pe principii mult mai greu de pus în cod. Exemple: antișah (suicide chess), Lines of Action.

  • prezentarea algoritmului, exemplu
  • definiție most proving node
  • considerente de memorie
  • recuperarea memoriei prin dealocarea arborilor salvați
  • cum stocăm demonstrația?
  • metode de accelerare
    • dacă actualizarea unui nod nu mai duce la actualizarea părintelui, putem opri propagarea
    • mai mult, putem începe de la acel nod căutarea următorului MPN
    • un nod poate fi inițializat cu 1/numărul de mutări în loc de 1/1, ceea ce accelerează demonstrația cu factori de 2...8
  • despre transpoziții
    • sunt o problemă reală: dacă le ignorăm, mărimea arborelui poate crește de câteva ori
    • algoritm teoretic, foarte complicat, bazat pe expresii booleene, care identifică corect MPN
    • în practică, selectăm un MPN neoptim, dar avem grijă să-i actualizăm toți părinții
  • despre repetiții
    • în practică, a doua repetiție este marcată ca nod terminal (remiză)

Shameless plug: http://catalin.francu.com/nilatac/book.php

Tabele de final (endgame tablebases - EGTB)

Este util să putem răspunde în O(1) (printr-o căutare într-o bază de date) la orice poziție cu cel mult k piese pe tablă. Aceasta poate crește incredibil viteza de calcul a unui program.

EGTB se aplică bine la șah, unde au fost calculate toate pozițiile cu până la 7 piese pe tablă. Ea se pretează mai puțin la jocuri ca Reversi (Othello), deoarece finalul are multe piese pe tablă, nu puține. În plus, multe din pozițiile de final sunt ilegale (nu se poate ajunge la ele printr-o succesiune de mutări).

  • tehnică: analiză retrogradă, pornind de la mat, capturi sau promoții
  • verificare prin analiză înainte
  • codificarea pozițiilor
    • indexarea după poziția celor doi regi (la șah)
    • rotații, simetrii
    • conversia rapidă a unei poziții într-o combinare și invers
  • problema rocadei (poate fi ignorată) și a capturilor en passant (nu poate fi ignorată)
  • spațiu necesar pe disc: 100 TB pentru 7 piese, circa 7 GB pentru 5 piese
  • necesită acces aleator în fișiere comprimate (LZMA / 7z / xz știu asta)
  • diferența între tablebase (cu distanța până la mat) și bitbase (unul sau doi biți pentru rezultatul final)
  • diferența între distance-to-mate (DTM) și distance-to-conversion (DTC)
    • DTM este mult mai util, dar riscă să nu încapă pe un octet
    • DTC încape (în general) pe un octet, dar duce la mat pe căi ocolite
    • DTC evită mai bine remizele după 50 de mutări
  • învățăminte pentru jucătorii umani
  • maturi în peste 50 de mutări
    • modificarea regulilor jocului de șah

În limita timpului

Cazuri-limită la alpha-beta:

  • quiescent search (probleme la orizont)
  • tratarea repetițiilor drept remize, exemple caraghioase
  • pondering