Turochamp

Turochamp [a] er et skakprogram udviklet af Alan Turing og David Champernowne i 1948 som en del af et studie i datalogi og maskinlæring. Inden du laver et træk, overvejer Turochamp alle mulige træk og beregner hver mulig modstanders respons, hvorefter den analyserer succesfulde træk yderligere. Alle positioner opnået som et resultat af analysen tildeles en metrik, hvorved programmet vælger det mest succesfulde træk. Efter denne algoritme er programmet i stand til at spille et fuldgyldigt spil fra start til slut mod en live modstander på niveau med en nybegynder skakspiller .

Turing og Champernowne fuldførte aldrig Turochamp , fordi algoritmen var for kompleks til at køre på datidens computere, såsom Automatic Computing Engine . Turing forsøgte at implementere algoritmen på en Manchester Ferranti Mark 1 computer fra 1951 , men det lykkedes ikke. I 1952 spillede Turing en kamp mod videnskabsmanden Alik Glennie , hvor han trin for trin selv udførte algoritmen. Turing døde i 1954 uden at få Turochamp til at arbejde på en rigtig computer; Champernowne gik ikke videre med projektet, og koden gik tabt .

På trods af at algoritmen aldrig blev formaliseret i form af et program, betragtes Turochamp som det første spil til en personlig computer og hævder at være det første skakprogram i historien (flere andre skakprogrammer blev udviklet samtidigt med Turochamp , men ingen af dem blev afsluttet). Det første arbejdsprogram, skrevet i 1951 af Dietrich Prinz til Ferranti Mark 1-computeren, var baseret på Turochamp og var begrænset til at løse makkerproblemer i to træk . Ved Alan Turings 100-års konference i 2012 blev Turochamp genskabt, og stormester Garry Kasparov spillede mod programmet .

Gameplay

Turochamp er et computerprogram, der spiller skak, som modtager spillerens træk som input, og som svar udsender det sit eget træk. Programalgoritmen bruger en heuristisk metode til at bestemme det bedst mulige træk. Programmet tager hensyn til alle de træk, der er tilladt i henhold til reglerne, beregner hver mulig modstanders respons, samt yderligere "betydelige" træk - at fange ubeskyttede brikker, fuldføre udvekslingen , samt at erobre modstanderens stærke brik med en svagere brik. Hver opnået position tildeles en metrik, hvorefter programmet vælger det bedst mulige træk ved hjælp af minimax- algoritmen [3] [4] [5] . Metrikken beregnes ud fra flere kriterier - mobiliteten og sikkerheden af ​​hver brik, truslen om skakmat, værdien af ​​den erobrede brik, samt en række andre faktorer [6] . Ifølge Champernowne handler algoritmen faktisk om at tage beslutninger om, hvorvidt man skal tage dette eller hint stykke; ifølge Turing er Turochamp i stand til at spille skak på niveau med en nybegynder, hvilket han anså for at stå mål med hans eget niveau af skakspil [3] [6] .

Historie

Fra 1941, mens han arbejdede med militær kryptografi i Bletchley Park , begyndte Turing at diskutere med kolleger muligheden for at skabe en maskine, der kunne spille skak og løse andre "intelligente" problemer, såvel som ideen om at løse problemer ved at sortering gennem alle mulige svar med brug af en heuristisk algoritme [7] [8] . En række af Turings værker inden for kryptoanalyse, herunder Bombe , brugte en model af en computer, der gennemgår alle mulige løsninger [8] . I 1944 diskuterede Turing sine ideer med den økonomiske statistiker David Champernowne , og i 1945 konkluderede de, at en maskine, der er i stand til at udføre vilkårlige beregninger, teoretisk set er i stand til at replikere alt, hvad den menneskelige hjerne er i stand til, inklusive skakspillet . 7] [9] .

Efter Anden Verdenskrig arbejdede Turing på National Physical Laboratory , hvor han udviklede Automatic Computing Engine (ACE), en af ​​de første prototyper af en computer med et gemt program i hukommelsen. I 1946 skrev Turing en rapport med titlen "Proposed Electronic Calculator" (fra  engelsk  -  "proposed electronic calculator"), som oplistede de projekter, som han skulle bruge ACE til – et af dem var et spil skak. Et år senere holdt han en tale til London Mathematical Society , hvor han præsenterede ideen om en maskine programmeret til at spille skak og lære af sin egen spilleoplevelse. I 1948 sendte han en ny rapport "Intelligent Machinery" (fra  engelsk  -  "intelligent equipment"), hvori han foreslog en måde at efterligne et skakspil [1] .

I sensommeren 1948 udviklede Turing og Champernowne, der arbejdede på King's College, Cambridge , et system af teoretiske regler til at bestemme det optimale næste træk i et skakspil. De implementerede denne algoritme som et computerprogram, men det viste sig at være for kompliceret for ACE eller enhver anden computer på den tid [3] . Programmet fik navnet Turochamp - til ære for skabernes navne ( Turing og Champernowne ) [1] . Det er nogle gange fejlagtigt omtalt i pressen som Turbochamp [2] . Ifølge Champernowne spillede hans kone et parti skak mod et program kaldet en "papircomputer" og tabte [1] [10] . Turing forsøgte at implementere algoritmen på en Manchester Ferranti Mark 1 computer fra 1951 , men på grund af kodens kompleksitet lykkedes det ikke [2] . Turings monografi Jack Copeland skrev, at Turings mislykkede forsøg på at skrive et program til rigtig computer ikke generede Turing, da han var overbevist om, at hastigheden og kompleksiteten af ​​computere snart ville stige, og det ville blive muligt at skrive et sådant program. [11] . I sommeren 1952 spillede Turing en kamp mod Alik Glennie ved hjælp af et program, hvor han trin for trin selv udførte algoritmen. Kampen, hvis rekord er blevet bevaret, varede 29 træk og endte med Turochamps nederlag , og hvert træk i programmet tog op til 30 minutters beregninger. Denne kamp viste, at et program, der kunne spille en fuld kamp mod et menneske, var muligt. Turing døde i 1954 uden at lade Turochamp køre på en rigtig computer [2] .

Kildekoden og algoritmen skrevet af Turing og Champernowne har ikke overlevet. I 1980 beskrev Champernowne, hvordan algoritmen fungerede, men han kunne ikke huske alle detaljerne om, hvordan metrikken blev beregnet [3] [11] . Ifølge denne beskrivelse blev Turochamp genskabt i 2012 [12] . Rekonstruktionen af ​​algoritmen formåede dog ikke at gengive den optagede kamp mellem Turing og Glennie. I et forsøg på at fortolke de overlevende beskrivelser af programmet korrekt, besluttede forfatterne at konsultere en række skakeksperter og Turings samtidige, herunder Ken Thompson , skaberen af ​​Belle skakmaskinen og Unix -operativsystemet , dog ingen af de kunne finde en årsag til uoverensstemmelserne. Endelig foreslog Donald Meehee, at Turing ikke fulgte algoritmen omhyggeligt under spillet; senere lykkedes det forskerne at bevise, at Turing, startende fra det allerførste træk, fejlagtigt udelukkede de træk, der forekom ham ikke-optimale, fra overvejelse for at spare tid på deres analyse [b] . Den resulterende rekonstruktion blev præsenteret som en del af Alan Turings hundredeårskonference , der blev afholdt den 22.-25. juli 2012, i en kamp mod stormesteren og eks-verdensmesteren Garry Kasparov [13] . Kasparov slog programmet i 16 træk [14] .

Legacy

På trods af at algoritmen aldrig blev formaliseret som et program, hævder Turochamp at være det første skakprogram i historien. Samtidig med Turochamp blev andre skakprogrammer udviklet og diskuteret: i 1950 udgav Claude Shannon en artikel "Programming a Computer for Playing Chess" (fra  engelsk  -  "programmering af en computer til at spille skak"), Konrad Zuse i 1941-1945 løste skak problemer i det Plankalkül sprog, han udviklede , og Donald Michi og Sean Wylie udviklede Machiavelli skakalgoritmen , som Turing uden held forsøgte at implementere på Ferranti Mark I samtidig med Turochamp [1] [15] [ 16] [17] . I november 1951 blev Dietrich Prinz , en Ferranti -medarbejder , inspireret af Turings arbejde med Turochamp og udviklede baseret på det det første succesrige skakprogram til Ferranti Mark I, som var begrænset til at løse makkerproblemer i to træk [3]

Turochamp blev genskabt i 2012 og præsenteret som en del af Alan Turing Centenary Conference [13] . Garry Kasparov , der deltog i konferencen, holdt en tale, hvori han kaldte oprettelsen af ​​et skakprogram under forhold, hvor resultatet af hans arbejde ikke kan udføres på en computer, "en enestående præstation" og erklærede, at Turochamp havde fundet sin plads i historien [14] .

Se også

• Computerspils historie

Kommentarer

1. ↑ Turochamp er opkaldt efter dets skabere , Turing og Champernowne [ 1 ] .  Kaldes nogle gange fejlagtigt Turbochamp [2] . 
2. ↑ Turing åbnede især med et to-kvadratisk kongebondetræk, da han mente, at skiftet til E4 åbenbart var bedre end skiftet til E3. Algoritmen anser imidlertid overgangen til E4 for mindre vellykket, da den i teorien giver modstanderen mere plads til at angribe kongen - på trods af at ikke en eneste fjendebrik kunne nå E3-pladsen i det øjeblik [13] .

Noter

1. ↑ 1 2 3 4 5 Alan Turing: His Work and Impact , s. 644-650
2. ↑ 1 2 3 4 Clark, Liat; Steadman, Ian Husker Alan Turing: Fra kodebrud til kunstig intelligens har Turing gjort verden til, hvad den er i dag . kablet . Conde Nast (7. juni 2017). Dato for adgang: 7. februar 2019. (ubestemt)
3. ↑ 1 2 3 4 5 The Essential Turing , s. 563-564
4. ↑ "David Champernowne (1912-2000)". ICGA Journal . 23 (4): 262. December 2000. DOI : 10.3233/ICG-2000-23419 .
5. ↑ Cochlin, Daniel Kasparov versus Turing . University of Manchester (26. juni 2012). Dato for adgang: 9. april 2019. (ubestemt)
6. ↑ 1 2 Sådan spiller computere skak , s. 35
7. ↑ 1 2 Hodges, Andrew (2013-09-30), Alan Turing , Stanford Encyclopedia of Philosophy , Stanford University , < https://plato.stanford.edu/entries/turing/ > . Hentet 22. maj 2019. . 
8. ↑ 1 2 Copeland, Jack ; Proudfoot, Diane (2012). "Alan Turing, grundlægger af den moderne computer" . Rutherford Journal . 1 (4). ISSN  1177-1380 .
9. ↑ Alan Turing: The Enigma , s. 488
10. ↑ "Rekonstruering af Turings "Papirmaskine " ". ICGA Journal . 40 (2): 1-8. juni 2018.
11. ↑ 1 2 The Antipodean Philosopher , s. 13-14
12. ↑ "Århundredes spiller". Ny i skak . Interchess: 6-7. august 1999. ISSN  0168-8782 .
13. ↑ 1 2 3 Kasparov, Garry (juni 2012). Rekonstruktionen af ​​Turings 'Paper Machine'. Alan Turing 100-års konference . Manchester, England . Hentet 2019-04-09 – via VideoLectures.net .
14. ↑ 1 2 Parnell, Brid-Aine Skakalgoritme skrevet af Alan Turing går op mod Kasparov . Registeret . Situation Publishing (26. juni 2012). Dato for adgang: 9. april 2019. (ubestemt)
15. ↑ Det begyndte med Babbage: The Genesis of Computer Science , s. 193
16. ↑ Prof: Alan Turing Decoded , kap. 9
17. ↑ Skak og maskinintuition , s. 39

Litteratur

• Hodges, Andrew. Alan Turing: Gåden. - Princeton University Press , 2014. - ISBN 978-1-4008-6512-3 .
• Beavers, Anthony. Alan Turing: Hans arbejde og indvirkning. - Elsevier , 2013. - ISBN 978-0-12-386980-7 .
• Oppy, Graham. The Antipodean Philosopher / Graham Oppy, Nick Trakakis. - Lexington Books , 2011. - ISBN 978-0-7391-6655-0 .
• Atkinson, George W. Skak og maskinintuition . - Intellect Books, 1998. - ISBN 978-1-871516-44-9 .
• Copeland, B. Jack. Den essentielle Turing. - Oxford University Press , 2004. - ISBN 978-0-19-825079-1 .
• Levy, David. Sådan spiller computere skak / David Levy, Monty Newborn. - Ishi Press , 2009. - ISBN 978-4-87187-801-2 .
• Sipser, Michael. Introduktion til teorien om beregning. - PWS Publishing, 2006. - ISBN 978-0-534-95097-2 .
• Dasgupta, Subrata. Det begyndte med Babbage: Datalogiens tilblivelse. - Oxford University Press , 2014. - ISBN 978-0-19-930941-2 .
• Turing, Dermot. Prof: Alan Turing Decoded . - The History Press , 2015. - ISBN 978-0-7509-6524-8 .

Links

• Turochamp vs Alik Glennie (1952) på Chessgames.com
• Turochamp vs. Garry Kasparov (2012) på Chessgames.com

Tematiske steder	Internet film database