Jak poprawiły się silniki od Deep Blue?

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ć?

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

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.

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.

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.

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 .