Jak poprawiły się silniki od Deep Blue?

17

Komputerowe silniki szachowe stały się lepsze, odkąd Deep Blue pokonał Kasparowa w 1997 roku.

Czy algorytmy uległy poprawie, czy też ulepszenia wynikały głównie z tego, że te same algorytmy działały szybciej dzięki szybszemu sprzętowi itp.?

Jeśli to pierwsze, czy te ulepszenia algorytmu są publiczne?

A jeśli tak, jakie ulepszenia? Gdzie mogę o nich przeczytać?

MaxB
źródło
W jaki sposób ? Dramatycznie.
Evargalo

Odpowiedzi:

8

Może zajrzysz na TalkChess , forum poświęcone szachom komputerowym. Znalazłem najnowszy wątek, który może być dla ciebie interesujący: Postęp za 30 lat w czterech odstępach 7-8 lat

Kilka meczów pomiędzy (poprzednimi) najlepszymi silnikami jest rozgrywanych na tym samym sprzęcie . Test sugeruje, że w ostatnich latach (2002-2017) zysk jest głównie spowodowany ulepszeniami oprogramowania. W teście Sztokfisz (2017) strzelił imponującą liczbę 94/100 przeciwko RobboLito (2009), podczas gdy RobboLito z kolei zmiażdżył Shredder (2002) 92/100.

Ważna uwaga: ponieważ obliczenia równoległe nie są zaimplementowane w starszych silnikach, test został przeprowadzony na jednym rdzeniu. W rezultacie wzmocnienie sprzętu przez maszyny równoległe nie jest mierzone. Z drugiej strony można argumentować, że obliczenia równoległe to także zysk oprogramowania: nie jest łatwo zaprojektować i wdrożyć wydajną i dobrze skalowalną równoległość algorytmu wyszukiwania.

Silnik Sztokfisz jest oprogramowaniem typu open source, więc ulepszenia algorytmu są publiczne. Wiele dokumentacji można znaleźć na https://chessprogramming.wikispaces.com

Maxwell86
źródło
To odpowiada jego twierdzeniom. Spróbuj odpowiedzieć na pytanie następnym razem.
Fred Knight
1
Cóż, wydaje mi się, że odpowiedziałem na pytanie: zysk wynika głównie z ulepszeń algorytmu. Ponadto pokazałem dane, które potwierdzają to twierdzenie (patrz link) i wskazałem na ewentualne niedociągnięcia (bez pomiaru równoległości).
Maxwell86,
3

Nie mogę mówić za algorytmem zastosowanym w Deep Blue, ale spróbuję wyjaśnić ulepszenia w programowaniu szachowym. Szybkość to największa poprawa. Deep Blue używało wieloprocesorowych komputerów dedykowanych, więc porównanie nie jest tak naprawdę możliwe.

https://chessprogramming.wikispaces.com/ jest doskonałym źródłem, ale nawigacja jest trudna.

Istnieją 3 główne funkcje, które zostały ulepszone w celu ulepszenia silnika szachowego: funkcje oceny, generowania ruchów i wyszukiwania.

Ocena jest najtrudniejsza do zaprogramowania, ponieważ istnieje wiele wyjątków od zasad. Ponieważ miejsce na dysku twardym staje się coraz tańsze, funkcja eval pozwala na ocenę większej liczby wyjątków.

Generowanie ruchów, a także wykonywanie i cofanie ruchów, pochłania dużo pamięci, ponieważ trzeba je wykonać wiele razy. Najczęstsze funkcje generowania to skrzynka pocztowa, płyta główna, 0x88, 8x8, rozszerzone płyty (10x10, 10x12) i z góry określona tablica / tabela ruchów (* Używam indeksowanej tabeli ruchów). Obecna opinia jest taka, że ​​bitboardy są szybsze, a używanie magicznych bitboardów przyspiesza to nawet o 30%. Dr Robert Hyatt, profesor i twórca cratfy silnika szachowego, twierdzi, że nie ma znaczącego wzrostu prędkości.

Funkcja wczesnego wyszukiwania była pierwotną funkcją min-max. Zasadniczo próbowałeś zmaksymalizować wynik strony, aby się poruszyć i zminimalizować wynik przeciwnika. Alpha-Beta była pierwszą poprawą. Zmniejszyli liczbę przeszukiwanych ruchów według tabeli transpozycji, wartości odcięcia, okien aspiracji i heurystyki historii. Są to wyszukiwania w pierwszej kolejności. Istnieje również wewnętrzne iteracyjne wyszukiwanie pogłębiające, które próbuje wyszukać „najlepszy” ruch (y) najgłębiej mając nadzieję, że wyszukiwanie innych ruchów okaże się bezowocne.

UWAGA: Moja tabela indeksu. GNUChess i Jester używają tablicy indeksów do generowania swoich ruchów. Inicjują silnik, wypełniając tablicę możliwymi ruchami. Weź sześć elementów i oblicz legalne ruchy dostępne z każdego kwadratu. Więc każdy kawałek miał tablicę [64] [8]. Wziąłem ten pomysł i skompresowałem go do dwóch indeksów i tabeli. Tabela zawiera wartość, która mówi, czy 16 ruchów jest możliwych, jeden indeks przechowuje przesunięcie, a drugi maskę.

offset [] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};

maska ​​[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};

Następnie wygenerowanie ruchu przesuwnego jest tak proste, jak sprawdzenie ważności maski w dopuszczalnych przesunięciach względem tabeli ruchów.

Fred Knight
źródło
7
Staram się nie odpowiadać na odpowiedzi, ale to po prostu .... Alpha-beta i płyty główne zostały wymyślone DŁUGO przed Deep Blue. Jestem też całkiem pewien, że eval płyty nie ma dostępu do HD w żadnym rozsądnym silniku (opóźnienie jest OGROMNE). Po czwarte, jestem bardzo sceptycznie nastawiony do tego, że rozmiar pamięci RAM ma rzeczywistą różnicę w normalnej implementacji wyszukiwania alfa-beta.
MaxB
Czy mógłbyś dodać jakieś hiperłącza do niektórych omawianych pojęć? Jako ktoś, kto interesuje się tą koncepcją, ale nie zna terminologii, trudno ją śledzić, ponieważ nie wiem, co to jest płyta bitowa lub silnik Crafty Chess.
Thunderforge
Pomyślałem, że jestem pewien, że nie porównuję się do Deep Blue, ale przedstawiłem krótką historię. Dysk twardy, o którym mówiłem, to sam program. Za każdym razem, gdy nowa koncepcja ewaluacji jest zawarta w silniku szachowym, potrzeba więcej kodu, a zatem wymagana jest większa przestrzeń HD.
Fred Knight
@Thunderforge, jeden link, który podałem, wyjaśnia każdy aspekt, jaki możesz chcieć zajmować się programowaniem szachowym, jednak przyznam, że nawigacja jest trudna. Nauczyłem się czytając kody źródłowe innych, ale tym, który jest najbardziej komentowany, jest przebiegły silnik Dr. Hyatta. Zdecydowałem się nie być zbyt kompleksowy z powodu ograniczeń miejsca i różnic między platformami i kompilatorami. Jeśli po przeczytaniu strony szachowej wiki nadal jesteś zdezorientowany, zadaj pytanie i jestem pewien, że wielu zapewni lepszą odpowiedź.
Fred Knight
1
Every time that a new eval concept in included into a chess engine, more code, and therefore more HD space is required.Funkcje ewaluacji płytki są zazwyczaj zaprojektowane tak, aby pasowały do ​​pamięci podręcznej procesora. Pamięć podręczna procesora << RAM << HD. Rozmiar HD nie ma znaczenia.
MaxB
2

Czy algorytmy stały się lepsze?

Oczywiście tak trochę.

a może ulepszenia wynikały głównie z tego, że te same algorytmy działały szybciej dzięki szybszemu sprzętowi i oprogramowaniu?

Minor nit: Jeśli algorytmy uległy poprawie, oznacza to, że oprogramowanie jest coraz lepsze, więc nie ma „lub”.

Prawo Moore'a mówi nam, że prędkość procesora podwoi się mniej więcej co 18 miesięcy. Oznacza to, że podwoił się około 13 razy w ciągu 20 lat. To sprawia, że ​​nowoczesne procesory gdzieś w regionie 8 000 razy szybsze. Tak więc zdecydowanie większa poprawa wydajności silnika wynika z szybszego sprzętu.

Jeśli to pierwsze, czy te ulepszenia algorytmu są publiczne?

A jeśli tak, jakie ulepszenia? Gdzie mogę o nich przeczytać?

Cóż, to nie był pierwszy, to był drugi. Niemniej jednak ulepszenia są głównie otwarte i łatwo widoczne, pobierając źródła dla silników takich jak Sztokfisz . Być może warto również podać ogólny link do pobrania Sztokfisz, ponieważ konkretny link do kodu źródłowego prawdopodobnie wygasa, gdy wyjdzie wersja 9.

Brian Towers
źródło
2
That means it has doubled roughly 13 times in 20 years.Myślę, że źle cytujesz prawo Moore'a. Nie mówi nic o szybkości procesora. W rzeczywistości od jakiegoś czasu się nie podwoiła.
MaxB
hardware and softwareMiałem na myśli oprogramowanie jak w implementacji algorytmu (ASM vs C ++), ale widzę, jak to jest mylące. Naprawiony.
MaxB
1
Prawo Moore'a jest poprawne, z tym wyjątkiem, że zawiera zwrot „w następnej dekadzie”. Byłoby to w 1975 roku i miał rację.
Fred Knight
-1, ponieważ odpowiedź jest niepoprawna - na tym samym sprzęcie obecne silniki wciąż miażdżą silniki poprzednio najlepsze.
Allure
0

Chodzi o algorytmy.

Wcielając się w szachistę, zabrał jeden z najpotężniejszych komputerów na świecie. To podejście oparte na brutalnej sile pozwoliło Deep Blue spojrzeć na około 6-8 ruchów do przodu. W zaciętej walce maszyna ostatecznie pokonała Kasparowa o 3 1/2 gry do 2 1/2.

Sześć lat później Kasparow brał udział w innym konkursie człowiek kontra maszyna. Tym razem grał przeciwko następcy Deep Blue, Deep Junior. Rezultatem była losowana seria w trzech grach. Największą różnicą było to, że Deep Junior działał na maszynie z około jednym procentem mocy obliczeniowej Deep Blue. Algorytmy gry w szachy poprawiły się do tego stopnia, że ​​osiągnęły praktycznie ten sam wynik przy stukrotnie mniejszej mocy obliczeniowej.

David Hambling
źródło
4
Witamy w szachach! Napisałeś główną część swojej odpowiedzi, jakby to był cytat; czy możesz podać źródło?
Glorfindel
0

Oświadczenie: nie jest ekspertem.

Algorytmy uległy poprawie, a najlepsze dzisiejsze silniki działające w 1995 r. (Pamiętaj, że Deep Blue to 1999), sprzęt pokona Kasparowa. Jak rozumiem, istnieją dwa aspekty algorytmów:

Szukaj . Jeśli na przykład zabiorę twoją królową z moją królową, przeciwnik automatycznie spojrzy najpierw na złapanie. Jednak w przypadku komputera będzie oceniać każdą możliwą odpowiedź na QxQ. Prawie cały czas marnuje się moc obliczeniową. Dobry algorytm wyszukiwania ogranicza wszystkie te „gałęzie”, ponieważ i tak są one nieistotne.

Standardowym algorytmem wyszukiwania jest przycinanie alfa-beta i było ono stosowane w najwcześniejszych komputerach szachowych. Nie wiem, czy Deep Blue zastosowało przycinanie alfa-beta, ale nowoczesne silniki tego nie robią. W rezultacie ich wyszukiwania są „niebezpieczne” - mogą na przykład przeoczyć, że jakiś ruch inny niż odzyskanie królowej wygrałby grę. Jednak zdarza się to rzadko, aw zamian pchają swoje głębokości bardzo wysoko. („Głębokość” to termin techniczny określający, jak głęboko silnik szuka, więc np. Silnik, który szuka do głębokości 30, prawdopodobnie pobije taki, który szuka tylko do głębokości 20, przy czym wszystkie inne rzeczy są równe).

Ewaluacja . To jest druga kwestia kodu silnika. Biorąc pod uwagę określoną pozycję, czy jest lepiej dla bieli, czerni lub równości? Może to obejmować różnego rodzaju funkcje, np

  • Jeśli jedna strona ma dodatkowy materiał / przestrzeń, daj jej premię do ewaluacji.
  • Jeśli biały ma zaawansowanego rycerza wspieranego przez pionka, daj mu premię do ewaluacji.
  • Jeśli król czarnych jest w impasie, daj białym premię do ewaluacji.
  • Jeśli biały ma wieżę na 7. pozycji, daj białemu premię do ewaluacji.
  • Jeśli jest to gra końcowa (i istnieją algorytmy decydujące o tym, czy pozycja jest grą końcową), a obie strony mają przeciwnych kolorów biskupów, nałóż karę na ewaluację (tj. Popchnij ją w kierunku 0,00).

Dzisiejsze silniki oceniają pozycje znacznie lepiej niż Deep Blue.

Jeśli chodzi o to, czy algorytmy są publiczne, Sztokfisz jest obecnie najsilniejszym silnikiem na świecie i jest open source. Możesz pobrać kod samodzielnie z Github .

Nęcić
źródło