Predstava, ze staci pouzit hrubou silu, je naivni. Pocet moznosti, ve kterych se pocitac muze octnut po x-tem pultahu roste s x exponencialne, pricemz zaklad mocniny je u sachu kolem 30-35. (Zajit pri prohledavani o jeden pultah hloubeji tedy znamena pocitat asi 30krat dele) Propocitat si nasledujici 4 tahy (8 pultahu) by tedy vyzadovalo analyzovat asi 650-2250 miliard pozic, coz je myslim pro "bezny Athlon" docela fuska. (frekvence rekneme 1000MHz, jedna instrukce za takt a jedna pozice vyhodnocena jednou instrukci - takovyto pocitac by pocital 4 tahy asi 650-2250 sekund, coz je neco od deseti minut do vice nez pul hodiny (ve skutecnosti vetsina instrukci trva vice nez jeden takt a instrukci je pro analyzu pozice potreba mnoho, takze spise by to byly jednotky dni)) Prohledani do hloubky 8 tahu (cca 10^24 pozic) algoritmem hrube sily je pro jakykoliv dnes existujici pocitac v nasledujicich 100 letech nemozne. Pro tyto problemy plati, ze o trosku lepsi algoritmus je daleko lepsi nez mnohokrat rychlejsi pocitac. Vylouceni neperspektivnich tahu co nejdrive tak muze vyrazne zvetsit hloubku, do ktere je mozne stavovy prostor prohledat.
"...dnes existujici pocitac v nasledujicich 100 letech nemozne"
Tohle si trochu protireci. Pro dnesni pocitace to zustane navzdy nemozne, na tom se shodneme. U pocitacu 'zitrejsich' bych si tim nebyl tak jisty. Kdo vi, co bude za 100 let?! Ja ne! Myslim si ale, ze je jen otazkou casu, kdy pocitace zacnou sachum dominovat pri pouziti hrube sily.
Mozna s pomoci kvantovych pocitacu pujde projit cely strom hry a zjistit kdo (cerny nebo bily) ma jistou vyhru pri idealni hre anebo mozna takovy zapas konci remizou. Problem je vytvorit takovy algoritmus pro kvantovy pocitac a to ze pozic v sachu je vic nez atomu ve vesmiru neni prekvapive ten nejvetsi problem.
Pozic v sachu je vice nez atomu ve vesmiru? Pocet pozic je IMHO mnoho, ale stale konecne mnozstvi aneb matice vyuzitelneho prostoru sachovnice je nemenna, coz se o stale se rozpinajicim vesmiru rici neda. ;-)
Ale je to zajimavy clanek a zajimalo by me, zda autor se venuje vice neuronovym sitim a AI nebo teorii sachu nebo programovani? :)
- ad "prohledat vše na kvantovém počítači". jedna vec je navrhnout algoritmus (neznám ho, otázka je to však velmi zajímavá), druhá je faktická konstrukce počítače. obávám se, že na tomto poli přichází jistá deziluze. kdy jste na poli kvantových počítačů zaznamenali nějaký poslední pokrok?
- výsledkem prohledání na kvantovém počítači by téměř jistě byla remíza. lze to dovodit z extrapolace - čím silnější hráči -> tím větší procentuální zastoupení nerozhodných výsledků.
- ad hrubá síla a exponenciální nárůst možností: samozřejmě, že nějaká vylepšení jsou. jak jsem psal, počítá se od určité hloubky jenom něco. taktéž lze zesložiťovat hodnotící funkci.
- teď jsem na toto téma korespondoval s dušanem dobešem, autorem phalanx. ani současné programy neumí v pravém slova smyslu "rozpoznávat vzory". kdo četl Makrosvět, mikrosvět a lidská mysl od Hawkingova spolupracovníka Rogera Penroseho, on toto přirovnává k matematickým důkazům a k důkazům toho, že lidské myšlení není v některých ohledech algoritmické. V té knize jsou uvedeny i speciální pozice. To je samozřejmě téma na úplně jiný článek, který by ale byl spíše filosofický než o počítačích. (možná znáte pojmy chalmersova zombie, čínský pokoj apod.)
Prakticky z toho vyplývá to, že zvládnout Go bude pro počítače možná větší problém...
To mě vždy dokáže rozesmát, když si někde přečtu jak počítač používá hrubou sílu a tupě počítá miliardy kombinací, zatímco člověk koukne a hned vidí. Je to právě člověk, který používá skutečně brutální sílu. Výkon počítače je oproti jeho paralelně pracujícímu mozku na atomární úrovni jen kuličkové počítadlo. Za tím pocitem "tahle pozice je dobrá" stojí X krát více "binárních" operací než kolik jich zvládne sebelepší současný počítač. Rozdíl je i v tom, jak s informacemi zachází člověk a jak počítač. K tomu, aby počítač pochopil, že hraje šachy by potřeboval něco víc než jen znát pravidla hry a hodnocení síly pozice. Stačí se podívat na složitost lidského mozku a je hned jasné proč se mu v současné době žádný počítač nemůže rovnat inteligencí. Mozek je fenomenální nástroj, ale je uzavřen ve svém historickém vývoji. Některé věci není schopen pochopit a není schopen zvládnout. Ztěží domyslet, co se stane až se alespoň část know-how mozku převede na rychlejší substrát než je lidská buňka. Co takhle současná partička šachu všech lidí na zeměkouli proti jednomu kvantovému mozku v kapalném dusíku :-)
vyhoda mozku oproti kremiku je dle meho nazoru predevsim v os (nebo biosu, zkratka ve zpusobu zpracovavani a uceni se z chyb)
at clovek napise sebelepsi algoritmus na hrani sachu, lidsky mozek dokaze ten algoritmus pokorit, protoze pouziva to o cem sni dna pocitace. dokaze nejit tu vetev ktera pokracuje nejdale a vcas zahazovat alternativy ktery nikam nevedou.
velmi zajimava uvaha!!! Nemyslim si ze jsi neco hulil, ba naopak. Vzhledem k tomu ze lidsky mozek pracuje na frekvenci kolem 20-24 Hz a pri zakloneni hlavy se tato frekvence snizi az na 10 Hz a cloveku to potom lepe mysli !?!? Nemyslim si ze je vhodne ponorovat mozek do kapalneho dusiku za ucelem zvyseni jeho rychlosti. Spise to funguje opacne. Ja vim ze to zni divne, ale spousta studii to dokazuje. Staci jen hledat. Mam pocit ze mozek s nizsi frekvenci dokaze lepe paralelizovat procesy probihajici na pozadi. Zatimco stroj s kazdym flopem provrde 1 instrukci, mozek jich provede nespocetne vice. Zatimco pri vyssi frekvenci se soustredi vice primocare, pri snizeni frekvence je mysleni spise abstraktniho charakteru. To si muze kazdy zkusit sam na sobe. Dychanim zhluboka pri zaklonene hlave lze tuto frekvenci jeste trochu snizit. Okyslicovany mozek pracuje totiz (paradoxne) pomaleji. (lekarske studie EEG apod.) Tedy clovek pararelizujici na pozadi nejakou uloho, vlastne aniz by si to uvedomaoval jich dela nekolik najednou a podvedome vybere to nejlepsi reseni. To je to o kterem si mysli ze je to o kterem prave premysli, ale to se behem tohoto cyklu muze nekolikanasobne zmenit. Kazdopadne nikdo asi nebude schopen tomuto problemu nikdy poradne porozumet stejne tak jako nalezt kde se v tele nachazi lidska duse. ("wisp" jak ji rikaji elfove)
K tomu by se hodilo samostatné téma, jen nějaké kapky.
Mozek jede paralelně, ovšem také užívá sofistikovanějších metod, jak pouhou "hrubou sílu" (příliš nezabředávaje příklad s integrálem - hrubá síla přičítá kousíčky a přičítá a... až se řekne dost, výsledek je dostatečný i když né zcela přesný. Mozek zintegruje (zvládne-li:) vzorec, dosadí a... někde tady bych hledal i proble-matiku s "nekonečny" tahů).
Zajímavé téma, obzvláště dokáže-li se mozek najednou věnovat tak pěti záležitostem, tudíš bych zapřemýšlel, kde ty paralelní zpracování tahů vlastně hledat. Pro začátek by asi bylo vhodné zapátrat po významu samotného slova paralela.
Mí-ja.
PS: vyřčené nevylučuje existenci lidských jedinců, pro které je adekvátní použití hrubé síly nad jejich schopnosti. Ozřejmuje však možnou existenci těch, s kterými jsou šachy (a go taky Karle, go taky!... a vůbec) o něčem jiném, jak o porovnání hrubých sil...