Turochamp

A Turochamp [a] egy sakkprogram , amelyet Alan Turing és David Champernowne fejlesztett ki 1948-ban egy számítástechnikai és gépi tanulási tanulmány részeként. Mielőtt megtenne egy lépést, Turochamp mérlegeli az összes lehetséges lépést, és kiszámítja minden lehetséges ellenfél válaszát, majd tovább elemzi a sikeres lépéseket. Az elemzés eredményeként kapott összes pozícióhoz hozzárendelnek egy mérőszámot, amely alapján a program kiválasztja a legsikeresebb lépést. Ezt az algoritmust követve a program képes az elejétől a végéig teljes értékű játékot játszani egy élő ellenféllel szemben egy kezdő sakkozó szintjén .

Turing és Champernowne soha nem fejezte be a Turochampot , mert az algoritmus túl bonyolult volt ahhoz, hogy az akkori számítógépeken, például az Automatic Computing Engine -en fusson . Turing megpróbálta megvalósítani az algoritmust egy 1951-es Manchester Ferranti Mark 1 számítógépen , de nem járt sikerrel. 1952-ben Turing meccset játszott a tudós Alik Glennie ellen , lépésről lépésre maga is végrehajtva az algoritmust. Turing 1954-ben halt meg anélkül, hogy Turochampot valódi számítógépen dolgozta volna; Champernowne nem folytatta a projektet, és a kód elveszett .

Annak ellenére, hogy az algoritmust soha nem formalizálták program formájában, a Turochampot az első személyi számítógépes játéknak tekintik, és azt állítja, hogy ez a történelem első sakkprogramja (sok más sakkprogramot fejlesztettek ki a Turochamp -pel egy időben , de egyik sem elkészültek). Az első munkaprogram, amelyet Dietrich Prinz írt 1951-ben a Ferranti Mark 1 számítógéphez, Turochampon alapult, és arra korlátozódott, hogy két mozdulattal megoldja a páros problémákat . A 2012 -es Alan Turing centenáriumi konferenciájára Turochampot újrateremtették, és Garri Kaszparov nagymester a program ellen játszott .

Játékmenet

A Turochamp egy sakkot játszó számítógépes program, amely bemenetként fogadja a játékos lépéseit, és válaszul a saját lépéseit adja ki. A programalgoritmus heurisztikus módszert használ a lehető legjobb lépés meghatározására. A program figyelembe veszi a szabályok által megengedett összes lépést, kiszámítja minden lehetséges ellenfél reakcióját, valamint a további „jelentős” mozdulatokat - a nem védett figurák elfogását , a csere befejezését , valamint az ellenfél erős bábujának elfogását egy gyengébb bábuval. Minden kapott pozícióhoz hozzárendelünk egy metrikát, amely után a program a minimax [3] [4] [5] algoritmus segítségével kiválasztja a lehető legjobb mozgást . A mérőszámot több szempont alapján számítják ki – az egyes darabok mobilitása és biztonsága, a sakk-matt veszélye, az elfogott darab értéke, valamint számos egyéb tényező [6] . Champernowne szerint az algoritmus tulajdonképpen azon a döntésen múlik, hogy ezt vagy azt a darabot választjuk-e; Turing szerint Turochamp egy kezdő játékos szintjén képes sakkozni, amit saját sakkjátéki szintjével arányosnak tartott [3] [6] .

Történelem

1941-től, miközben a Parkban katonai kriptográfián dolgozott , Turing elkezdett megvitatni kollégáival egy olyan gép létrehozásának lehetőségéről, amely képes sakkozni és más "intelligens" problémákat megoldani, valamint azt az ötletet, hogy a problémákat úgy oldják meg az összes lehetséges válasz válogatása heurisztikus algoritmus segítségével [7] [8] . Turing számos munkája a kriptoanalízis területén, köztük Bombe is olyan számítógép modellt használt, amely minden lehetséges megoldáson keresztülmegy [8] . 1944-ben Turing megvitatta elképzeléseit David Champernowne statisztikussal , és 1945-re arra a következtetésre jutottak, hogy egy tetszőleges számítások elvégzésére képes gép elméletileg képes mindent megismételni, amire az emberi agy képes, beleértve a sakkjátszmát is . 7] [9] .

A második világháború után Turing a National Physical Laboratory -ban dolgozott, ahol kifejlesztette az Automatic Computing Engine -t (ACE), amely a memóriában tárolt programmal rendelkező számítógép egyik első prototípusa. 1946-ban Turing írt egy jelentést "Javasolt elektronikus számológép" (  angolul  -  "javasolt elektronikus számológép") címmel, amelyben felsorolta azokat a projekteket, amelyekhez az ACE-t használni fogja - ezek közül az egyik egy sakkjátszma volt. Egy évvel később előadást tartott a London Mathematical Society -nek , bemutatva egy olyan gép ötletét, amely sakkozni és saját játéktapasztalataiból tanulni programozott. 1948-ban új jelentést küldött az "Intelligent Machinery"-ről (  angolul  -  "intelligens felszerelés"), amelyben egy sakkjáték utánzásának módját javasolta [1] .

1948 késő nyarán Turing és Champernowne a cambridge-i King's College-ban dolgozott egy elméleti szabályrendszert a sakkjátszma optimális következő lépésének meghatározására. Ezt az algoritmust számítógépes programként valósították meg, de túl bonyolultnak bizonyult az ACE vagy bármely más korabeli számítógép számára [3] . A program a Turochamp nevet kapta – az alkotók ( Turing és Champernowne ) nevének tiszteletére [1] . A sajtóban néha tévesen Turbochamp -ként [2] emlegetik . Champernowne szerint a felesége sakkozott egy "papírszámítógép" nevű program ellen, és veszített [1] [10] . Turing egy 1951-es Manchester Ferranti Mark 1 számítógépen próbálta megvalósítani az algoritmust , de a kód bonyolultsága miatt nem járt sikerrel [2] . Turing monográfusa, Jack Copeland azt írta, hogy Turing sikertelen próbálkozásai valódi számítógépre való programírással nem zavarták Turingot, mivel meg volt győződve arról, hogy a számítógépek sebessége és összetettsége hamarosan növekedni fog, és lehetővé válik egy ilyen program megírása. [11] . 1952 nyarán Turing egy játékot játszott Alik Glennie ellen egy program segítségével, lépésről lépésre maga hajtva végre az algoritmust. A rekordot megőrzött meccs 29 mozdulatig tartott és Turochamp vereségével ért véget, a program minden lépése pedig 30 perces számításokat vett igénybe. Ez a meccs bebizonyította, hogy lehetséges egy olyan program, amely képes egy teljes meccset lejátszani egy ember ellen. Turing 1954-ben halt meg anélkül, hogy Turochampot valódi számítógépen futtatta volna [2] .

A Turing és Champernowne által írt forráskód és algoritmus nem maradt fenn. 1980-ban Champernowne leírta az algoritmus működését, de nem emlékezett a metrika kiszámításának minden részletére [3] [11] . E leírás szerint a Turochampot 2012- ben hozták újra [12] . Az algoritmus rekonstrukciója azonban nem tudta reprodukálni a Turing és Glennie között rögzített egyezést. A program fennmaradt leírásainak helyes értelmezésére a szerzők úgy döntöttek, hogy számos sakkszakértővel és Turing kortársával konzultálnak, köztük Ken Thompsonnal , a Belle sakkgép és a Unix operációs rendszer megalkotójával , azonban egyik sem találhattak okot az eltérésekre. Végül Donald Meehee azt javasolta, hogy Turing nem követte aprólékosan az algoritmust a játék során; később a kutatóknak sikerült bebizonyítaniuk, hogy Turing a legelső lépéstől kezdve tévesen kizárta a számításból a számára nem optimálisnak tűnő lépéseket, hogy időt takarítson meg az elemzésükön [b] . Az így létrejött rekonstrukciót a 2012. július 22–25-én megrendezett Alan Turing centenáriumi konferencia részeként mutatták be a nagymester és az exvilágbajnok Garri Kaszparov elleni mérkőzésen [13] . Kaszparov 16 mozdulattal verte a programot [14] .

Legacy

Annak ellenére, hogy az algoritmust soha nem formalizálták programként, Turochamp azt állítja, hogy ő az első sakkprogram a történelemben. A Turochamp -pal egyidejűleg más sakkprogramokat is kidolgoztak és megvitattak: 1950-ben Claude Shannon publikált egy cikket "Programming a Computer for Playing Chess" (  angolul  -  "programing a computer for Playing Chess"), Konrad Zuse 1941-1945-ben a sakkot oldotta meg. problémákat az általa kifejlesztett Plankalkül nyelvben , Donald Michi és Sean Wylie pedig kidolgozta a Machiavelli sakk algoritmust , amelyet Turing sikertelenül próbált megvalósítani a Ferranti Mark I-en Turochamp -pal egy időben [1] [15] [ 16] [17] . 1951 novemberében Dietrich Prinz , a Ferranti alkalmazottja ihlette Turing Turochamp -on végzett munkáját, és ez alapján kifejlesztette az első sikeres sakkprogramot a Ferranti Mark I számára, amely a páros problémák két lépésben történő megoldására korlátozódott [3].

A Turochampot 2012-ben hozták újra, és az Alan Turing Centenáriumi Konferencia részeként mutatták be [13] . Garri Kaszparov , aki részt vett a konferencián, beszédet mondott, amelyben "kiemelkedő teljesítménynek" nevezte egy sakkprogram létrehozását olyan körülmények között, ahol munkája eredménye nem hajtható végre számítógépen, és kijelentette, hogy Turochamp megtalálta a helyét. a történelemben [14] .

Lásd még

• A számítógépes játékok története

Megjegyzések

1. ↑ A Turochamp nevét alkotóiról , Turingról és Champernowne -ról kapta [ 1 ] .  Néha tévesen Turbochampnak [2] nevezik . 
2. ↑ Konkrétan Turing két négyzetes király mancsával nyitott, mivel úgy vélte, hogy az E4-re lépés nyilvánvalóan jobb volt, mint az E3-ra lépés. Az algoritmus azonban kevésbé tartja sikeresnek az E4-re lépést, mivel elméletileg több teret hagy az ellenfélnek a király megtámadására – annak ellenére, hogy abban a pillanatban egyetlen ellenséges bábu sem érhette el az E3 mezőt [13] .

Jegyzetek

1. ↑ 1 2 3 4 5 Alan Turing: His Work and Impact , pp. 644–650
2. ↑ 1 2 3 4 Clark, Liat; Steadman, Ian Alan Turingra emlékezve: a kódtöréstől a mesterséges intelligenciaig Turing olyanná tette a világot, amilyen ma . vezetékes . Conde Nast (2017. június 7.). Hozzáférés időpontja: 2019. február 7. (határozatlan)
3. ↑ 1 2 3 4 5 Az alapvető Turing , pp. 563-564
4. ↑ "David Champernowne (1912-2000)". ICGA folyóirat . 23 (4): 262. 2000. december. DOI : 10.3233/ICG-2000-23419 .
5. ↑ Cochlin, Daniel Kaszparov kontra Turing . Manchesteri Egyetem (2012. június 26.). Hozzáférés időpontja: 2019. április 9. (határozatlan)
6. ↑ 1 2 Hogyan sakkoznak a számítógépek , p. 35
7. ↑ 1 2 Hodges, Andrew (2013. 09. 30.), Alan Turing , Stanford Encyclopedia of Philosophy , Stanford Egyetem , < https://plato.stanford.edu/entries/turing/ > . Letöltve: 2019. május 22 . 
8. ↑ 1 2 Copeland, Jack ; Proudfoot, Diane (2012). "Alan Turing, a modern számítógép alapítója" . A Rutherford Journal . 1 (4). ISSN  1177-1380 .
9. ↑ Alan Turing: The Enigma , p. 488
10. ↑ "A Turing-féle "Papírgép" rekonstrukciója . ICGA folyóirat . 40 (2): 1-8. 2018. június.
11. ↑ 1 2 The Antipodean Philosopher , pp. 13–14
12. ↑ „Az évszázad játékosa”. Új a sakkban . Interches: 6-7. 1999. augusztus. ISSN  0168-8782 .
13. ↑ 1 2 3 Kaszparov, Garry (2012. június). Turing „papírgépének” rekonstrukciója. Alan Turing Centenáriumi Konferencia . Manchester, Anglia . Letöltve: 2019-04-09 – a VideoLectures.net -en keresztül .
14. ↑ 1 2 Parnell, Brid-Aine Alan Turing által írt sakk algoritmus szembeszáll Kaszparovval . A regiszter . Helyzetkiadó (2012. június 26.). Hozzáférés időpontja: 2019. április 9. (határozatlan)
15. ↑ Babbage-cal kezdődött: A számítástechnika keletkezése , p. 193
16. ↑ Prof: Alan Turing Decoded , ch. 9
17. ↑ Sakk és gépi intuíció , p. 39

Irodalom

• Hodges, Andrew. Alan Turing: Az Enigma. - Princeton University Press , 2014. - ISBN 978-1-4008-6512-3 .
• Hódok, Anthony. Alan Turing: Munkája és hatása. - Elsevier , 2013. - ISBN 978-0-12-386980-7 .
• Jaj, Graham. Az antipodeus filozófus / Graham Oppy, Nick Trakakis. - Lexington Books , 2011. - ISBN 978-0-7391-6655-0 .
• Atkinson, George W. Sakk és gépi intuíció . - Intellect Books, 1998. - ISBN 978-1-871516-44-9 .
• Copeland, B. Jack. Az alapvető Turing. - Oxford University Press , 2004. - ISBN 978-0-19-825079-1 .
• Levy, David. Hogyan sakkoznak a számítógépek / David Levy, Monty Newborn. - Ishi Press , 2009. - ISBN 978-4-87187-801-2 .
• Sipser, Michael. Bevezetés a számításelméletbe. - PWS Publishing, 2006. - ISBN 978-0-534-95097-2 .
• Dasgupta, Subrata. Babbage: A számítástechnika keletkezése című könyvvel kezdődött. - 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 .

Linkek

• Turochamp vs Alik Glennie (1952) a Chessgames.com oldalon
• Turochamp vs. Garry Kasparov (2012) a Chessgames.com oldalon

Tematikus oldalak	Internet Movie Database