Funkcja oceny - Evaluation function

Funkcja oceny , znana również jako funkcja oceny heurystycznej lub funkcja oceny statycznej , jest funkcją używaną przez programy komputerowe grające w gry do oszacowania wartości lub dobroci pozycji (zwykle na liściu lub węźle końcowym) w drzewie gry. Drzewo takich ocen jest zwykle częścią minimaksu lub pokrewnego paradygmatu wyszukiwania, który zwraca określony węzeł i jego ocenę w wyniku naprzemiennego wybierania najkorzystniejszego ruchu dla strony w ruchu na każdej warstwie drzewa gry. Wartość jest skwantyzowanym skalarem, często równym n -tym wartości figury grającej, takiej jak kamień w rzucie lub pionek w szachach. n może być dziesiętnymi, setnymi lub inną dogodną częścią.

Zakłada się, że wartość reprezentuje względne prawdopodobieństwo wygranej, jeśli drzewo gry zostało rozwinięte od tego węzła do końca gry. Funkcja patrzy tylko na aktualną pozycję (tj. Na jakich przestrzeniach znajdują się figury i ich wzajemne relacje) i nie bierze pod uwagę historii pozycji ani nie analizuje możliwych ruchów do przodu węzła (czyli statycznych). Oznacza to, że w przypadku dynamicznych pozycji, na których istnieją zagrożenia taktyczne, funkcja oceny nie będzie dokładną oceną pozycji. Pozycje te określa się jako nieruchome ; wymagają co najmniej ograniczonego rodzaju rozszerzenia wyszukiwania, zwanego wyszukiwaniem w uśpieniu, w celu rozwiązania zagrożeń przed oceną. Niektóre wartości zwracane przez funkcje oceniające są raczej bezwzględne niż heurystyczne, jeśli w węźle wystąpi wygrana, przegrana lub remis.

Nie istnieją analityczne ani teoretyczne modele funkcji oceny nierozwiązanych gier, ani też takie funkcje nie są całkowicie ad-hoc. Skład funkcji oceny jest określany empirycznie przez wstawienie funkcji kandydującej do automatu i ocenę jej późniejszej wydajności. Obecnie istnieje znaczący materiał dowodowy dotyczący kilku gier, takich jak szachy, shogi, i dotyczy ogólnego zestawienia funkcji oceny dla nich.

Ogólne podejście do konstruowania funkcji oceny to liniowa kombinacja różnych składników ważonych określonych w celu wpływania na wartość pozycji. Każdy termin można uznać za złożony z czynników pierwszego rzędu (tych, które zależą tylko od przestrzeni i dowolnego elementu na niej), czynników drugiego rzędu (przestrzeń w stosunku do innych przestrzeni) i czynników n-tego rzędu (zależności od historii pozycja).

W funkcji oceny istnieje skomplikowany związek między wyszukiwaniem a wiedzą. Głębsze wyszukiwanie faworyzuje mniej krótkoterminowych czynników taktycznych i bardziej subtelne długoterminowe motywy pozycyjne w ocenie. Istnieje również kompromis między skutecznością zakodowanej wiedzy a złożonością obliczeniową: obliczanie szczegółowej wiedzy może zająć tyle czasu, że wydajność spada, więc przybliżenia do dokładnej wiedzy są często lepsze. Ponieważ funkcja oceny zależy od nominalnej głębokości wyszukiwania, a także od rozszerzeń i redukcji zastosowanych w wyszukiwaniu, nie istnieje ogólne lub samodzielne sformułowanie dla funkcji oceny. Funkcja oceny, która działa dobrze w jednej aplikacji, będzie zwykle wymagała znacznego dostrojenia, aby działała skutecznie w innej aplikacji.

Gry komputerowe, które wykorzystują funkcje oceny, obejmują szachy , go , shogi (szachy japońskie), othello , hex i warcaby . Niektóre gry, takie jak kółko i krzyżyk, są mocno rozwiązane i nie wymagają wyszukiwania ani oceny, ponieważ dostępne jest dyskretne drzewo rozwiązań.

W szachach

Funkcje oceny w szachach składają się z elementu równowagi materialnej, który dominuje w ocenie, oraz zestawu terminów pozycyjnych, które zwykle nie przekraczają wartości pionka, chociaż w niektórych pozycjach wyrażenia pozycyjne mogą być znacznie większe, na przykład gdy zbliża się mata . Funkcja oceny również domyślnie koduje wartość prawa do ruchu, która może wahać się od niewielkiej części pionka do wygranej lub przegranej. W grze końcowej możliwe jest skonstruowanie pozycji, w których ten, kto się poruszy, wygrywa, chociaż w przeciwnym razie pozycja jest w równowadze; możliwe jest również konstruowanie pozycji, na których ten, kto musi się ruszyć, przegrywa ( Zugzwang ).

Funkcja oceny szachów może przyjąć formę

c ₁ * materiał + c ₂ * mobilność + c ₃ * bezpieczeństwo króla + c ₄ * kontrola centralna + c ₅ * struktura pionka + c ₆ * tropizm króla + ...

Każdy z terminów to waga pomnożona przez współczynnik różnicy: wartość materiału białego lub wynik pozycyjny minus czarny. Punktację materialną uzyskuje się przez przypisanie wartości w pionkach każdej z figur. Konwencjonalne wartości to: dama = 9, wieża = 5; Rycerz lub Biskup = 3; Pion = 1; królowi przypisuje się dowolnie dużą wartość, zwykle większą niż łączna wartość wszystkich pozostałych figur. Nie tylko bezwzględna wartość materiału, ale także stosunek między białymi a czarnymi materiałami: poświęcenie pionka w otwarciu może dać przewagę pozycyjną (na stosunek materialny w niewielkim stopniu wpływa), ale plus pionka w królu i Gra pionkiem na koniec gry jest zwykle wystarczająca, aby wygrać (stosunek materiału jest duży). Ten stosunek jest zwykle wprowadzany jako premia za wymianę w dół zgodnie z praktyczną zasadą: „wymieniaj pionki, ale nie pionki, gdy jesteś na prowadzeniu i odwrotnie, gdy jesteś z tyłu”. Wynik mobilności to liczba legalnych ruchów dostępnych dla gracza lub, na przemian, suma pól atakowanych lub bronionych przez każdą bierkę, wliczając w to pola zajmowane przez sprzymierzone lub przeciwne bierki. Efektywna mobilność, czyli liczba „bezpiecznych” przestrzeni, do których bierka może się poruszyć, również może być brana pod uwagę. Efektywna mobilność królowych jest często bardzo niska, chociaż liczba jej legalnych ruchów może być dość wysoka. Punktacja bezpieczeństwa króla to zestaw premii i kar ocenianych za położenie króla i konfigurację pionów i pionków sąsiadujących z królem lub przed nim, a także przeciwnych bierek znajdujących się na przestrzeni wokół króla. Kontrola środkowa jest wyprowadzana z tego, ile pionków i pionków zajmuje lub znajduje się na czterech środkowych polach, a czasami na 12 polach przedłużonego środka. Struktura pionka to zestaw kar i premii za różne mocne i słabe strony w strukturze pionka, na przykład kary za zdublowane i izolowane pionki. Tropizm króla to premia za bliskość (lub karę za odległość) niektórych figur, zwłaszcza królowych i rycerzy, do króla przeciwnika.

Wagi c1 itp. Niekoniecznie są stałe - są to współczynniki stosowania, które mogą się zmieniać w zależności od etapu gry (otwarcie, gra środkowa, końcówka), figur na szachownicy (np. Obecność lub brak królowych), inne cechy pozycja lub strategia lub plany wysokiego poziomu (np. przypisanie większej wagi figurom leżącym na polach wokół króla przeciwnika, jeśli plan jest atakiem ze strony królestwa).

Koncentracja, a zatem odpowiednie terminy i wagi funkcji oceny, różnią się w zależności od etapu gry. W debiucie dominującymi względami są rozwój drobnych figur, bezpieczeństwo roszady i króla oraz kontrola nad centrum. Kary są zwykle nakładane za nierozwinięte fragmenty i opóźnioną roszadę. W końcówkach dominuje promocja pionka lub matowanie pionkami. W sytuacjach matowych istotnymi czynnikami są odległość króla będącego celem od krawędzi lub rogu szachownicy oraz bliskość króla i matowanych figur do króla przeciwnika. W przypadku końcówek króla i pionka, istotnymi czynnikami są bliskość królów do pionków, awans pionków oraz kontrola pól królowych.

Równanie jest modelem koncepcyjnym. W konkretnej implementacji każdy złożony pseudo-termin może być reprezentowany przez od kilku do nawet setek indywidualnych terminów, z których każdy ma własną wagę lub obliczoną wartość. Na przykład struktura pionka może mieć określenia dla izolowanych, podwójnych, do tyłu, posuwających się naprzód, spasowanych, chronionych pasujących, połączonych pasujących, dołkowych, półotwartych i otwartych kartotek, większości pionków, falang i wielu innych formacji. Inne szczególne czynniki, które są często brane pod uwagę to: rozwój mniejszych figur, wieże na otwartych plikach lub siódmym rzędzie, zdublowane wieże, skoczki na posterunkach (skoczkowie w centralnych miejscach chronionych przez pionka i nie podlegający atakowi przez pionka przeciwnika), posiadanie pary gońców, biskupów na długich przekątnych, figur zajmujących lub stojących na przestrzeniach wokół przeciwnego króla oraz ruchliwości królów (królowie nie powinni być „ciasni”, a zatem podlegać mate w ruchu). Niektóre terminy, takie jak bezpieczeństwo króla w grze końcowej z kilkoma figurami, można i należy zignorować w zależności od kontekstu.

Terminy składające się na niektóre czynniki, takie jak bezpieczeństwo króla, łączą się nieliniowo - jedna słabość w bezpieczeństwie króla, jak otwarta teczka sąsiadująca z królem, może zostać ukarana na przykład pionkiem 1/4, ale dwie słabości mogą wymagać ukarania jeden lub nawet dwa pełne pionki i trzy słabości na figurę, wieżę lub nawet więcej, ponieważ mat staje się prawdopodobną możliwością. Czynniki związane z awansem i awansem pionka również łączą się nieliniowo.

Typowe wartości wielokrotności pionków przypisane do figur również nie są stałe, ale zależą od kontekstu: nierozwinięte figury są warte znacznie mniej, podobnie jak figury o ograniczonej mobilności z dowolnego powodu: biskupi ograniczeni przez własne pionki („zły goniec”) ; skoczkowie tracą na wartości, gdy pozycja jest oczyszczana z figur, a gońce i wieże zyskują na wartości; królowe są warte znacznie więcej, jeśli przeciwny król nie jest chroniony przed czekami.

Funkcje oceny zwykle zawierają dziesiątki do setek indywidualnych terminów, a ocena pozycji zwykle waha się od plus lub minus niewielki ułamek pionka. Większe oceny wskazują na brak równowagi materialnej lub na to, że zdobycie materiału jest zwykle nieuchronne. Bardzo duże oceny mogą wskazywać, że mat jest bliski.

W praktyce efektywne funkcje oceny nie są tworzone przez ciągłe rozszerzanie listy ocenianych parametrów, ale przez staranne dostrojenie wag względem siebie skromnego zestawu parametrów, takich jak te opisane powyżej. W tym celu wykorzystywane są przykładowe pozycje z gier mistrzowskich, a skuteczność funkcji oceny mierzona jest procentem wybranych ruchów, które są zgodne z wyborami mistrzów.

Stoły kwadratowe

Ważną techniką oceny od co najmniej wczesnych lat 90. XX wieku jest wykorzystywanie do oceny tabel kawałek-kwadrat (zwanych również tabelami wartości sztuk). Każda tabela to zestaw 64 wartości odpowiadających kwadratom szachownicy. Dla każdego rodzaju figury jest osobna tabela: król, królowa, skoczek, goniec, wieża, pionek. Istnieje oddzielny (odwrócony) zestaw tabel dla przeciwnych figur. Wartości w tabelach to premie / kary za położenie każdego elementu na każdym polu. Wartości kodują połączenie wielu subtelnych czynników trudnych do ilościowego określenia analitycznego. Podstawowe tabele mogą być zbudowane z zasad rozwoju, kontroli centrum, bezpieczeństwa króla, itp. W programach na poziomie mistrzowskim i poza nim tabele są zbudowane z połączenia pozycji zajmowanych przez pionki w grach mistrzowskich, dostosowanych do aplikacji. Na przykład, rycerze rzadko znajdują się po lewej i prawej krawędzi planszy w grach mistrzowskich, więc można przypisać wartość karną do tych miejsc na stole rycerzy z kwadratami, proporcjonalnie do tego, jak rzadko można tam znaleźć skoczka w grach mistrzowskich. Często są dwa zestawy tabel: jeden do otwarcia, a drugi do gry końcowej; pozycje środkowej gry są interpolowane między tymi dwoma. Twórcy programów szachowych mają tendencję do utrzymywania w tajemnicy składu swoich pionowych stołów, a także metod ich tworzenia, ponieważ ich skonstruowanie i staranne dostrojenie wymaga wiele czasu, wysiłku, testów i doświadczenia w grze. oferuje przewagę konkurencyjną.

Ocena w wyszukiwaniu drzew Monte-Carlo

Maszyny szachowe, takie jak Leela Chess Zero, mają zasadniczo inny paradygmat wyszukiwania i oceny niż konwencjonalny schemat alfabeta / minimaks z oceną węzła liścia. W przeszukiwaniu drzewa Monte-Carlo przestrzeń wyszukiwania wszystkich wariantów z węzła jest próbkowana przez rozwijanie lub granie gry do końca poprzez naprzemienne wybieranie losowego ruchu dla każdej strony. Wynik, wygrana, przegrana lub remis, jest zapisywany w węźle początkowym. Wybrany ruch to ten, który prowadzi do pozycji z największą liczbą wygranych lub najwyższym średnim wynikiem, chociaż żadna konkretna linia gry nie jest powiązana z ruchem. Analogiczna sytuacja to odsetek wygranych / remisów / przegranych skumulowanych dla różnych otwarć stosowanych w grach mistrzowskich. Jeśli ktoś wybiera otwarcie, będzie wybierał spośród tych z największym procentem wygranych lub największym procentem wygranych + remisów. Podobnie jest z każdą odmianą w otwarciu, jeśli statystyki są dostępne. Wadą takiego schematu jest to, że najsilniejsza linia (-e) gry dla każdej ze stron może nie być częścią tego otwarcia - mogą one stanowić wąskie szanse w otwarciu, które w innym przypadku jest słabe.

Tak więc „ocena” we wdrożeniach monte-carlo jest raczej prawdopodobieństwem wygranej niż liczbową wyceną pozycji.

W Go

Funkcje oceny w Go uwzględniają zarówno kontrolowane terytorium, wpływ kamieni, liczbę więźniów, jak i życie i śmierć grup na planszy.

Zobacz też

Bibliografia

Shannon, Claude, 1950, „Programowanie komputera do gry w szachy”, Magazyn filozoficzny, Ser. 7, t. 41, nr 314.
Slate, D and Atkin, L., 1983, „Chess 4.5, the Northwestern University Chess Program” w książce Chess Skill in Man and Machine, wyd. 2, str. 93–100. Springer-Verlag, Nowy Jork, NY.
Ebeling, Carl, 1987, All the Right Moves: A VLSI Architecture for Chess (ACM Distinguished Dissertation), str. 56–86. MIT Press, Cambridge, MA
Przewodnik po ocenie sztokfisza, [1]

Languages

In other projects