Nedeľník touchIT vážne i nevážne. Odľahčené IT témy na tisíc spôsobov.
Kto by nepoznal legendárnu hru piškvôrky. Vo svojej základnej podobe, známej ako Tic-tac-toe, je hraná len na hracom poli z troch radov a stĺpcov, pričom je dobrou ukážkou herného prelomenia.
Ak proti sebe pozorne hrajú dvaja ľudia, je prakticky nemožné, aby hra skončila inak ako remízou. Je to z dôvodu, že obaja hráči dokážu vo svojej predstavivosti simulovať celú hru až do jej konca a vyhnú sa prípadom, ktoré vedú k ich prehre. Jediná možnosť výhry je, že súper prehliadne smrtiacu kombináciu a adekvátne nezareaguje, čo sa môže stať napríklad vtedy, ak hru hráte s malým dieťaťom.
Túto hru je schopný svojpomocne prelomiť takmer každý človek, pričom pri bezchybných hráčoch je výsledkom nevyhnutná remíza. Nech ste akýkoľvek dobrý hráč, neexistuje možnosť, aby ste bezchybne hrajúceho súpera donútili k porážke.
U mnohých iných hier to ale neplatí. Dobrý príklad je hra Maharadža a sipáhiovia, čo je jedna zo šachových variant, ktorá vznikla v 19-tom storočí v Indii. Ide o klasické šachové pole, pri ktorom má čierny všetky figúry a biely len jednu (Maharadžu). Tá má štatút šachového kráľa, pričom sa môže pohybovať ako dáma a kôň dohromady. Čierny hýbe figúrami klasicky, s rozdielom, že pešiaka nie je možné premeniť na dámu. Hra rozhodne nie je jednoduchá a pri hre si rýchlo uvedomíte, že biely hráč nie je ani zďaleka bezbranný.
Všetko sa ale zrúti v momente prelomenia. Existujú totiž kombinácie, ktoré čiernemu vyhrajú hru, pričom nezáleží na tom, aké ťahy biely urobí. Stačí si zapamätať len 24 ťahov, ktoré čiernemu zaistia výhru za každých okolností.
Tu do hry vo vstupujú počítače. Ak dokáže človek prepočítať piškvôrky s poľom 3 × 3 a odhaliť víťaznú kombináciu v hre Maharadža a sipáhiovia, nedokáže dostatočne výkonný počítač spočítať všetky možnosti aj iných zložitejších hier a odhaliť nevyhnutné víťazné kombinácie?
Číslo Boha Rubiku je 20. Ďakujeme Google
Rubikovu kocku asi netreba nikomu zvlášť predstavovať. Šesť stien z rozličných farieb za neodlučiteľne zapísalo do detstva mnohých ľudí.
Táto hračka od maďarského tvorcu Ernő Rubika vznikla v roku 1974 a v priebehu 80-tych rokov postupne opantala celý svet. Ide dodnes o najpredávanejší hlavolam, s viac ako 350 miliónmi predaných kusov.
Kým niektorí sú z nej frustrovaní, iní ju milujú. Obvyklou cestou k úspechu je uvedomenie si toho, že vyriešenie rôznych stavov kocky zvládnu pomerene jednoduché algoritmy.
Ak spoznáte na kocke nejaký známy tvar, tak jeho preskupenie do želanej formy sa dá dosiahnuť naučenými sekvenciami pohybov.
Ako by si s kockou poradil vševediaci Rubikový Boh? Ten by samozrejme poznal všetky možné ťahy a vždy by sa vydal najkratšou cestou k vyriešeniu. Nikdy by pri tom neurobil viac ťahov, ako by musel.
Takýto postup sa označuje ako Boží algoritmus, pričom sa používa nielen pri Rubikovej kocke, ale aj pri iných kombinatorických a matematických hrách.
Od počiatku tohto hlavolamu sa zvedaví ľudia pokúšali prísť na to, aký počet ťahov je pre Rubikovho Boha maximom a teda s akým minimálnym počtom ťahom sa dajú vyriešiť tie najťažšie stavy.
V roku 1981 vytvoril americký matematik Morwen Thistlethwaite dôkaz, že na vyriešenie akejkoľvek pozície nie je celkom určite potrebné viac ako 52 ťahov. Za jeden ťah sa pri tom považuje jedno otočenie akýmkoľvek smerom, teda pohyb na jednej osi o 90, 180 alebo 270°.
Od tejto doby sa rôzny matematici začali predbiehať v dôkaze čoraz nižšieho čísla a snažili sa dopátrať sa k tomu finálnemu. Hans Kloosterman v roku 1990 vytvoril matematický dôkaz na 42 ťahov a v roku 1992 sa Dik Winter s pomocou 112 počítačov dostal až na 37 ťahov.
Do práce sa počítače zapájali čoraz viac. Matematika však hrala stále prvé husle. V roku 1995 Michael Reid analyzovaním Kociembovho dvojfázového algoritmu určil, že celkom určite nejde o viac ako 29 ťahov a o desať rokov neskôr sa dostal Silviu Radu s mierne vylepšeným postupom na 28 ťahov.
Všetko sa zlomilo v roku 2008, kedy sa do boja zapojil programátor Tomas Rokicki, ktorý predložil dôkaz na 25 ťahov, aby nakoniec v júli roku 2010 v spolupráci s matematikom Morleyom Davidsonom dokázal, že akákoľvek pozícia a pomiešaný stav Rubikovej kocky sa dá definitívne vyriešiť za maximálne 20 ťahov.
Toto číslo je už definitívne a ide o maximálnu možnú kombinačnú situáciu. Existuje niekoľko stoviek miliónov kombinácii, ktoré sa dajú vyriešiť za najmenej 20 ťahov, ale neexistuje žiadna kombinácia, ktorá by ťahov vyžadovala viac.
Ako teda bolo vyriešených 43 252 003 274 489 856 000 (43 triliónov) možných stavov Rubikovej kocky? Zjednodušením.
Obrovské množstvo kombinácii sa tímu podarilo redukovať pomocou rôznych algoritmov na 55 882 296 unikátnych setov, pričom vytvorili program, ktorý jeden set dokáže vyriešiť zhruba za 20 sekúnd. To bol síce úspech, ale bežný počítač by danú úlohu riešil 35 rokov.
Tím sa teda obrátil na Google, ktorý bol projektom nadšený a poskytol na výpočet dostatočne veľký cluster svojich počítačov, ktorý problém vyriešil za niekoľko týždňov.
Super ťažké pozície, vyžadujúce od Rubikového Boha až 20 ťahov (ako napríklad tento), sú raritou a na každú pripadá viac ako miliarda ľahších stavov. Ich presný počet stále nepoznáme. Kocka je kompletne vyriešené do kombinácii s 15 ťahmi. V stavoch vyžadujúcich 16, 17, 18, 19 a 20 ťahov už ide len o odhady, ktoré sú však už pravde značne blízke.
Tomas Rokicki v riešení pokračuje a zatiaľ publikoval 93 miliónov rôznych stavov, vyžadujúcich si 20 ťahov a v pátraní po ďalších pokračuje.
V auguste 2014 pritom svetu poskytol aj odveď na to, koľko ťahov je potrebné za predpokladu, že môžete kocku otáčať len o 90°. S pomocou superpočítačového centra v Ohiu sa ukázalo, že v tomto prípade je Božie číslo 26.
Prelomená dáma
Anglicko-americký variant hry dáma je v súčasnosti najkomplexnejšou prelomenou hrou. Tento variant používa hraciu plochu s ôsmimi riadkami a stĺpcami, ktoré obsadia tri rady figúr na každej strane. Často sa hráva aj u nás, pretože je na ňu možné použiť klasickú šachovnicu (existujú však aj varianty pre plochy 10 × 10 alebo 12 × 12).
Počítačový softvér dosiahol v hre dáma nadľudskej úrovne po prvý krát v roku 1995, kedy program Chinook vytvorený Jonathanom Schaefferom z Albertskej univerzity v Kanade dokázal poraziť aktuálneho svetového veľmajstra v 32 kolovom zápase (1 výhra, 31 remíz).
V nasledujúcom roku vyhral program národný turnaj s mamutím náskokom a autor programu sa stiahol zo scény s úmyslom hru definitívne prelomiť.
Finálny dôkaz uzrel svetlo sveta v roku 2007, kedy ho Schaeffer publikoval vo vedeckom žurnále Science.
Jonathan Schaeffer
Šlo o výpočtový dôkaz, ktorý počítalo 50 až 200 počítačov po dobu 18 rokov. Od tohto momentu sa stal program Chinook v dáme neporaziteľným a najlepší výsledok, ktorý je proti nemu možné dosiahnuť, je remíza (ak rovnako ako on hráte bezchybne). Kto má odvahu, môže si to vyskúšať.
Pri bezchybne hrajúcich hráčoch hru nie je možné vyhrať. Ide teda o podobný stav ako pri piškôrkach na deviatich poliach. Neexistuje možnosť, ako bezchybne hrajúceho súpera donútiť k prehre (ako pri Maharadžavi a sipáhioch).
Šach hraný na nadľudskej úrovni
Na rozdiel od dámy existuje pri šachu všeobecná predstava, že ideálna hra, pri ktorej biely bezpodmienečne vyhrá, nech robí čierny čokoľvek, existuje. Dôkaz pravdaže nemáme a ani nijaký nie je v dohľade.
Je možné šach prelomiť hrubou výpočtovou silou podobne ako anglicko-americkú dámu? So súčasnou technológiou počítačov a zrejme ani technológiou počítačov najbližšieho storočia nie.
Anglicko-americká dáma má zhruba 1020 herných kombinácii, zatiaľ čo počet legálnych pozícii v šachu sa odhaduje na 1043 až 1050.
Počítač by pre prelomenie tejto hry musel zhodnocovať hrubou silou okolo 10120 možných variácii, alebo mať databázu optimálnych stratégii pre všetkých 1043 klasických herných stavov.
Ak chcete nejaké porovnanie k týmto mamutím číslam a dôkaz o sile narastajúceho exponentu, tak ľudské telo je zložené zhruba z 1027 atómov. Celá zemeguľa ich má zhruba 1050 a celý vesmír okolo 1080. Prelomenie šachu je dnes niečo celkom nereálne a zatiaľ len snívame o tom, že by potenciálne niečo také mohol riešiť extrémne vyspelý kvantový počítač o niekoľko storočí.
To však neznamená, že počítač nedokáže byť lepší ako človek. Šachový softvér je na nadľudskej úrovni už dlhé roky. Ešte v priebehu 80-tych rokov nebolo jasné, či nejaký šachový program bude schopný poraziť špičkových ľudských hráčov v dohľadnej dobe. Pokiaľ totiž nejde o cvičnú šachovú úlohu v podobe záverečného matu, tak kombinatorická explózia, ktorá nastane po pár ťahoch, znemožní počítanie všetkých možných kombinácií do veľkých hĺbok.
Šachové programy tak namiesto hrubej sily hrajú ako človek, pričom sa učia a hľadajú najlepšie stratégie. Len najvhodnejšie ťahy tak začnú prehľadávať do veľkých hĺbok, podobne ako veľmajstri.
Zlom nastal v 90-tych rokoch minulého storočia, kedy šachový počítač Deep Blue od IBM porazil v máji 1997 svetového šampióna Garriho Kasparovova v sérii šiestich zápasov so skóre 3,5 ku 2,5 (dve víťazstvá, tri remízy, jedna prehra). Deep Blue bol masívne paralelný systém vytvorený z tridsiatich uzlov IBM RS/6000. Obsahoval 30 procesorov POWER2 s frekvenciou 120 MHz, ktoré boli doplnené o 480 špecializovaných VLSI čipov navrhnutých pre šachové operácie.
Na prelome 20-teho a 21-storočia sa vďaka zvyšovaniu výkonu bežných PC začali vyrovnávať veľmajstrovskej úrovni aj klasické šachové softvéry (bez špecializovaného hardvéru), akým bol napríklad Junior a Fritz.
Jeden z posledných významných zápasov sa odohral v roku 2006, kedy vtedajší svetový šampión Vladimir Kramnik prehral s programom Deep Fritz v pomere 4:2.
Šachový program Deep Fritz
Počítače dnes majú vlastný šachový turnaj, kde nastupujú proti sebe. Aktuálnym šampiónom je program Jonny, ktorý vytvoril nemecký programátor a matematik Johannes Zwanzger. Funguje na linuxovom clusteri Bayreuthskej univerzity a používa 2400 jadier AMD procesorov s frekvenciou 2,8 GHz. Vo finále minuloročného turnaja porazil predchádzajúceho dvojnásobného šampióna v podobe programu Junior, ktorý vytvorili izraelskí programátori Amir Ban a Shaya Bushinsky. Ten fungoval na 24 jadrách procesorov Intel Xeon (presnejšie na jeho 48 vláknach).
Súbežne s týmito súťažami sa odohrávajú aj šampionáty softvéru na totožných počítačoch a takisto súťaže šachových mikropočítačov.
Umelá inteligencia Googlu prechádza do nadľudskej úrovne v hre Go
Fascinujúca a starodávna hra Go patrí k enormným výzvam počítačov. Hra má elegantné a jednoduché pravidlá a vždy vyvolávala záujem matematikov. Z hľadiska počtu možných herných pozícii jej šach nesiaha ani po päty. Hracie pole 19 × 19 môže obsahovať až 10170 legálnych herných pozícii.
Aktuálne výpočty z tohto roku presnejšie ukazujú na číslo: 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935.
Neurónová sieť Googlu pred pár mesiacmi po prvý krát porazila európskeho šampióna v Go
K takémuto číslu sa už nič fyzické z nášho vesmíru ani nedá prirovnať. Môžeme to ale skúsiť. Predstavme si, že každý atóm, ktorých je v našom vesmíre 1080, by bol v skutočnosti vesmírom a každý by teda obsahoval 1080 vlastných atómov. Dohromady by všetky tieto atomo-vesmíry obsahovali 10160 atómov, čo je stále menej, než pozícii v hre Go.
Poraziť človeka je však opäť niečo celkom iné. Súčasné systémy hlbokých neurónových sietí sú totiž schopné sa hru naučiť a samostatne sa v nej zlepšovať podobne, ako to robí biologický organizmus.
V minulom roku došlo k historickému úspechu, kedy neurónová sieť Googlu Deep Mind (v rámci svojej časti AlphaGo) porazila európskeho šampióna v Go v piatich zápasoch z piatich (Fan Hui).
Používala algoritmus, ktorý dokázal interpretovať pravidlá, zákonitosti a opakujúce sa vzory v hre a naučila sa ju teda hrať sama. Výsledky boli odhalené 27. januára vo vedeckom žurnále Nature.
Neurónová sieť Deep Mind doteraz vyhrala 99,8 % zápasov proti iným programom a tento mesiac sa postaví proti Juhokórejčanovi Lee Se-dolovi, ktorý je v súčasnosti svetovou dvojkou tejto hry (jednotka je Juhokórejčan Lee Chang-ho). Pôjde o päť zápasov, pričom ten prvý sa uskutoční už túto stredu 9. marca a ďalšie budú nasledovať 10, 12, 13 a 15. marca. Zápasy budú vysielané on-line, takže pokiaľ vás to zaujíma, môžete byť svedkami histórie.
Niektoré stroje sa s nevyhrateľnosťou hry tic-tac-toe nezmierili
