Domov > Různé hry > Umělá inteligence a znalostní báze. Výukový projekt Otázky umělé inteligence, které vedou projekt

Umělá inteligence a znalostní báze. Výukový projekt Otázky umělé inteligence, které vedou projekt

Podívejme se na některé základní koncepty, které nám pomohou vytvořit jednoduchou umělou inteligenci, která umí hrát šachy:

pohybující se;
hodnocení šachovnice;
minimax;
alfa beta limit.

V každém kroku vylepšíme náš algoritmus pomocí jedné z těchto osvědčených technik šachového programování. Uvidíte, jak každý z nich ovlivňuje herní styl algoritmu.

Hotový algoritmus lze nalézt na GitHubu.

Krok 1. Generování tahů a vizualizace šachovnice

Knihovny chess.js použijeme ke generování tahů a chessboard.js k vykreslení desky. Knihovna pro generování tahů implementuje všechna pravidla šachu. Na základě toho můžeme vypočítat všechny tahy pro daný stav desky.

Vizualizace funkce generování pohybu. Výchozí pozice se používá jako vstup a na výstupu jsou všechny možné pohyby z této pozice.

Použití těchto knihoven nám pomůže soustředit se pouze na ten nejzajímavější úkol – vytvořit algoritmus, který najde nejlepší tah. Začneme napsáním funkce, která vrací náhodný pohyb ze všech možných tahů:

Var vypocetBestPohyb = function(hra) ( //Generování všech pohybů pro danou pozici var newGameMoves = game.ugly_moves(); return newGameMoves; );

Ačkoli tento algoritmus není příliš spolehlivým šachovým hráčem, je to dobrý výchozí bod, protože je dostatečně na úrovni, aby nás mohl hrát:

Černý hraje náhodnými tahy

JSFiddle.

Krok 2: Hodnocení rady

Nyní se pokusme pochopit, která strana je v určité pozici silnější. Nejjednodušší způsob, jak toho dosáhnout, je vypočítat relativní sílu kusů na desce pomocí následující tabulky:

Pomocí bodovací funkce můžeme vytvořit algoritmus, který vybere tah s nejvyšším skóre:

Var vypočítejteBestMove = funkce (hra) ( var newGameMoves = game.ugly_moves(); var bestMove = null; //Použijte libovolné záporné číslo var bestValue = -9999; for (var i = 0; i< newGameMoves.length; i++) { var newGameMove = newGameMoves[i]; game.ugly_move(newGameMove); //Возьмите отрицательное число, поскольку ИИ играет черными var boardValue = -evaluateBoard(game.board()) game.undo(); if (boardValue >bestValue) (nejlepšíHodnota = boardValue; bestMove = newGameMove ) ) return bestMove; );

Jediným hmatatelným zlepšením je, že náš algoritmus nyní sežere kus, pokud je to možné:

Černý hraje s jednoduchou funkcí bodování

Co se stalo v této fázi, můžete vidět na JSFiddle.

Krok 3. Prohledejte strom a minimax

Poté vytvoříme vyhledávací strom, ze kterého si algoritmus vybere nejlepší tah. To se provádí pomocí algoritmu minimax.

Poznámka překlad V jednom z našich článků jsme se již zabývali - naučili jsme se vytvářet AI, kterou nelze porazit piškvorky.

V tomto algoritmu je prozkoumán rekurzivní strom všech možných tahů do dané hloubky a pozice je vyhodnocena na „listech“ stromu.

Nadřazenému uzlu pak vrátíme buď nejmenší, nebo největší hodnotu potomka, podle toho, čí tah se počítá (to znamená, že se snažíme minimalizovat nebo maximalizovat výsledek na každé úrovni).

Vizualizace minimaxu v umělé poloze. Nejlepší tah pro bílého je b2-c3, takže můžeme zaručit, že se dostaneme do pozice, kde je skóre -50

Var minimax = funkce (hloubka, hra, isMaximisingPlayer) ( if (hloubka === 0) ( return -evaluateBoard(hra.board()); ) var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) ( var bestMove = -9999; pro (var i = 0; i< newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } };

S minimaxem začíná náš algoritmus chápat základní taktiku šachu:

Minimax s úrovní hloubky 2

Co se stalo v této fázi, můžete vidět na JSFiddle.

Účinnost minimaxu závisí do značné míry na dosažitelné hloubce vyhledávání. To je to, co vylepšíme v dalším kroku.

Krok 4. Alfa-beta výstřižek

Pozice, které při použití alfa-beta ořezávání nepotřebujeme. Strom je navštěvován v popsaném pořadí.

S alfa-beta prořezáváním dosáhneme výrazného zlepšení minimaxu, jak ukazuje následující příklad:

Počet pozic, které je potřeba vyhodnotit v případě vyhledávání s hloubkou 4 a výchozí pozice znázorněné na obrázku.

Co se stalo v této fázi, můžete vidět na JSFiddle.

Krok 5: Vylepšená funkce hodnocení

Původní bodovací funkce je docela naivní, protože jednoduše počítáme body figurek, které jsou na desce. Abychom to vylepšili, začneme brát v úvahu polohu figurek. Například jezdec ve středu šachovnice je „dražší“, protože má k dispozici více tahů, a je tedy aktivnější než jezdec na okraji šachovnice.

1997, New York. Mistr světa v šachu Garry Kasparov prohrává s počítačem Deep Blue od IBM v této největší šachové hře všech dob. O této hře se bude mluvit jako o „poslední bitvě lidské mysli“, mnozí ji budou srovnávat s prvním letem bratří Wrightů a přistáním astronautů na Měsíci.

20. července – Mezinárodní den šachu – vám prozradíme, co se dělo dál. A také o tom, jak je umělá inteligence horší než inteligence lidská a kde s ní má společného Alan Turing. Slovo Garryho Kasparova, mistra světa v šachu a autora knihy.

Paradoxně při simultánní hře s nejlepšími profesionálními šachisty by pro robota bylo nejtěžší pohybovat se mezi stoly a přeskupovat šachové figurky, ne počítat tahy. Ačkoli autoři sci-fi vymýšlejí automaty, které vypadají a pohybují se jako lidé již několik století, a roboti dnes úspěšně vykonávají fyzickou práci, musíme přiznat, že naše stroje reprodukují lidské myšlení mnohem lépe než lidské pohyby.

V šachu, stejně jako v mnoha jiných oblastech činnosti, jsou stroje silné ve věcech, ve kterých jsou lidé slabí, a naopak.

Tento známý princip v oblasti umělé inteligence a robotiky zformuloval v roce Hans Moravec, který poznamenal, že „přimět počítače, aby provedly test inteligence nebo hrály dámu na úrovni dospělého, je poměrně snadné, je obtížné nebo nemožné vštípit jim dovednosti ročního dítěte, pokud jde o vnímání nebo pohyblivost."

V té době jsem si těchto teorií nebyl vědom; Navíc Moravec mluvil o dámě, ne o šachu, ale o deset let později se ukázalo, že tento princip zasahuje i do mého pole působnosti. Velmistři byli vynikající v hodnocení pozic a strategického plánování – slabých míst šachových počítačů, ale dokázali vypočítat taktické důsledky během několika sekund, které by zabraly i těm nejlepším lidským myslím mnoho dní.

To mi dalo nápad. Poté, co moje zápasy s Deep Blue získaly tolik pozornosti, chtěl jsem pokračovat v experimentování se šachy, i když od toho IBM upustilo.

Můj plán, jednoduše řečeno, byl tento: pokud je nemůžete porazit, přidejte se k nim.

Říkal jsem si: co kdyby člověk a stroj nebyli protivníci, ale partneři? Myšlenka byla realizována ve španělském Leonu, kde se odehrál první pokročilý šachový zápas. Oba partneři měli po ruce osobní počítač a během hry mohli používat libovolný program dle vlastního výběru. Cílem bylo dosáhnout nové, nejvyšší úrovně hry – prostřednictvím syntézy největších předností lidské a strojové inteligence. I když, jak uvidíme, ne vše vyšlo podle plánu, úžasné výsledky těchto „bitev kentaurů“ mě přesvědčily, že šachy mají v oblasti interakce mezi lidskou myslí a umělou inteligencí stále co nabídnout.

Nebyl jsem zdaleka první, kdo k tomuto přesvědčení dospěl. Šachové stroje byly svatým grálem dávno předtím, než se je lidé naučili stavět. A nyní věda konečně získala přístup k tomuto poháru – a ukázalo se, že jsem to já, kdo jej drží v rukou. Měl jsem na výběr: odmítnout výzvu nebo ji přijmout. Jak bych mohl odolat? Byla to šance dále zviditelnit šachy a rozšířit publikum, které si získalo od slavného zápasu mezi Bobby Fischerem a Borisem Spasským za studené války a po mých bojích o světovou korunu s Anatolijem Karpovem. To by umožnilo přilákat do světa šachu armádu štědrých sponzorů, zejména z řad high-tech společností. V polovině 90. let Intel sponzoroval sérii turnajů v rapid a klasickém šachu a celé mistrovství světa, včetně mého titulového zápasu s Viswanathanem Anandem v nejvyšším patře World Trade Center. Kromě toho mě poháněla neodolatelná zvědavost. Mohou se stroje naučit hrát šachy tak dobře jako mistr světa? Jsou opravdu schopni myslet?

Zajímalo by mě co
První šachový program se objevil před prvním počítačem.

Byl vyvinut brilantním britským matematikem Alanem Turingem, který rozluštil kód nacistického šifrovacího stroje Enigma. V roce 1952 napsal na papír algoritmus, se kterým mohl stroj hrát šachy, pouze matematik sám fungoval jako centrální procesor. Ukázalo se, že "Paper Turing Machine" je docela schopný hráč. Důvod jeho výstavby přesahoval Turingův osobní zájem o šachy. Schopnost hrát šachy byla dlouho považována za součást lidské inteligence a vytvoření zařízení schopného porazit člověka při této hře mělo být předzvěstí vzniku skutečně inteligentního stroje.

Jméno Alana Turinga je také navždy spojeno se jménem myšlenkového experimentu, který navrhl, později ve skutečnosti provedl a nazval „Turingův test“. Jeho podstatou je zjistit, zda počítač dokáže člověka oklamat tak, že si myslí, že má co do činění s člověkem, a pokud ano, je test považován za splněný. Ještě před mým prvním zápasem s Deep Blue začaly počítače procházet tím, co by se dalo nazvat „Turingovým testem šachů“. Stále hráli dost špatně a často dělali jasně nelidské tahy, ale někdy se jim podařilo zahrát hry, které by na slušném turnaji lidí vypadaly jako doma. Každým rokem byly stroje silnější a silnější, ale jak se vyvíjely, dozvěděli jsme se více o šachu samotném než o umělé inteligenci (AI).

Nedá se říci, že by vyvrcholení 45letého pátrání, které se stalo celosvětovou událostí, dopadlo zklamáním, ale jasně ukázalo, že sestrojit šachový superpočítač není vůbec totéž jako vytvořit umělou inteligenci schopnou odpovídat lidská mysl, o které snil Turing a další.

V podstatě se „mysl“ Deep Blue nelišila od „mysli“ programovatelného budíku.

Pomyšlení na to ve mně jen prohloubilo hořkost porážky – prohru s programovatelným budíkem, dokonce i s takovým, který stál 10 milionů dolarů?!

Takzvaná komunita umělé inteligence byla jistě potěšena výsledkem a pozorností, kterou vzbudil, ale zároveň byli vědci zjevně sklíčeni skutečností, že Deep Blue se v ničem nepodobá umělé inteligenci, o které snili jejich předchůdci. Místo toho, aby hrál šachy jako člověk – předváděl lidskou intuici a nestandardní kreativní myšlení – hraje šachy jako stroj: vyhodnocuje až 200 milionů možných tahů za sekundu a vyhrává díky hrubému výpočetnímu výkonu. To samozřejmě nijak neubírá na samotném úspěchu. Koneckonců, Deep Blue je výtvorem lidské mysli a ztráta člověka pro stroj, který vytvořil, znamená zároveň jeho vítězství.

Po neuvěřitelném napětí toho zápasu, ke kterému se přidalo podezřívavé chování IBM a moje tendence pochybovat, jsem nebyl připraven snadno přiznat porážku. Abych byl upřímný, nikdy se mi nedařilo prohrávat. Věřím, že člověk, který snadno přijme porážku, se nikdy nestane skutečným šampionem a tento princip samozřejmě platí i v mém případě. Ale věřím ve férový boj. V té době jsem věřil, že mě IBM oklamalo – stejně jako celý svět, který náš zápas bedlivě sledoval.

Musím přiznat, že znovu analyzovat každý aspekt toho neslavného boje s Deep Blue nebyl snadný úkol.

Léta jsem se záměrně vyhýbal jakékoli diskusi na toto téma, dotkl jsem se pouze toho, co je již známé široké veřejnosti.

Existuje velké množství publikací věnovaných Deep Blue, ale tato kniha je první a jediná, kde jsou shromážděna všechna fakta a celý příběh je vyprávěn tak, jak ho vidím já. I přes bolestné vzpomínky to byla poučná a přínosná zkušenost. Můj velký učitel Michail Botvinnik, šestý mistr světa v šachu, mě naučil hledat pravdu v každé pozici. A já se snažil splnit jeho přání a hledat pravdu v samotné podstatě Deep Blue.

Ilustrace: Shutterstock

Vyvinutý inženýry z Massachusetts Institute of Technology. Fischer dal počítači třikrát mat a získal bezpodmínečné vítězství. Ve svých dopisech šachista napsal, že programy dělají „hrubé chyby“ a samotné počítače nazval „zbytečnými kusy železa“.

Ale téhož roku Monty Newborn, jeden z prvních vědců, kteří studovali počítačové šachy, pronesl prorocká slova:

„Velmistři se chodili smát na turnaje v počítačovém šachu. Nyní přijdou pozorovat a v budoucnu tam budou studovat.“

Bobby Fischer poté, co porazil počítač. Foto: Getty Images

Zdá se, že lidé mají nějaký druh vrozené lásky k hrám mysli. Když byl v roce 1649 anglický král Karel I. odsouzen k smrti, vzal si s sebou na popravu dvě věci – Bibli a šachy. Slavný umělec 20. století Marcel Duchamp na vrcholu své kariéry náhle odešel do Argentiny a začal vyřezávat šachové figurky ze dřeva a vůbec se začal zajímat o šachy. V 19. století se v Japonsku odehrál záhadný příběh související s hrou Go. Podle legendy řekli duchové jednomu slavnému hráči tři skvělé tahy. Díky tomu dokázal vyhrát a po hře jeho soupeř spadl na podlahu, udusil se krví a zemřel.

Počítače jsou daleko od tohoto mysticismu, ale za pouhých pár desetiletí prostudovaly intelektuální hry hlouběji než lidstvo za tisíciletí. V roce 2014 společnost získala DeepMind za 400 milionů dolarů, aby „prováděla ten nejneobvyklejší a nejkomplexnější výzkum, jehož konečným cílem je odhalit podstatu inteligence“. Vědci chtěli především naučit počítač hrát Go. Tato hra je mnohem složitější než šachy. V roce 1985 tchajwanský průmyslový magnát řekl, že zaplatí 1,4 milionu dolarů za program, který by mohl porazit nejlepšího hráče Go. Tycoon zemřel v roce 1997 a o tři roky později jeho nabídka vypršela - nikdo se nemohl domoci ceny.

Nyní by mohl patřit do programu DeepMind AlphaGo, který využívá moderní neuronové sítě. Před rokem byla mezinárodní šampionkou Go Lee Sedol. V květnu letošního roku opět porazila nejlepší hráčku Go, stejně jako tým dalších pěti profesionálních hráček.

AlphaGo se stal absolutním šampionem. Brzy po jejích velkých vítězstvích ji ale čeká zapomnění. Na konci května DeepMind v tichosti oznámil, že AlphaGo opouští konkurenční scénu. K této příležitosti společnost zveřejnila 50 verzí her, které si program sám proti sobě zahrál. V budoucnu chce DeepMind vydat závěrečný výzkumný dokument, který bude popisovat efektivitu algoritmu programu.

Pokud jde o šachy, lidstvo v nich ztratilo dlaň 20 let před těmito událostmi, když šachista Garry Kasparov prohrál se superpočítačem IBM Deep Blue. Chess and Go nejsou jediné hry, které se snaží naučit AI. Snažili se naučit počítač dámu, backgammon, reversi, poker a mnoho dalších deskových her. A lidská inteligence se už nemůže srovnávat s inteligencí umělou. Částečně to bylo způsobeno rozvojem technologií. Například ještě v roce 1997 byl počítač Deep Blue na 259. místě v seznamu nejrychlejších superpočítačů na světě a dokázal provést asi 11 miliard operací za sekundu. Nyní, díky moderním algoritmům, může Kasparova porazit i váš smartphone.

Garry Kasparov versus počítač Deep Blue. Vlevo je jeden z inženýrů IBM Xiong Feixiong. Foto: Getty Images

Takové úspěchy AI způsobily v lidech docela lidské emoce: smutek, depresi a zoufalství. Poté, co byl Lee Sedol poražen AlphaGo, utrpěl existenční krizi. "Pochyboval jsem o lidské vynalézavosti," přiznal po zápase. "Začal jsem pochybovat, zda všechny pohyby Go, které jsem znal, byly správné." Podle jednoho očitého svědka Lee po porážce vypadal, jako by byl „fyzicky nemocný“. Kasparov se po prohře s počítačem necítil o nic lépe. Když se vrátil do hotelu, jednoduše se svlékl, lehl si do postele a díval se do stropu.

"Počítač analyzuje některé pozice tak hluboce, že hraje jako bůh," řekl Kasparov.

Deep Blue poprvé ukázal veřejnosti, že počítač může překonat lidi při řešení intelektuálních problémů. "V tu chvíli to byl šok," řekl Murray Campbell, spolutvůrce Deep Blue. "Nyní si na tuto myšlenku postupně zvykáme." Není však jasné, co čeká lidstvo v budoucnu. Jak lze úspěchy ve hrách využít v reálném světě? Campbellova odpověď na tuto otázku zní pesimisticky. "Je těžké najít dobrý příklad toho, jak tyto pokroky byly aplikovány na deskové hry," řekl. - Na počátku 90. let se zaměstnanec IBM jménem Gerald Tesauro pokusil naučit umělou inteligenci hrát vrhcáby a udělal určité pokroky v motivačním učení. Nyní se jeho metody často používají v robotice. Jeho případ je však spíše výjimkou z pravidla.“

Historie vývoje automatizace a výpočetní techniky je podivně spjata se šachy. V 18. stol „myslící“ šachové automaty sloužily k trikům a podvodům. První stroj se skutečnou umělou inteligencí, který vznikl ve Španělsku na začátku dvacátého století, dokázal dát šachistovi hrajícímu s králem mat s králem a věží. Zřejmě není náhoda, že jedním z prvních skutečně intelektuálních úkolů zadaných programátorům na úsvitu výpočetní techniky bylo hraní šachů. Jeden z těch, kdo vytvořili první šachové programy, doktor technických věd, profesor Vladimir Lvovich Arlazarov, hovoří o šachových programech a propojení této prastaré hry s vývojem technologií umělé inteligence.

– Vladimíre Lvoviči, jak jste přišel na myšlenku, že počítač může řešit intelektuální problémy?

– Když zjistili, že počítače dokážou nejen vypočítat, jak bylo vynalezeno od samého počátku, že za aritmetickými operacemi se skrývá logická akce, která plní nejen pomocné funkce při činnostech počítačových programů, ale s jejichž pomocí je možné řešit nezávislé problémy, stalo se Je to jasné: stojí za to zkusit dát do počítače intelektuální úkoly. Někde od konce 40. do konce 50. let se o tom aktivně diskutovalo, navíc byly položeny polofilozofické otázky: možná budou počítače chytřejší než lidé? A pak co? A to vše se vší vážností. Dnes se takové otázky nekladou, koneckonců uplynulo 40 let. Pak, na úsvitu výpočetní techniky, jsme si teprve uvědomili, co stroje v principu umí. Uvědomili jsme si, že lidský mozek je zařízení podobné počítači a tisíckrát, milionkrát výkonnější, ale zásadně se mírně liší. Ukázalo se, že přinejmenším většinu racionálních problémů, které člověk řeší, lze přiřadit stroji. Proto se můžete pokusit napsat programy, které tyto problémy vyřeší. Jeden, dva, tisíc... vždyť člověk také neřeší nekonečné množství problémů. A je možné, abych tak řekl, naprogramovat veškerou intelektuální aktivitu člověka.

– Proč jste se rozhodli přejít ke hře?

– Jak jsem již řekl, široce se diskutovalo o tom, zda stroj může myslet. Je však naprosto jasné, že pokud se bavíme o programátorech, o lidech, kteří se zabývají nikoli filozofií, ale skutečným počítačem, tak otázka nezní, jestli ten stroj principiálně něco umí, ale v hledání příkladů, kde stroje rozhodovat o intelektuálních úkolech a o těch, které jsou člověku přístupné v jeho intelektuální činnosti. Hranice zde samozřejmě není jasná. Je však jasné, že pokud člověk vynásobí 20místná čísla, pak se nezabývá hluboce intelektuálním úkolem, protože k jeho provedení je velmi snadné najít triviální algoritmus, který zná každý školák. Ale ty úkoly, u kterých je naprosto jasné, že člověk nemá žádný apriorní algoritmus, ale přesto je řeší dobře, budeme nazývat intelektuální. Prvními uchazeči o takové úkoly jsou hry, a to z toho prostého důvodu, že alespoň pravidla jsou jasně daná. Úkol je to nesmírně obtížný, ale pravidla hry se dají snadno formulovat, a tím snadno určit funkce stroje. Na druhou stranu jsou pro člověka šachy těžký úkol, o kterém se jaksi nikdy nemluvilo a ani se teď nemluví.

– Proč sis vybral jako hru šachy? Možná tradice?

– Proč jen šachy? Zkoušeli jsme přespolní a jiné hry. Ale šachy mají oproti jiným hrám mnoho výhod. Pokud v jednoduchých hrách stroj porazí člověka, pak to nikoho nepřekvapuje. Šachy jsou těžká hra a počítačové vítězství je významné. Pak v šachu, na rozdíl od řady jiných her, existuje mnoho rozlišitelných kritérií kvality, to znamená, že můžete určit: stroj hraje dobře, stroj hraje lépe, lépe, lépe. V mnoha jiných hrách se taková gradace stanovuje velmi obtížně. V některých z nich je automat buď naučený hrát naprosto přesně, a tím okamžitě ztratí veškerý zájem o hru, nebo se hraje extrémně špatně. A v šachu, ne abstraktním, ale takříkajíc zvládnutém, existuje tolik úrovní, že s jejich pomocí můžete určit třídu hry stroje.

– Je tedy jasné, proč byly šachy jedním z prvních a nejdůležitějších úkolů umělé inteligence. Jaké metody byly použity k jeho řešení?

– Od samého začátku jsem si postupně osvojoval metodiku řešení problému šachové partie. Šachy jsou v principu konečná hra a lze s matematickou přesností dokázat, že v jakékoli pozici, abstraktně, existuje pro každého soupeře nejlepší tah, a tedy nějaký výsledek. Proto je nutné popsat algoritmus, ve kterém lze tuto hru dopočítat do konce. Jedinou nevýhodou takového algoritmu je, že vyžaduje spoustu času. A nejsme o nic blíže k časovým řádům potřebným k výpočtu, řekněme, šachu do konce z výchozí pozice. Za posledních padesát let zůstal tento úkol z hlediska času nekonečně složitý. No, nekonečno mínus deset je pořád nekonečno. Ale pokud potřebujete čas, řekněme, 10 až 100. mocninu let a zrychlíte stroj, řekněme, 100krát a získáte 10 až 98 mocninu let, pak to pravděpodobně nebude jednodušší. Proto je hlavní algoritmus vyčerpávající, triviální: když to udělám, nepřítel má tolik možností. Možnosti rostou exponenciálně a tvoří řetězce. Ale počet pozic je obecně konečný a na každém řetězci jich není tolik. Řetězy jsou spojeny do stromů, které opět nejsou nekonečné. Pravda, rostou exponenciálně a počet řetězců se zvyšuje. Nabízí se tedy důležitá otázka: je nutné úplné hledání až do samého konce - ke všem matům, patům, trojitým opakováním a dalším zakončením partie podle šachových pravidel? Koneckonců, pokud algoritmus vede k pozicím, které nejsou na tomto stromě nutné, pak možná není třeba uvažovat celý tento strom. Všimněte si, že v situaci, kdy se bílý páří jedním tahem, můžete postavit stejný nekonečný strom, ale nemusíte o tom uvažovat, stačí najít tento jediný tah. Možná stejná situace platí pro šachy obecně? Algoritmus výčtu, výčtu možností se obecně vztahuje k tolika problémům řešeným lidmi, že kdybychom věděli, jak to zorganizovat nějakým velmi originálním způsobem, pak by to bylo v jistém smyslu jako vynález kola pro lidstvo - jeden z nejzásadnějších objevů. Hrubá síla by tedy mohla být, a možná i je, kolo umělé inteligence.

– V jednom z článků o umělé inteligenci jsem četl, že inteligence je schopnost rozumět a vybírat. Naučit počítač vybírat z mnoha možností je přirozeně velmi obtížné. Jsou však možná některá řešení specifická pro šachy?

- Ano ano. Tento problém bylo třeba rychle a efektivně vyřešit a v šachu rychle dospěli k následující teoretické formulaci otázky: nedívejme se na nekonečný počet tahů, ale jen na několik tahů dopředu. Řekněme, že se podíváme o 5 tahů dopředu. To je hodně. Pokud milujete šachy a 5 tahů se vám zdá málo, tak si vezměme 10. A pak automat, 10 tahů, 20 půltahů dopředu, neudělá žádnou chybu a zaručí, že po 10 tazích nebudete mít méně kousky. Je jasné, že máme co do činění se silným herním strojem. Takže strom hry bude muset být zkrácen a problém vyřešen na mnohem omezenějším prostoru. Další otázkou je, že se snaží tento strom zvážit neúplně pomocí matematických metod řezání. O jednom z nich jsem již mluvil: pokud je v jednom tahu mate, není třeba se ohlížet na další možnosti. Jiné algoritmy jsou heuristické a nepřesné. V průměru fungují správně, mnohé jsou naprosto přesné, ale mohou se také mýlit. Můžeme například projít ne všechny tahy, ale pouze zajetí a vypočítat je hodně dopředu, protože zajetí je málo. Celková hloubka pohybů je malá: nemůžete jíst více než třicet dva kousků. Proto jsou délky řetězů malé a je zde málo větví. Samozřejmě je jasné, že hru nelze postavit pouze na zajetí, musí být bráno v úvahu určité poziční úvahy. Kombinace vynucení (zachycení, kontrola) a úvah o poloze, stejně jako určitá hloubka vyhledávání, je základem všech existujících algoritmů a příliš se nemění. Další otázka: jak vybrat tahy, které budu dále zvažovat? Pouze na základě jednoduchých formálních kritérií (zajmout, zkontrolovat) nebo spojit tyto tahy, jak rádi říkají šachisté, s plánem, vymyslet nějaké řetězce, které mají nějakou společnou vlastnost? V každém případě o tom bylo napsáno mnoho seriózních prací s praktickými aplikacemi. Ne nadarmo se na tvorbě šachových programů podílejí poměrně renomované společnosti.

– Kdy se objevily první šachové programy?

– Skutečné šachové programy se poprvé objevily někde na konci 50. let v Americe a pak někde na začátku 60. let u nás. Programy byly velmi slabé, protože v té době existovaly extrémně primitivní stroje a naše myšlení ještě nebylo zvyklé na novotu. Do tohoto podnikání jsme se zapojili kolem roku 1963. Pak byly nějaké zápasy na našich domácích autech. Podle mě v roce 1967 došlo k prvnímu zápasu mezi SSSR a USA. Říkalo se tomu, i když se to samozřejmě odehrávalo mezi dvěma týmy, a ne zeměmi. Byl to zápas mezi naším programem vyvinutým na Ústavu teoretické a experimentální fyziky a programem Johna McCarthyho, velmi známé osobnosti v počítačovém světě, jednoho z tvůrců programovacích jazyků, který měl tehdy rád šachové programy. Pohyby se přenášely telegrafem, protože tehdy neexistovaly žádné sítě.

– A kdo vyhrál?

Tehdy jsme vyhráli 3:1. Hrály se 4 hry. Přesun se dělal každý den, protože Američané měli výkonnější a hlubší programy, které myslely dlouhou dobu, a hráli jsme na různých verzích programů, které myslely rychle i pomalu. Naše vítězství bylo naším prvním úspěchem. Tento směr se začal postupně rozvíjet a zvláště aktivní v 70. letech. Kolem roku 1974 se ve Stockholmu konalo první mistrovství světa mezi šachovými programy. Zúčastnilo se asi osm programů, včetně našeho. A pak jsme také vyhráli a stali se prvními mistry světa. Od té doby se mistrovství světa konají pravidelně, každé 3 roky. Zúčastnili jsme se jich ještě dvakrát - v roce 1977 a v roce 1980. Tehdy jsme nezískali žádný vavřín, protože v roce 1977 jsme se dělili o 2. a 3. místo (účastnilo se mnoho šachových programů, byly dokonce krajské výběry), v roce 1980 - 4. resp. 5. místo. Obecně se pomalu vracely zpět. Faktem je, že v této době již došlo k obrovskému pokroku ve výpočetní technice a stále jsme hráli na poněkud zastaralých počítačích. A v roce 1980 nám bylo jasné, že soutěžit na strojích, na kterých pracujeme, ztratilo veškerý smysl a obecně začala práce na poli šachových programů v Rusku přicházet vniveč. I když zajímavých teoretických prací bylo poměrně dost. O něco později vytvořili snad první program, který obletěl svět a dokázal naprosto přesně zahrát komplexní koncovku, tedy dámu a pěšce proti dámě nebo věž a pěšce proti věži. Program takové koncovky jednoduše zvážil až do konce, tj. v jakékoli pozici dal naprosto správný pohyb. Algoritmus byl postaven na principech mírně odlišných od jednoduchého výčtu, na úplné kontrole celé sady pozic. No, pak udělali nějakou práci tohoto druhu v šachu. A pak jsme se rozloučili s praktickou hrou, protože rozdíly v rychlostech byly již stonásobné. Ale šampionáty pokračovaly a vývoj šachových programů postoupil na zcela novou úroveň, jakmile se vše přesunulo na PC. V důsledku rozsáhlé komercializace se začaly do šachových programů investovat obrovské peníze a vše bylo okamžitě utajováno. A dříve patřili k vědcům, kteří, pokud nejsou výslovně donuceni, své úspěchy neskrývají, ale naopak propagují. V roce 1980 jsme poprvé pocítili, že nastal čas pro komerční programování. Tento svět je samozřejmě jedinečný. Za prvé proto, že se do něj investují peníze, a za druhé proto, že se z něj peníze těží. Přestože existují časopisy o šachových programech, za posledních 15 - 17 let se skutečná výměna nápadů značně zmenšila, protože se z nich stal obrovský byznys na PC.

– Ale obchod stimuluje rozvoj trhu se šachovým softwarem?

– Dříve byly počítačové soutěže načasovány tak, aby se kryly s fóry výpočetní techniky. Existuje taková organizace - IFI (Mezinárodní federace informatiky) a mistrovství světa jsou obvykle načasována tak, aby se kryla s jejím kongresem. Nyní se staly zcela nezávislými akcemi, docela prestižními. Takových programů jsou již stovky a stovky. Samotná úroveň programování a úroveň našich znalostí je již taková, že vyrobit jednoduchý šachový program není sebemenší problém. To je normální studentská práce. Jen to svěřím nějakému studentovi. Porazit šachový program se stalo takříkajíc samozřejmostí.

– Ale jako vždy, nižší úroveň se stává jednodušší a vyšší se stává komplikovanější?

- A je to. Proto nejnovější programy, ty, které nyní vítězí, zejména program, který porazil Kasparova, se staly mnohem silnějšími. Hloubka hledání se výrazně zvýšila a je to samozřejmě výsledek našeho matematického pokroku a částečně jednoduše pokroku výpočetní techniky. Koneckonců, pokud dříve bylo zvažováno zvažování 1000 pozic za sekundu, nyní se v těch stromech, o kterých jsme již mluvili, uvažuje více než milion pozic. A milion navíc znamená několik úrovní tahů se správným výběrem. A každá úroveň hloubky vyhledávání výrazně posiluje program. Každá úroveň na pohyb vpřed je přibližně hodnost a řekněme hloubka hledání čtyř tahů je třetí pozice a pět tahů je již druhá pozice. Když dosáhneme úrovně 11–13 tahů, jedná se o mistrovskou úroveň a je poměrně obtížné pokračovat ve hře se strojem. Samozřejmě teď vedou Američané, protože vědí, jak do takových věcí investovat velké peníze.

– Jakýkoli program umělé inteligence pro rozhodování potřebuje nejen heuristické mechanismy, ale také nějaký druh znalostní báze. Jaký je vztah mezi znalostní bází a algoritmy, které generují pozice v šachových programech?

– Nikdo to nemůže říct s jistotou, protože jde o spekulace. Existovaly docela silné programy s prostě minimálními znalostmi, záměrně minimálními, konkrétně proto, aby viděli, co se dá vymáčknout z čisté matematiky. V určitém okamžiku to bylo způsobeno komercializací a zejména tím, že začali vyrábět co nejvýkonnější programy - bez ohledu na to, co. Ale částečně díky tomu, že práce s vloženými znalostmi je samostatný úkol, je jich hodně. Nejprve byla vytvořena obrovská referenční kniha. Nyní adresáře obsahují stovky tisíc pozic. Do hodnocení pozic se pak vždy investuje hodně šachové inteligence. Záleží samozřejmě na hracím materiálu, který je triviální, a na některých pozičních faktorech. Takže poziční faktory jsou čistě šachová inteligence, která je samozřejmě naprogramovaná, ale tady se toho hodně stanoví a neustále se zlepšuje. A čím více faktorů je do toho vloženo, tím silnější je program. Schopnost vyhodnotit pozici a hloubku hledání jsou v jistém smyslu vzájemně zaměnitelné věci. Kdybychom uměli bravurně vyhodnotit pozici, tak by nám stačilo vyzkoušet všechny první tahy. To je jako extrémní příklad. Je zřejmé, že lepší posouzení pozice má odpovídajícím způsobem větší vliv na hloubku vyhledávání. Toto je druhá, základní metoda. Existuje poměrně hodně programů, kde je šachová inteligence zakotvena ve výběru samotných možností, tedy nějaké čistě šachové úvahy, nějaké plány. Takových úvah je poměrně hodně, což omezuje rozsah vyhledávání. Oblast jejich působnosti není příliš široká a intelektuální data specifická pro šachy zpomalují vyhledávání. Mimochodem, právě pro intelektuální věci Botvinnik kdysi silně obhajoval. Byl velkým nadšencem pro strojové šachy a přispěl tam několika nápady. Sice se mu nikdy nepodařilo vytvořit fungující program, nicméně jeho autorita byla v té době velmi vysoká. Takže byl velmi naštvaný, že obecně není směr tak „intelektuální“, jak by si přál, a do programů bylo investováno velmi omezené množství čistých šachových znalostí.

– A co specializované šachové počítače? Jednají zřejmě přesně metodou generování?

- Samozřejmě. Za prvé, z hlediska generování je vyhledávání schematické. Za druhé, neméně důležité jsou jakékoliv tabulky pozic, protože v šachu je opakování pozic velmi vysoké. Jdete E4E6D4 nebo D4E6E4 - pozice bude stejná, ale jedná se pouze o 3 poloviční tahy. A když začneme jít hlouběji, opakování pozic je velmi vysoké. Za třetí, technická oblast. Vlastně jsme svého času budovali teorie o tom, u kterých pozic lokální změny zásadně nemohou vést ke změnám vynucených možností, jak vytvořit nějaké šablony. Šablony pro takové možnosti dobře zapadají do různých čistě technických počítačových schémat. Velmi důležité jsou samozřejmě referenční diagramy.

– Existují nějaké prostředky k vytvoření univerzálního mentálního aparátu, do kterého by se dala vložit znalostní báze – nezáleží na šachových pozicích nebo čemkoli jiném, pravidla, podle kterých se s těmito znalostmi musí pracovat – a získat z toho adekvátní výsledky?

– Je jasné, že z hlediska konstruktivity se dnes takový úkol vyřešit nedá a není relevantní. I když se nyní řeší mnoho intelektuálních problémů, jako je rozpoznávání textu. Můžete vložit kus textu do skeneru a zobrazit jej na obrazovce ve Wordu. Přečte se to samo, pozná se každé písmeno. Ve skutečnosti jsme pokročili v mnoha intelektuálních úkolech. Některé z nich jsou již vyřešeny, jiné se řeší. V některých ohledech to funguje srovnatelně lépe než s lidskou účastí, v jiných je to stále horší. Příkladů praktických problémů je mnoho. Pokud jde o univerzální umělý mentální mechanismus, je to spíše filozofický problém než praktický. Vždyť i u tak jednoduché hry, jako jsou šachy, nám trvalo 30 - 40 let, než jsme něčeho skutečně dosáhli. Veškerá filozofie je založena na názorech. Každý si myslí, že má pravdu a možná každý má svým způsobem pravdu. Umělou inteligencí se například zabývám celý život a věřím, že lidský mozek není nic jiného než velký počítač, proto nelze říci, že je v podstatě nemožné vytvořit mu podobný. Otázkou je jeho výkon, rychlostní charakteristiky a naplnění znalostí. Není zde nic nepochopitelného. To je můj osobní úhel pohledu. Ale jsou i jiné názory. Samozřejmě, pokud rozpoznáme božskou podstatu člověka, pak musíme zvolit jednu ze dvou epistemologických možností. Buď ano, máme božskou přirozenost, ale je to poznat. V tomto případě nebudeme schopni pravdivě reprodukovat to, co Pán Bůh dokázal, ale alespoň budeme moci Jeho výtvory alespoň částečně znovu vytvořit. Nebo stojíme na pozici agnosticismu, a pak je to nepoznatelné a otázka je zcela odstraněna. Ukazuje se, že lidský mozek řeší některé problémy – a nikdo o tom nepochybuje. Ale mozek nemůžeme dohnat, protože ho na jedné straně stvořil Bůh a na druhé ho nejsme schopni poznat. Všechny tři pozice jsou spojeny s vírou, protože ve skutečnosti není nutné znát všechny funkce mozku. Pokud vyrobíme stroj se stejnou silou jako mozek, nebude mít potřebu myslet jako mozek. Bude to fungovat jinak.

– V psychologii, pokud vím, je intelektuální vývoj člověka určován třemi kritérii: schopností abstrahovat, vytvářet intelektuální řadu a ještě něčím... Do jaké míry jsou tyto schopnosti realizovány v umělé inteligenci a jsou realizovány vůbec?

– Existuje mnoho programů, které jsou specificky zaměřeny na vytváření konceptů, které abstrahují od existujícího faktického materiálu. Takové programy fungují dobře. Další otázkou je, že člověk ví, jak tyto pojmy vytvořit, jakoby podle svých zákonů, které si sám vymyslí. Všechny naše pokusy přeložit tyto jeho zákony do jazyka logické algebry se ukázaly jako marné. Lidé mají mnohem silnější mechanismus myšlení, který prostě neznáme. Nevíme, jak „vůbec“ nic dělat. Vytváříme formulace, které potřebujeme, ale nemůžeme je „vyjádřit“ v přesných strojových problémech. Všechno se s obtížemi přiblíží mechanickým problémům, a i když se to pokazí, je to pomalé. Pravděpodobně zatím neznáme přímější cesty k dosažení cíle. Do počítače můžete vložit cokoliv. Otázkou je, že s těmito znalostmi je člověk schopen neustále manipulovat, ale zatím neví, jak k tomu samému přinutit stroj kvůli omezenému objemu a rychlosti dat.

– Možná ale nedává smysl nutit stroj, aby manipuloval se znalostmi?

– Zde se dotýkáme jak nemorálních, tak konstruktivních aspektů. K bouřícím strojům máme ještě hodně daleko. Určitě bude dostatek klidu pro můj život a pro váš taky. Ani v omezených oblastech jsme se ještě nenaučili, jak přinutit stroj, aby manipuloval s úkoly, dokonce i s těmi, které dokáže vyřešit. Zadali jsme úkol a ona myslí jen na povel.

– Vladimíre Lvoviči, řekněte mi, kdyby nyní opět nastal úsvit výpočetní techniky, stálo by za to pracovat na šachových programech? Opravdu tolik přispěli k pokroku?

– Přesto nám šachy rozšiřují obzory. V šachových programech se zadávají úkoly, je vidět výsledek, hodnotíme ho. Přesto by mělo existovat mnoho vyřešených zajímavých problémů, což přispívá k pokroku ve výpočetní technice.

Předmět, věk studentů

Informatika a ICT, 10.-11. ročník

Stručné shrnutí projektu

Projekt byl vypracován v rámci disciplíny „Informatika a ICT“ pro žáky 10.–11.

Otázky vedoucí k projektu

Základní otázka

Může počítač nahradit člověka?

Problematické problémy

1. Může počítač sám představovat problémy a řešit je?

2. Je počítač schopen reprodukovat všechny lidské činy a myšlenky?

3. Je počítač schopen ovládat člověka?

Studijní otázky

1. Jaké problémy řeší počítač?

2. Učí se počítač sám?

3. Mohou stroje nahradit člověka?

4. Umělá inteligence=Lidská inteligence?

5. Je nutné dohlížet na provoz počítače?

6. Je možné postavit robota „do čela stolu“?

7. Dokáže počítač myslet?

8. Je možné nahradit lidský mozek umělým?

9. Jsou lidé připraveni svěřit veškerou práci robotům?

Plán projektu

Prezentace problémové situace:

Učitel potřebuje brainstorming se studenty, aby identifikoval stávající znalosti studentů o problému, jejich motivaci, sklony a zájmy. Nástroj je brainstorming pomocí úvodní prezentace. Učitel pomocí prezentace vytváří problémovou situaci, organizuje brainstorming, diskutuje o vzniklých problémech, předkládá hypotézy a rozděluje studenty do tematických skupin s ohledem na jejich zájmy.

Projektová práce:

V počáteční fázi práce na projektu učitel pomáhá jednotlivým tematickým skupinám přidělovat role, diskutovat o strategii výzkumu, metodách vyhledávání informací, metodách výzkumu a možnostech formátování výsledků práce. Výsledkem je individuální plán aktivit. Dále začíná samostatná výzkumná a rešeršní práce studentů v souladu s plánem. V této fázi studenti shromažďují informace na téma problematického problému v encyklopediích, učebnicích a na internetu, diskutují o shromážděných informacích ve skupině, vyvíjejí výzkumné nástroje, provádějí výzkum, porovnávají jeho výsledky se shromážděnými informacemi a vyvozují závěry, které odpoví na problematickou otázku. Učitel by se měl zaměřit na středně pokročilé diskuse, diskuse ve skupinách a konzultace s učiteli předmětů Sebehodnotící list pomůže účastníkům projektu porozumět úrovni osobního růstu.

Registrace výsledků projektových aktivit:

Výsledky se plánují prezentovat ve formě prezentace, brožury nebo wiki článku, takže zde možná budete potřebovat konzultaci s učitelem informatiky, na jedné z konzultací je potřeba prodiskutovat kritéria pro hodnocení těchto produktů s studentů. Zároveň se připravuje výkon skupiny, takže hodnotící kritéria musí obsahovat body pro hodnocení výkonu žáků, schopnost klást otázky a odpovídat na ně.

Obhajoba projektu, opozice, diskuse:

Při obhajobě každá skupina prezentuje svou práci (prezentaci, brožuru nebo wiki článek) a odpovídá na otázky. Hodnocení probíhá pomocí kritérií vytvořených členy skupiny, členy jiných skupin a učiteli. Obhajoba projektu umožňuje odpovědět na zásadní otázku a na základě výsledků práce formulovat obecné závěry.

Po dokončení práce:

Nezbytnou součástí všech projektových aktivit je analýza odvedené práce, kdy učitel se studenty diskutuje o tom, co dělali, co nefungovalo a proč. V této fázi se můžete znovu podívat na sebehodnotící list a vidět kvalitativní růst každého účastníka. Navíc je možné uspořádat reflexi na blogu. Důležitým se stává odměňování skupin Výsledky práce najdete na stránkách projektu.