Jaki jest dokładny sposób oceny pozycji w szachach?

13

Przez jakiś czas interesowałem się algorytmami komputerowej sztucznej inteligencji w szachach (w pewnym momencie miałem okazję pracować nad jednym), takim jak Minimax , a jako podstawowy składnik tych algorytmów jest tak zwana funkcja oceny w celu określenia, co jest dobra konfiguracja płytki i co jest złe .

Innymi słowy, biorąc pod uwagę konfigurację szachownicy, w jaki sposób określasz, że jest to na twoją korzyść i z jakim stopniem pewności siebie?

Na przykład:

  • Jeśli jesteś właścicielem centrum, jest to raczej korzystne.
  • Jeśli masz więcej elementów niż przeciwnik, jest to raczej korzystne.
  • Jeśli straciłeś Królową, raczej nie jest to korzystne.
  • Jeśli masz pionka, który jest bliski awansu, jest to korzystne.
  • ...

Chciałbym więc poprosić o radę, jak stworzyć dobrą funkcję oceny, opartą na wiedzy eksperckiej na temat gry w szachy w ogóle. I jeśli to możliwe, stopień uprzywilejowania (powiedzmy, że 1 jest bardzo niekorzystny, a 100 bardzo korzystny).

Ostatecznie chodzi o to, aby móc stworzyć algorytm, który będzie przeglądał drzewo możliwości do pewnej głębokości i oceni, jaka jest najkorzystniejsza konfiguracja dla następnego ruchu (biorąc pod uwagę kilka ruchów w przyszłości) na podstawie tego, co jest korzystny dla gracza, a nie dla przeciwnika. Ale bez dobrej funkcji oceny algorytm jest niczym.

Charles Menguy
źródło
Myślę, że to pytanie poradziłoby sobie dobrze na StackOverflow. Jest już wiele pytań dotyczących szachy AI
xaisoft
3
Już wcześniej myślałem o opublikowaniu go na SO, ale jestem prawie pewien, że zostanie zamknięty, ponieważ nie jest konstruktywny ani nie jest prawdziwym pytaniem. Może jeśli potrzebuję większego nacisku na sam kod, ale myślę, że do funkcji oceny wymaga wiedzy o szachach, a nie tyle kodu i algorytmów.
Charles Menguy,
Jak dokładne Jedynym całkowicie dokładnym sposobem jest wygrana, przegrana lub remis.
edwina oliver

Odpowiedzi:

9

Oto dobry punkt wyjścia. Porównanie materiałów jest kluczowe (i łatwe), możesz je dostroić, aby uwzględnić aspekty pozycyjne, takie jak otwarte szeregi / pliki / przekątne, struktura pionków itp.

https://www.chessprogramming.org/Evaluation

Eve Freeman
źródło
5

Dodając do odpowiedzi @Eve Freeman, sugerowałbym zbadanie, w jaki sposób najlepszy silnik komputerowy na świecie, Sztokfisz, ocenia dane stanowisko. Ponieważ kod źródłowy jest otwarty, możesz to zrobić za darmo. Myślę, że ten plik z funkcją oceny, której szukasz, jest właśnie ten .

Pablo S. Ocal
źródło
5

Mam wrażenie, że trochę się spóźniłem z odpowiedzią, ale - jestem też w trakcie tworzenia silnika. Kod źródłowy znajduje się w Pythonie (który jest dość łatwy do odczytania, nawet jeśli go nie znasz) i jest dostępny tutaj, jeśli chcesz go przeczytać. Lista obecnie aktywnych „heurystyk” (w momencie publikacji):

  • Im bardziej rozwinięte (bliżej przeciwnej strony) elementy, tym lepiej
  • Pionki bliższe promocji są dobre
  • Królowie są punktowani osobno w oparciu o fazę gry (otwarcie, środkowa, końcowa)
  • Jeśli gracz ma obu biskupów, otrzymuje premię
  • Jeśli gracz ma castled, otrzymaj bonus
  • Pojedyncze pionki (pionki bez niczego wokół nich) nie są dobre
  • Podwójne pionki (dwa pionki w tym samym pliku bez odstępu między) nie są dobre
  • Posiadanie wszystkich 8 pionków nie jest dobrą rzeczą i jest karane (zaśmiecają tablicę i przeszkadzają)
  • Zobacz tę wspaniałą funkcję oceny, która jest również używana
  • Biskupi z większą liczbą pionków na tym samym placu co biskup są karani (nie są tak dobrzy w zatłoczonych sytuacjach)
  • Jeszcze nie zaimplementowane, ale zaplanowane: Rycerze otrzymują bonus w bardziej zatłoczonych sytuacjach

W jednym z tych punktów wspomniałem o „fazie” gry (np. Otwarcie, środkowa gra, gra końcowa), a jeśli chcesz uwzględnić to w silniku, prawdopodobnie napotkasz ten sam problem, co ja: wyraźna linia oddzielająca je. Moja funkcja decydująca o tym, w której fazie jest gra, wykorzystuje kilka rzeczy:

  • Ilość materiału na planszy (gdy tylko jeden kawałek zostanie zabity, oznacza to, że gra nie znajduje się na początku)
  • Liczba ruchów (mniej niż 6 pełnych ruchów to otwarcie, bez względu na wszystko)
  • ruch królowych (jeśli obie królowe zostały przeniesione, oznacz grę jako środkową)

Ta odpowiedź mogła być długa, spóźniona i nie na temat, ale mam nadzieję, że i tak była pomocna.

mishaturnbull
źródło
4

Nieoczekiwanie okazuje się, że silnik Minimax będzie grał dość dobrze, gdy funkcja oceny jest losowa ; jest to znane jako efekt Beale i wynika z zasady, że pozycje, które dają więcej opcji, a przeciwnikowi mniej opcji, są ogólnie korzystne. Jednym rozsądnym sposobem na spójne i skuteczne generowanie losowych ocen jest wygenerowanie skrótu Zobrist dla pozycji (przy użyciu współczynników wybranych losowo na początku gry) i wyprowadzenie losowej oceny bezpośrednio z skrótu.

Na drugim końcu skali AlphaZero i Leela przeprowadzają niezwykle wyrafinowaną ocenę każdej przeszukiwanej pozycji, wykorzystując dużą sieć neuronową . Niepraktyczne jest opisywanie w kategoriach ludzkich funkcji, które ta sieć skutecznie realizuje, ale jest ona niezaprzeczalnie bardziej skuteczna niż funkcja oceny Sztokfisz. Dokument badawczy AlphaZero wskazuje, że to podejście najlepiej działa w przypadku wyszukiwania drzewa Monte-Carlo, a nie Minimax.

Z drugiej strony, jeśli chcesz opracować silnik analizy, aby pomóc graczom lub komentatorom zrozumieć niuanse pozycji, warto wdrożyć konwencjonalną funkcję oceny z wykorzystaniem ustalonych wartości materiałowych i teorii pozycji . Dobrym przykładem jest Inside Rebel Eda Schrödera , dokumentujący główne cechy konstrukcyjne cenionego silnika stosowanego w kilku komputerach szachowych Mephisto. Możesz użyć pewnego stopnia uczenia maszynowego, aby określić względne znaczenie każdego elementu funkcji oceny, a także rozbić te elementy indywidualnie w celu prezentacji w GUI.

Chromatix
źródło
3

Myślę, że programiści szachowi nie polegają na wiedzy silnych szachistów podczas projektowania ich funkcji oceny, ale zamiast tego wypróbowują różne elementy, a następnie testują je w grach z innymi silnikami i decydują, co zachować. Larry Kaufman mówi sporo o swoich poglądach na temat zrozumienia człowieka, ale wygląda na to, że zarówno Rajlich, jak i Dailey byli bardzo zorientowani na wyniki i nie przyjęli pomysłów Kaufmana hurtowo.

Jednym z interesujących mnie artykułów był Zach Wegner porównujący funkcje oceny Rybki i Fruita. Jednym z obszarów, w których Rybka mogła stanowić krok naprzód, było włączenie tabel nierówności materiałowych opartych na określonych kombinacjach elementów. Kaufman również napisał na ten temat artykuł.

http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm

Przechodzień
źródło
0

Ten link jest najlepszym punktem wyjścia IMHO. Używam tego jako punktu wyjścia do mojego własnego programu szachowego i uważam go za prosty do zrozumienia i przydatny.

https://chessprogramming.wikispaces.com/Simplified+evaluation+function

techcraver
źródło
2
Czy mógłbyś krótko rozwinąć treść linku?
Pablo S. Ocal
Witryna Wikispaces jest teraz nieczynna. Poprawiony link do nowego domu: chessprogramming.org/Simplified_Evaluation_Function
Chromatix
0

W skrócie, standardowe podejście do dostrajania parametrów silnika szachowego to:

  1. Zdefiniuj parametry
  2. Podaj parametry wartości nominalne (początkowe)
  3. Uruchom silnik, aby zobaczyć, jak działa
  4. Dostrój wartości parametrów, aby spróbować poprawić jego wydajność

Następnie powtarzaj kroki 3 i 4, aż osiągniesz swój cel wydajności.

Typowym podejściem do tego jest założenie laboratorium, w którym silniki walczą w turniejach silnikowych. Wykorzystywanych jest wiele gier, w których silnik odtwarza oba kolory. Główne interesujące turnieje obejmują uruchomienie silnika z zestawem wartości parametru A przeciwko temu samemu silnikowi z zestawem wartości parametru B.

Jak zapewne można się domyślić, wyniki tego podejścia są silnie zależne od:

  • Wybrane parametry
  • Jak określono parametry
  • Jak wartości parametrów są zmieniane podczas testowania
  • Sposób działania silników (ograniczona głębokość warstwy, ograniczony czas, czułość itp.)

Takie podejście zajmuje również dużo czasu.

Nowsze (i innowacyjne podejście) zostało opracowane w 2010 r. Przez naukowców wykorzystujących techniki algorytmu genetycznego, aby a) określić parametry ib) dostroić wartości parametrów. Badacze najpierw uruchomili silnik z początkowym, nominalnym zestawem wartości parametrów w stosunku do zestawu gier arcymistrzowskich, aby sprawdzić, czy może on skutecznie wybrać „najlepszy ruch”. „Najlepszy ruch” został zdefiniowany jako ruch, który wykonał arcymistrz *. Gdziekolwiek nie udało się tego zrobić, było to rejestrowane. Następnie wypróbowano inny zestaw wartości parametrów i określono względną wydajność w porównaniu z poprzednim przebiegiem.

Następnie wypróbowano programowe podejście do łączenia wartości parametrów , stosując zasadę algorytmu genetycznego przeżycia „najsilniejszych”. W tym przypadku „najlepiej przystosowany” oznacza taki, który generuje wynik, który najlepiej pasuje do ideału. (Zdarza się również, że jest to gra słów na temat techniki statystycznej regresji „najmniejszych kwadratów”, techniki stosowanej do oceny jakości przybliżenia.)

Dopiero po znalezieniu parametrów silnika, które mogą dość dobrze naśladować GM, rozpoczyna się faktyczna faza turnieju silnika. W tej fazie różne zestawy wartości parametrów są ponownie zestawiane ze sobą, tym razem bezpośrednio . Techniki ulepszania algorytmu genetycznego są stosowane do generowania sukcesywnie lepszych generacji silnika.

W tym projekcie badawczym wykorzystano 36 parametrów, w tym wszystkie wartości materiałowe kawałków, i wiele bardziej powszechnych strategicznych kryteriów oceny, takich jak pionki do tyłu, słabe kwadraty, para biskupów i tak dalej. Jednak naukowcy dodali kilka nowych parametrów, takich jak „presja króla”, wartości „mobilności” dla każdego rodzaju elementu, gawron na pliku sąsiadującym z królem, gawron na półotwartym pliku, wieża atakująca króla na - / b- / g- / h-file, separacja między minionym pionkiem a broniącym królem i więcej.

Niestety badacze nie opracowują, w jaki sposób wymyślili ten zestaw parametrów i jakie alternatywne parametry mogli przetestować i odrzucić. Rozsądnie byłoby założyć, że zaczęły one od znacznie większego zestawu i określiły (metodą prób i błędów), które z nich miały największy wpływ na wydajność, a które były albo nieznaczne, albo pochodne, a więc mogły zostać porzucone.

Jeśli wydaje się to przydatne, możesz znaleźć badania tutaj .

* Zastrzeżenie dotyczące fazy podejścia zastosowanego przez naukowców jest w porządku. W swoim Wstępie do zrozumienia gry w szachy Move by Move John Nunn wybrał „... ciężkie walki między silnymi arcymistrzami ...”, aby zilustrować swoje tematy. Następnie dodaje:

Czytelnicy mogą być zaskoczeni, widząc liczbę znaków zapytania, które zdobią gry z tej książki. Na pewno możesz pomyśleć, mając tylko trzydzieści gier do wyboru, znalezienie gier dźwiękowych powinno być łatwe. Mogę jednak zapewnić, że tak nie było. ... można znaleźć błąd w praktycznie każdej złożonej, trudnej grze ... Nigdy nie czułem, że moja gra była prawie całkowicie dokładna, więc osobiście nie uważam tych rewelacji za niepokojące. Jednak niektórym może być trudno przyznać, że szachy rozgrywane przez ludzi są mniej dokładne niż wcześniej sądzono.

Punkt, który podnosi dr Nunn, sugeruje, że początkowe podejście badaczy do ustawiania parametrów silnika poprzez wymaganie od nich naśladowania ruchów arcymistrza może być błędne, ponieważ gra ludzi jest wadliwa . W rzeczywistości ustalono, że silniki już działają lepiej niż ludzie .

Dlatego być może lepszym podejściem do ustawiania parametrów początkowych byłoby dopasowanie nowego silnika do istniejącego silnika lepszej jakości .

Jaxter
źródło