LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> Š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 16612×

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ů

13.9.2017 8:00 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt – tentokrát netradičně v pondělí: 18. září od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

3.9.2017 20:45 /Redakce Linuxsoft.cz
PR: Dne 21. září 2017 proběhne v Praze konference "Mobilní řešení pro business". Hlavní tématy konference budou: nejnovější trendy v oblasti mobilních řešení pro firmy, efektivní využití mobilních zařízení, bezpečnostní rizika a řešení pro jejich omezení, správa mobilních zařízení ve firmách a další.
Přidat komentář

15.5.2017 23:50 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

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

> Poslední diskuze

18.9.2017 14:37 / Rojas
high security vault

15.9.2017 7:33 / Wilson
new zealand childcare jobs

31.8.2017 12:11 / Jaromir Obr
Re: ukůládání dat ze souboru

30.7.2017 11:12 / Jaromir Obr
Národní znaky

27.7.2017 12:24 / Jaromir Obr
Cteni/zapis

Více ...

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