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

> Šachové myšlení (11) - Ohodnocovací funkce

Cílem ohodnocovací funkce je jednoduchým způsobem odhadnout pozici, do jaké míry je lepší pro bílého nebo pro černého. Odhad nemusí být dokonalý, ale musí být hodně rychlý.

6.1.2010 10:00 | Jan Němec | Články autora | přečteno 7580×

Jak již víme, šachový program provádí propočet do nějaké hloubky (která je pro různé varianty rozdílná) a koncové pozice odhaduje jednoduchou ohodnocovací funkcí. Ve funkci je zadrátovaná cena figur a poziční cit programu. Ačkoli číselně vyjádřeno rozhodující složkou funkce je materiál, není možné zanedbávat ani poziční složku neboť program obvykle nedopočítá důležité varianty až do matu nebo k rozhodující ztrátě materiálu.

Materiální složka

Nejjednodušší a nejdůležitější je pochopitelně sečíst materiál. Pokud má bílý pěšec cenu 1, bude cena jezdce a střelce přibližně 3, věže 5 a dámy 9. Přesné hodnoty se mohou v jednotlivých programech lišit, například hodnota střelce bývá někdy nepatrně vyšší než hodnota jezdce a podobně. Šachový program s ohodnocovací funkcí degenerovanou na prostý součet materiálu se bude pochopitelně chovat divně. Cesta i od velmi zjevné poziční chyby k vynucené ztrátě materiálu nebo k matu bývá velmi dlouhá, mnohem delší než hloubka propočtu dnešních programů, takže se součtem materiálu si nevystačíme.

Poziční složka

Poziční složka bývá číselně velmi malá, jen zřídka kdy v reálných pozicích z partie přesáhne v absolutní hodnotě cenu pěšce. Zpravidla se počítá průchodem šachovnice a oceněním jednotlivých kamenů. Výsledná cena je pak součet ohodnocení jednotlivých kamenů.

Řadu pozičních faktorů můžeme ocenit statickou tabulkou pro jednotlivá políčka. Například pěšci e2 v základním postavení udělíme postih a po vývinu na e4 bonus, přičemž tento postih a bonus nezávisí na ostatních pozičních faktorech. Poziční složka poskládaná z podobných bonusů a postihů jistě nebude dokonalá, ale zato bude velmi rychlá. V následujícím textu ukážu příklady těchto tabulek ze svého šachového programu s šachovnicí 12x10 (stovky na okrajích jsou prostě jen nevyužité hodnoty) a cenou jednoho pěšce 50. Všechny uvedené tabulky jsou z pohledu bílého, černé kameny oceníme symetricky. Kladné číslo znamená bonus a záporné postih. Hodnoty uvádím jen jako příklady a rozhodně je nelze brát jako nějaké dogma. Právě naopak, ve skutečně kvalitním programu by bylo třeba nějakou pokročilou statistickou metodou hodnoty doladit.

Pěšec

Pro pěšce existuje celá řada heuristik. Ohodnotit můžeme již samotný fakt, že pěšec stojí na nějakém políčku.

/* Pěšec */
{  100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   /*     a    b    c    d    e    f    g    h */
   100,   0,   0,   0,   0,   0,   0,   0,   0, 100, /* 1 */
   100,   0,   0,  -1,  -8,  -8,   0,   0,   0, 100, /* 2 */
   100,   1,   1,   1,   4,   4,   0,   1,   1, 100, /* 3 */
   100,   1,   1,   6,   8,   8,   6,   1,   1, 100, /* 4 */
   100,   4,   4,   6,  10,  10,   3,   4,   4, 100, /* 5 */
   100,  10,  10,  10,  15,  15,  10,  10,  10, 100, /* 6 */
   100,  20,  20,  20,  20,  20,  20,  20,  20, 100, /* 7 */
   100,   0,   0,   0,   0,   0,   0,   0,   0 }     /* 8 */

Všimněte si, že je třeba především vyvinout centrální pěšce, na křídlech mohou pěšci zůstat v základním postavení. Pokud se nějakému pěšci podaří postoupit na čtvrtou řadu, bude jej ocenění popohánět dál směrem do dámy. Tabulka se týká zahájení a střední hry, v koncovce by již mohly být jednotlivé sloupce téměř stejné, neboť dominantní úlohou pěšce v koncovce již není boj o prostor a o centrum, zatlačování soupeřových figur a ochrana vlastního krále, atd. atd..., ale docela obyčejný úprk do dámy.

Kromě samotného políčka pěšce musíme ještě ocenit, pokud je volný (tj. žádný soupeřův pěšec mu nebrání v cestě do dámy), krytý jiným pěšcem nebo vedle jiného pěšce téže barvy. Posledně jmenované ocenění je důležité, jinak se bude program snažit vytvořit šikmý pěšcový řetězec - tak jako můj pětiletý syn poté, co pochopil, že se pěšci mohou navzájem krýt. Pěšec může nasbírat i řadu postihů. Špatný je dvoj- a trojpěšec, izolovaný pěšec a dále pěšec opožděný. Přesná definice opožděnosti se může lišit, ale například při pěšcové struktuře bílý: e3, d4 a černý d5 a f5 je bílý pěšec e3 opožděný, neboť nemůže pokračovat dopředu, není krytý pěšcem a soupeř na něj může tlačit po sloupci e. V královské koncovce bez figur bychom měli pomocí známého pravidla čtverce ocenit uteklé pěšce.

Jezdec

Jezdec stojí dobře v centru, naopak v rohu se mu obvykle vůbec nedaří.

/* Jezdec */
{  100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   /*     a    b    c    d    e    f    g    h */
   100, -10,  -4,  -3,  -2,  -2,  -3,  -4, -10, 100, /* 1 */
   100,  -5,  -5,  -3,   0,   0,  -3,  -5,  -5, 100, /* 2 */
   100,  -3,   0,   3,   5,   5,   3,   0,  -3, 100, /* 3 */
   100,  -2,   5,   5,   7,   7,   5,   5,  -2, 100, /* 4 */
   100,   0,   5,   6,   8,   8,   6,   5,   0, 100, /* 5 */
   100,   5,   6,   7,   8,   8,   7,   6,   5, 100, /* 6 */
   100,   0,   5,   6,   8,   8,   6,   5,   0, 100, /* 7 */
   100, -10,  -5,  -2,   0,   0,  -2,  -5, -10 }     /* 8 */

Smysl může mít i bonus pro dobře umístěného jezdce krytého pěšcem.

Střelec

Pro střelce už nemusí být ohodnocení tabulkou tak jednoznačné, přesto se o ně můžeme pokusit:

{  100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   /*     a    b    c    d    e    f    g    h */
   100,  -5,  -4,  -3,  -2,  -2,  -3,  -4,  -5, 100, /* 1 */
   100,  -5,   6,  -2,   5,   5,  -2,   6,  -5, 100, /* 2 */
   100,   0,   0,   1,   5,   5,   1,   0,   0, 100, /* 3 */
   100,   0,   2,   5,   5,   5,   5,   5,   0, 100, /* 4 */
   100,   0,   5,   6,   8,   8,   6,   5,   0, 100, /* 5 */
   100,   0,   0,   0,   0,   0,   0,   0,   0, 100, /* 6 */
   100,   0,   0,   0,   0,   0,   0,   0,   0, 100, /* 7 */
   100,  -5,   0,   0,   0,   0,   0,   0,  -5 }     /* 8 */

Dobrý střelec by měl mít barvu soupeřových pěšců, aby je mohl napadat. Za každého soupeřova pěšce na poli stejné barvy, jako je pole střelce, tedy můžeme přičíst malý bonus a malý postih za každého pěšce na poli barvy opačné. Výhodou bývá dvojice střelců, tedy 2 střelci jsou o něco cennější než 2 krát cena jednoho. Střelci se daří v otevřených pozicích a podobně jako u jezdce má smysl bonus za dobře umístěného střelce krytého vlastním pěšcem. Bonus bychom měli dát i za vazbu pomocí střelce.

Věž

U věže už statická ohodnocovací tabulka ani nemá smysl. Věž patří na volný nebo polovolný (obsazený soupeřovým pěšcem) sloupec, má tlačit na opožděné nebo prostě jen nekryté pěšce. Obě věže by se měly navzájem krýt. Velmi silnou zbraní bývá tzv. harmonika, tedy zdvojené věže na sedmé řadě respektive druhé řadě v případě černého.

Dáma

Pro dámu je obtížné definovat jakoukoli jednoduchou ohodnocovací heuristiku. Všechny učebnice pro začátečníky uvádějí tragické důsledky předčasného vývinu dámy, soupeř prostě dámu s tempy napadá pomocí běžných vývinových tahů. Ovšem jde spíš o ztrátu času, nedá se obecně říci, že by dáma v zahájení třeba na a4 nebo d4 stála hůř než na d1 a případné napadání dámy vývinovými tahy soupeře snadno odhalí propočet. Stačí tedy program nemotivovat k vývinu dámy a program bude preferovat vývin pěšců a lehkých figur.

Král

V zahájení a střední hře je důležitá bezpečnost krále. Jde jednak o umístění

/* Král */
{  100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   /*     a    b    c    d    e    f    g    h */
   100,  10,  15,  13,  -5,   0,  -5,  17,  12, 100, /* 1 */
   100,  -5,  -5, -10, -15, -15, -10,  -5,  -5, 100, /* 2*/
   100, -15, -15, -18, -20, -20, -18, -15, -15, 100, /* 3*/
   100, -30, -30, -30, -30, -30, -30, -30, -30, 100, /* 4*/
   100, -30, -30, -30, -30, -30, -30, -30, -30, 100, /* 5*/
   100, -30, -30, -30, -30, -30, -30, -30, -30, 100, /* 6*/
   100, -30, -30, -30, -30, -30, -30, -30, -30, 100, /* 7*/
   100, -30, -30, -30, -30, -30, -30, -30, -30},     /* 8*/

zachované právo rošády (pozor na umělou rošádu a zapomenutou věž zapomenutou v rohu!), pěšcový kryt krále, počet napadených polí v okolí a podobně. V koncovce se role krále radikálně mění, stává se z něj aktivně bojující figura, která musí opustit úkryt a bojovat o střed.

   /* Král v koncovce */
{  100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   /*     a    b    c    d    e    f    g    h */
   100, -20, -15, -12, -10, -10, -12, -15, -20, 100, /* 1 */
   100, -15, -12,  -7,   0,   0,  -7, -12, -15, 100, /* 2*/
   100, -12,  -7,   1,   5,   5,   1,  -7, -12, 100, /* 3*/
   100, -10,   0,   5,  10,  10,   5,   0, -10, 100, /* 4*/
   100, -10,   0,   5,  10,  10,   5,   0, -10, 100, /* 5*/
   100, -12,  -7,   1,   5,   5,   1,  -7, -12, 100, /* 6*/
   100, -15, -12,  -7,   0,   0,  -7, -12, -15, 100, /* 7*/
   100, -20, -15, -12, -10, -10, -12, -15, -20},     /* 8*/

V matící koncovce se pak král silnější strany snaží přiblížit soupeřovu králi. Specifická je koncovka krále, jezdce a střelce proti samotnému králi. Mat lze sice nastavit kdekoli při okraji šachovnice, ale proti rozumné obraně je možné jej vynutit pouze v rohu barvy střelce. Při bělopolném střelci tedy tlačíme krále do rohu s bílým políčkem a naopak.

   /* Král tlačený do bíleho rohu */
{
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
   /*     a    b    c    d    e    f    g    h */
   100, -10,  -8,  -6,  -4,  -2,   0,   1,   2, 100, /* 1 */
   100,  -8,  -6,  -3,  -1,   2,   2,   3,   1, 100, /* 2*/
   100,  -6,  -3,   0,   2,   3,   5,   1,   0, 100, /* 3*/
   100,  -4,  -1,   2,   9,  11,   3,   0,  -2, 100, /* 4*/
   100,  -2,   0,   3,  11,   9,   2,  -1,  -4, 100, /* 5*/
   100,   0,   1,   5,   3,   2,   0,  -3,  -6, 100, /* 6*/
   100,   1,   3,   1,   0,  -1,  -3,  -6,  -8, 100, /* 7*/
   100,   2,   1,   0,  -2,  -4,  -6,  -8, -10 }     /* 8*/

Ohodnocovací funkce napsaná pomocí statických tabulek je velmi rychlá, ale má jednu vážnou slabinu. Tabulky jsou napsány obecně, mohou tedy být docela dobré pro běžnou pozici, ale stačí několik netypických tahů a správné ohodnocení políček například pro jezdce může být úplně jiné. Řešením je místo samotného pole oceňovat pohyblivost figur, oceňovat pole, která figury napadají a podobně. To vše je ovšem za cenu vyšší časové náročnosti.

Doporučené techniky

Alfa-beta prořezání

Pokud mám o figuru méně, nemá cenu posuzovat poziční jemnosti, jako třeba opožděné pěšce. V programu založeném na alfa-beta metodě předáme ohodnocovací funkci parametry alfa a beta a jakmile bude zřejmé, že výsledek nebude v intervalu (alfa, beta), ukončíme výpočet a vrátíme příslušnou mezní hodnotu. Výsledek ohodnocovací funkce můžeme odhadnout, jako materiální složka + poziční složka z rodiče ve stromu propočtu +- malé epsilon. Vhodná doba pro test a případné ukončení je hned na začátku po prostém sečtení materiálu nebo i později před jakýmkoli složitějším výpočtem.

Inkrementální výpočet

Řadu faktorů můžeme počítat inkrementálně. V kořeni propočtu provedeme nějakou analýzu pozice a vypočteme plnohodnotnou ohodnocovací funkci nebo nějakou její složku. S každým tahem od kořene dále v propočtu pak jen dopočítáme změnu této složky. Nejjednodušší je to v případě materiální složky. Na začátku prostě sečteme materiál for cyklem přes políčka šachovnice. Při tahu v propočtu pak jen přičteme změnu materiálu v důsledku tohoto tahu. Obvykle to bude 0, jen braní a proměny pěšce mají změnu nenulovou. V listech propočtu si už můžeme for cyklus přes políčka ušetřit. Na podobném principu funguje i inkrementální výpočet poziční složky. Při tahu Jg1-f3 přičteme hodnotu jezdce na f3 a odečteme tu z g1. Inkrementální výpočet poziční složky se obvykle kombinuje s nastavením tabulek (například právě poziční hodnota jezdce na jednotlivých polích) ohodnocovací funkce v kořeni propočtu podle aktuální pozice. Není to ideální, neboť charakter pozice se na cestě od kořene do listu může změnit, ale pořád je to přesnější než globální statické ohodnocovací tabulky. Nevýhodou uvedeného řešení je závislost ohodnocovací funkce na výchozí pozici propočtu. Konkrétním nepříjemným důsledkem je třeba nutnost vyprázdnit hašovací tabulky po každém tahu v partii (změna kořene).

Hašování pěšcové struktury

Časově náročné je ohodnocení struktury pěšců. Nalezení všech dvojpěšců, slabých pěšců a podobně je přeci jen o dost náročnější než prostý průchod for cyklem přes šachovnici, který používáme u jednodušších pozičních faktorů. Naštěstí se pěšcová struktura mění v průběhu propočtu jen málo a v řadě pozic z propočtu se dokola opakuje jen několik rozložení pěšců. Pěšcovou strukturu tedy můžeme hašovat. Postupovat lze přesně stejně jako v případě hašování výsledků propočtů podstromů. Tedy dvě inkrementálně počítané hašovací funkce F a G, jedna pro umístění do tabulky, druhá pro kontrolu. Jedinou změnou je, že funkce obě závisí pouze na rozložení pěšců a ukládáme cenu pěšcové struktury.

Několik rad

  • Nesnažte se o dokonalou ohodnocovací funkci, funkce musí být rychlá heuristika, nemá nahrazovat propočet
  • Nepřeceňujte poziční složku, nejdůležitější je materiál. Pokud váš program požírá otrávené pěšce, zatímco soupeř chystá matový útok, nemusí to být jen chyba ohodnocovací funkce.
  • Pozor na neutralitu pozičních bonusů a postihů. Pokud například u střelce budou převažovat bonusy nad postihy, výpočet poziční složky pak do jisté míry supluje výpočet materiálu se všemi negativními důsledky.
  • Pozor na související faktory, neoceňujte jednu věc dvakrát, pokaždé jiným způsobem.
  • Napište si automatické testování nebo dokonce dolaďování pozičních faktorů.
  • Pokud to s programováním šachů myslíte vážně, prohlédněte si ohodnocovací funkci nějakého silného open source programu.

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

V příštím dílu si napíšeme knihovnu zahájení.

Verze pro tisk

pridej.cz

 

DISKUZE

Komentář 12.1.2010 23:14 Karl von Neklbaur




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

12.7.2016 13:14 /František Kučera
Spolek OpenAlt zve na 130. distribuovaný sraz příznivců svobodného softwaru a otevřených technologií (hardware, 3D tisk, SDR, DIY, makers…), který se bude konat ve čtvrtek 21. července od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

11.7.2016 16:53 /Redakce Linuxsoft.cz
Konference LinuxDays hledá přednášející. Přihlášky poběží do konce prázdnin, v září bude hlasování a program. Více na https://www.linuxdays.cz/2016/cfp/.
Přidat komentář

8.5.2016 17:19 /Redakce Linuxsoft.cz
PR: Dne 26.5.2016 proběhne v Praze konference Cloud computing v praxi. Tématy bude např. nejnovější trendy v oblasti cloudu a cloudových řešení, cloudové služby, infrastruktura cloudu, efektivní využití cloudu, možné nástrahy cloudů a jak se jim vyhnout
Přidat komentář

21.4.2016 8:01 /František Kučera
Spolek OpenAlt zve na 127. distribuovaný sraz příznivců svobodného softwaru a otevřených technologií (hardware, 3D tisk, SDR, DIY, makers…), který se bude konat ve čtvrtek 28. dubna od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář

2.3.2016 22:41 /Ondřej Čečák
Letošní ročník konference InstallFest již tento víkend!
Přidat komentář

14.2.2016 16:39 /Redakce Linuxsoft.cz
O víkendu 5. a 6. března 2016 proběhne na pražském Strahově 8. ročník tradiční konference InstallFest. Celkem za dva dny uvidíte ​30 přednášek​ a ​6 workshopů.
Přidat komentář

5.2.2016 17:38 /Petr Ježek
Utilitka z XFce "xfce4-power-manager" nejen umožňuje nastavení lhůty pro uspání či hybernaci, ale i zapínání a vypínání prezentačního módu pro nerušené sledování videí. Stačí ji nastavit v každém vybavenějším panelu a v jakémkoli nontiled WM/DE.
Přidat komentář

10.1.2016 11:32 /Pavel `Goldenfish' Kysilka
LinuxMarket změnil provozovatele. Nově jej provozuje Marek Pszczolka. Více info a detaily #1 a #2.
Přidat komentář

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

> Poslední diskuze

10.6.2016 21:10 / pavel riha
FreeBSD 10.3 a virtualizace

8.6.2016 21:56 / Milan Gallas
Nevalidní prefix m

7.5.2016 14:58 / Teodor Komárek
Soubory

20.4.2016 0:07 / Jakub Cleing
Sázkový panel PHP FUSION

9.4.2016 9:43 / jiwopene@gmail.com
Re: problém s dpkg a nemožností instalovat

Více ...

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