Artificial Stupidity: One Google Engineer’s Algorithms for Bad Chess Playing

Cosa succede quando applichiamo tecnologie moderne all’avanguardia al vecchio gioco degli scacchi? E cosa succede quando un disadattato annoiato con un surplus di potenza di calcolo conduce i suoi strani esperimenti domestici sul gioco?

Quest’anno un ingegnere del software della Pennsylvania che si fa chiamare Tom Murphy VII ha deciso di creare alcuni algoritmi di scacchi ridicolmente cattivi usando di tutto, dall’apprendimento automatico e dalle reti neurali a una quantità gratuita di cicli della CPU-e poi ha snocciolato i cattivi algoritmi l’uno contro l’altro per creare un “torneo di sciocchi.”

” È la mia idea di divertimento… ” dice Murphy in un video umoristico che descrive gli esperimenti.

Prime mosse

Murphy ha il cervello per tirarlo fuori. Ci dice che nel 2007 ha difeso il suo dottorato in informatica. alla Carnegie Mellon-che era lo stesso anno gli studenti hanno iniziato a tenere la conferenza annuale SIGBOVIK il giorno del pesce d’aprile. Sponsorizzato dalla “Association for Computational Heresy”, era una sorta di gruppo di interesse speciale satirico dedicato a un ricercatore fittizio di nome” Harry Quizmaster Bovik”, e includeva una chiamata per documenti stupidi su argomenti come ” stupidità artificiale.”

Negli ultimi 11 anni, Murphy è stato un senior staff software engineer presso Google (nei suoi uffici di Pittsburgh). Ma quest’anno ha deciso di tornare di nuovo per la conferenza del pesce d’aprile — e di nuovo, ha contribuito a una sua ricerca umoristica.

Murphy si vanta con orgoglio che alcune delle sue presentazioni passate hanno coinvolto indagini ridicole che erano “indistinguibili dalla ricerca “reale” (ad esempio il primo livello di Super Mario Bros. è facile con ordini lessicografici e il viaggio nel tempo ha alcune citazioni 20 nella ricerca accademica “reale”).

Ma questo fu l’anno in cui Murphy rivolse la sua attenzione agli scacchi.

Lascia che i giochi inizino

Nel gioco iniziale di Murphy, i giocatori umani sono bendati, costringendoli a ricordare dove sono i pezzi. Ma qual è l’equivalente di un computer? Dicendogli dove si trovano i pezzi ma non quali pezzi sono (o anche di che colore)…

Naturalmente, il computer non sarebbe fornito con le mosse che portano a una posizione sia. Non saprebbe nemmeno di chi fosse il turno. Sì, c’è la possibilità che il re del computer sia sotto controllo — a quel punto praticamente ogni mossa è illegale tranne una mossa che porta il tuo re in salvo. Ma per aggirare il problema, Tom ha creato un programma che genera un elenco di possibili mosse, classificate in ordine di preferenza — da cui verrà scelta la prima mossa legale.

“Mi piace giocare contro di esso, perché non è molto buono”, dice Murphy nel video. “Ma la domanda naturale è come non-molto-buono è?”Testarlo contro i programmi di gioco degli scacchi dimostra che sì, perde con grande regolarità-come in” ogni singola volta.”

Poi ha deciso di costruire altri algoritmi di scacchi cattivi, in modo da poter confrontare le loro prestazioni relative

Uno aveva una preferenza per posizionare i suoi pezzi sui quadrati bianchi quando sta giocando in bianco, e sui quadrati neri quando sta giocando in nero. (Il suo avversario? Un algoritmo che preferiva posizionare i suoi pezzi su quadrati di colore opposto.) Alla fine, entrambi hanno giocato piuttosto male. “Hanno una preferenza, ma in realtà non ha a che fare con la vittoria.”In realtà, sono entrambi solo un po’ peggio dell’algoritmo che sceglie le sue mosse a caso.

C’erano anche due algoritmi che chiamò “Huddle” e “Swarm” — in cui un giocatore automatico cerca le mosse mantenendo i suoi pezzi vicino al proprio re, mentre l’altro cerca le mosse posizionando i suoi pezzi vicino al re del suo avversario. Questo a volte porta il re di Huddle a essere costretto a seguire le proprie pedine su tutta la linea, in cui almeno alcuni casi la sua pedina poi accidentalmente promossa in pezzi più potenti e inavvertitamente scacchiera il re avversario.

Ma più spesso, funziona nell’altro modo. “Se si dispone di una preferenza per attaccare l’avversario, si sta andando a scacco matto accidentalmente a volte.”Nel video, Murphy rivela che tra gli algoritmi di scacchi cattivi, questo è sorprendentemente non così male. “‘Sciame’ è infatti molto meglio di ‘ Mossa casuale.'”

E un’altra strategia di successo è un algoritmo che dà la priorità a quattro tipi specifici di mossa (in questo ordine): scacco matto, controllare, catturare un pezzo o spingere nel territorio del suo avversario.

Ma ci sono altre idee terribili — come un algoritmo che cerca di rispecchiare i pezzi del suo avversario, o di spostare tutti i suoi pezzi dall’altra parte del tabellone. Un algoritmo sceglie semplicemente qualsiasi mossa viene prima in ordine alfabetico.

E c’è un altro algoritmo in cui ogni mossa viene scelta da un elenco di possibili mosse – con le scelte dettate arbitrariamente dalle cifre di pi

Survival in Chessland

Ma alla fine il suo algoritmo più elaborato è iniziato con una domanda: quale singolo pezzo degli scacchi è per lo più probabile che “sopravviva” — per rimanere sul tabellone fino alla fine del gioco, ed emergendo vittorioso con tutti i suoi compagni di scacchi? Indagando doverosamente la risposta, Murphy ha fatto visita al sito di scacchi free/libre LiChess.org (che ora vede più di un milione di giochi al giorno). Offre anche giochi per il download-così Murphy scaricato tutti i 506.000.416 di loro.

Ha riassunto i risultati in un documento chiamato “Survival in Chessland”, che spiega la sua metodologia. Murphy ha scaricato ogni gioco completo che hanno avuto fino a novembre di 2018, anche se altri 200 milioni sono apparentemente diventati disponibili negli otto mesi successivi. Anche il suo raggio di novembre ha rappresentato un enorme 875GB di giochi di scacchi,” quindi l’elaborazione di questi ha preso una certa cura per l’efficienza e il parallelismo”, dice Murphy nel video.

“Fortunatamente, ho un computer con solo un numero osceno di core e RAM veramente eccessiva, quindi devi usarlo per qualcosa.”

Er, quanto osceno? In una e-mail, descrive il suo sistema domestico “gratuito”, un 32-core AMD ThreadRipper 2990WX. L’esecuzione dei programmi C++ multi-threaded per alcune ore è stata sufficiente per scricchiolare l’intero set di dati. “Penso che la gente sottovaluti ciò che si può fare in modo efficiente con una singola macchina!”

“Il lavoro in questione è piuttosto semplice: Analizzo il PGN (che descrive il gioco), quindi eseguo le mosse nel gioco, tenendo traccia del destino di ogni pezzo, e quindi sommare i conteggi per ogni destino””

” Fondamentalmente ho scritto tutto il codice da zero, perché questo è più divertente che far funzionare il codice di altre persone. :)”

E poi questo ha portato a più cattivi algoritmi di gioco degli scacchi. In primo luogo, c’è quello che sposta solo i pezzi in quei quadrati dove sono statisticamente più probabilità di sopravvivere. O semplicemente alle piazze dove sono più probabilità di essere alla fine di una partita. E altri algoritmi fanno l’esatto contrario: spostando i pezzi in quadrati dove hanno meno probabilità di sopravvivere (o finire). Due algoritmi calcolano quale quadrato ha il più alto tasso di sopravvivenza (rispetto al tasso di cattura) per un pezzo su ogni quadrato, con un algoritmo che cerca il rapporto più alto favorendo la sopravvivenza — e l’algoritmo “fatalista” che cerca il rapporto più basso.

“Stranamente, ha le migliori possibilità di vincita di queste strategie.”

E infine, ha deciso di confrontarli tutti con il motore di scacchi dello Stoccafisso su più livelli (incluso uno speciale algoritmo in cui è costretto a giocare la sua mossa meno promettente). “Guardando i risultati, non sorprende che questa sia la strategia peggiore in generale, e riesce a perdere quasi tutti.”

Ma ricorda l’algoritmo “bendato” originale di Tom, che non sapeva quale pezzo occupasse un quadrato (o anche il suo colore)? Ha deciso di aumentarlo con una rete neurale, che ha eseguito l’apprendimento automatico-utilizzando i miliardi di posizioni disponibili nei giochi da LiChess.org. Ora era in grado di prevedere correttamente i pezzi effettivi in ogni posizione con una precisione del 100%-circa un quinto del tempo. E anche quando è sbagliato, è solo erroneamente indovinato una media di 3,22 pezzi per ogni posizione.

E questo diventa un punto di partenza per calcoli ancora più selvaggi. Ad un certo punto, deduce che tutti i giochi nel loro database alla fine passano attraverso 21.553.382.902 posizioni uniche. Con 204GB puoi memorizzarli tutti — insieme alla prossima mossa-ma c’è un’altra statistica interessante. Un enorme 76% delle posizioni si è verificato esattamente una volta. “Quindi questi occupano molto spazio e non sono molto utili per giocare, perché è molto improbabile che li riveda mai più.”Buttando via queste posizioni una tantum, ogni altra possibile posizione di gioco può essere memorizzata con circa 500 MB di memoria. Questo può essere facilmente convertito in un algoritmo che riproduce la mossa più popolare per qualsiasi posizione che incontra (mentre si scambia in una mossa casuale se capita di trovarsi intrappolato in una posizione unica).

Ma poi c’è un trucco facile per batterlo. “Non appena faccio una mossa un po’ strana, inizia a suonare in modo casuale. E poi è molto facile da battere.”

Un esperimento finale coinvolge varie” diluizioni ” del motore dello Stoccafisso — in cui la sua mossa preferita viene sostituita da una mossa scelta casualmente x per cento del tempo.”

“Possiamo effettivamente valutare quanto è bravo un giocatore ora confrontandolo direttamente con una specifica diluizione di Stoccafisso…”

Dopo che tutti gli elaborati algoritmi di gioco degli scacchi di Murphy erano stati debitamente testati, ha riassunto i risultati in una tabella massiccia, e ha concluso trionfalmente il suo video annunciando che era finalmente pronto a perseguire altri interessi.

” Ora si passa al prossimo progetto, che sta insegnando a questo cane come giocare a scacchi.”

• Cosa succede quando l’apprendimento automatico porta l’umanità a risposte che non capiamo?
• Incontra Sophie, il robot noodle-making.
• Dopo 15 anni, i ricercatori svelano un braccio artificiale che può sentire.