[¯|¯] Il gioco degli scacchi, Mathematica e l'Algoritmo di Elo generalizzato
Marzo 19th, 2014 | by Marcello Colozzo |Cos'è l'algoritmo di Elo?
È ben spiegato su Wikipedia. Arpad Emrick Elo era un fisico ungherese e campione di scacchi. Scrisse il famoso algoritmo che permette di computare le "aspettative" (o probabilità ) di vittoria per una coppia di giocatori (A,B). Le probabilità si calcolano in funzione alla differenza di forza relativa o punteggio (ranking) di singolo giocatore. Più precisamente:
Pa = (1+10^(Rb-Ra)/400)^-1
dove Pa è la probabilità di vittoria per A. Qui Ra e Rb sono i punteggi di A e B. La probabilità per B è ovviamente:
Pb = 1-Pa = (1+10^(Ra-Rb)/400)^-1
Questo formule sono date ad hoc e se tracciamo i grafici, riusciamo a capire che sono ragionevoli. Sono noti Ra e Rb, per cui le formule ci permettono di calcolare le probabilità . L'algoritmo di Elo è basato sulla regola di aggiornamento dei punteggi di A e B. Più precisamente, A e B eseguono N partite. Si parte dalla partita 0 con punteggi noti e si aggiornano secondo la regola riportata su wikipedia. Ad esempio, se A ha una bassa probabilità ma, comunque, riesce a vincere, allora il suo punteggio avrà un buon incremento. Viceversa, se perde pur avendo un'alta probabilità . Facendo alcuni passaggi si ottiene che la (k+1)-esima probabilità si esprime attraverso la k-esima probabilità . In breve, abbiamo un processo ricorsivo, ovvero un sistema dinamico iterato, cioè una black box che accetta un input x_k=probabilità k-esima e, in base a una funzione di trasferimento f(x), emette un output x_(k+1)=
probabilità (k+1)-esima.
Possiamo modificare l'algoritmo in modo da applicarlo a un qualunque gioco a somma zero G. Le probabilità sono:
Pa = (1+e^b(Rb-Ra))^-1
e Pb=1-Pa
Qui b è un fattore di scala. Ora Ra e Rb vanno da -oo a +oo, e ciò permette di definire:
L'algoritmo è indeterminato quando A e B sono entrambi infinitamente forti o infinatamente deboli. Escludendo questi casi estremi si perviene a una Sistema dinamico iterato con funzione di trasferimento:
Qui W_a,k è un parametro che controlla l'esito della partita.
W_a,k = 1 se A vince la k-esima partita
W_a,k =0 altrimenti
Abbiamo, dunque, tutti gli ingredienti per implementare una simulazione con Mathematica, studiando il diagramma delle orbite e l'eventuale presenza di caos deterministico. C'è però un problema: ho dato in pasto a Mathematica il parametro W attraverso un pseudo random in {0,1}:
Ecco il risultato con una probabilità iniziale per A pari a 0.8:
Per maggiori dettagli, scarica il pdf al link seguente:
Algoritmo di Elo.
Tags: algoritmo di Elo, scacchi
Articoli correlati