Vyhodnocovací funkce - Evaluation function

Vyhodnocovací funkce , také známý jako heuristické vyhodnocovací funkce , nebo statické funkce vyhodnocovací , je funkce, které herní hraní počítačových programů, použita pro odhad hodnoty nebo dobrotu pozice (obvykle na list nebo koncového uzlu) v herní stromu. Strom takových hodnocení je obvykle součástí minimaxu nebo souvisejícího paradigmatu vyhledávání, který vrací konkrétní uzel a jeho hodnocení v důsledku střídavého výběru nejpříznivějšího tahu pro stranu v tahu u každé vrstvy stromu hry. Hodnota je kvantovaný skalární, často v n ths hodnoty hrací figurky, jako je kámen v pohybu nebo pěšec v šachu. n může být desetina, setina nebo jiný vhodný zlomek.

Předpokládá se, že hodnota představuje relativní pravděpodobnost výhry, pokud byl herní strom rozšířen z tohoto uzlu do konce hry. Funkce se dívá pouze na aktuální pozici (tj. Na jaké mezery jsou jednotlivé části a jejich vzájemný vztah) a nebere v úvahu historii polohy ani prozkoumává možné pohyby vpřed uzlu (tedy statické). To znamená, že u dynamických pozic, kde existují taktické hrozby, nebude vyhodnocovací funkce přesným hodnocením polohy. Tyto pozice se nazývají neklidné ; k vyhodnocení hrozeb před hodnocením vyžadují alespoň omezený druh rozšíření vyhledávání, které se nazývá klidové vyhledávání . Některé hodnoty vrácené vyhodnocovacími funkcemi jsou spíše absolutní než heuristické, pokud v uzlu dojde k výhře, ztrátě nebo remíze.

Pro nevyřešené hry neexistují analytické ani teoretické modely pro vyhodnocovací funkce, ani tyto funkce nejsou zcela ad-hoc. Složení hodnotících funkcí se určuje empiricky vložením kandidátské funkce do automatu a hodnocením jejího následného výkonu. Významné množství důkazů nyní existuje pro několik her, jako jsou šachy, šógi a jde o obecné složení hodnotících funkcí pro ně.

Obecný přístup pro konstrukci hodnotících funkcí je lineární kombinací různých vážených výrazů určených k ovlivnění hodnoty polohy. Každý termín lze považovat za složený z faktorů prvního řádu (ty, které závisí pouze na prostoru a libovolném díle na něm), faktorů druhého řádu (prostor ve vztahu k ostatním prostorům) a faktorů n-tého řádu (závislosti na historii pozice).

Ve funkci hodnocení existuje složitý vztah mezi vyhledáváním a znalostmi. Hlubší hledání upřednostňuje při hodnocení méně krátkodobé taktické faktory a subtilnější poziční motivy dlouhého horizontu. Existuje také kompromis mezi účinností zakódovaných znalostí a výpočetní složitostí: výpočet podrobných znalostí může trvat tolik času, že výkon klesá, takže aproximace přesných znalostí jsou často lepší. Protože funkce vyhodnocení závisí na nominální hloubce hledání a také na rozšířeních a redukcích použitých při hledání, neexistuje žádná obecná nebo samostatná formulace pro funkci hodnocení. Vyhodnocovací funkce, která funguje dobře v jedné aplikaci, bude obvykle nutné podstatně přeladit, aby fungovala efektivně v jiné aplikaci.

Mezi počítačové hry využívající hodnotící funkce patří šachy , go , shogi (japonské šachy), othello , hex a dáma . Některé hry jako tic-tac-toe jsou silně vyřešeny a nevyžadují vyhledávání ani hodnocení, protože je k dispozici diskrétní strom řešení.

V šachu

Vyhodnocovací funkce v šachu sestávají z termínu materiálové bilance, který dominuje hodnocení, a ze sady pozičních členů, jejichž celková hodnota obvykle nepřesahuje hodnotu pěšce, i když v některých pozicích se mohou poziční termíny mnohem zvětšit, například když se blíží mat . Vyhodnocovací funkce také implicitně kóduje hodnotu práva na pohyb, které se může lišit od malého zlomku pěšce po výhru nebo prohru. V koncovce je možné postavit pozice, kde kdokoli pohne, vyhraje, i když pozice je jinak v rovnováze; je také možné postavit pozice, kde každý, kdo se musí pohybovat, ztrácí ( Zugzwang ).

Hodnotící funkce pro šachy může mít podobu

c ₁ * materiál + c ₂ * mobilita + c ₃ * královská bezpečnost + c ₄ * středové ovládání + c ₅ * struktura pěšce + c ₆ * královský tropismus + ...

Každý z výrazů je váha vynásobená rozdílovým faktorem: hodnota bílého materiálu nebo poziční skóre minus černé. Materiálové skóre se získá přiřazením hodnoty v pěščích jednotkách každému z kamenů. Konvenční hodnoty jsou: Queen = 9, Rook = 5; Rytíř nebo biskup = 3; Pěšec = 1; králi je přidělena libovolně velká hodnota, obvykle větší než celková hodnota všech ostatních figurek. Nejde jen o absolutní hodnotu materiálu, ale také o poměr mezi bílým a černým materiálem: obětování pěšce v otvoru může přinést poziční výhodu (poměr materiálu je sotva ovlivněn), ale plus pěšce v králi a hra s pěšcem je obvykle dostatečná k vítězství (poměr materiálu je velký). Tento poměr je obvykle implementován jako bonus směny dolů podle obecného pravidla: „vyměňujte figurky, ale ne pěšáky, když jsou vpřed, a naopak, když jsou vzadu.“ Skóre mobility je počet legálních tahů, které má hráč k dispozici, nebo střídavě součet počtu polí napadených nebo bráněných každou figurkou, včetně polí obsazených přátelskými nebo protichůdnými figurkami. Rovněž lze vzít v úvahu efektivní mobilitu nebo počet „bezpečných“ prostorů, na které se kus může přesunout. Efektivní mobilita královen je často velmi nízká, i když počet jejích legálních tahů může být poměrně vysoký. Skóre bezpečnosti krále je sada bonusů a trestů posuzovaných podle polohy krále a konfigurace pěšců a figurek sousedících s králem nebo před ním a protilehlých figurek, které nesou mezery kolem krále. Ovládání středu je odvozeno od toho, kolik pěšců a figurek zaujímá nebo nese čtyři středové prostory a někdy 12 prostor rozšířeného středu. Struktura pěšce je sada trestů a bonusů za různé silné a slabé stránky ve struktuře pěšce, například tresty za zdvojnásobené a izolované pěšce. Králův tropismus je bonusem za blízkost (nebo trest za vzdálenost) určitých kamenů, zejména královen a rytířů, proti nepřátelskému králi.

Váhy c1 atd. Nemusí být nutně konstantní - jsou to aplikační koeficienty, které se mohou lišit podle fáze hry (otevření, střední hra, koncovka), figurek na hrací desce (např. Přítomnost nebo nepřítomnost královen), další vlastnosti hry pozice nebo strategie nebo plány na vysoké úrovni (např. přiřaďte vyšší váhu dílům, které nesou na polích kolem nepřátelského krále, pokud je plán útokem krále).

Zaměření, a tedy i příslušné pojmy a váhy vyhodnocovací funkce, se liší v závislosti na fázi hry. V úvodní části dominují úvahy o vývoji menších dílků, bezpečnosti rošády a krále a ovládání centra. Sankce se obvykle posuzují za nevyvinuté kousky a opožděné rošády. V koncových hrách je dominantním faktorem buď propagace pěšce nebo páření s figurkami. V situacích páření jsou relevantními faktory vzdálenost cílového krále od okraje nebo rohu hrací plochy a blízkost krále a párových figur k protivníkovi. U koncových her krále a pěšce jsou relevantními faktory blízkost králů k pěšcům, postup pěšců a ovládání pole královny.

Rovnice je koncepční model. V konkrétní implementaci může být každý složený pseudotermín představován hrstkou až stovkami jednotlivých pojmů, z nichž každý má svou vlastní váhu nebo vypočítanou hodnotu. Například struktura pěšce může obsahovat pojmy pro izolované, zdvojené, zpětné, pokročilé, předané, chráněné předané, propojené předané, díry, polootevřené a otevřené soubory, většinové figurky, falangy a mnoho dalších formací. Mezi další speciální faktory, které se často berou v úvahu, patří: vývoj drobných figurek, věže na otevřených souborech nebo sedmém pořadí, zdvojené věže, předzvěstní rytíři (rytíři v centrálních lokacích chráněných pěšcem a nepodléhajících útoku pěšce), držení biskupské dvojice, biskupové na dlouhých úhlopříčkách, kousky, které zaujímají nebo nesou mezery kolem protivníka, a pohyblivost králů (králové by neměli být „stísněni“, proto by měli podléhat kamarádovi v pohybu). Některé výrazy, jako je například bezpečnost krále v koncovce s několika kousky, mohou a měly by být ignorovány v závislosti na kontextu.

Pojmy skládající některé faktory, jako je bezpečnost krále, se kombinují nelineárně - jednu slabost v bezpečnosti krále, jako je otevřený soubor sousedící s králem, lze potrestat například 1/4 pěšcem, ale může být nutné potrestat dvě slabosti jeden nebo dokonce dva úplní pěšci a tři slabosti o kousek, věž nebo dokonce více, protože mat se stává pravděpodobnou možností. Faktory spojené s postupem a propagací pěšce se také nelineárně kombinují.

Typické hodnoty pěšec-vícenásobné přiřazené figurkám také nejsou konstantní, ale závisí na kontextu: nevyvinuté figurky mají mnohem menší hodnotu jako figurky se sníženou pohyblivostí z jakéhokoli důvodu: biskupové omezeni vlastními figurkami („špatný biskup“) ; rytíři ztrácejí hodnotu, když je pozice zbavena kamenů, a biskupové a věží získávají hodnotu; královny mají podstatně větší hodnotu, pokud nepřátelský král není chráněn před šeky.

Vyhodnocovací funkce obvykle obsahují desítky až stovky jednotlivých pojmů a vyhodnocení pozice se obvykle pohybuje v rozmezí plus nebo minus malého zlomku pěšce. Větší hodnocení naznačují materiální nerovnováhu nebo to, že výhra materiálu obvykle hrozí. Velmi velká hodnocení mohou naznačovat, že se blíží mat.

V praxi se efektivní vyhodnocovací funkce nevytvářejí nikdy rozšířením seznamu hodnocených parametrů, ale pečlivým vyladěním vzájemných vah skromné sady parametrů, jako jsou ty popsané výše. Za tímto účelem se používají příkladné pozice z hlavních her a účinnost vyhodnocovací funkce měřená procentem vybraných tahů, které souhlasí s výběrem mistrů.

Kousky čtvercových stolů

Důležitou technikou při hodnocení, protože přinejmenším na počátku 90. let 20. století, je pro hodnocení použití tabulek typu square-square (nazývané také tabulky kusové hodnoty). Každá tabulka je sada 64 hodnot odpovídajících čtvercům šachovnice. Pro každý druh kusu: král, královna, rytíř, biskup, věž, pěšec je samostatný stůl. K dispozici je samostatná (převrácená) sada stolů pro protiklady. Hodnoty v tabulkách jsou bonusy / pokuty za umístění každého kusu na každém políčku. Hodnoty kódují směsici mnoha jemných faktorů, které je obtížné analyticky kvantifikovat. Základní tabulky mohou být vytvořeny z principů vývoje, ovládání centra, bezpečnosti krále atd. V programech na hlavní úrovni i mimo ni jsou tabulky konstruovány ze složené z pozic obsazených figurkami v hlavních hrách, upravených pro aplikaci. Například rytíři se v mistrovských hrách zřídka vyskytují na levém a pravém okraji hrací plochy, takže je možné těmto mezerám rytířského čtvercového stolu přiřadit trestnou hodnotu úměrně tomu, jak zřídka se tam v mistrovských hrách rytíř nachází. Často existují dvě sady tabulek: jedna pro otevírání a druhá pro koncovku; pozice prostřední hry jsou mezi nimi interpolovány. Autoři šachových programů mají tendenci udržovat složení svých čtvercových tabulek, stejně jako metody použité k jejich vytváření, tajné, protože do jejich konstrukce je třeba hodně času, úsilí, testování a herních zkušeností a pečlivé ladění zde nabízí konkurenční výhodu.

Vyhodnocení při hledání stromu Monte Carlo

Šachové stroje, jako je Leela Chess Zero, mají podstatně odlišné paradigma hledání a hodnocení než konvenční schéma abecedy / minimaxu s hodnocením listových uzlů. Při hledání stromu Monte Carlo je vyhledávaný prostor všech variant z uzlu vzorkován zavedením nebo hraním hry až do konce střídavým výběrem náhodného pohybu pro každou stranu. Výsledek, výhra, prohra nebo remíza, je zálohován do počátečního uzlu. Vybraný tah je tah, který vede k pozici s největším počtem výher nebo nejvyšším průměrným skóre, ačkoli s tahem není spojena žádná konkrétní linie hry. Analogická situace je procento výher / remíz / ztrát akumulovaných pro různé otvory používané v hlavních hrách. Pokud si někdo zvolí otevření, bude mít tendenci vybírat z těch, které mají největší procento výher nebo největší procento výher + remízy. A podobně pro každou variantu v rámci otevření, jsou-li k dispozici statistiky. Slabinou takového systému je, že nejsilnější hrací linie pro každou stranu nemusí být součástí tohoto otvoru - mohou to být úzké příležitosti v otvoru, který je jinak slabý.

Takže „vyhodnocení“ v implementacích monte-carlo je spíše pravděpodobnost výhry než numerické ocenění pozice.

V Go

Hodnotící funkce v Go berou v úvahu jak kontrolované území, vliv kamenů, počet vězňů, tak i život a smrt skupin na palubě.

Viz také

Reference

Shannon, Claude, 1950, „Programování počítače pro hraní šachů“, Philosophical Magazine, Ser.7, sv. 41, č. 314.
Slate, D a Atkin, L., 1983, „Chess 4.5, Northwestern University Chess Programme“ v Chess Skill in Man and Machine, 2. vydání, str. 93–100. Springer-Verlag, New York, NY.
Ebeling, Carl, 1987, All the Right Moves: A VLSI Architecture for Chess (ACM Distinguished Dissertation), s. 56–86. MIT Press, Cambridge, MA
Průvodce vyhodnocením populace ryb, [1]

Languages

In other projects