Heurystyczna funkcja oceny Eval (s,p) zwraca graczowi p oszacowanie oczekiwanej użyteczności stanu s, podobnie jak funkcje heurystyczne z rozdziału 3 zwracają oszacowanie odległości do celu. Dla stanów końcowych musi być tak, że Eval(s,p) = Utility(s,p), a dla stanów nieterminalnych ocena musi być gdzieś pomiędzy stratą a wygraną:
Utility(loss,p) ≤ Eval(s,p) ≤ Utility(winn,p)
Co poza tymi wymaganiami zapewnia dobrą funkcję oceny? Po pierwsze, obliczenia nie mogą trwać zbyt długo! (Chodzi o szybsze wyszukiwanie). Po drugie, funkcja oceny powinna być silnie skorelowana z rzeczywistymi szansami na wygraną. Można się zastanawiać nad wyrażeniem „szanse na wygraną”. W końcu szachy nie są grą losową: znamy obecny stan z całą pewnością i nie ma w tym żadnych kości; jeśli żaden z graczy nie popełni błędu, wynik jest z góry określony. Ale jeśli wyszukiwanie musi zostać odcięte w stanach nieterminalnych, wówczas algorytm będzie z konieczności niepewny co do końcowych wyników tych stanów (nawet jeśli tę niepewność można rozwiązać przy nieskończonych zasobach obliczeniowych).
Ukonkretnijmy ten pomysł. Większość funkcji oceny działa poprzez obliczanie różnych cech stanu — na przykład w szachach mielibyśmy cechy liczby białych pionków, czarnych pionków, białych hetmanów, czarnych hetmanów i tak dalej. Cechy wzięte razem definiują różne kategorie lub klasy równoważności stanów: stany w każdej kategorii mają te same wartości dla wszystkich cech. Na przykład jedna kategoria może zawierać wszystkie gry końcowe z dwoma pionkami i jednym pionkiem. Każda dana kategoria będzie zawierać pewne stany, które prowadzą (przy doskonałej grze) do wygranych, niektóre prowadzą do remisów, a niektóre prowadzą do przegranych.
Funkcja oceny nie wie, które stany są jakimi, ale może zwrócić pojedynczą wartość, która szacuje proporcję stanów z każdym wynikiem. Załóżmy na przykład, że nasze doświadczenie sugeruje, że 82% stanów napotkanych w kategorii dwóch pionków kontra jeden pion prowadzi do zwycięstwa (użyteczność +1); 2% do straty (0) i 16% do remisu (1/2) . Wówczas rozsądną oceną dla stanów w kategorii jest wartość oczekiwana:
(0,82 x +1) + (0,02 x + 0) + (0,16 x 1/2) = 0,90
W zasadzie wartość oczekiwaną można określić dla każdej kategorii stanów, co skutkuje funkcją oceny, która działa dla dowolnego stanu.
W praktyce tego rodzaju analiza wymaga zbyt wielu kategorii, a co za tym idzie zbyt dużego doświadczenia, aby oszacować wszystkie prawdopodobieństwa. Zamiast tego większość funkcji oceny oblicza oddzielne wkłady liczbowe z każdej cechy, a następnie łączy je, aby znaleźć łączną wartość. Od wieków szachiści opracowują sposoby oceniania wartości pozycji, używając właśnie tego pomysłu. Na przykład wprowadzające księgi szachowe podają przybliżoną wartość materialną każdej figury: każdy pionek jest wart 1, rycerz lub goniec wart jest 3, wieża 5, a hetman 9. Inne cechy, takie jak „dobra struktura pionków” i „król bezpieczeństwo” może być warte pół pionka, powiedzmy. Te wartości cech są następnie po prostu sumowane, aby uzyskać ocenę pozycji. Matematycznie ten rodzaj funkcji oceny nazywa się ważoną funkcją liniową, ponieważ można ją wyrazić jako
gdzie każde fi jest cechą pozycji (np. „liczba białych gońców”), a każde wi jest wagą (mówiącą, jak ważna jest ta cecha). Wagi należy znormalizować tak, aby suma zawsze mieściła się w przedziale od przegranej (0) do wygranej (+1). Pewna przewaga równoważna pionkowi daje duże prawdopodobieństwo wygranej, a bezpieczna przewaga równoważna trzem pionkom powinna dać prawie pewne zwycięstwo, jak pokazano na rysunku (a).
Powiedzieliśmy, że funkcja oceny powinna być silnie skorelowana z rzeczywistymi szansami na wygraną, ale nie musi być skorelowana liniowo: jeśli stan ma dwa razy większe prawdopodobieństwo wygrania niż stan s’, nie wymagamy, aby EVAL(S) była dwukrotnie EVAL (S’); wszystko czego potrzebujemy to, że EVAL(s) > EVAL(s)
Zsumowanie wartości cech wydaje się rozsądne, ale w rzeczywistości wiąże się z mocnym założeniem: wkład każdej cechy jest niezależny od wartości innych cech. Z tego powodu obecne programy do szachów i innych gier również wykorzystują nieliniowe kombinacje cech. Na przykład, para gońców może być warta ponad dwukrotnie więcej niż pojedynczy goniec, a goniec jest wart więcej w końcowej fazie gry niż wcześniej – gdy cecha liczby ruchów jest wysoka lub liczba pozostałych bierek jest niska. Skąd pochodzą cechy i wagi? Nie są częścią zasad szachów, ale są częścią kultury ludzkiego doświadczenia szachowego. W grach, w których tego rodzaju doświadczenie nie jest dostępne, wagi funkcji oceny można oszacować za pomocą technik uczenia maszynowego z rozdziału 22 . Zastosowanie tych technik do szachów potwierdziło, że biskup rzeczywiście jest wart około trzech pionków i wydaje się, że stulecia ludzkiego doświadczenia można odtworzyć w ciągu zaledwie kilku godzin uczenia maszynowego.