LINUXSOFT.cz Přeskoč levou lištu

ARCHIV



   

> Šachové myšlení (3) - alfabeta

Existuje algoritmus, který je mnohem rychlejší než minimax, protože některé varianty vůbec nepropočítává. Přesto dojde vždy ke stejnému výsledku. Tento zázračný algoritmus se jmenuje alfabeta metoda a je základem dnešních šachových programů.

12.5.2006 06:00 | Jan Němec | Články autora | přečteno 19123×

Alfabeta metoda

V minulém dílu jsme si ukázali algoritmus minimax, který, zhruba řečeno, počítá všechny tahy, všechny odpovědi na tyto tahy, všechny odpovědi na odpovědi a tak dále až do nějaké dané hloubky nebo do konce partie. Zároveň jsme si ukázali, že algoritmus není paměťově náročný, dnešní počítače mají dost paměti na to, aby prošly celý strom hry šachy. Přirozená otázka je, zda mají také dostatečnou trvanlivost, jinými slovy, kdy tento propočet skončí. Předpokládejme, že z pozice máme vždy 38 tahů a že dokážeme spočítat milión ohodnocovacích funkcí za vteřinu. Čas na provádění a generování tahů a další režii zanedbáme. Při úplném propočtu do hloubky n nás čeká 38n ohodnocovací funkcí. 384 je asi 2 miliony, tady propočet do hloubky 4 půltahy neboli 2 tahy trvá 2 vteřiny. Hloubka 2 a půl tahu by už zabrala přes minutu. Propočet do hloubky 3 tahy by už program nezvládal ani při turnajovém tempu pro vážné partie. Při hloubce 20 tahů by myšlení trvalo přes 1050 let, což není příliš uspokojivý výsledek.

Je zřejmé, že propočet do hloubky dvou tahů nemůže stačit na velmistry. Naopak úplné začátečníky, kteří se právě naučili pravidla, by měl program bez problémů porážet. Bude však stačit na běžné klubové hráče?

diagram

Na diagramu je pozice, která by snadno mohla vzniknout v partii, jež přešla do koncovky těžkých figur. Na tahu je bílý. První, co každého šachistu napadne je vzetí pěšcem b4 soupeřova pěšce na a5. Hned druhé co ho napadne je, že černý potom může vyměnit obě věže a dámu na b3 a vznikne koncovka králů a pěšců. A konečně třetí myšlenka bílého bude patřit vzdálenému černému pěšci h7, který může nezadržitelně kráčet do dámy, neboť jej bílý král již nedohoní. Bílý proto brát pěšce a5 nesmí. Tohle všechno napadne obyčejného klubového hráče během několika vteřin, i když se zřejmě bude ještě chvíli ujišťovat, že se v propočtu nespletl a že ten pěšec h7 opravdu uteče. A jak je na tom minimax? Počítejme spolu: 1. bxa5 Vxb3 2. Vxb3 Vxb3 3. Dxb3 Dxb3 4. Kxb3. Tady již dobrá ohodnocovací funkce uvidí průšvih - nechytatelného pěšce h7. Pokud nekontroluje uteklé pěšce musíme počítat dál: 4. ...h5 5. Kc2 h4 6. Kd2 h3 7. Ke2 h2 8. Kf2 h1D a nově postavenou dámu vidí už i jednoduchá ohodnocovací funkce. Při větvícím faktoru 38 povede algoritmus minimax na 387 nebo 3816 ohodnocovacích funkcí. Propočet pozice, kde běžný klubový hráč vidí řešení za pár vteřin, bude trvat více než jeden den a noc a to v tom lepším případě. Konce výpočtu ve variantě se slabší ohodnocovací funkcí se nejspíš nedočká ani naše galaxie.

Jak můžeme časovou složitost zlepšit? Pokud chceme minimalizovat výraz xy, můžeme zmenšovat y. To je v našem případě hloubka propočtu a ta má zásadní vliv na úroveň hry. Druhou možností je zmenšit x, větvící faktor. Jinými slovy prořezat v propočtu strom hry a některé varianty vůbec nepočítat. Existují dva typy prořezání. První typ je blízký lidskému uvažování. Člověk obvykle vybere na základě pozičního citu jeden nebo několik málo nejnadějnějších tahů a zabývá se pouze jimi. Dobří šachisté vidí nejlepší tahy v pozici velmi rychle a mýlí se jen málokdy. Častější chybou je, že šachista uvažované tahy nesprávně ohodnotí a z těch několika kandidátů nevybere nejlepšího. Ve světě počítačů tato metoda zatím nenaplnila původní očekávání. Běžně se sice zahazují zvlášť ošklivé tahy, prohlubují se nadějné varianty (což je v podstatě také ořezání - těch ostatních variant), dopočítávají se šachy a výměny figur a podobně, ale o nějakém ořezání základního propočtu stromu hry třeba na 1 až 3 tahy z typické pozice nemůže být ani řeč. Docházelo by k příliš velkým přehmatům. Počítačům prostě chybí poziční cit lidských velmistrů.

Naštěstí existuje ještě druhý typ prořezání. Nepočítat variantu, jejíž výsledek (ať už bude jakýkoli) neovlivní výběr tahu z úvodní pozice. Tohle zní na první pohled téměř neuvěřitelně. Je opravdu možné zahazovat některé varianty a přesto dojít na 100% ke správnému výsledku? Ano, je. Ukážeme si to na příkladu.

diagram

V pozici na diagramu je na tahu bílý, jedná se o známou pozici ze zahájení jménem španělská hra (1. e4 e5 2. Jf3 Jc6 3. Sb5), kde se černý brání obvyklým tahem 3. ...a6. Napadl tedy bílému střelce a ten musí hrozbu nějak pokrýt. Běžné tahy jsou nyní 4. Sa4 a Sxc6, hrát by se dalo i Sc4 a snad ještě hodně defétistické Se2, všechny ostatní tahy jsou již vyloženě špatné. Z této pozice dáme programu za úkol provést propočet do hloubky 2 půltahy. Vygeneruje tahy a zkouší jeden po druhém zahrát. Generátor tahů je lehce modifikovaný, tak aby vracel braní před ostatními tahy. Program tedy nejprve propočítá 4. Sxc6, projde všechny odpovědi černého a zjistí, že po nejlepším 4. ...dxc6 je pozice přibližně vyrovnaná. Bílý sice ztratil výhodu dvojice střelců, ale zase černému znehodnotil pěšcovou strukturu. Ohodnocení prvního tahu zatím proběhlo tak, jako v algoritmu minimax. Rozdíl nastane až u druhého tahu bílého 4. Sxa6. Jedná se o zjevnou chybu, kterou bílý odevzdává střelce za pouhého pěšce, ale minimax by musel projít všechny odpovědi, aby si to uvědomil. Tedy poctivě počítat a ohodnocovat nejen 4. ...bxa6 a Vxa6, ale i zcela nesmyslné tahy jako 4. ...Jh6 nebo g5. Modifikovanému algoritmu stačí jediná: 4. ...Vxa6 nebo bxa6. Navíc generátor tahů, který preferuje braní, vrátí jeden z uvedených tahů hned jako první. Jak program pozná, že může propočet odpovědí na 4. Sxa6 přerušit a prohlásit tah za neperspektivní? Z propočtu 4. Sxc6 si zapamatoval hodnotu nejlepší odpovědi 4. ...dxc6, tedy zhruba 0 tj. vyrovnanou pozici. Při propočtu dalších tahů (4. Sxa6) uvedenou hodnotu použijeme jako práh. Pokud jej jakákoli odpověď (4. ...bxa6 nebo Vxa6) přesáhne, propočet tahu (4. Sxa6) ukončíme, neboť již víme, že je špatný. Jinými slovy: pokud víme, že tah je špatný (= horší než nějaký jiný - zde 4. Sxc6), nemá smysl dále zkoumat, jestli není náhodou ještě o něco horší, než jsme zatím zjistili.

V příkladu jsme počítali do hloubky 2, zde se prořezávali pouze tahy černého. Při hloubce 3 a více dojde na oba hráče a jsou zde proto prahy na obě strany. Dolní mezi se říká alfa a horní beta, odtud název algoritmu: alfabeta metoda. Pokud během propočtu narazíme na variantu, která je horší než alfa, víme, že to není hlavní varianta s nejlepšími tahy za oba hráče, protože máme lepší tah. Vyjde-li varianta lépe než beta, může se ji zase vyhnout soupeř a zahrát tah, který je lepší pro něj.

Vlastní implementace není příliš složitá, je pouze třeba dát pozor na některé nepříjemné drobnosti, hlavně předávání hodnot do volaných funkcí. Posunutím o jeden půltah si alfa a beta prohodí role, neboť se změní hráč na tahu. Ze stejného důvodu je třeba hodnoty vynásobit mínus jedničkou. Stejně jako v případě algoritmu minimax musíme korektně upravovat hodnoty propočtu s matem na dohled, tak aby se např. z "Dávám mat 3 půltahem." stalo po zahrání 1. půltahu (a tím i výměnou hráče, který je na tahu) "Dostávám mat 2. půltahem".

/* Úprava cen pozic s matem na dohled. */
int blizKMatu(int cena) {
  if (cena > MNOHO) return cena + 1;
  if (cena < -MNOHO) return cena - 1;
  return cena;
}

int dalOdMatu(int cena) {
  if (cena > MNOHO) return cena - 1;
  if (cena < -MNOHO) return cena + 1;
  return cena;
}

/* Rekurzivní volání. */
int alfabeta(Pozice p, int hloubka, int alfa, int beta) {
  Tahy t;
  int i, indexNejlepsiho;
  int cena;

  /* V případě koncové pozice nebo nulové hloubky propočet ukončíme. */

  if (jsemVMatu(p)) return -MAT;
  if (remiza(p)) return 0;
  /* Dávat mat nemůžu, protože pozice je po tahu soupeře. */

  if (hloubka <= 0) return hodnotaPozice(p);

  t = generujTahy(p);

  for (i = 0; i < tahy.pocet; i++) {
    zahrajTah(p, t[i]);
    cena = -alfabeta(p, hloubka - 1, blizKMatu(-beta), blizKMatu(-alfa));
    cena = dalOdMatu(cena);
    zahrajTahZpet(p, t[i]);
    if (cena > alfa) {
      alfa = cena;
      if (cena >= beta) {
        /* Zde je právě to ořezání. */
        return beta;
      }
    }
  }

  return alfa;
}

Stejně jako u minimaxu, i zde se vyplatí propočet z kořene ošetřit zvlášť. V kořeni hrajeme vždy za jednoho hráče, proto zde není žádná beta, pouze alfa.

Tah nejlepsiTah(Pozice p, int hloubka) {
  Tahy t;
  int i, indexNejlepsiho;
  int cena, alfa;

  t = generujTahy(p);
  alfa = -NEKONECNO;

  for (i = 0; i < tahy.pocet; i++) {
    zahrajTah(p, t[i]);
    cena = -alfabeta(p, hloubka, -NEKONECNO, blizKMatu(-alfa));
    cena = dalOdMatu(cena);
    zahrajTahZpet(p, t[i]);
    if (cena > alfa) {
      alfa = cena;
      indexNejlepsiho = i;
    }
  }
  return t[indexNejlepsiho];
}

Pokračování příště

V příštím dílu se zamyslíme nad efektivitou alfabeta metody. Ukážeme si také, jak ošetřit propočet výměnných operací na konci propočtu.

Verze pro tisk

pridej.cz

 

DISKUZE

Nejsou žádné diskuzní příspěvky u dané položky.



Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1

12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář

6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář

18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business. Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář

12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář

16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

30.11.2022 9:32 / Kyle McDermott
Hosting download unavailable

13.12.2018 10:57 / Jan Mareš
Re: zavináč

2.12.2018 23:56 / František Kučera
Sraz

5.10.2018 17:12 / Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?

20.9.2018 10:04 / Jan Ober
Jaký kurz a software by jste doporučili pro začínajcího kodéra?

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2023) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze