… E Scrabble ha dimostrato che PSPACE è completo

Essendo stato inventato negli Stati Uniti a metà del 20 ° secolo, Scrabble è ora disponibile in dozzine di lingue e vende in numeri misurati in centinaia di milioni. Questo lo rende uno dei giochi più popolari al mondo.

Ciò ha naturalmente suscitato l'interesse dei teorici dei giochi. Dal momento che Scrabble è un gioco di tale successo, diventa una domanda naturale determinare la complessità computazionale di trovare un gioco ottimale, affermano Michael Lampis al KTH Royal Institute of Technology in Svezia e alcuni amici.

La stessa domanda è stata posta con successo a molti giochi da tavolo, come scacchi, Go e Othello, che tendono ad essere PSPACE o EXPTIME-complete. Ma Scrabble è più complicato perché i giocatori non conoscono l'ordine in cui verranno disegnate le tessere, il che significa che il caso gioca un ruolo maggiore.

La domanda a cui Lampis e compagni tentano di rispondere è questa: data una posizione a Scarabeo quanto è difficile determinare la migliore strategia di gioco?

Sottolineano che in un dato round, un giocatore di Scrabble deve affrontare due compiti: decidere quale parola formare e decidere dove posizionarla sul tabellone. Questi compiti sono correlati perché le parole che possono essere formate dipendono dalla posizione delle lettere sulla lavagna.

Ma quale di questi compiti è che rende difficile Scarabeo? Ciò che Lampis e compagni mostrano è che entrambi sono duri e danno una prova di ciascuno per sostenere la loro affermazione. È impressionante perché ci permette di 'vedere' perché Scrabble è difficile.

Stabiliamo che durante il corso di un gioco, i giocatori di Scrabble devono eseguire non uno, ma due compiti computazionalmente difficili, che è probabilmente il motivo per cui Scrabble è così divertente da giocare, scrivono.

Questo non vuol dire che i teorici della complessità computazionale siano finiti e spolverati con Scrabble. Il loro prossimo compito è scoprire se esiste un algoritmo tempo-polinomiale per determinare la mossa che massimizzerebbe il punteggio ottenuto in questo round.

Ora sarebbe utile!

Rif: arxiv.org/abs/1201.5298 : Scrabble è completo per PSPACE

nascondere