Chess & Complexity
Souhrn
Přednáška se zabývá otázkou, zda je možné “vyřešit” hru šachy, podobně jako se to podařilo u her jako piškvorky a dáma. Hry s dokonalou informací, kde oba hráči vidí všechny tahy, jsou teoreticky řešitelné – lze najít optimální strategii vedoucí k nejlepšímu možnému výsledku (výhra, remíza, prohra). Piškvorky jsou řešitelné, dáma byla vyřešena v roce 2007 díky rozsáhlým výpočtům. Šachy jsou však řádově komplexnější, s odhadovaným počtem 10120 možných her, což je více než atomů v pozorovatelném vesmíru.
Přednášející vysvětluje fungování moderních šachových enginů, které využívají pokročilé algoritmy a umělou inteligenci k vyhodnocování pozic a výběru nejlepších tahů. Tyto enginy dosahují nadlidské úrovně, ale stále se jedná o aproximaci, nikoli o “vyřešení” hry. K vyřešení šachu by bylo nutné vypočítat a uložit optimální tah pro každou možnou pozici, což je i s existujícími databázemi koncovek pro 7 kamenů zatím nemožné. Přednáška zmiňuje potenciál kvantových počítačů, které by díky schopnosti paralelního zpracování dat mohly teoreticky urychlit potřebné výpočty, ale i ty jsou stále v raných fázích vývoje. Závěrem zdůrazňuje, že schopnost vyřešit šachy závisí na budoucím technologickém pokroku.
Přepis
Co kdybych vám řekl, že jsem přišel na nový způsob, jak podvádět v šachu? Můžete za záda soupeře propašovat zrcadlo a vidět jeho tahy. To je samozřejmě směšné, protože vidíte přesně to, co vidí váš soupeř, a víte všechno, co ví váš soupeř. Taková hra je známá jako hra s dokonalou informací a lze ji vyřešit. Ale co to přesně znamená? Znamená to, že je známa optimální strategie a výsledek, ať už je to výhra, prohra nebo remíza, lze určit z jakékoli možné pozice. Za předpokladu, že oba hráči hrají perfektně. Vezměme si jednoduchý příklad piškvorek, další hry s dokonalou informací. Piškvorky jsou vyřešené. Víme, že pokud oba hráči hrají perfektně, hra vždy končí remízou.
Dalším příkladem je dáma. Dáma byla vyřešena v roce 2007 týmem vedeným informatikem Jonathanem Schaeferem. Použili program Chinook a kombinaci rozsáhlých výpočtů a algoritmů k analýze každé možné pozice a sekvence ve hře. Víme, že pokud oba hráči hrají perfektně, hra bude vždy remíza.
Takže pokud jste vyřešili piškvorky a dámu, co je tak složitého na šachu? Stručná odpověď je jeho komplexnost. Piškvorky jsou relativně jednoduchá hra s 255 000 různými možnými hrami. Dáma je o úroveň výš s 500 kvintiliony různých možných her. Šachy však zvyšují komplexnost na další úroveň. Existuje ohromující jeden november (10120) různých možných šachových her. Toto je známé jako Shannonovo číslo, pojmenované po slavném matematikovi a informatikovi Claudu Shannonovi. Jen pro představu tohoto obrovského čísla, existuje více možných šachových her než atomů v pozorovatelném vesmíru.
Věřili byste, že toto obrovské číslo vzniká proto, že každý hráč má v každém tahu mnoho možností a tyto možnosti se exponenciálně větví? Ve skutečnosti v průměru každá šachová pozice vede k 35 potenciálním tahům. Tento větvící faktor 35 velmi rychle vede k mnoha dalším možným pozicím po zahájení, přičemž po pouhých čtyřech tazích je k dispozici téměř 85 miliard různých možných pozic. Kvůli této komplexnosti, hloubce a obrovskému počtu možných pozic matematici a informatici považují šachy za ideální testovací prostředí pro algoritmy a modely umělé inteligence.
Možná se ptáte, proč prostě nepoužijeme šachového robota nebo šachový engine? Pojďme si stručně projít, jak fungují. Moderní šachové enginy využívají různé techniky, aby vynikly v šachu. Generují všechny legální tahy, používají vyhledávací algoritmy a umělou inteligenci k vyhodnocení nejlepšího tahu. Vyhodnocují miliony pozic za sekundu a pomocí optimalizačních technik jim umožňují dosáhnout nadlidské úrovně výkonu v šachu. Jen pro srovnání, Stockfish, jeden z nejvýznamnějších příkladů šachového enginu, má odhadované hodnocení 3642. Pro srovnání, Magnus Carlsen, jeden z nejlépe hodnocených šachistů světa, má vrcholné hodnocení 2882.
Ale moderní šachové enginy nejsou dokonalé. Spoléhají se na aproximaci spíše než na přímé řešení šachu. Abychom vyřešili šachy, musíme vypočítat všechny informace potřebné k vytvoření dokonalé hry, a do určité míry se to již stalo u šachových koncovek. Šachové koncovky byly vyřešeny pro pozice obsahující až sedm figurek. To se provádí zpětným postupem, technikou zvanou zpětná indukce, generováním 18 terabajtové databáze, která identifikovala výsledek dokonalé hry z jakékoli možné pozice. Rozšíření na všechny figurky by vyžadovalo zcela jinou úroveň zdrojů.
Řešení šachu vyžaduje uložení informací pro každou možnou pozici a její dokonalý tah. Jak jsme právě viděli, databáze tabulek šachových koncovek až pro sedm figurek již vyžadují terabajty úložiště a představují pouze malý zlomek hry. Rozšíření na všech 32 figurek by vyžadovalo úložiště o mnoho řádů větší, než jaké máme dnes. Nejrychlejší superpočítače na světě dokážou provést kvintiliony operací za sekundu, ale i při této rychlosti by jim trvalo déle než věk vesmíru, než by tento problém vypočítaly. Zpracování všech těchto pozic vyžaduje výpočetní výkon, který přesahuje to, co máme dnes.
Abychom překonali tato omezení, jednou z technologií, která má pro naše úsilí největší potenciál, je kvantové počítání. Kvantové počítání, se svou schopností zpracovávat informace jinak, by mohlo změnit způsob, jakým chápeme a zkoumáme hru, využitím jedinečných principů kvantové mechaniky. Na rozdíl od klasických bitů, které mohou být buď 0, nebo 1, kvantové bity, neboli qubity, mohou existovat v superpozici stavů, existují jako 0 i 1 současně. Klasické počítače mohou provádět jeden proces najednou, zatímco kvantové počítače mohou provádět více procesů paralelně. Kvantové algoritmy jsou mnohem rychlejší než klasické algoritmy, což zkracuje čas potřebný k vyhodnocení dokonalého tahu.
Všechny tyto vlastnosti, spolu s dalšími, dávají kvantovému počítání výhodu oproti klasickému počítání a viděli jsme slibné výsledky od raných kvantových počítačů. Příkladem toho bylo nedávno, koncem roku 2024, kdy Google publikoval výsledky ukazující, že jeho kvantový počítačový čip Willow by dokončil výpočet za pět minut, který by nejrychlejším superpočítačům na světě trval více než 10 septilionů let. Opravdu ohromující, že? Ačkoli tento problém byl přizpůsoben silným stránkám kvantového počítače, má potenciál přinést stejné výsledky i v oblasti klasického počítání problémů.
Klasické kvantové počítání je však stále v raných fázích a aktivně se zkoumá, je třeba jej dále rozvíjet, než bude možné jej plně využít. Nakonec naše schopnost vyřešit šachy závisí na schopnostech budoucích technologií a naší vynalézavosti při řešení problémů kolem těchto omezení. Vrátíme-li se k příkladu dámy, která byla vyřešena v roce 2007, Jonathan Schaefer uvedl, že jedna věc, kterou se naučil z 16letého úsilí, je nikdy nepodceňovat pokrok v technologii. Děkuji.
Kritické zhodnocení
Přednáška Adita Sooda poskytuje srozumitelný a poutavý přehled o nesmírné komplexnosti šachu a výzvách spojených s jeho “vyřešením”. Sood správně poukazuje na rozdíl mezi aproximací optimální hry, kterou provádějí moderní šachové enginy, a skutečným vyřešením, které by vyžadovalo výpočet a uložení optimálního tahu pro každou možnou pozici. Jeho odhad 10120 možných šachových her (Shannonovo číslo) je standardně uváděný odhad komplexnosti šachu.
Soodovo tvrzení, že šachy jsou mnohem komplexnější než dáma, je pravdivé. Dáma byla skutečně “slabě vyřešena” v roce 2007 Jonathanem Schaefferem a jeho týmem, což znamená, že je známo, že při dokonalé hře obou stran hra vždy skončí remízou.[1] Nicméně i výpočetní úsilí potřebné k vyřešení dámy bylo obrovské.
Zmínka o kvantových počítačích jako o potenciálním řešení je relevantní, ale je důležité zdůraznit, že kvantové počítače jsou stále ve velmi rané fázi vývoje. Ačkoliv Google skutečně dosáhl pokroku v oblasti kvantových výpočtů, jak zmiňuje Sood (včetně experimentů s čipem “Willow”, i když přesný rok se liší a zmíněný výpočet se týkal specifického problému optimalizovaného pro kvantové počítače, ne obecného výpočtu[2]), praktické využití kvantových počítačů pro řešení problémů takové komplexity, jako jsou šachy, je stále vzdálenou budoucností. Potenciál kvantových počítačů je teoreticky obrovský, praktické překážky (stabilita qubitů, škálovatelnost, oprava chyb) jsou stále značné.[3]
Přednáška je celkově přesná a poskytuje dobrý úvod do problematiky komplexnosti šachu. Je však důležité zdůraznit, že “vyřešení” šachu, i s hypotetickým využitím budoucích kvantových počítačů, zůstává extrémně náročným, možná nedosažitelným cílem.
Zdroje:
[1] Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., … & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518-1522. [2] Arute, F., Arya, K., Babbush, R. et al. (2019). Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510. (Poznámka: Tento článek popisuje experiment s čipem Sycamore, předchůdcem Willow, a demonstruje “kvantovou nadvládu” ve specifickém výpočetním úloze, nikoli obecné řešení komplexních problémů.) [3] Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. Quantum, 2, 79.
