Anatomia comparata di un giocatore artificiale di scacchi
- giochi ad informazione completa
- anatomia:
  (1) rappresentazione della scacchiera
  (2) generatore di mosse
  (3) ricerca
  (4) valutazione
  (5) interfaccia utente

(1) rappresentazione della scacchiera
  - occupazione di memoria
  - approccio piu' semplice: array da 64 byte
  - cornici di bogus square (velocizza la generazione di mosse)
  - approccio inverso: array da 32 byte (uno per pezzo) con bogus square per i
    pezzi catturati. Meno memoria occupata, problemi di promozione
  - mappa di bit (URSS late 60's)
    - un predicato su caselle: 64 bit (una word), un bit per casella
    - stato della scacchiera: 12 bitboard (96 byte vs 64)
    - altre bitboard: e.g. una bitboard per ogni pezzo che indichi quali casella
      sono attualmente tenute sotto scacco da quel pezzo
    - molte operazioni sono operazioni logiche su una word -> 1 ciclo di clock.
      - e.g. controlliamo se la regina bianca checka il re nero
      - e.g. dove puo' muovere il cavallo
  - transposition table
  - chiavi hash per scacchiere
    - 12*64 random numbers
    - scansione della scacchiera partendo con chiave hash 0
    - per ogni cella xor della chiave hash con il random number corrispondente
    - aggiornamento della chiave hash

(2) generatore di mosse
  - mosse legali
  - approcci (non e' una tassonomia):
    - generazione selettiva (e forward pruning)
    - generazione completa
  - generazione selettiva
    idea: scelgo le mosse migliori e proseguo la ricerca solo su quelle
    - human-like playing
    - non funge: scegliamo ad ogni passo le 5 mosse migliori, supponiamo di
      prenderci il 95% delle volte (veramente improbabile). In un gioco di 40
      mosse: 0.95^40 < 0.13 :-( Con il 99%: 0.99^40 = 0.67, scazza in 1/3 delle
      partite
  - idea di cutoff
  - generazione completa
    - idea: genero tutte le mosse, le ordino e procedo ricorsivamente fino a che
      non le ho esaminate tutte o ho un cutoff
    - vettori di movimento
    - mappe di movimento
  - tecnica implementativa: mosse pseudo legali

(3) ricerca
  - concetti e terminologia: giochi finiti, albero di gioco, funzione di
    valutazione, strategie, strategia ottimale
  - approccio infattibile per gli scacchi: pregenerare tutte le mosse migliori
    in ogni situazione di gioco
  - min-max
    - idea:
      - due giocatori: Min e Max
      - assumiamo esista funzione di valutazione > 0 se Max vince < 0 se Min
	vince, 0 se si pareggia
      - scopi di Min e di Max
      - entrambi i giocatori giocano senza sbagliare
    - esempio:            *
                        /   \
                       *     *
                      / \   / \
                     *   * *   *
                    5    6 -2  12
  - esplosione: B (branching factor), n (numero di ply).
    minMax = O(B^n) negli scacchi: 33^(40*2) = 3e121
    con 8 ply: 33^8 = 1'406'408'618'241
  - alfa-beta pruning
    - algoritmo:
       evaluate (node, alpha, beta)
       if node is a leaf
	   return the heuristic value of node
       if node is a minimizing node
	   for each child of node
	       beta = min (beta, evaluate (child, alpha, beta))
	       if beta <= alpha
		   return alpha
	   return beta
       if node is a maximizing node
	   for each child of node
	       alpha = max (alpha, evaluate (child, alpha, beta))
	       if beta <= alpha
		   return beta
	   return alpha
    - esempio (come sopra)
    - osservazioni:
      - simmetria dell'algoritmo
      - ricordarsi qual e' la mossa giusta
  - ordinamento delle mosse: quando alfa-beta e' efficiente?
    - osservazione: alfa-beta e' tanto piu' efficiente quanto prima trova buone
      mosse
    - ordinamento migliore: cercare per prima la mossa migliore (assurdo)
    - iterative deepening
      - si fa potenzialmente lavoro in piu', ma non e' poi cosi' male
  - stile di gioco di alfa-beta: molto cauto

(4) valutazione
  - importanza della funzione di valutazione
  - materiale (100, 300, 325, 500, 900)
  - fattore di mobilita' (numero di mosse legali)
  - controllo dello spazio statico

(5) interfaccia utente