Turochamp

Turochamp
Vývojáři Alan Turing a David Champernowne [d]
Datum vydání 1948
Žánr počítačové šachy
Technické údaje
Herní mód Hra pro jednoho hráče

Turochamp [a] je šachový program vyvinutý Alanem Turingem a Davidem Champernownem v roce 1948 jako součást studia informatiky a strojového učení. Před provedením tahu Turochamp zvažuje všechny možné tahy a vypočítá každou možnou soupeřovu odpověď, načež dále analyzuje úspěšné tahy. Všem pozicím získaným jako výsledek analýzy je přiřazena metrika, podle které program vybere nejúspěšnější tah. Podle tohoto algoritmu je program schopen odehrát plnohodnotnou partii od začátku do konce proti živému soupeři na úrovni začínajícího šachisty .

Turing a Champernowne Turochamp nikdy nedokončili, protože algoritmus byl příliš složitý na to, aby běžel na tehdejších počítačích, jako byl Automatic Computing Engine . Turing se pokusil implementovat algoritmus na počítači Manchester Ferranti Mark 1 z roku 1951 , ale byl neúspěšný. V roce 1952 Turing hrál zápas proti vědci Alik Glennie , krok za krokem sám provedl algoritmus. Turing zemřel v roce 1954, aniž by Turochampa přiměl k práci na skutečném počítači; Champernowne nepokračoval v projektu a kód se ztratil .

Navzdory skutečnosti, že algoritmus nebyl nikdy formalizován ve formě programu, je Turochamp považován za první hru pro osobní počítač a prohlašuje se za první šachový program v historii (současně s Turochampem bylo vyvinuto několik dalších šachových programů , ale žádný z nich byly dokončeny). První pracovní program, napsaný v roce 1951 Dietrichem Prinzem pro počítač Ferranti Mark 1, byl založen na Turochamp a byl omezen na řešení partnerských problémů ve dvou tahech . Na konferenci stého výročí Alana Turinga v roce 2012 Turochamp byl znovu vytvořen a velmistr Garry Kasparov hrál proti programu .

Hratelnost

Turochamp je počítačový program, který hraje šachy, který přijímá tahy hráče jako vstup a v reakci na to vydává svůj vlastní tah. Algoritmus programu používá k určení nejlepšího možného tahu heuristickou metodu . Program zvažuje všechny tahy povolené pravidly, vypočítá každou možnou soupeřovu odpověď, stejně jako další "významné" tahy - zachycení nechráněných figurek, dokončení výměny , stejně jako zachycení soupeřovy silné figurky slabší figurkou. Každé získané pozici je přiřazena metrika, na jejímž základě program vybere nejlepší možný pohyb pomocí algoritmu minimax [3] [4] [5] . Metrika se počítá na základě několika kritérií – pohyblivost a bezpečnost každé figurky, hrozba matu, hodnota ukořistěné figurky a také řada dalších faktorů [6] . Podle Champernowneho algoritmus ve skutečnosti spočívá v rozhodování o tom, zda vzít ten nebo ten kus; podle Turinga je Turochamp schopen hrát šachy na úrovni začínajícího hráče, což považoval za úměrné své vlastní úrovni hraní šachů [3] [6] .

Historie

Od roku 1941, při práci na vojenské kryptografii v Bletchley Park , Turing začal diskutovat s kolegy o možnosti vytvořit stroj schopný hrát šachy a řešit další „inteligentní“ problémy, stejně jako o myšlence řešit problémy pomocí třídění všech možných odpovědí pomocí heuristického algoritmu [7] [8] . Řada Turingových prací v oblasti kryptoanalýzy, včetně Bombe , používala model počítače, který prochází všemi možnými řešeními [8] . V roce 1944 Turing diskutoval o svých myšlenkách s ekonomickým statistikem Davidem Champernownem a v roce 1945 dospěli k závěru, že stroj schopný provádět libovolné výpočty je teoreticky schopen replikovat vše, čeho je lidský mozek schopen, včetně hry šachů. [ 7] [9] .

Po druhé světové válce Turing pracoval v National Physical Laboratory , kde vyvinul Automatic Computing Engine (ACE), jeden z prvních prototypů počítače s uloženým programem v paměti. V roce 1946 Turing napsal zprávu nazvanou „Proposed Electronic Calculator“ (z  angličtiny  –  „navrhovaná elektronická kalkulačka“), ve které vyjmenovával projekty, pro které se chystal použít ACE – jedním z nich byla šachová hra. O rok později měl přednášku pro London Mathematical Society , kde představil myšlenku stroje naprogramovaného tak, aby hrál šachy a učil se ze svých vlastních herních zkušeností. V roce 1948 zaslal novou zprávu „Intelligent Machinery“ (z  angličtiny  –  „inteligentní zařízení“), ve které navrhl způsob, jak napodobit šachovou hru [1] .

Na konci léta 1948 Turing a Champernowne, pracující na King's College v Cambridge , vyvinuli systém teoretických pravidel pro určení optimálního dalšího tahu v šachové hře. Implementovali tento algoritmus jako počítačový program, ale pro ACE nebo jakýkoli jiný počítač té doby se ukázal být příliš komplikovaný [3] . Program byl pojmenován Turochamp - na počest jmen tvůrců ( Turing a Champernowne ) [1] . V tisku je někdy mylně označován jako Turbochamp [2] . Podle Champernowneho hrála jeho žena šachovou partii proti programu zvanému „papírový počítač“ a prohrála [1] [10] . Turing se pokusil implementovat algoritmus na počítači Manchester Ferranti Mark 1 z roku 1951 , ale kvůli složitosti kódu nebyl úspěšný [2] . Turingův monograf Jack Copeland napsal, že Turingovy neúspěšné pokusy napsat program pro skutečný počítač Turinga neobtěžovaly, protože byl přesvědčen, že rychlost a složitost počítačů se brzy zvýší a bude možné takový program napsat. [11] . V létě 1952 hrál Turing hru proti Alikovi Glenniemu s pomocí programu, který krok za krokem sám spouštěl algoritmus. Zápas, jehož záznam se zachoval, trval 29 tahů a skončil porážkou Turochampa a každý tah programu zabral až 30 minut výpočtů. Tento zápas ukázal, že je možný program schopný odehrát celý zápas proti člověku. Turing zemřel v roce 1954, aniž by Turochamp běžel na skutečném počítači [2] .

Zdrojový kód a algoritmus napsaný Turingem a Champernownem se nedochovaly. V roce 1980 Champernowne popsal, jak algoritmus fungoval, ale nemohl si vzpomenout na všechny podrobnosti o tom, jak byla metrika vypočítána [3] [11] . Podle tohoto popisu byl Turochamp znovu vytvořen v roce 2012 [12] . Rekonstrukce algoritmu však nedokázala reprodukovat zaznamenaný zápas mezi Turingem a Glenniem. Ve snaze správně interpretovat dochované popisy programu se autoři rozhodli konzultovat řadu šachových odborníků a Turingových současníků, včetně Kena Thompsona , tvůrce šachového automatu Belle a operačního systému Unix , nicméně žádný z mohli najít důvod nesrovnalostí. Nakonec Donald Meehee navrhl, že Turing během hry pečlivě nedodržoval algoritmus; později se výzkumníkům podařilo dokázat, že Turing, počínaje úplně prvním tahem, chybně vyloučil z úvahy tahy, které se mu zdály neoptimální, aby ušetřil čas na jejich analýzu [b] . Výsledná rekonstrukce byla prezentována v rámci konference stého výročí Alana Turinga , která se konala ve dnech 22.–25. července 2012, v zápase proti velmistrovi a bývalému mistru světa Garry Kasparovovi [13] . Kasparov porazil program v 16 tazích [14] .

Legacy

Navzdory skutečnosti, že algoritmus nebyl nikdy formalizován jako program, Turochamp tvrdí, že je prvním šachovým programem v historii. Současně s Turochampem byly vyvíjeny a diskutovány další šachové programy: v roce 1950 publikoval Claude Shannon článek „Programming a Computer for Playing Chess“ (z  angličtiny  –  „programming a computer for playing chess“), Konrad Zuse v letech 1941-1945 řešil šachy problémy v jazyce Plankalkül , který vyvinul , a Donald Michi a Sean Wylie vyvinuli Machiavelliho šachový algoritmus , který se Turing neúspěšně pokusil implementovat na Ferranti Mark I ve stejnou dobu jako Turochamp [1] [15] [ 16] [17] . V listopadu 1951 Dietrich Prinz , zaměstnanec Ferranti , se inspiroval Turingovou prací o Turochampovi a na jejím základě vyvinul první úspěšný šachový program pro Ferranti Mark I, který se omezoval na řešení problémů partnera ve dvou tazích [3].

Turochamp byl znovu vytvořen v roce 2012 a představen jako součást Alan Turing Centenary Conference [13] . Garry Kasparov , který se konference zúčastnil, pronesl projev, ve kterém označil vytvoření šachového programu v podmínkách, kdy výsledek jeho práce nelze provést na počítači, za „výjimečný výkon“ a uvedl, že Turochamp našel své místo v historii [14] .

Viz také

Komentáře

  1. ↑ Turochamp je pojmenován po svých tvůrcích , Turingovi a Champernowne [ 1 ] .  Někdy mylně nazýván Turbochamp [2] . 
  2. ↑ Turing otevřel zejména tahem pěšce krále na dvě pole, protože se domníval, že tah na E4 byl zjevně lepší než tah na E3. Algoritmus však považuje tah na E4 za méně úspěšný, protože teoreticky ponechává protivníkovi více prostoru k útoku na krále – a to i přesto, že na pole E3 nemohla v tu chvíli dosáhnout ani jedna nepřátelská figurka [13] .

Poznámky

  1. ↑ 1 2 3 4 5 Alan Turing: Jeho práce a dopad , str. 644–650
  2. ↑ 1 2 3 4 Clark, Liat; Steadman, Ian Vzpomínka na Alana Turinga: od rozluštění kódu po AI udělal Turing svět tím, čím je dnes . drátové . Conde Nast (7. června 2017). Datum přístupu: 7. února 2019.
  3. ↑ 1 2 3 4 5 The Essential Turing , str. 563-564
  4. ↑ "David Champernowne (1912-2000)". Deník ICGA . 23 (4): 262. prosinec 2000. DOI : 10.3233/ICG-2000-23419 .
  5. ↑ Cochlin, Daniel Kasparov versus Turing . University of Manchester (26. června 2012). Datum přístupu: 9. dubna 2019.
  6. ↑ 1 2 Jak počítače hrají šachy , str. 35
  7. ↑ 1 2 Hodges, Andrew (2013-09-30), Alan Turing , Stanford Encyclopedia of Philosophy , Stanford University , < https://plato.stanford.edu/entries/turing/ > . Staženo 22. května 2019. . 
  8. ↑ 1 2 Copeland, Jack ; Proudfoot, Diane (2012). „Alan Turing, zakladatel moderního počítače“ . The Rutherford Journal . 1 (4). ISSN  1177-1380 .
  9. ↑ Alan Turing: The Enigma , str. 488
  10. ↑ "Rekonstrukce Turingova "papíráku " ". Deník ICGA . 40 (2): 1-8. června 2018.
  11. ↑ 1 2 The Antipodean Philosopher , str. 13–14
  12. ↑ „Hráč století“. Novinka v šachu . Interches: 6-7. srpen 1999. ISSN  0168-8782 .
  13. ↑ 1 2 3 Kasparov, Garry (červen 2012). Rekonstrukce Turingova „stroje na papír“. Konference stého výročí Alana Turinga . Manchester, Anglie . Staženo 2019-04-09 – přes VideoLectures.net .
  14. ↑ 1 2 Parnell, Brid-Aine Šachový algoritmus napsaný Alanem Turingem jde proti Kasparovovi . Registr . Situační nakladatelství (26. června 2012). Datum přístupu: 9. dubna 2019.
  15. ↑ Začalo to Babbage: The Genesis of Computer Science , str. 193
  16. ↑ Prof: Alan Turing Decoded , kap. 9
  17. ↑ Intuice šachů a strojů , str. 39

Literatura

Odkazy

  Přejděte na položku Wikidata  Tematické stránky