Programmare un computer per giocare a scacchi

Programmare un computer per giocare a scacchi è l'articolo fondante degli scacchi per computer, scritto da Claude Shannon nel 1949. Tutti i programmi di scacchi passati e presenti sono ispirati da questo documento. Shannon presenta la sua strategia minimax basata su funzioni di valutazione. Propone due tipi di ricerca delle mosse da giocare (tipo A e tipo B) e rileva l'impossibilità di utilizzare una ricerca di forza bruta, in particolare a causa della limitata capacità di calcolo dei computer dell'epoca. La ricerca di tipo B, simile a quella umana, si concentra sulle posizioni e sui colpi più promettenti.

Nel suo articolo, Shannon, solleva l'impossibilità di calcolare tutte le possibili posizioni e colpi. Calcola un numero di mosse potenziali che hanno un significato durante una partita, un numero noto come "  numero Shannon  " .

L'articolo di Shannon fa molto di più che riassumere come dovrebbe essere una macchina in grado di giocare a scacchi. Solleva le sfide teoriche da risolvere, informa un vasto pubblico della possibilità di creare una macchina in grado di giocare a scacchi e stimola la ricerca di una generazione di programmatori di scacchi. Claude Shannon è il primo a pubblicare una descrizione coerente dell'applicazione del minimax al gioco degli scacchi e questo articolo lo rende uno dei candidati al titolo di fondatore dei programmi di scacchi, insieme ad Alan Turing con il suo programma del 1948 intitolato Turochamp e quel Konrad Zuse attraverso il suo linguaggio di programmazione intitolato Plankalkül e le routine di scacchi al computer che scrisse dal 1941 al 1945.

Allo stesso tempo, a partire dal 1949, Shannon costruì un automa composto solo da 150 relè elettromeccanici che giocavano a scacchi.

Contesto

Claude Shannon , nato il 30 aprile 1916 e morto il 24 febbraio 2001, è un matematico , crittografo e ingegnere di Electrical US . Fu il fondatore della teoria della progettazione di circuiti digitali nel 1937 , quando all'età di 21 anni scrisse, mentre completava il master presso il Massachusetts Institute of Technology (MIT), la sua tesi che mostrava che le applicazioni dell'algebra booleana nel campo della l'elettricità permette di costruire qualsiasi relazione logica o numerica. Shannon ha anche contribuito nel campo della crittoanalisi per la difesa nazionale americana durante la seconda guerra mondiale , in particolare grazie al suo lavoro di decrittazione e messa in sicurezza delle telecomunicazioni . È anche il fondatore della teoria dell'informazione , con un articolo di riferimento intitolato A Mathematical Theory of Communication che ha pubblicato nel 1948.

Shannon, che lavora ai Bell Laboratories dal 1941, approfondisce il lavoro di Turing sul tema degli scacchi ( Turochamp ). Alla Convenzione IRE che si tenne nel marzo 1949 a New York , Shannon presentò un articolo intitolato Programmazione di un computer per giocare a scacchi , sull'argomento di un computer per giocare a scacchi . L'articolo fu successivamente pubblicato nel febbraio 1950 in una versione più semplice sulla rivista Scientific American n °  182, e in una versione dettagliata nel marzo 1950 sulla rivista Philosophical Magazine n °  314.

Generale

Shannon non scrive programmi ma propone tecniche e algoritmi che costituiscono la base dei programmi di scacchi creati da allora. Ammette che gli scacchi sono un problema interessante e una cartina di tornasole delle capacità dei sistemi di elaborazione delle informazioni . Descrive l'analisi della strategia della macchina come un vero problema di forma senza la complessità del mondo reale. Secondo lui, sebbene ciò possa non avere alcuna importanza pratica, se un computer può giocare a scacchi è di interesse teorico e si spera che una soluzione soddisfacente a questo problema possa fungere da leva nel gioco. natura, ma di maggiore importanza.

Secondo Shannon, lo scopo degli scacchi è chiaro e distinto: dare scacco matto . Inoltre, il gioco utilizza un semplice sistema di regole che non prevede alcun elemento di fortuna o fortuna, sebbene questo semplice obiettivo, con queste semplici regole, sia difficile da avvicinare. Vede l'incontro uomo-macchina negli scacchi come un'opposizione leale.

Non pensa che la vittoria del computer sull'uomo nel gioco degli scacchi sia inevitabile, ma rileva comunque quattro vantaggi per ogni avversario. ritiene che un computer sia molto veloce nell'eseguire i calcoli, non sbaglia mai a meno che non venga introdotto un errore nel programma, non si annoia né si stanca e analizza a fondo ogni posizione o ogni possibile mossa, e non gioca con un registro emotivo o sbaglia il lato dell'eccessiva fiducia in situazioni vincenti a priori che potrebbero essere sprecate o trasformate in situazioni difficili che potrebbero richiedere un soccorso. Shannon ritiene che l'avversario umano, d'altra parte, abbia una mente flessibile che è in grado di cambiare il ragionamento o la velocità per risolvere un problema piuttosto che applicare semplicemente un semplice insieme di regole. Si accorge di essere dotato anche di ragione , immaginazione e capacità di apprendere.

L'articolo descrive come una macchina o un computer possono giocare una partita ragionevole di scacchi . Presenta il modo in cui un programma può rappresentare una scacchiera , valutare una posizione e generare i movimenti successivi.

Ricerca

Shannon considera due tipi di ricerca per valutare la scelta dei colpi da giocare. Si oppone alla ricerca e all'approccio della conoscenza alle macchine scacchistiche. Il primo che chiama "Tipo A" è una ricerca di forza bruta per tutte le variazioni. Un programma di ricerca approfondito analizza tutte le possibili sequenze di movimento e le loro conseguenze con la profondità di corsa desiderata e assegna un valore a ciascuna posizione finale. L' algoritmo minimax sceglie la migliore mossa possibile in base a ciò che il suo avversario gli consente. L'unica conoscenza relativa ai guasti è contenuta nella funzione di valutazione che determina il valore associato ad una posizione. Il secondo metodo di ricerca, che chiama "Tipo B" , è una ricerca selettiva solo sui rami importanti. Il materiale basato sulla ricerca imita il comportamento di un giocatore di scacchi principiante, che, conoscendo solo le mosse, armeggia sistematicamente fino a un momento chiave in cui può selezionare la mossa migliore da giocare.

Shannon considera le strategie di tipo A non praticabili per ragioni di complessità dei calcoli numerici e dimostra l'impossibilità di considerare tutte le posizioni: ci sono una trentina di possibili mosse per ogni posizione, e tenendo conto di una profondità di tre colpi, per ciascuna delle due colori, il calcolo richiederebbe sedici minuti, con un sistema in grado di valutare un milione di posizioni al secondo (in confronto, Deep Blue può valutare 200 milioni di posizioni al secondo). Inoltre, Shannon ha notato che le strategie di tipo A sono troppo semplicistiche, ignorando l'aspetto della ricerca quiescente  (in) (una ricerca euristica intelligente segue i movimenti più promettenti in maggiore profondità, evitando colpi poco promettenti o silenziosi).

Shannon suggerisce che le strategie di tipo B possono utilizzare due approcci. È possibile utilizzare una sorta di ricerca quiescente o la valutazione di poche mosse per ciascuna posizione, ignorando tutte le mosse tranne quelle identificate come buone (un metodo chiamato potatura).

Funzioni di valutazione

Shannon espone il suo processo tipo Minimax presentato per la prima volta qualche anno fa da von Neumann , basato sulla funzione di valutazione  (in) statica data la posizione di un pezzo degli scacchi per permettere al computer di decidere improvvisamente di giocare. Fornisce l'esempio approssimativo di una funzione di valutazione in cui il valore delle posizioni nere viene sottratto da quello di quelle bianche. Il materiale è stimato in base al consueto valore relativo dei pezzi (1 punto per un pedone , 3 punti per un cavaliere o un alfiere , 5 per una torre e 9 punti per una regina o un re ). Considera fattori come i pedoni posizionati raddoppiati , il pedone arretrato o i pedoni isolati . La mobilità è anche un fattore che aggiunge 0,1 punti a ogni movimento consentito. Considera anche lo scacco matto come la cattura del re e gli dà il valore artificiale di 200 punti.

Suggerimenti

Shannon offre anche alcuni suggerimenti e commenti aggiuntivi. Come Charles Babbage , sostiene l'uso di elementi statistici per scegliere a caso tra i colpi più sicuri. Raccomanda anche l'uso di una libreria di aperture con una scelta casuale che ha l'effetto di portare varietà.

Numero di Shannon

Nel suo articolo, Shannon solleva l'impossibilità di calcolare tutte le possibili posizioni e colpi. Calcola un numero di mosse potenziali che hanno un significato durante una partita, un numero noto come "numero Shannon" . Il numero Shannon, o 10.120 , è la stima della complessità dell'albero degli scacchi , cioè il numero di partite diverse con un possibile significato scacchistico.

I posteri

L'articolo di Shannon è più di un semplice riassunto di come dovrebbe essere una macchina in grado di giocare a scacchi. Evidenzia questioni teoriche irrisolte e ha allertato un vasto pubblico sulla possibilità di creare una macchina in grado di giocare a scacchi e ha anche ispirato una generazione di programmatori di scacchi. Claude Shannon è il primo a pubblicare una descrizione coerente dell'applicazione del minimax al gioco degli scacchi e questo articolo lo rende uno dei candidati al titolo di fondatore dei programmi di scacchi, insieme ad Alan Turing con il suo programma del 1948 intitolato Turochamp e che Konrad Zuse grazie al suo linguaggio di programmazione chiamato Plankalkül e alle routine di scacchi al computer che scrisse dal 1941 al 1945. Tutti i programmi di scacchi passati e presenti erano basati sulle tecniche descritte da Claude Shannon.

Allo stesso tempo, a partire dal 1949, Shannon costruì un automa composto solo da 150 relè elettromeccanici . La macchina è progettata per consentire il test di diversi metodi di programmazione. Può muovere sei pezzi, fa la sua mossa in 10-50 secondi e le scelte che fa hanno un aspetto casuale, il che significa che non deve giocare la stessa mossa tutto il tempo a seconda della stessa situazione. Durante il periodo in cui Shannon è alla ricerca di idee che lo possano portare a realizzare la macchina, passa così tanto tempo a giocare a scacchi ai Bell Laboratories che almeno uno dei suoi superiori era "un po '" preoccupato.

In un'asta chiamata The Origins of Cyberspace , tenuta nel febbraio 2003 da Christie's al Rockefeller Plaza di New York , le pagine dell'articolo completo della rivista Philosophical Magazine Programming a Computer for Playing Chess del marzo 1950 furono vendute a 960  dollari USA .

Pubblicazioni

Riferimenti

  1. (in) I. James , "  Claude Elwood Shannon dal 30 aprile 1916 al 24 febbraio 2001  " , Memorie biografiche di Fellows of the Royal Society , vol.  55,2009, p.  257–265.
  2. (in) "  Bell Labs Advances Intelligent Networks  " ,1 ° novembre 2006.
  3. William Poundstone 2006 , Parte prima - Entropia - Claude Shannon .
  4. Claude Elwood Shannon, Neil James Alexander Sloane e Aaron D. Wyner 1993 , p.  XI.
  5. (en) Erik J. Larson, "  A Brief History of Computer Chess  " , su The Best Schools .
  6. George W. Atkinson 1998 , p.  39.
  7. (in) "  di Christie Vendita 1484 - Le Origini del cyberspazio, 23 febbraio 2005, New York, Rockefeller Plaza  " su Christies.com .
  8. Nate Silver 2012 , La nascita della Chess Computer .
  9. (in) Charles Eames e Ray Eames, "  A Computer Perspective: Background to the Computer Age  " , Harvard University Press ,1990, p.  149.
  10. Friedrich von Borries, Steffen P. Walz e Matthias Böttger 2007 , p.  16-17.
  11. (in) "  I computer di scacchi fanno la loro mossa  " , New Scientist , vol.  123, n o  1676,5 agosto 1989, p.  50-51 ( ISSN  0262-4079 , leggi in linea ).
  12. George W. Atkinson 1998 , p.  5.
  13. George W. Atkinson 1998 , p.  40.
  14. Hamid Reza Ekbia 2008 , p.  46.
  15. (in) Claude Shannon, "  Programmazione di un computer per il gioco di scacchi  " , Philosophical Magazine , 7 ° di serie, vol.  41, n o  314,Marzo 1950, p.  256-275.
  16. George W. Atkinson 1998 , p.  41.
  17. Gary M. Danelishen , p.  6.
  18. Subrata Dasgupta , p.  181.
  19. S. Barry Cooper e Jan van Leeuwen , Parte III , p.  644-650.
  20. Subrata Dasgupta , p.  193.
  21. (in) "  Interview with Claude Shannon - Grazie, Dr. Shannon  " , ICGA Journal  (in) , vol.  12, n o  4,1989, p.  217.
  22. (in) "  Shannon e Shannon al motore scacchistico di Lasker  " su Computerhistory .org .
  23. (a) John Horgan, "  Claude Shannon: Tinkerer, Prankster, and Father of Information Theory  " su IEEE Spectrum: Technology, Engineering, and Science News ,27 aprile 2016.

Bibliografia

Documento utilizzato per scrivere l'articolo : documento utilizzato come fonte per questo articolo.