Turochamp

Turochamp [a] on shakkiohjelma, jonka Alan Turing ja David Champernowne kehittivät vuonna 1948 osana tietojenkäsittelytieteen ja koneoppimisen tutkimusta. Ennen siirtoa Turochamp harkitsee kaikki mahdolliset liikkeet ja laskee jokaisen mahdollisen vastustajan vastauksen, minkä jälkeen se analysoi onnistuneita liikkeitä edelleen. Kaikille analyysin tuloksena saaduille positioille osoitetaan mittari, jonka mukaan ohjelma valitsee menestyneimmän liikkeen. Tätä algoritmia noudattaen ohjelma pystyy pelaamaan täysimittaisen pelin alusta loppuun elävää vastustajaa vastaan ​​aloittelevan shakinpelaajan tasolla .

Turing ja Champernowne eivät koskaan saaneet Turochampia valmiiksi, koska algoritmi oli liian monimutkainen ajaakseen sen ajan tietokoneissa, kuten Automatic Computing Engine . Turing yritti toteuttaa algoritmin vuoden 1951 Manchester Ferranti Mark 1 -tietokoneella , mutta epäonnistui. Vuonna 1952 Turing pelasi ottelun tiedemies Alik Glennie vastaan , askel askeleelta suorittaen algoritmin itse. Turing kuoli vuonna 1954 saamatta Turochampia työskentelemään oikealla tietokoneella; Champernowne ei jatkanut projektia ja koodi katosi .

Huolimatta siitä, että algoritmia ei koskaan formalisoitu ohjelman muodossa, Turochampia pidetään ensimmäisenä henkilökohtaisen tietokoneen pelinä ja se väittää olevansa ensimmäinen shakkiohjelma historiassa (useita muita shakkiohjelmia kehitettiin samanaikaisesti Turochampin kanssa , mutta mikään ne valmistuivat). Ensimmäinen työohjelma, jonka Dietrich Prinz kirjoitti vuonna 1951 Ferranti Mark 1 -tietokoneelle, perustui Turochampiin ja rajoittui mate-ongelmien ratkaisemiseen kahdella siirrolla . Vuoden 2012 Alan Turingin satavuotisjuhlakonferenssiin mennessä Turochamp luotiin uudelleen ja suurmestari Garry Kasparov pelasi ohjelmaa vastaan .

Pelin kulku

Turochamp on shakkia pelaava tietokoneohjelma, joka vastaanottaa syötteenä pelaajan liikkeet ja antaa vastauksena oman liikkeensä. Ohjelman algoritmi käyttää heuristista menetelmää parhaan mahdollisen liikkeen määrittämiseen. Ohjelma ottaa huomioon kaikki sääntöjen sallimat liikkeet, laskee jokaisen mahdollisen vastustajan vastauksen sekä muut "merkittävät" liikkeet - suojaamattomien nappuloiden sieppaamisen , vaihdon loppuun saattamisen sekä vastustajan vahvan nappulan kaappaamisen heikoimmalla nappulalla. Kullekin saadulle sijainnille annetaan metriikka, jonka jälkeen ohjelma valitsee parhaan mahdollisen liikkeen käyttämällä minimax -algoritmia [3] [4] [5] . Mittari lasketaan useiden kriteerien perusteella - kunkin kappaleen liikkuvuus ja turvallisuus, matin uhka, nappatun kappaleen arvo sekä monet muut tekijät [6] . Champernownen mukaan algoritmi itse asiassa perustuu siihen, että tehdään päätöksiä siitä, otetaanko tämä vai tuo kappale; Turingin mukaan Turochamp pystyy pelaamaan shakkia noviisipelaajan tasolla, minkä hän piti sopivana omaan shakinpelitasoonsa [3] [6] .

Historia

Vuodesta 1941 lähtien työskennellessään sotilassalauksen parissa Parkissa Turing alkoi keskustella kollegoiden kanssa mahdollisuudesta luoda kone, joka pystyy pelaamaan shakkia ja ratkaisemaan muita "älykkäitä" ongelmia, sekä ajatuksesta ratkaista ongelmia lajitella kaikki mahdolliset vastaukset heuristisen algoritmin avulla [7] [8] . Useissa Turingin töissä kryptaanalyysin alalla, mukaan lukien Bombe , käytettiin tietokonemallia, joka käy läpi kaikki mahdolliset ratkaisut [8] . Vuonna 1944 Turing keskusteli ajatuksistaan ​​talousstatistikon David Champernownen kanssa, ja vuoteen 1945 mennessä he päättelivät, että mielivaltaisiin laskelmiin kykenevä kone pystyy teoriassa toistamaan kaiken, mihin ihmisaivot pystyvät, mukaan lukien shakkipelin . 7] [9] .

Toisen maailmansodan jälkeen Turing työskenteli National Physical Laboratoryssa , jossa hän kehitti automaattisen laskentamoottorin (ACE), joka on yksi ensimmäisistä prototyypeistä tietokoneesta, jossa on muistiin tallennettu ohjelma. Vuonna 1946 Turing kirjoitti raportin nimeltä "Proposed Electronic Calculator" (  englanniksi  "  ehdotettu elektroninen laskin"), jossa lueteltiin projektit, joihin hän aikoi käyttää ACE:tä - yksi niistä oli shakkipeli. Vuotta myöhemmin hän piti puheen London Mathematical Societylle esitellen idean koneesta, joka on ohjelmoitu pelaamaan shakkia ja oppimaan omasta pelikokemuksestaan. Vuonna 1948 hän lähetti uuden raportin "Intelligent Machinery" (  englanniksi  "  älykäs laite"), jossa hän ehdotti tapaa jäljitellä shakkipeliä [1] .

Loppukesällä 1948 Turing ja Champernowne, jotka työskentelivät King's Collegessa Cambridgessa , kehittivät teoreettisten sääntöjen järjestelmän shakkipelin optimaalisen seuraavan liikkeen määrittämiseksi. He toteuttivat tämän algoritmin tietokoneohjelmana, mutta se osoittautui liian monimutkaiseksi ACE:lle tai mille tahansa muulle sen ajan tietokoneelle [3] . Ohjelma sai nimekseen Turochamp - tekijöiden ( Turing ja Champernowne ) nimien kunniaksi [1] . Lehdistössä sitä kutsutaan joskus virheellisesti Turbochampiksi [2] . Champernownen mukaan hänen vaimonsa pelasi shakkia "paperitietokoneeksi" kutsuttua ohjelmaa vastaan ​​ja hävisi [1] [10] . Turing yritti toteuttaa algoritmin vuoden 1951 Manchester Ferranti Mark 1 -tietokoneella , mutta koodin monimutkaisuuden vuoksi hän ei onnistunut [2] . Turingin monografi Jack Copeland kirjoitti, että Turingin epäonnistuneet yritykset kirjoittaa ohjelma oikealle tietokoneelle eivät häirinneet Turingia, koska hän oli vakuuttunut siitä, että tietokoneiden nopeus ja monimutkaisuus lisääntyvät pian ja että tällaisen ohjelman kirjoittaminen tulisi mahdolliseksi. [11] . Kesällä 1952 Turing pelasi peliä Alik Glennie vastaan ​​ohjelman avulla, askel askeleelta suorittaen algoritmin itse. Ottelu, jonka ennätys on säilynyt, kesti 29 siirtoa ja päättyi Turochampin tappioon , ja jokainen ohjelman siirto kesti jopa 30 minuuttia laskelmia. Tämä ottelu osoitti, että ohjelma, joka pystyy pelaamaan täyden ottelun ihmistä vastaan, oli mahdollista. Turing kuoli vuonna 1954 ilman, että Turochamp oli ajanut oikealla tietokoneella [2] .

Turingin ja Champernownen kirjoittama lähdekoodi ja algoritmi eivät ole säilyneet. Vuonna 1980 Champernowne kuvaili algoritmin toimintaa, mutta hän ei muistanut kaikkia metriikan laskennan yksityiskohtia [3] [11] . Tämän kuvauksen mukaan Turochamp luotiin uudelleen vuonna 2012 [12] . Algoritmin rekonstruktio ei kuitenkaan onnistunut toistamaan tallennettua ottelua Turingin ja Glennien välillä. Yrittäessään tulkita oikein ohjelman säilyneitä kuvauksia kirjoittajat päättivät kuulla useita shakkiasiantuntijoita ja Turingin aikalaisia, mukaan lukien Ken Thompson , Belle shakkikoneen ja Unix - käyttöjärjestelmän luoja . he voivat löytää syyn eroihin. Lopuksi Donald Meehee ehdotti, että Turing ei seurannut algoritmia huolellisesti pelin aikana; Myöhemmin tutkijat onnistuivat todistamaan, että Turing jo ensimmäisestä liikkeestä alkaen jätti virheellisesti huomioimatta liikkeet, jotka tuntuivat ei-optimaalisilta säästääkseen aikaa analyysiinsä [b] . Tuloksena oleva jälleenrakennus esiteltiin osana Alan Turingin 100-vuotisjuhlakonferenssia , joka pidettiin 22.–25. heinäkuuta 2012, ottelussa suurmestari ja entinen maailmanmestari Garry Kasparov [13] . Kasparov voitti ohjelman 16 siirrolla [14] .

Legacy

Huolimatta siitä, että algoritmia ei koskaan muotoiltu ohjelmaksi, Turochamp väittää olevansa historian ensimmäinen shakkiohjelma. Samaan aikaan Turochampin kanssa kehitettiin muita shakkiohjelmia ja niistä keskusteltiin: vuonna 1950 Claude Shannon julkaisi artikkelin "Tietokoneen ohjelmointi shakin pelaamista varten" (  englanniksi  -  "tietokoneen ohjelmointi shakin pelaamista varten"), Konrad Zuse ratkaisi shakin vuonna 1941-1945. ongelmia kehittämässään Plankalkül -kielessä , ja Donald Michi ja Sean Wylie kehittivät Machiavelli - shakkialgoritmin , jota Turing epäonnistui toteuttaa Ferranti Mark I:lle samaan aikaan kuin Turochamp [1] [15] [ 16] [17] . Marraskuussa 1951 Ferrantin työntekijä Dietrich Prinz inspiroitui Turingin työstä Turochampissa ja kehitti sen pohjalta ensimmäisen onnistuneen shakkiohjelman Ferranti Mark I:lle, joka rajoittui mate-ongelmien ratkaisemiseen kahdessa siirrossa [3]

Turochamp luotiin uudelleen vuonna 2012 ja esiteltiin osana Alan Turing Centenary Conference [13] . Konferenssiin osallistunut Garry Kasparov piti puheen, jossa hän kutsui shakkiohjelman luomista olosuhteissa, joissa hänen työnsä tulosta ei voida suorittaa tietokoneella, "erinomainen saavutus" ja totesi Turochampin löytäneen paikkansa . historiassa [14] .

Katso myös

• Tietokonepelien historia

Kommentit

1. ↑ Turochamp on nimetty sen tekijöiden Turingin ja Champernownen mukaan [ 1 ] .  Joskus kutsutaan virheellisesti Turbochampiksi [2] . 
2. ↑ Erityisesti Turing aloitti kahden ruudun kuninkaan sotilasliikkeellä, koska hänen mielestään siirto E4:lle oli selvästi parempi kuin siirto E3:lle. Algoritmi kuitenkin pitää siirtymistä E4:ään vähemmän onnistuneena, koska se jättää teoriassa vastustajalle enemmän tilaa hyökätä kuninkaaseen - huolimatta siitä, ettei yksikään vihollisen nappula päässyt E3-ruutuun sillä hetkellä [13] .

Muistiinpanot

1. ↑ 1 2 3 4 5 Alan Turing: His Work and Impact , s. 644–650
2. ↑ 1 2 3 4 Clark, Liat; Steadman, Ian Muistaa Alan Turing: koodinmurtamisesta tekoälyyn, Turing teki maailmasta sen, mikä se on tänään . langallinen . Conde Nast (7. kesäkuuta 2017). Käyttöönottopäivä: 7.2.2019. (määrätön)
3. ↑ 1 2 3 4 5 The Essential Turing , ss. 563-564
4. ↑ "David Champernowne (1912-2000)". ICGA-lehti . 23 (4): 262. Joulukuu 2000. DOI : 10.3233/ICG-2000-23419 .
5. ↑ Cochlin, Daniel Kasparov vastaan ​​Turing . Manchesterin yliopisto (26. kesäkuuta 2012). Käyttöönottopäivä: 9.4.2019. (määrätön)
6. ↑ 1 2 Kuinka tietokoneet pelaavat shakkia , s. 35
7. ↑ 1 2 Hodges, Andrew (30.9.2013), Alan Turing , Stanford Encyclopedia of Philosophy , Stanford University , < https://plato.stanford.edu/entries/turing/ > . Haettu 22.5.2019 . 
8. ↑ 1 2 Copeland, Jack ; Proudfoot, Diane (2012). "Alan Turing, modernin tietokoneen perustaja" . Rutherford Journal . 1 (4). ISSN  1177-1380 .
9. ↑ Alan Turing: The Enigma , s. 488
10. ↑ "Turingin "paperikoneen" rekonstruoiminen . ICGA-lehti . 40 (2): 1-8. Kesäkuu 2018.
11. ↑ 1 2 The Antipodean Philosopher , s. 13–14
12. ↑ "Vuosisadan pelaaja". Uutta Shakissa . Välivuoro: 6-7. elokuu 1999. ISSN  0168-8782 .
13. ↑ 1 2 3 Kasparov, Garry (kesäkuu 2012). Turingin "paperikoneen" rekonstruktio. Alan Turingin satavuotisjuhlakonferenssi . Manchester, Englanti . Haettu 2019-04-09 – VideoLectures.net:n kautta .
14. ↑ 1 2 Parnell, Brid-Aine Alan Turingin kirjoittama shakkialgoritmi vastustaa Kasparovia . Rekisteri . Tilannejulkaisu (26. kesäkuuta 2012). Käyttöönottopäivä: 9.4.2019. (määrätön)
15. ↑ Se alkoi Babbagesta: The Genesis of Computer Science , s. 193
16. ↑ Prof: Alan Turing Decoded , ch. 9
17. ↑ Shakki ja koneintuitio , s. 39

Kirjallisuus

• Hodges, Andrew. Alan Turing: Enigma. - Princeton University Press , 2014. - ISBN 978-1-4008-6512-3 .
• Majavat, Anthony. Alan Turing: Hänen työnsä ja vaikutuksensa. - Elsevier , 2013. - ISBN 978-0-12-386980-7 .
• Oho, Graham. Antipodean filosofi / Graham Oppy, Nick Trakakis. - Lexington Books , 2011. - ISBN 978-0-7391-6655-0 .
• Atkinson, George W. Shakki ja koneintuitio . - Intellect Books, 1998. - ISBN 978-1-871516-44-9 .
• Copeland, B. Jack. Essential Turing. - Oxford University Press , 2004. - ISBN 978-0-19-825079-1 .
• Levy, David. Kuinka tietokoneet pelaavat shakkia / David Levy, Monty Newborn. - Ishi Press , 2009. - ISBN 978-4-87187-801-2 .
• Sipser, Michael. Johdatus laskentateoriaan. - PWS Publishing, 2006. - ISBN 978-0-534-95097-2 .
• Dasgupta, Subrata. Se alkoi Babbagesta: Tietojenkäsittelytieteen synty. - 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 .

Linkit

• Turochamp vs Alik Glennie (1952) Chessgames.comissa [
• Turochamp vs. Garry Kasparov (2012) Chessgames.comissa [

Temaattiset sivustot	Internet-elokuvatietokanta