Szachy komputerowe -Computer chess

Dla filmu 2013, zobacz Szachy komputerowe (film) .
Komputer szachowy z czujnikiem ciśnienia z lat 90. z ekranem LCD
Ten artykuł jest częścią serii na
Programowanie szachów
Szachy Programowanie.svg
Reprezentacje Zarządu
Funkcje oceny
Algorytmy wyszukiwania grafów i drzew
Komputery szachowe
Silniki szachowe

Szachy komputerowe obejmują zarówno sprzęt (dedykowane komputery), jak i oprogramowanie umożliwiające grę w szachy . Szachy komputerowe dają graczom możliwość ćwiczenia nawet pod nieobecność ludzkich przeciwników, a także dają możliwość analizy, rozrywki i treningu.

Komputerowe aplikacje szachowe, które grają na poziomie mistrza szachowego lub wyższym, są dostępne na sprzęcie od superkomputerów po smartfony . Dostępne są również wolnostojące maszyny do gry w szachy. Stockfish , GNU Chess , Fruit i inne bezpłatne aplikacje typu open source są dostępne dla różnych platform.

Komputerowe aplikacje szachowe, zaimplementowane w sprzęcie lub oprogramowaniu, wykorzystują inne strategie niż ludzie, aby wybrać swoje ruchy: używają metod heurystycznych do budowania, wyszukiwania i oceny drzew reprezentujących sekwencje ruchów z aktualnej pozycji i próbują wykonać najlepszą taką sekwencję podczas gry . Takie drzewa są zazwyczaj dość duże, od tysięcy do milionów węzłów. Szybkość obliczeniowa nowoczesnych komputerów, zdolnych do przetwarzania dziesiątek tysięcy do setek tysięcy węzłów lub więcej na sekundę, wraz z heurystykami rozszerzania i redukcji, które zawężają drzewo do najbardziej istotnych węzłów, sprawiają, że takie podejście jest skuteczne.

Pierwsze maszyny szachowe zdolne do gry w szachy lub zredukowane gry podobne do szachów były programami działającymi na komputerach cyfrowych na początku ery komputerów z lampą próżniową (lata pięćdziesiąte XX wieku). Wczesne programy grały tak słabo, że nawet początkujący mógł je pokonać. W ciągu 40 lat, w 1997 roku, silniki szachowe działające na superkomputerach lub specjalistycznym sprzęcie były w stanie pokonać nawet najlepszych ludzkich graczy . Do 2006 r. programy działające na komputerach stacjonarnych osiągnęły te same możliwości. W 2006 roku Monroe Newborn , profesor informatyki na Uniwersytecie McGill , oświadczył: „nauka została dokonana”. Niemniej jednak rozwiązywanie szachów nie jest obecnie możliwe na nowoczesnych komputerach ze względu na niezwykle dużą liczbę możliwych odmian gry .

Szachy komputerowe były kiedyś uważane za „ Drozofilę AI”, krawędź inżynierii wiedzy . Ale ta dziedzina jest obecnie uważana za naukowo ukończony paradygmat, a gra w szachy jest przyziemną czynnością komputerową.

Dostępność i siła gry

Układ scalony szachów komputerowych noszący imię twórcy Fransa Morscha (patrz Mephisto )

Automaty/programy szachowe są dostępne w kilku różnych postaciach: samodzielne maszyny szachowe (zwykle mikroprocesor z oprogramowaniem do szachów, ale czasami jako wyspecjalizowana maszyna sprzętowa), programy działające na standardowych komputerach PC, strony internetowe i aplikacje na urządzenia mobilne . Programy działają na wszystkim, od superkomputerów po smartfony. Wymagania sprzętowe dla programów są minimalne; aplikacje są nie większe niż kilka megabajtów na dysku, zużywają kilka megabajtów pamięci (ale mogą używać znacznie więcej, jeśli jest dostępna), a wystarczy dowolny procesor 300Mhz lub szybszy. Wydajność będzie się nieznacznie różnić w zależności od szybkości procesora, ale wystarczająca ilość pamięci do przechowywania dużej tabeli transpozycji (do kilku gigabajtów lub więcej) jest ważniejsza dla siły odtwarzania niż szybkość procesora.

Większość dostępnych komercyjnych programów i maszyn szachowych może grać z mocą super arcymistrza (Elo 2700 lub więcej) i korzystać z wielordzeniowych i hiperwątkowych architektur procesorów komputerowych. Najlepsze programy, takie jak Stockfish , prześcignęły nawet mistrzów świata w kalibrze. Większość programów szachowych zawiera silnik szachowy połączony z graficznym interfejsem użytkownika, takim jak Winboard lub Chessbase . Siłę gry, kontrolę czasu i inne ustawienia związane z wydajnością można regulować z poziomu GUI. Większość GUI pozwala również graczowi na ustawianie i edycję pozycji, odwracanie ruchów, oferowanie i akceptowanie remisów (i rezygnację), żądanie i otrzymywanie rekomendacji ruchów oraz pokazywanie analizy silnika w miarę postępu gry.

Istnieje kilka silników szachowych, takich jak Sargon , IPPOLIT , Stockfish , Crafty , Fruit , Leela Chess Zero i GNU Chess , które można bezpłatnie pobrać (lub uzyskać kod źródłowy w inny sposób) z Internetu .

Rodzaje i cechy oprogramowania szachowego

Być może najczęstszym rodzajem oprogramowania szachowego są programy, które po prostu grają w szachy. Gracz-człowiek wykonuje ruch na planszy, sztuczna inteligencja oblicza i gra kolejny ruch, a człowiek i sztuczna inteligencja naprzemiennie tury, dopóki jeden z graczy nie zrezygnuje. Silnik szachowy , który oblicza ruchy, oraz graficzny interfejs użytkownika (GUI) to czasem osobne programy. Do GUI można podłączyć różne silniki, co pozwala na grę przeciwko różnym stylom przeciwnika. Silniki często mają prosty tekstowy interfejs wiersza poleceń , podczas gdy GUI mogą oferować różnorodne zestawy elementów, style plansz, a nawet elementy 3D lub animowane. Ponieważ najnowsze silniki są tak wydajne, silniki lub GUI mogą oferować pewien sposób upośledzenia zdolności silnika, aby zwiększyć szanse na wygraną przez ludzkiego gracza. Silniki Universal Chess Interface (UCI), takie jak Fritz lub Rybka , mogą mieć wbudowany mechanizm zmniejszania oceny Elo silnika (poprzez parametry UCI uci_limitstrength i uci_elo). Niektóre wersje Fritza mają tryb Handicap and Fun, który ogranicza obecny silnik lub zmienia procent popełnianych przez niego błędów lub zmienia jego styl. Fritz ma również tryb przyjaciela, w którym podczas gry stara się dopasować poziom gracza.

Zrzut ekranu szachów , składnika systemu macOS

Szachowe bazy danych pozwalają użytkownikom przeszukiwać obszerną bibliotekę historycznych partii, analizować je, sprawdzać statystyki i formułować repertuar debiutów. Chessbase (na PC) jest popularnym programem do tych celów wśród profesjonalnych graczy, ale istnieją alternatywy, takie jak Shane's Chess Information Database (Scid) dla Windows, Mac lub Linux, Chess Assistant na PC, Gerhard Kalab's Chess PGN Master dla Androida lub Giordano Studio szachowe Vicoli na iOS.

Programy takie jak Playchess umożliwiają grę z innymi graczami przez Internet.

Szachowe programy szkoleniowe uczą gry w szachy. Chessmaster miał tutoriale do gry autorstwa IM Josha Waitzkina i GM Larry'ego Christiansena . Stefan Meyer-Kahlen oferuje nauczyciela szachów Shredder w oparciu o podręczniki Step Roba Brunia i Cora Van Wijgerdena. Mistrzowie świata, Magnus Carlsen , firma Play Magnus, wydała aplikację Magnus Trainer na Androida i iOS. Chessbase ma Fritz i Chesster dla dzieci. Convekta zapewnia dużą liczbę aplikacji szkoleniowych, takich jak CT-ART i linia Chess King, oparta na samouczkach GM Alexandra Kalinina i Maxima Blokha.

Istnieje również oprogramowanie do rozwiązywania problemów szachowych .

Komputery kontra ludzie

Główny artykuł: Mecze szachowe człowiek-komputer

Po odkryciu w 1957 roku badań przesiewowych obalania — zastosowania przycinania alfa-beta do optymalizacji oceny ruchu — zespół z Carnegie Mellon University przewidział, że komputer pokona światowego mistrza świata do 1967 roku. Nie przewidział trudności w ustaleniu właściwej kolejności oceniać ruchy. Naukowcy pracowali nad poprawą zdolności programów do identyfikowania zabójczych heurystyk , niezwykle wysoko punktowanych ruchów, które należy ponownie przeanalizować podczas oceny innych gałęzi, ale w latach 70. większość czołowych szachistów wierzyła, że ​​komputery nie będą wkrótce w stanie grać na poziomie mistrzowskim . W 1968 roku międzynarodowy mistrz David Levy poczynił słynny zakład , że żaden komputer szachowy nie będzie w stanie go pokonać w ciągu dziesięciu lat, a w 1976 roku starszy mistrz i profesor psychologii Eliot Hearst z Indiana University napisał, że „jedyny sposób, w jaki obecny program komputerowy może kiedykolwiek wygranie jednej gry z mistrzem byłoby dla mistrza, być może w pijackim odrętwieniu podczas rozgrywania 50 gier jednocześnie, popełnić raz w roku błąd”.

Pod koniec lat 70. programy szachowe nagle zaczęły pokonywać wysoko wykwalifikowanych graczy. W roku, w którym Hearst wygłosił oświadczenie, gra szachowa Northwestern University 4.5 na poziomie klasy B Paula Massona American Chess Championship jako pierwsza wygrała turniej ludzi. Levy wygrał swój zakład w 1978 roku, pokonując Chess 4.7 , ale odniósł pierwsze komputerowe zwycięstwo przeciwko graczowi klasy mistrzowskiej na poziomie turniejowym, wygrywając jedną z sześciu gier. W 1980 Belle zaczęła często pokonywać Masters. Do 1982 roku dwa programy grane były na poziomie Master, a trzy były nieco słabsze.

Nagła poprawa bez teoretycznego przełomu była nieoczekiwana, ponieważ wielu nie spodziewało się, że zdolność Belle do zbadania 100 000 pozycji na sekundę – około ośmiu warstw – będzie wystarczająca. Spracklens, twórcy odnoszącego sukcesy programu mikrokomputerowego Sargon , oszacowali, że 90% ulepszeń wynikało z większej szybkości ewaluacji, a tylko 10% z ulepszonych ewaluacji. New Scientist stwierdził w 1982 roku, że komputery „grają w okropne szachy… niezdarne, nieefektywne, rozproszone i po prostu brzydkie”, ale ludzie przegrali z nimi, popełniając „okropne błędy, zdumiewające błędy, niezrozumiałe przeoczenia, rażące błędy w obliczeniach i tym podobne”. znacznie częściej, niż sądzili; „w skrócie, komputery wygrywają przede wszystkim dzięki swojej zdolności do znajdowania i wykorzystywania błędnych obliczeń w ludzkich inicjatywach”.

Do 1982 r. mikrokomputerowe programy szachowe mogły oceniać do 1500 ruchów na sekundę i były tak silne, jak programy szachowe na mainframe pięć lat wcześniej, zdolne pokonać większość graczy amatorów. Chociaż byli w stanie patrzeć w przyszłość tylko o jedną lub dwie warstwy więcej niż podczas swojego debiutu w połowie lat 70., poprawiło to ich grę bardziej, niż oczekiwali eksperci; pozornie drobne usprawnienia „wydaje się, że umożliwiły przekroczenie psychologicznego progu, po którym dostępne stają się bogate żniwo ludzkiego błędu”, napisał New Scientist . Recenzując SPOC w 1984 roku, BYTE napisał, że „komputery — mainframe, minis i mikro — mają tendencję do grania brzydkich, nieeleganckich szachów”, ale zauważył stwierdzenie Roberta Byrne’a , że ​​„taktycznie są bardziej wolne od błędów niż przeciętny gracz”. Magazyn opisał SPOC jako „najnowocześniejszy program szachowy” dla IBM PC z „zaskakująco wysokim” poziomem gry i oszacował jego ocenę USCF na 1700 (klasa B).

Podczas Mistrzostw Ameryki Północnej w Szachach Komputerowych w 1982 r. Monroe Newborn przewidział, że program szachowy może zostać mistrzem świata w ciągu pięciu lat; dyrektor turnieju i mistrz międzynarodowy Michael Valvo przewidział dziesięć lat; Spracklenowie przewidzieli 15; Ken Thompson przewidział ponad 20; a inni przewidywali, że to się nigdy nie zdarzy. Najpopularniejsza opinia głosiła jednak, że nastąpi to około 2000 roku. W 1989 roku Levy został pokonany przez Deep Thought w meczu pokazowym. Jednak Deep Thought wciąż było znacznie poniżej poziomu Mistrzostw Świata, co panujący mistrz świata, Garry Kasparow , zademonstrował dwa silne zwycięstwa w 1989 roku. Dopiero w 1996 roku w meczu z Deep Blue IBM , Kasparow przegrał swoją pierwszą grę z komputerem podczas kontroli czasu turnieju w grze Deep Blue kontra Kasparow, 1996, mecz 1 . W tej grze po raz pierwszy panujący mistrz świata przegrał z komputerem używającym regularnych kontroli czasu. Jednak Kasparow przegrupował się, aby wygrać trzy i zremisować dwa z pozostałych pięciu meczów, odnosząc przekonujące zwycięstwo.

W maju 1997, zaktualizowana wersja Deep Blue pokonała Kasparowa 3½–2½ w rewanżu. Film dokumentalny głównie o konfrontacji powstał w 2003 roku, zatytułowany Game Over: Kasparow i maszyna .

Deep Blue kontra Kasparow, 1996, mecz 1
a b c d mi f g h
8
Szachownica480.svg
h7 biała wieża
f6 czarna królowa
h6 czarny król
d5 biała królowa
g5 biały rycerz
d4 czarny pionek
biały pionek a3
b3 biały pionek
f3 czarny pionek
biały pionek g3
h3 biały pionek
f2 czarny rycerz
h2 biały król
e1 czarna wieża
 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d mi f g h
Pozycja końcowa

Wraz ze wzrostem mocy obliczeniowej i ulepszonymi funkcjami oceny, programy szachowe działające na dostępnych na rynku stacjach roboczych zaczęły rywalizować z najlepszymi graczami. W 1998 roku Rebel 10 pokonał Viswanathana Ananda , który w tym czasie zajmował drugie miejsce na świecie, wynikiem 5-3. Jednak większość z tych gier nie była rozgrywana przy normalnych kontrolach czasu. Z ośmiu gier cztery były grami błyskawicznymi (pięć minut plus pięć sekund opóźnienia Fischera na każdy ruch); ci Rebel wygrali 3-1. Dwie gry były pół-blitzowe (piętnaście minut dla każdej ze stron), które Rebel również wygrał (1½–½). Ostatecznie dwie gry rozegrano jako zwykłe gry turniejowe (czterdzieści ruchów w dwie godziny, jedna godzina nagłej śmierci); tutaj to Anand wygrał ½-1½. W szybkich grach komputery grały lepiej niż ludzie, ale przy klasycznych kontrolach czasu – przy których ustalana jest ocena gracza – przewaga nie była tak wyraźna.

Na początku XXI wieku dostępne na rynku programy, takie jak Junior i Fritz , były w stanie zremisować mecze z byłym mistrzem świata Garrym Kasparowem i klasycznym mistrzem świata Vladimirem Kramnikiem .

W październiku 2002 roku Vladimir Kramnik i Deep Fritz zmierzyli się w ośmiomeczowym meczu Brains in Bahrain , który zakończył się remisem. Kramnik wygrał partie 2 i 3 „konwencjonalną” taktyką antykomputerową – graj konserwatywnie, aby uzyskać długoterminową przewagę, której komputer nie jest w stanie zobaczyć w przeszukiwaniu drzewa gier. Fritz wygrał jednak piątą partię po poważnym błędzie Kramnika. Gra 6 została opisana przez komentatorów turnieju jako „spektakularna”. Kramnik, mający lepszą pozycję we wczesnej grze środkowej , spróbował poświęcić kawałek, aby osiągnąć silny atak taktyczny, strategię, o której wiadomo, że jest wysoce ryzykowna przeciwko komputerom, które najlepiej bronią się przed takimi atakami. Zgodnie z formą, Fritz znalazł wodoszczelną obronę, a atak Kramnika wygasł, pozostawiając go w złej pozycji. Kramnik zrezygnował z gry, wierząc, że pozycja jest stracona. Jednak analiza ludzi i komputerów po grze wykazała, że ​​program Fritza prawdopodobnie nie był w stanie wymusić wygranej, a Kramnik skutecznie poświęcił remisowaną pozycję. Ostatnie dwie gry były remisami. Biorąc pod uwagę okoliczności, większość komentatorów nadal ocenia Kramnika jako silniejszego zawodnika w meczu.

W styczniu 2003 roku Kasparow grał Junior , inny program komputerowy do gry w szachy, w Nowym Jorku. Mecz zakończył się wynikiem 3:3.

W listopadzie 2003 Kasparow grał w X3D Fritz . Mecz zakończył się wynikiem 2:2.

W 2005 roku Hydra , dedykowany komputer szachowy z niestandardowym sprzętem i sześćdziesięcioma czterema procesorami, a także zwycięzca 14. edycji IPCCC w 2005 roku, pokonał siódmego w rankingu Michaela Adamsa 5½–½ w sześciomeczowym meczu (chociaż przygotowania Adamsa były znacznie mniejsze dokładny niż Kramnika dla serii 2002).

W listopadzie i grudniu 2006 roku mistrz świata Vladimir Kramnik grał w Deep Fritz. Tym razem wygrał komputer; mecz zakończył się wynikiem 2-4. Kramnik mógł wyświetlić książkę otwierającą komputer. W pierwszych pięciu meczach Kramnik skierował grę w typową „antykomputerową” rywalizację pozycyjną. Przegrał jedną partię ( przeoczył mata w jednym ), a kolejne cztery zremisował. W finale, próbując zremisować mecz, Kramnik zagrał bardziej agresywną obronę Sicilian Defense i został zmiażdżony.

Spekulowano, że w wyniku meczu Kramnik-Deep Fritz w 2006 roku zainteresowanie zawodami szachowymi człowiek-komputer spadnie. Według Newborna na przykład „nauka jest skończona”.

Mecze szachowe człowiek-komputer pokazały, że najlepsze systemy komputerowe wyprzedziły ludzkich mistrzów szachowych pod koniec lat 90-tych. Przez ostatnie 40 lat panował trend polegający na tym, że najlepsze maszyny zdobywały około 40 punktów rocznie w rankingu Elo , podczas gdy najlepsi ludzie zyskiwali tylko około 2 punkty rocznie. Najwyższą oceną uzyskaną przez komputer w rywalizacji międzyludzkiej była ocena Deep Thought USCF wynosząca 2551 w 1988 r., a FIDE nie akceptuje już wyników człowiek-komputer na swoich listach rankingowych. Do oceniania maszyn stworzono specjalne pule Elo przeznaczone tylko dla maszyn, ale takie liczby, chociaż mają podobny wygląd, nie są bezpośrednio porównywane. W 2016 roku Szwedzkie Stowarzyszenie Komputerów Szachowych oceniło program komputerowy Komodo na 3361.

Silniki szachowe wciąż się poprawiają. W 2009 roku silniki szachowe działające na wolniejszym sprzęcie osiągnęły poziom arcymistrzowski . Telefon komórkowy wygrał turniej kategorii 6 z oceną wydajności 2898: silnik szachowy Hiarcs 13 działający w Pocket Fritz 4 na telefonie komórkowym HTC Touch HD wygrał turniej Copa Mercosur w Buenos Aires w Argentynie z 9 zwycięstwami i 1 remisem w dniu 4 sierpnia – 14, 2009. Pocket Fritz 4 przeszukuje mniej niż 20 000 pozycji na sekundę. Jest to w przeciwieństwie do superkomputerów, takich jak Deep Blue, które przeszukiwały 200 milionów pozycji na sekundę.

Advanced Chess to forma szachów opracowana w 1998 roku przez Kasparowa, w której człowiek gra przeciwko drugiemu człowiekowi i obaj mają dostęp do komputerów, aby zwiększyć swoją siłę. Kasparow twierdził, że powstały „zaawansowany” gracz jest silniejszy niż sam człowiek lub komputer. Zostało to udowodnione przy wielu okazjach, na przykład na imprezach Freestyle Chess.

Dzisiejsi gracze są skłonni traktować silniki szachowe jako narzędzia analityczne, a nie przeciwników. Szachowy arcymistrz Andrew Soltis stwierdził w 2016 roku: „Komputery są po prostu zbyt dobre” i że mistrz świata Magnus Carlsen nie będzie grał w szachy komputerowe, ponieważ „po prostu przegrywa cały czas i nie ma nic bardziej przygnębiającego niż przegrywanie nawet bez udziału w grze. "

Metody komputerowe

Od ery maszyn mechanicznych, które grały w końcówki wież i królów oraz maszyn elektrycznych, które grały w inne gry, takie jak hex we wczesnych latach XX wieku, naukowcy i teoretycy starali się opracować proceduralną reprezentację tego, jak ludzie uczą się, zapamiętują, myślą i stosują wiedza, a gra w szachy, ze względu na swoją zniechęcającą złożoność, stała się „ Drosophila sztucznej inteligencji (AI)”. Proceduralne rozwiązanie złożoności stało się synonimem myślenia, a wczesne komputery, jeszcze przed erą automatów szachowych, były popularnie określane jako „elektroniczne mózgi”. Kilka różnych schematów zostało opracowanych od drugiej połowy XX wieku, aby reprezentować wiedzę i myślenie w odniesieniu do gry w szachy (i innych gier, takich jak warcaby):

Wykorzystując heurystykę „końca i środka”, szachista może intuicyjnie określić optymalne wyniki i sposób ich osiągnięcia, niezależnie od liczby niezbędnych ruchów, ale komputer musi być systematyczny w swojej analizie. Większość graczy zgadza się, że patrzenie na co najmniej pięć ruchów do przodu (dziesięć warstw ), gdy jest to konieczne, jest wymagane do dobrej gry. Normalne zasady turniejowe zapewniają każdemu graczowi średnio trzy minuty na ruch. Przeciętnie na jedną pozycję szachową przypada ponad 30 prawidłowych ruchów, więc komputer musi zbadać biliardy możliwości wybiegania w przyszłość dziesięciu partii (pięć pełnych ruchów); taki, który mógłby zbadać milion pozycji na sekundę, wymagałby ponad 30 lat.

Najwcześniejsze próby proceduralnych reprezentacji gry w szachy poprzedzały erę cyfrowej elektroniki, ale to cyfrowy komputer z zapisanym programem dał pole do obliczenia takiej złożoności. Claude Shannon w 1949 przedstawił zasady algorytmicznego rozwiązywania szachów. W tym artykule gra jest reprezentowana przez „drzewo” lub cyfrową strukturę danych wyborów (gałęzi) odpowiadających ruchom. Węzły drzewa były pozycjami na planszy wynikającymi z wyborów ruchu. Niemożność przedstawienia całej partii szachów przez zbudowanie drzewa od pierwszego do ostatniego ruchu była od razu widoczna: w szachach jest średnio 36 ruchów na pozycję, a przeciętna partia trwa około 35 ruchów do rezygnacji (60-80 ruchów, jeśli gra się mat, pat lub inny remis). Istnieje 400 pozycji możliwych po pierwszym ruchu każdego gracza, około 200 000 po dwóch ruchach i prawie 120 milionów po zaledwie 3 ruchach.

Zaproponowano więc ograniczone spojrzenie w przód (wyszukiwanie) do pewnej głębokości, a następnie wykorzystanie wiedzy specyficznej dla domeny w celu oceny wynikowych pozycji terminali. Skutkiem tego byłaby swego rodzaju pozycja na środku pola, przy dobrych ruchach obu stron, a jej ocena informowałaby gracza o słuszności lub złości wybranych posunięć. Wyszukiwanie i porównywanie operacji na drzewie dobrze nadawały się do obliczeń komputerowych; reprezentacja subtelnej wiedzy szachowej w funkcji oceny nie była. Wczesne programy szachowe ucierpiały w obu obszarach: przeszukiwanie ogromnego drzewa wymagało zasobów obliczeniowych znacznie przewyższających te dostępne, a odkrycie tego, jaka wiedza szachowa była przydatna i jak ją zakodować, zajęłoby dziesięciolecia.

Twórcy systemu komputerowego do gry w szachy muszą zdecydować się na szereg zasadniczych kwestii implementacyjnych. Obejmują one:

  • Graficzny interfejs użytkownika (GUI) — w jaki sposób ruchy są wprowadzane i przekazywane użytkownikowi, w jaki sposób rejestrowana jest gra, jak ustawiane są kontrolki czasu i inne kwestie związane z interfejsem
  • Reprezentacja na tablicy – ​​jak pojedyncza pozycja jest reprezentowana w strukturach danych;
  • Techniki wyszukiwania – jak zidentyfikować możliwe ruchy i wybrać najbardziej obiecujące do dalszego zbadania;
  • Ocena liścia – jak ocenić wartość pozycji na tablicy, jeśli dalsze poszukiwania nie będą prowadzone z tej pozycji.

Adriaan de Groot przeprowadził wywiady z wieloma szachistami o różnej sile i doszedł do wniosku, że zarówno mistrzowie , jak i początkujący przyglądają się około czterdziestu do pięćdziesięciu pozycjom przed podjęciem decyzji, który ruch zagrać. Tym, co czyni tych pierwszych znacznie lepszymi graczami, jest to, że wykorzystują umiejętności rozpoznawania wzorców zbudowane na doświadczeniu. Dzięki temu mogą badać niektóre linie o wiele głębiej niż inne, po prostu nie biorąc pod uwagę ruchów, które mogą uznać za słabe. Dodatkowym dowodem na to jest sposób, w jaki dobrym ludzkim graczom znacznie łatwiej jest przywołać pozycje z prawdziwych partii szachowych, dzieląc je na niewielką liczbę rozpoznawalnych podpozycji, a nie całkowicie losowe układy tych samych figur. W przeciwieństwie do tego, słabi gracze mają ten sam poziom pamięci dla obu.

Odpowiednikiem tego w szachach komputerowych są funkcje oceny do oceny liści, które odpowiadają umiejętnościom rozpoznawania wzorców przez graczy, oraz wykorzystanie technik uczenia maszynowego do ich treningu, takich jak strojenie Texela, stochastyczne zejście gradientowe i uczenie się ze wzmocnieniem , które odpowiada budowaniu doświadczenia w ludzkich graczach. Dzięki temu nowoczesne programy mogą badać niektóre linie znacznie głębiej niż inne, używając przycinania w przód i innych selektywnych heurystyk, aby po prostu nie brać pod uwagę ruchów, które program zakłada jako słabe przez ich funkcję oceny, w taki sam sposób, jak robią to ludzie. Jedyna zasadnicza różnica między programem komputerowym a człowiekiem w tym sensie polega na tym, że program komputerowy może przeszukiwać znacznie głębiej niż człowiek, co pozwala mu przeszukiwać więcej węzłów i omijać efekt horyzontu w znacznie większym stopniu niż jest to możliwe w przypadku człowieka. gracze.

Graficzny interfejs użytkownika

Komputerowe programy szachowe zazwyczaj obsługują wiele powszechnych standardów de facto . Prawie wszystkie dzisiejsze programy potrafią odczytywać i zapisywać ruchy w grze jako Portable Game Notation (PGN) oraz mogą odczytywać i zapisywać poszczególne pozycje jako Forsyth-Edwards Notation (FEN). Starsze programy szachowe często rozumiały tylko długą notację algebraiczną , ale dzisiejsi użytkownicy oczekują, że programy szachowe będą rozumieć standardową notację algebraiczną .

Począwszy od późnych lat 90. programiści zaczęli opracowywać oddzielnie silniki (z interfejsem wiersza poleceń, który oblicza, które ruchy są najsilniejsze na danej pozycji) lub graficznym interfejsem użytkownika (GUI), który zapewnia graczowi widoczną szachownicę i pionki. które można przenieść. Silniki przekazują swoje ruchy do GUI za pomocą protokołu takiego jak Chess Engine Communication Protocol (CECP) lub Universal Chess Interface (UCI). Dzieląc programy szachowe na te dwie części, programiści mogą napisać tylko interfejs użytkownika lub tylko silnik, bez konieczności pisania obu części programu. (Zobacz także silnik szachowy .)

Deweloperzy muszą zdecydować, czy podłączyć silnik do księgi otwierającej i/lub baz tabel końcowych, czy pozostawić to GUI.

Reprezentacje Zarządu

Główny artykuł: reprezentacja zarządu (szachy)

Struktura danych używana do reprezentowania każdej pozycji w szachach jest kluczem do wykonania generowania ruchów i oceny pozycji . Metody obejmują elementy przechowywane w tablicy ("skrzynka pocztowa" i "0x88"), pozycje elementów przechowywane na liście ("lista elementów"), kolekcje zestawów bitów dla lokalizacji elementów (" tablice bitowe ") i kodowane pozycje Huffmana dla zwartych długoterminowe przechowywanie.

Techniki wyszukiwania

Komputerowe programy szachowe traktują ruchy szachowe jako drzewo gry . Teoretycznie badają wszystkie ruchy, następnie wszystkie ruchy kontrujące do tych ruchów, następnie wszystkie ruchy je kontrujące i tak dalej, gdzie każdy indywidualny ruch jednego gracza jest nazywany „ warstwą ”. Ta ocena jest kontynuowana aż do osiągnięcia określonej maksymalnej głębokości wyszukiwania lub gdy program określi, że osiągnięta została końcowa pozycja „liścia” (np. mat).

Wyszukiwanie minimaksowe

Dalsze informacje: przycinanie alfa-beta i minimax

Jednym szczególnym rodzajem algorytmu przeszukiwania używanego w szachach komputerowych są algorytmy przeszukiwania minimaksów , w których przy każdej warstwie wybierany jest „najlepszy” ruch gracza; jeden gracz stara się zmaksymalizować wynik, drugi go zminimalizować. W tym naprzemiennym procesie zostanie osiągnięty jeden konkretny węzeł końcowy, którego ocena reprezentuje poszukiwaną wartość pozycji. Jego wartość jest poparta do korzenia, a ocena ta staje się oceną pozycji w zarządzie. Ten proces wyszukiwania nazywa się minimax.

Naiwna implementacja algorytmu minimax może przeszukiwać tylko niewielką głębokość w praktycznym czasie, więc opracowano różne metody, aby znacznie przyspieszyć wyszukiwanie dobrych ruchów. Przycinanie alfa-beta , system definiowania górnych i dolnych granic możliwych wyników wyszukiwania i wyszukiwania do czasu, gdy granice się pokrywają, jest zwykle używany w celu zmniejszenia przestrzeni wyszukiwania programu.

Ponadto stosowane są również różne selektywne heurystyki wyszukiwania, takie jak wyszukiwanie w spokoju , przycinanie do przodu, rozszerzenia wyszukiwania i redukcje wyszukiwania. Te heurystyki są uruchamiane w oparciu o określone warunki w celu odrzucenia oczywiście złych ruchów (ruchów historycznych) lub zbadania interesujących węzłów (np. rozszerzenia sprawdzania, zdane pionki na siódmej randze itp.). Te selektywne heurystyki wyszukiwania muszą być jednak używane bardzo ostrożnie. Przedłużenie i program marnuje zbyt dużo czasu na szukanie nieciekawych pozycji. Jeśli zbyt wiele zostanie przyciętych lub zredukowanych, istnieje ryzyko wycięcia interesujących węzłów.

Wyszukiwanie drzew w Monte Carlo

Dalsze informacje: wyszukiwanie drzewa Monte Carlo

Przeszukiwanie drzewa Monte Carlo (MCTS) to heurystyczny algorytm wyszukiwania, który rozszerza drzewo wyszukiwania na podstawie losowego próbkowania przestrzeni wyszukiwania. Wersją wyszukiwania drzewa Monte Carlo powszechnie używaną w szachach komputerowych jest PUCT , Predictor i Upper Confidence bounds , stosowane do drzew .

AlphaZero DeepMind i Leela Chess Zero używają MCTS zamiast minimax. Takie silniki wykorzystują przetwarzanie wsadowe na procesorach graficznych w celu obliczenia ich funkcji oceny i zasad (wybór ruchu), dlatego wymagają równoległego algorytmu wyszukiwania, ponieważ obliczenia na GPU są z natury równoległe. Algorytmy przycinania minimax i alfa-beta używane w szachach komputerowych są z natury algorytmami szeregowymi, więc nie działałyby dobrze z przetwarzaniem wsadowym na GPU. Z drugiej strony MCTS jest dobrą alternatywą, ponieważ losowe próbkowanie używane w wyszukiwaniu drzewa Monte Carlo dobrze nadaje się do obliczeń równoległych i dlatego prawie wszystkie silniki obsługujące obliczenia na GPU używają MCTS zamiast alfa-beta.

Inne optymalizacje

Wiele innych optymalizacji może być wykorzystanych do wzmocnienia programów do gry w szachy. Na przykład tabele transpozycji służą do rejestrowania pozycji, które zostały wcześniej ocenione, aby zaoszczędzić na ich przeliczaniu. Tabele refutacji rejestrują kluczowe ruchy, które „odrzucają” to, co wydaje się być dobrym ruchem; są one zazwyczaj wypróbowywane najpierw w różnych pozycjach (ponieważ ruch, który obala jedną pozycję, prawdopodobnie obali inną). Wadą jest to, że tabele transpozycji przy głębokich warstwach mogą być dość duże – od dziesiątek do setek milionów wpisów. Na przykład tabela transpozycji Deep Blue IBM w 1996 roku zawierała 500 milionów wpisów. Zbyt małe tabele transpozycji mogą skutkować poświęceniem więcej czasu na wyszukiwanie nieistniejących wpisów z powodu młócenia niż czas zaoszczędzony przez znalezione wpisy. Wiele maszyn szachowych wykorzystuje rozważanie , przeszukiwanie głębszych poziomów czasu przeciwnika, podobnie jak istoty ludzkie, aby zwiększyć swoją siłę gry.

Oczywiście szybszy sprzęt i dodatkowa pamięć mogą poprawić siłę gry programu szachowego. Architektury wielowątkowe mogą nieznacznie poprawić wydajność, jeśli program działa na jednym rdzeniu lub niewielkiej liczbie rdzeni. Większość nowoczesnych programów jest zaprojektowana tak, aby wykorzystywać wiele rdzeni do równoległego wyszukiwania. Inne programy są przeznaczone do uruchamiania na komputerze ogólnego przeznaczenia i przydzielania generowania ruchu, wyszukiwania równoległego lub oceny do dedykowanych procesorów lub wyspecjalizowanych koprocesorów.

Historia

Pierwszy artykuł na temat wyszukiwania napisał Claude Shannon w 1950 roku. Przewidział dwie główne możliwe strategie wyszukiwania, które zostaną użyte, które nazwał „Typ A” i „Typ B”, zanim ktokolwiek zaprogramował komputer do gry w szachy.

Programy typu A wykorzystywałyby podejście „ brutalnej siły ”, badając każdą możliwą pozycję dla ustalonej liczby ruchów przy użyciu czysto naiwnego algorytmu minimaksowego . Shannon uważał, że byłoby to niepraktyczne z dwóch powodów.

Po pierwsze, przy około trzydziestu ruchach możliwych w typowej rzeczywistej pozycji, spodziewał się, że przeszukanie około 10 9 pozycji związanych z szukaniem trzech ruchów do przodu dla obu stron (sześć warstw ) zajmie około szesnastu minut, nawet w „bardzo optymistycznej” pozycji. przypadku, że komputer szachowy oceniał milion pozycji na sekundę. (Osiągnięcie tej prędkości zajęło około czterdziestu lat. Późniejszy algorytm wyszukiwania zwany przycinaniem alfa-beta , system definiowania górnych i dolnych granic możliwych wyników wyszukiwania i wyszukiwania do momentu, gdy granice się pokrywają, zmniejszył logarytmicznie współczynnik rozgałęzienia drzewa gry, ale nadal nie było możliwe, aby programy szachowe w tamtym czasie wykorzystywały wykładniczą eksplozję drzewa.

Po drugie, zignorował problem spokoju, próbując ocenić tylko pozycję, która jest na końcu wymiany pionów lub innej ważnej sekwencji ruchów („linii”). Spodziewał się, że dostosowanie minimaxu do radzenia sobie z tym znacznie zwiększy liczbę stanowisk, które należy zbadać, i jeszcze bardziej spowolni program. Spodziewał się, że przystosowanie typu A do radzenia sobie z tym znacznie zwiększy liczbę stanowisk, które należy zbadać, i jeszcze bardziej spowolni program.

To w naturalny sposób prowadziło do czegoś, co nazywa się „poszukiwaniem selektywnym” lub „poszukiwaniem typu B”, wykorzystującym wiedzę szachową (heurystykę), aby wybrać kilka przypuszczalnie dobrych ruchów z każdej pozycji do wyszukiwania i odciąć pozostałe bez szukania. Zamiast marnować moc obliczeniową na badanie złych lub trywialnych ruchów, Shannon zasugerował, że programy typu B będą korzystać z dwóch ulepszeń:

  1. Zatrudnij poszukiwanie spokoju .
  2. Zatrudnij przycinanie do przodu; tzn. spójrz tylko na kilka dobrych ruchów dla każdej pozycji.

Umożliwiłoby im to spojrzenie dalej ("głębiej") na najważniejsze linie w rozsądnym czasie.

Jednak wczesne próby selektywnego wyszukiwania często skutkowały przycięciem najlepszego ruchu lub ruchów. W rezultacie przez następne 25 lat, zdominowanych przez tę pierwszą iterację paradygmatu wyszukiwania selektywnego, osiągnięto niewielki lub żaden postęp. Najlepszym programem wyprodukowanym w tym wczesnym okresie był Mac Hack VI w 1967; grał na mniej więcej tym samym poziomie, co przeciętny amator (klasa C w skali rankingowej United States Chess Federation).

W międzyczasie sprzęt nadal się poprawiał, a w 1974 r. Po raz pierwszy w programie Northwestern University Chess 4.0 wdrożono wyszukiwanie siłowe. W tym podejściu przeszukiwane są wszystkie alternatywne ruchy w węźle i żaden z nich nie jest przycinany. Odkryli, że czas potrzebny na proste przeszukanie wszystkich ruchów był znacznie krótszy niż czas potrzebny na zastosowanie opartej na wiedzy heurystyki w celu wybrania tylko kilku z nich, a korzyść z tego, że nie przedwcześnie lub nieumyślnie nie przycinała dobrych ruchów, skutkowała znacznie lepszą wydajnością. .

W latach 80. i 90. dokonano ostatecznie postępu w paradygmacie wyszukiwania selektywnego, wraz z rozwojem wyszukiwania w spokoju , przycinania ruchu zerowego i innych nowoczesnych heurystyk wyszukiwania selektywnego. Te heurystyki zawierały znacznie mniej błędów niż wcześniejsze heurystyki i uznano, że są warte zaoszczędzonego dodatkowego czasu, ponieważ mogą wyszukiwać głębiej i powszechnie stosowane przez wiele wyszukiwarek. Podczas gdy wiele nowoczesnych programów używa wyszukiwania alfa-beta jako podłoża dla swojego algorytmu wyszukiwania, te dodatkowe selektywne heurystyki wyszukiwania stosowane w nowoczesnych programach oznaczają, że program nie wykonuje już wyszukiwania „brute force”. Zamiast tego w dużym stopniu polegają na tych selektywnych heurystykach wyszukiwania, aby wydłużyć wiersze, które program uważa za dobre i przyciąć, oraz zmniejszyć wiersze, które program uważa za złe, do punktu, w którym większość węzłów w drzewie wyszukiwania jest usuwana, umożliwiając nowoczesnym programom bardzo głębokie wyszukiwanie.

W 2006 r. Rémi Coulom stworzył wyszukiwanie drzewa Monte Carlo , inny rodzaj wyszukiwania selektywnego typu B. W 2007 roku Levente Kocsis i Csaba Szepesvári stworzyli adaptację wyszukiwania drzewa Monte Carlo o nazwie Upper Confidence bounds (Ograniczenia górnej granicy zaufania stosowane do drzew lub w skrócie UCT). W 2011 r. Chris Rosin opracował odmianę UCT o nazwie Predictor + Upper Confidence bounds w odniesieniu do drzew, w skrócie PUCT. PUCT został następnie użyty w AlphaZero w 2017 roku, a później w Leela Chess Zero w 2018 roku.

Wiedza a wyszukiwanie (szybkość procesora)

W latach 70. większość programów szachowych działała na superkomputerach, takich jak Control Data Cyber ​​176s lub Cray-1s, co wskazuje, że w tym okresie rozwoju szachów komputerowych moc obliczeniowa była czynnikiem ograniczającym wydajność. Większość programów szachowych zmagała się z wyszukiwaniem do głębokości większej niż 3 warstwy. Dopiero sprzętowe maszyny szachowe z lat 80. ujawniły związek między szybkością procesora a wiedzą zakodowaną w funkcji oceny.

Szacuje się, że podwojenie szybkości komputera zwiększa siłę gry o około pięćdziesiąt do siedemdziesięciu punktów Elo ( Levy i Newborn 1991 :192).

Ocena liści

Główny artykuł: Funkcja oceny

W przypadku większości pozycji szachowych komputery nie mogą przewidywać wszystkich możliwych pozycji końcowych. Zamiast tego muszą spojrzeć w przyszłość na kilka warstw i porównać możliwe pozycje, zwane liśćmi. Algorytm oceniający liście jest nazywany „ funkcją oceny ”, a algorytmy te często znacznie różnią się między różnymi programami szachowymi. Funkcje oceniające zazwyczaj oceniają pozycje w setnych częściach pionka (tzw. centipona), gdzie zgodnie z konwencją pozytywna ocena faworyzuje białych, a negatywna faworyzuje czarnych. Jednak niektóre funkcje oceny wyświetlają procenty wygranych/remisów/strat zamiast centipionów.

Historycznie, ręczne funkcje oceny uwzględniają wartość materiału wraz z innymi czynnikami wpływającymi na siłę każdej ze stron. Licząc materiał z każdej strony, typowe wartości dla bierek to 1 punkt za pionka , 3 punkty za skoczka lub gońca , 5 punktów za wieżę i 9 punktów za hetmana . (Zob . Względna wartość bierek szachowych .) Król czasami otrzymuje arbitralnie wysoką wartość, taką jak 200 punktów ( artykuł Shannona ), aby upewnić się, że mat przeważa nad wszystkimi innymi czynnikami ( Levy i Newborn 1991 :45). Oprócz punktów za bierki, większość ręcznych funkcji oceny bierze pod uwagę wiele czynników, takich jak struktura pionków, fakt, że para gońców jest zwykle warta więcej, scentralizowane bierki są warte więcej i tak dalej. Zwykle bierze się pod uwagę ochronę króli, a także fazę gry (otwarcie, środek lub końcówkę). Techniki uczenia maszynowego , takie jak toczenie Texel, stochastyczne opadanie gradientu lub uczenie ze wzmacnianiem, są zwykle używane do optymalizacji ręcznych funkcji oceny.

Większość nowoczesnych funkcji oceny wykorzystuje sieci neuronowe . Najpopularniejszą obecnie używaną funkcją oceny jest wydajnie aktualizowana sieć neuronowa , która jest płytką siecią neuronową, której dane wejściowe są tablicami kwadratów . Tabele pionowo-kwadratowe to zestaw 64 wartości odpowiadających kwadratom szachownicy, a dla każdego pionu i koloru zazwyczaj istnieje tabela pionowo-kwadratowa, co daje 12 tabel pionowo-kwadratowych, a tym samym 768 danych wejściowych do sieci neuronowej. Ponadto niektóre silniki wykorzystują głębokie sieci neuronowe w swojej funkcji oceny. Sieci neuronowe są zwykle szkolone przy użyciu algorytmu uczenia ze wzmocnieniem w połączeniu z uczeniem nadzorowanym lub uczeniem nienadzorowanym .

Wynikiem funkcji oceny jest pojedynczy skalar, skwantowany w centiponach lub innych jednostkach, który w przypadku ręcznie wykonanych funkcji oceny jest sumą ważoną różnych opisanych czynników, lub w przypadku funkcji oceny opartych na sieciach neuronowych wyjście głowicy sieci neuronowej. Ocena przypuszczalnie reprezentuje lub przybliża wartość poddrzewa poniżej ocenianego węzła, tak jakby było przeszukiwane do końca, tj. do końca gry. Podczas wyszukiwania ocena jest porównywana z ocenami innych liści, eliminując węzły, które reprezentują złe lub słabe ruchy dla obu stron, aby uzyskać węzeł, który przez zbieżność reprezentuje wartość pozycji z najlepszą grą obu stron.

Podstawy do gry końcowej

Główny artykuł: Baza tabeli Endgame

Rozgrywka końcowa od dawna była jedną z największych słabości programów szachowych ze względu na wymaganą głębię poszukiwań. Niektóre programy na poziomie mistrzowskim nie były w stanie wygrać na pozycjach, na których nawet średnio zaawansowani gracze mogli wymusić zwycięstwo.

Aby rozwiązać ten problem, komputery zostały użyte do kompletnej analizy niektórych pozycji końcowych w szachach , zaczynając od króla i pionka przeciwko królowi. Takie bazy tabel końcowych są generowane z wyprzedzeniem przy użyciu formy analizy wstecznej , zaczynając od pozycji, w których znany jest wynik końcowy (np. gdzie jedna strona została sparowana) i sprawdzając, które inne pozycje są o jeden ruch od nich, a które są o jeden ruch. od nich itp. Ken Thompson był pionierem w tej dziedzinie.

Wyniki analizy komputerowej czasami zaskakiwały ludzi. W 1977 roku maszyna do gry w szachy Thompsona Belle wykorzystała bazę tabeli końcowej dla króla i wieży przeciwko królowi i damie i była w stanie wylosować to teoretycznie przegrane zakończenie przeciwko kilku mistrzom (patrz pozycja Philidora #Królowa kontra wieża ). Stało się tak pomimo niestosowania zwykłej strategii opóźniania porażki poprzez trzymanie broniącego króla i wieży blisko siebie tak długo, jak to możliwe. Poproszony o wyjaśnienie przyczyn niektórych ruchów programu, Thompson nie był w stanie tego zrobić, poza stwierdzeniem, że baza danych programu po prostu zwróciła najlepsze ruchy.

Większość arcymistrzów odmówiła gry przeciwko komputerowi w końcówce hetmana z wieżą, ale Walter Browne przyjął wyzwanie. Ustawiono pozycję hetman kontra wieża, w której hetman może wygrać w trzydziestu ruchach, z perfekcyjną grą. Browne miał 2½ godziny na zagranie pięćdziesięciu ruchów, w przeciwnym razie remis zostałby zgłoszony zgodnie z regułą pięćdziesięciu ruchów . Po czterdziestu pięciu ruchach Browne zgodził się na remis, nie mogąc wymusić mata ani wygrać wieży w ciągu następnych pięciu ruchów. Na końcowej pozycji Browne miał jeszcze siedemnaście ruchów do mata, ale nie tak daleko do wygrania wieży. Browne studiował grę końcową i tydzień później ponownie grał na komputerze w innej pozycji, w której hetman może wygrać w trzydziestu ruchach. Tym razem zdobył wieżę w pięćdziesiątym ruchu, co dało mu zwycięską pozycję ( Levy & Newborn 1991 : 144-48), ( Nunn 2002 : 49).

Inne pozycje, od dawna uważane za wygrane, okazały się wykonywać więcej ruchów przeciwko doskonałej grze, aby rzeczywiście wygrać, niż pozwalała na to zasada pięćdziesięciu ruchów szachów. W konsekwencji przez kilka lat zmieniano oficjalne zasady gry w szachy FIDE, aby zwiększyć liczbę ruchów dozwolonych w tych zakończeniach. Po pewnym czasie reguła wróciła do pięćdziesięciu ruchów we wszystkich pozycjach – takich pozycji odkryto więcej, co jeszcze bardziej komplikowało regułę, a w grze ludzi nie miało to żadnego znaczenia, ponieważ nie potrafili idealnie zagrać pozycji.

Z biegiem lat zostały wydane inne formaty baz danych końcówek, w tym Edward Tablebase, De Koning Database i Nalimov Tablebase, które są używane przez wiele programów szachowych, takich jak Rybka , Shredder i Fritz . Dostępne są podstawy stołów dla wszystkich pozycji z sześcioma częściami. Niektóre siedmioczęściowe partie końcowe zostały przeanalizowane przez Marca Bourzutschky'ego i Yakova Konovala. Programiści korzystający z superkomputerów Łomonosowa w Moskwie skompletowali tabelę szachów dla wszystkich partii końcowych z siedmioma pionami lub mniej (wykluczone są trywialne pozycje końcowe, takie jak sześć białych pionów w porównaniu z samotnym czarnym królem ). We wszystkich tych bazach danych dotyczących końcówek zakłada się, że roszada nie jest już możliwa.

Wiele tabel nie uwzględnia zasady pięćdziesięciu ruchów, zgodnie z którą gra, w której przechodzi pięćdziesiąt ruchów bez bicia lub ruchu pionkiem, może być uznana przez któregokolwiek z graczy za remis. Powoduje to, że podstawa tabeli zwraca wyniki, takie jak „Mat wymuszony w sześćdziesięciu sześciu ruchach” w niektórych pozycjach, które w rzeczywistości zostałyby wylosowane z powodu zasady pięćdziesięciu ruchów. Jednym z powodów jest to, że gdyby raz jeszcze zmienić reguły gry w szachy, dając więcej czasu na zdobycie takich pozycji, nie będzie konieczne ponowne generowanie wszystkich tabel. Program korzystający z baz tabel jest również bardzo łatwy do zauważenia i uwzględnienia tej „funkcji”, a w każdym przypadku, jeśli użyje bazy tabeli końcowej, wybierze ruch, który prowadzi do najszybszej wygranej (nawet jeśli byłby faulowany z pięćdziesiątki -przesuń regułę z doskonałą grą). Jeśli grasz z przeciwnikiem nie korzystającym z podstawy stołu, taki wybór da duże szanse na wygraną w ciągu pięćdziesięciu ruchów.

Bazy tabel Nalimov, które wykorzystują najnowocześniejsze techniki kompresji , wymagają 7,05 GB miejsca na dysku twardym dla wszystkich pięcioczęściowych zakończeń. Do pokrycia wszystkich sześcioczęściowych zakończeń potrzeba około 1,2 TB . Szacuje się, że siedmioczęściowa podstawa stołu wymaga od 50 do 200 TB przestrzeni dyskowej.

Bazy danych o końcówkach gry pojawiły się na pierwszym miejscu w 1999 roku, kiedy Kasparow rozegrał w Internecie mecz pokazowy z resztą świata . Osiągnięto siedmioczęściową partię hetmana i pionka , a drużyna świata walczyła o uratowanie remisu. Eugene Nalimov pomógł, generując sześcioelementową bazę tabeli końcówek, w której obie strony miały dwie damy, co było intensywnie wykorzystywane do wspomagania analizy przez obie strony.

Otwieranie książki

Silniki szachowe, podobnie jak ludzie, mogą skrócić czas przetwarzania, a także wybrać mocne warianty, jak wyjaśniają mistrzowie, odwołując się do księgi otwierającej przechowywanej w bazie danych na dysku. Książki otwierające obejmują początkowe ruchy gry na zmienną głębokość, w zależności od otwarcia i odmiany, ale zwykle do pierwszych 10-12 ruchów (20-24 warstw). Ponieważ otwarcia były dogłębnie badane przez mistrzów od wieków, a niektóre znane są z tego, że dobrze znają się na grze środkowej, oceny poszczególnych wariacji przez mistrzów będą zwykle lepsze od ogólnej heurystyki programu.

Podczas gdy kiedyś granie ruchu poza książką w celu umieszczenia programu szachowego na własnych zasobach mogło być skuteczną strategią, ponieważ książki otwierające szachy były selektywne w stosunku do stylu gry programu, a programy miały zauważalne słabości w stosunku do ludzi , to już dziś nie jest prawdą. Księgi otwierające przechowywane w komputerowych bazach danych są najprawdopodobniej znacznie bardziej rozbudowane niż nawet najlepiej przygotowani ludzie, a zagranie wczesnego ruchu poza książką może spowodować, że komputer znajdzie w swojej księdze nietypowy ruch i obarczy przeciwnika ostrą wadą . Nawet jeśli tak nie jest, granie poza zakładem może być znacznie lepsze dla taktycznie ostrych programów szachowych niż dla ludzi, którzy muszą odkrywać silne ruchy w nieznanej odmianie nad szachownicą.

Listy rankingowe szachów komputerowych

Zobacz także: Silnik szachowy § Oceny

CEGT , CSS, SSDF , WBEC, REBEL , FGRL i IPON utrzymują listy ocen pozwalające fanom porównywać moc silników. Różne wersje Stockfish , Komodo , Leela Chess Zero i Fat Fritz zdominowały listy rankingowe na początku lat 20. XX wieku.

CCRL (Computer Chess Rating Lists) to organizacja, która testuje siłę silników szachów komputerowych , grając programy przeciwko sobie. CCRL została założona w 2006 roku, aby promować konkurencję komputer-komputer i umieszczać wyniki na liście rankingowej.

Organizacja prowadzi trzy różne listy: 40/40 (40 minut na każde 40 zagranych ruchów), 40/4 (4 minuty na każde 40 zagranych ruchów) i 40/4 FRC (ta sama kontrola czasu, ale Chess960). Rozważanie (lub permanentny mózg ) jest wyłączone, a taktowanie jest dostosowywane do procesora AMD64 X2 4600+ (2,4 GHz) przy użyciu Crafty 19.17 BH jako benchmarku. Ogólne, neutralne księgi otwierające są używane (w przeciwieństwie do własnej księgi silnika) do limitu 12 ruchów w grze wraz z 4 lub 5 osobowymi podstawami stołów .

Historia

Era sprzed komputera

Idea stworzenia maszyny do gry w szachy sięga XVIII wieku. Około 1769 roku automat szachowy o nazwie Turek , stworzony przez węgierskiego wynalazcę Farkasa Kempelena , stał się sławny, zanim został zdemaskowany jako mistyfikacja. Przed rozwojem komputerów cyfrowych poważne próby oparte na automatach, takich jak El Ajedrecista z 1912 roku, w których grał król i wieża kontra król, były zbyt skomplikowane i ograniczone, aby mogły być przydatne do rozgrywania pełnych partii szachów. Dziedzina mechanicznych badań szachowych słabła aż do pojawienia się komputera cyfrowego w latach 50. XX wieku.

Wczesna era oprogramowania: wyszukiwanie selektywne

Od tego czasu entuzjaści szachów i inżynierowie komputerowi z coraz większą powagą i sukcesem budowali maszyny do gry w szachy i programy komputerowe. Jednym z nielicznych arcymistrzów szachowych, którzy poświęcili się poważnie szachom komputerowym, był były mistrz świata w szachach Michaił Botwinnik , który napisał kilka prac na ten temat. Posiadał również doktorat z elektrotechniki. Pracując ze stosunkowo prymitywnym sprzętem dostępnym w Związku Radzieckim na początku lat sześćdziesiątych, Botwinnik nie miał innego wyboru, jak zbadać techniki wyboru ruchu oprogramowania; w tamtym czasie tylko najpotężniejsze komputery mogły osiągnąć znacznie więcej niż trzywarstwowe wyszukiwanie o pełnej szerokości, a Botvinnik nie miał takich maszyn. W 1965 Botwinnik był konsultantem zespołu ITEP w komputerowym meczu szachów amerykańsko-sowieckich (patrz Kotok-McCarthy ).

Późniejsza era oprogramowania: wyszukiwanie w pełnej szerokości

Jeden kamień milowy w rozwoju miał miejsce, gdy zespół z Northwestern University , który był odpowiedzialny za serię programów Szachowych i wygrał pierwsze trzy Mistrzostwa Komputerowych Szachów ACM (1970-72), porzucił wyszukiwanie typu B w 1973 roku. tegoroczne mistrzostwa i ich następcy zajęli drugie miejsce zarówno w Mistrzostwach ACM 1974, jak i inauguracyjnych Mistrzostwach Świata w Szachach Komputerowych , zanim ponownie wygrali Mistrzostwa ACM w 1975, 1976 i 1977. Implementacja typu A okazała się równie szybko: w czasie, jaki zabierało podjęcie decyzji, które ruchy zasługują na przeszukanie, można było po prostu przeszukać je wszystkie. W rzeczywistości Chess 4.0 ustanowił paradygmat, który był i nadal jest przestrzegany przez wszystkie współczesne programy szachowe.

Powstanie maszyn szachowych

W 1978 roku, wczesna wersja sprzętowej maszyny do gry w szachy Kena Thompsona Belle , weszła i wygrała Mistrzostwa Ameryki Północnej w Szachach Komputerowych nad dominującym Northwestern University Chess 4.7.

Rewolucja mikrokomputerowa

Postęp technologiczny o rzędy wielkości w zakresie mocy obliczeniowej sprawił, że podejście brutalnej siły stało się o wiele bardziej zdecydowane niż miało to miejsce we wczesnych latach. W rezultacie bardzo solidny, taktyczny gracz AI wspomagany pewną ograniczoną wiedzą pozycyjną wbudowaną w funkcję oceny i zasady przycinania/rozszerzania zaczął dorównywać najlepszym graczom na świecie. Okazało się, że przynajmniej w szachach osiąga się znakomite rezultaty, pozwalając komputerom robić to, co potrafią najlepiej (kalkulować), zamiast nakłaniać je do naśladowania ludzkich procesów myślowych i wiedzy. W 1997 Deep Blue , brutalna maszyna zdolna do badania 500 milionów węzłów na sekundę, pokonał mistrza świata Garry'ego Kasparowa, co oznacza, że ​​komputer po raz pierwszy pokonał panującego mistrza świata w szachowej kontroli czasu.

Szachy nadludzkie

W 2016 roku NPR poprosił ekspertów o scharakteryzowanie stylu gry silników komputerowych. Murray Campbell z IBM stwierdził, że „Komputery nie mają żadnego poczucia estetyki… Grają to, co uważają za obiektywnie najlepszy ruch na dowolnej pozycji, nawet jeśli wygląda to absurdalnie, i mogą zagrać każdy ruch, bez względu na to, jak brzydki jest." Arcymistrzowie Andrew Soltis i Susan Polgar stwierdzili, że komputery są bardziej skłonne do wycofania się niż ludzie.

Rewolucja w sieciach neuronowych

Podczas gdy sieci neuronowe były używane w funkcjach oceny silników szachowych od późnych lat 80-tych, z programami takimi jak NeuroChess, Morph, Blondie25, Giraffe, AlphaZero i MuZero , sieci neuronowe nie zostały powszechnie przyjęte przez silniki szachowe, aż do pojawienia się wydajnie aktualizowalne sieci neuronowe latem 2020 r. Wydajnie aktualizowalne sieci neuronowe zostały pierwotnie opracowane w shogi komputerowych w 2018 r. przez Yu Nasu i musiały zostać najpierw przeniesione do pochodnej Sztokfisza o nazwie Sztokfisz NNUE 31 maja 2020 r. i zintegrowane z oficjalnym Sztokfiszem silnik 6 sierpnia 2020 r., zanim inni programiści szachowi zaczęli adoptować sieci neuronowe w swoich silnikach.

Niektórzy ludzie, tacy jak Venki Ramakrishnan z Royal Society , uważają, że AlphaZero doprowadziło do powszechnego przyjęcia sieci neuronowych w silnikach szachowych. Jednak AlphaZero wpłynęło na to, że bardzo niewiele silników zaczęło używać sieci neuronowych, a były to zwykle nowe eksperymentalne silniki, takie jak Leela Chess Zero , które zaczęły specjalnie replikować artykuł AlphaZero. Głębokie sieci neuronowe używane w funkcji oceny AlphaZero wymagały drogich procesorów graficznych , które nie były kompatybilne z istniejącymi silnikami szachowymi. Zdecydowana większość silników szachowych korzysta tylko z centralnych jednostek obliczeniowych, a obliczanie i przetwarzanie informacji na procesorach graficznych wymaga specjalnych bibliotek w backendzie, takich jak CUDA Nvidii , do których żaden z silników nie miał dostępu. Tak więc zdecydowana większość silników szachowych, takich jak Komodo i Stockfish , nadal wykorzystywała ręcznie wykonane funkcje oceny, aż do momentu , gdy w 2020 r. wydajnie aktualizowalne sieci neuronowe zostały przeniesione do szachów komputerowych, co w ogóle nie wymagało użycia procesorów graficznych ani bibliotek, takich jak CUDA. Nawet wtedy sieci neuronowe używane w szachach komputerowych są dość płytkie, a metody uczenia się przez głębokie wzmocnienie zapoczątkowane przez AlphaZero są nadal niezwykle rzadkie w szachach komputerowych.

Oś czasu

  • 1769 – Wolfgang von Kempelen buduje Turka . Przedstawiony jako automat do gry w szachy, jest potajemnie obsługiwany przez człowieka ukrytego w maszynie.
  • 1868 – Charles Hooper przedstawia automat Ajeeb – w którym ukryty jest również ludzki szachista.
  • 1912 – Leonardo Torres y Quevedo buduje El Ajedrecista , maszynę, która może grać w końcowe partie króla i wieży z królem .
  • 1941 – Poprzedzając porównywalne prace o co najmniej dekadę, Konrad Zuse rozwija komputerowe algorytmy szachowe w swoim formalizmie programowania Plankalkül . Ze względu na okoliczności II wojny światowej nie zostały one jednak opublikowane i wyszły na jaw dopiero w latach 70. XX wieku.
  • 1948 – Książka Norberta Wienera Cybernetics opisuje, w jaki sposób program szachowy może być opracowany przy użyciu wyszukiwania minimaksowego o ograniczonej głębokości z funkcją oceny .
  • 1950 – Claude Shannon publikuje „Programowanie komputera do gry w szachy”, jeden z pierwszych artykułów na temat algorytmicznych metod gry w szachy komputerowe.
  • 1951 – Alan Turing jako pierwszy publikuje program opracowany na papierze, który umożliwiał rozegranie pełnej partii szachów (nazywany Turochamp ).
  • 1952 – Dietrich Prinz opracowuje program, który rozwiązuje problemy szachowe.
a b c d mi f
6 a6 czarna wieża b6 czarny rycerz c6 czarna królowa d6 czarny król e6 czarny rycerz f6 czarna wieża 6
5 czarny pionek a5 czarny pionek b5 czarny pionek c5 czarny pionek d5 e5 czarny pionek czarny pionek f5 5
4 a4 b4 c4 d4 e 4 f4 4
3 a3 b3 c3 d3 e3 f3 3
2 biały pionek a2 b2 biały pionek c2 biały pionek d2 biały pionek e2 biały pionek f2 biały pionek 2
1 a1 biała wieża b1 biały rycerz c1 biała królowa d1 biały król e1 biały rycerz f1 biała wieża 1
a b c d mi f
Szachy Los Alamos . W tę uproszczoną wersję szachów grał w 1956 rokukomputer MANIAC I.
  • 1956 – Los Alamos chess to pierwszy program do gry w szachy, opracowany przez Paula Steina i Marka Wellsa na komputer MANIAC I.
  • 1956 – John McCarthy opracowuje algorytm wyszukiwania alfa-beta .
  • 1957 – Powstają pierwsze programy, które mogą grać w pełną partię szachów, jeden przez Alexa Bernsteina i jeden przez rosyjskich programistów używających BESM .
  • 1958 – NSS staje się pierwszym programem szachowym wykorzystującym algorytm wyszukiwania alfa-beta.
  • 1962 – Na MIT zostaje opublikowany pierwszy wiarygodny program, Kotok-McCarthy .
  • 1963 – Arcymistrz David Bronstein pokonuje M-20 prowadząc wczesny program szachowy.
  • 1966-67 – Rozgrywany jest pierwszy mecz szachowy pomiędzy programami komputerowymi. Moskiewski Instytut Fizyki Teoretycznej i Doświadczalnej (ITEP) pokonał Kotok-McCarthy na Uniwersytecie Stanforda telegraficznie w ciągu dziewięciu miesięcy.
  • 1967 – Mac Hack VI , Richard Greenblatt i in. wprowadza tabele transpozycji i wykorzystuje dziesiątki starannie dostrojonych heurystyk wyboru ruchów; staje się pierwszym programem, który pokonuje osobę w grze turniejowej. Mac Hack VI grał na poziomie klasy C.
  • 1968 – szkocki mistrz szachowy David Levy stawia 500 funtów z pionierami sztucznej inteligencji Johnem McCarthy i Donaldem Michie , że żaden program komputerowy nie wygra z nim meczu szachowego w ciągu 10 lat.
  • 1970 – Monty Newborn i Association for Computing Machinery organizują pierwsze Mistrzostwa Ameryki Północnej w Szachach Komputerowych w Nowym Jorku.
  • 1971 – Ken Thompson , amerykański informatyk z Bell Labs i twórca systemu operacyjnego Unix, pisze swój pierwszy program do gry w szachy o nazwie „chess” dla najwcześniejszej wersji Uniksa .
  • 1974 – David Levy , Ben Mittman i Monty Newborn organizują pierwsze mistrzostwa świata w szachach komputerowych, które wygrywa rosyjski program Kaissa .
  • 1975 – Po prawie dekadzie jedynie marginalnego postępu od szczytowego wyniku gry Greenblatt MacHack VI w 1967 roku, wprowadza się grę Northwestern University Chess 4.5 z wyszukiwaniem na całej szerokości oraz innowacjami bitboardów i iteracyjnym pogłębianiem. Przywrócono również tabelę transpozycji, którą po raz pierwszy pokazano w programie Greenblatta. Był to zatem pierwszy program o zintegrowanej nowoczesnej strukturze i stał się wzorem dla całego przyszłego rozwoju. Chess 4.5 zagrało silną klasę B i wygrało trzecie mistrzostwa świata w szachach komputerowych w następnym roku. Szachy Uniwersytetu Northwestern i jego potomkowie dominowali w szachach komputerowych aż do ery sprzętowych maszyn szachowych we wczesnych latach 80-tych.
  • 1976 – W grudniu kanadyjski programista Peter R. Jennings wypuszcza Microchess , pierwszą sprzedawaną grę na mikrokomputery.
Wydany w 1977 roku Boris był jednym z pierwszych komputerów szachowych, które znalazły się na szerokim rynku. Działał na 8-bitowym mikroprocesorze Fairchild F8 z zaledwie 2,5 KiB ROM i 256 bajtami RAM.
  • 1977 – W marcu Fidelity Electronics wypuszcza na rynek Chess Challenger , pierwszy dedykowany komputer szachowy do sprzedaży. Międzynarodowe Stowarzyszenie Szachów Komputerowych zostało założone przez programistów szachowych w celu organizowania mistrzostw w szachach komputerowych i informowania w swoim czasopiśmie o badaniach i postępach w szachach komputerowych. Również w tym samym roku firma Applied Concepts wydała Boris , dedykowany komputer szachowy w drewnianym pudełku z plastikowymi figurami i składaną deską.
  • 1978 – David Levy wygrywa zakład postawiony 10 lat wcześniej, pokonując Chess 4.7 w sześciomeczowym meczu z wynikiem 4½-1½. Zwycięstwo komputera w czwartej grze to pierwsza porażka mistrza człowieka w turnieju.
  • 1979 – Frederic Friedel organizuje mecz pomiędzy IM Davidem Levy i Chess 4.8 , który jest transmitowany w niemieckiej telewizji. Levy and Chess 4.8, działający na CDC Cyber ​​176, najpotężniejszym komputerze na świecie, walczyli z wyczerpującym remisem 89 ruchów.
  • 1980 – Komputery Fidelity wygrywają co roku Mistrzostwa Świata Mikrokomputerów w latach 1980-1984. W Niemczech Hegener & Glaser wypuszczają swój pierwszy dedykowany komputer szachowy Mephisto . USCF zabrania komputerom konkurowania w turniejach z ludźmi, z wyjątkiem sytuacji, gdy są reprezentowane przez twórców systemów szachowych. Ustanowiona zostaje Nagroda Fredkina, oferująca 100 000 dolarów twórcy pierwszej maszyny szachowej, która pokona mistrza świata w szachach.
  • 1981 – Cray Blitz wygrywa mistrzostwa stanu Mississippi z doskonałym wynikiem 5-0 i wynikiem 2258. W rundzie 4 pokonuje Joe Sentefa (2262), zostając pierwszym komputerem, który pokonał mistrza w grze turniejowej i pierwszym komputerem, który uzyskać ocenę mistrzowską.
  • 1984 – Linia dedykowanych komputerów szachowych niemieckiej firmy Hegener & Glaser Mephisto rozpoczyna długą passę zwycięstw (1984-1990) w Mistrzostwach Świata Mikrokomputerów przy użyciu dedykowanych komputerów z programami ChessGenius i Rebel .
  • 1986 – Software Country (patrz Software Toolworks ) wypuszcza Chessmaster 2000 oparty na silniku Davida Kittingera, pierwszą edycję tego, co miało stać się najlepiej sprzedającą się na świecie linią programów szachowych.
  • 1987 – Frederic Friedel i fizyk Matthias Wüllenweber zakładają Chessbase , wypuszczając pierwszy program do obsługi szachowej bazy danych. Stuart Cracraft wypuszcza GNU Chess , jeden z pierwszych „ silników szachowych ”, który będzie dołączany do osobnego graficznego interfejsu użytkownika (GUI), chesstool.
  • 1988 – HiTech , opracowany przez Hansa Berlinera i Carla Ebelinga , wygrywa mecz z arcymistrzem Arnoldem Denkerem 3½–½. Deep Thought dzieli pierwsze miejsce z Tonym Milesem w mistrzostwach Software Toolworks, wyprzedzając byłego mistrza świata Michaiła Tala i kilku arcymistrzów, w tym Samuela Reshevsky'ego , Waltera Browne'a i Michaiła Gurevicha . Pokonuje również arcymistrza Benta Larsena , czyniąc go pierwszym komputerem, który pokonał GM w turnieju. Jego ocena za występ w tym turnieju wynosząca 2745 (w skali USCF) była najwyższa uzyskana przez gracza komputerowego.
  • 1989 – Deep Thought niszczy Davida Levy'ego w 4-meczowym meczu 0-4, kończąc jego słynną serię zakładów, która rozpoczęła się w 1968 roku.
  • 1990 – 25 kwietnia były mistrz świata Anatolij Karpow przegrał symulację z komputerem szachowym Mephisto Portorose M68030 firmy Hegener & Glaser.
  • 1991 – ChessMachine na podstawie Rebel Eda Schrödera wygrywa Mistrzostwa Świata w Szachach Mikrokomputerowych
  • 1992 – ChessMachine wygrywa 7. Mistrzostwa Świata w Szachach Komputerowych , po raz pierwszy mikrokomputer pokonał komputery mainframe . GM John Nunn wydaje Secrets of Rook Endings , pierwszą książkę opartą na bazach tabelek końcowych, stworzoną przez Kena Thompsona .
  • 1993 – Deep Thought-2 przegrywa czteromeczowy mecz z Bentem Larsenem . Programy szachowe działające na komputerach osobistych przewyższają dedykowane komputery szachowe Mephisto, aby wygrać mistrzostwa mikrokomputerowe, oznaczając przejście od dedykowanego sprzętu szachowego do oprogramowania na wielofunkcyjnych komputerach osobistych.
  • 1995 – Fritz 3 , działający na komputerze Pentium 90 MHz, pokonuje maszynę do gry w szachy Deep Thought-2 i programy działające na kilku superkomputerach, aby wygrać 8. Mistrzostwa Świata w Szachach Komputerowych w Hongkongu. To pierwszy raz, kiedy program szachowy działający na zwykłym sprzęcie pokonuje wyspecjalizowane maszyny szachowe i masywne superkomputery, co wskazuje na przesunięcie nacisku z brutalnej mocy obliczeniowej na usprawnienia algorytmiczne w ewolucji silników szachowych.
  • 1996 – IBM Deep Blue przegrywa sześciomeczowy mecz z Garrym Kasparowem , 2:4.
  • 1997 – Deep(er) Blue , wysoce zmodyfikowana wersja oryginału, wygrywa sześciomeczowy mecz z Garrym Kasparowem , 3,5-2,5.
  • 2000 – Stefan Meyer-Kahlen i Rudolf Huber opracowali Universal Chess Interface , protokół GUI do komunikacji z silnikami, który stopniowo stał się główną formą, jaką przybierałyby nowe silniki.
  • 2002 – Vladimir Kramnik remisuje ośmiomeczowy mecz z Deep Fritzem .
  • 2003 – Kasparow remisuje sześciomeczowy mecz z Deep Junior i remisuje czteromeczowy mecz z X3D Fritz .
  • 2004 – zespół komputerów ( Hydra , Deep Junior i Fritz ) wygrywa 8½–3½ przeciwko silnej ludzkiej drużynie utworzonej przez Veselina Topałowa , Ruslana Ponomariova i Sergeya Karjakina , których średnia ocena Elo wynosi 2681. Fabien Letouzey publikuje kod źródłowy dla Fruit 2.1, silnik dość konkurencyjny w stosunku do najlepszych w tamtych czasach silników o zamkniętym kodzie źródłowym. Skłania to wielu autorów do zrewidowania swojego kodu, włączając nowe idee.
  • 2005 – Rybka wygrywa turniej IPCCC i bardzo szybko staje się najsilniejszą lokomotywą.
  • 2006 – Mistrz świata Vladimir Kramnik zostaje pokonany 4:2 przez Deep Fritz .
  • 2009 – Kieszonkowy Fritz . 4 działa na smartfonie, wygrywa Copa Mercosur, międzynarodowy turniej na poziomie mistrzowskim, zdobywając 9½/10 punktów i uzyskując ocenę wydajności 2900. Grupa pseudonimowych rosyjskich programistów udostępnia kod źródłowy Ippolit, silnika pozornie silniejszego niż Rybka . Staje się to podstawą silników Robbolito i Ivanhoe, a wielu autorów silników przyjmuje z tego pomysły.
  • 2010 – Przed Mistrzostwami Świata w Szachach 2010 Topałow przygotowuje się do walki z superkomputerem Blue Gene z 8192 procesorami zdolnymi do wykonywania 500 bilionów (5 × 10 14 ) operacji zmiennoprzecinkowych na sekundę. Deweloper Rybki, Vasik Rajlich , oskarża Ippolita o bycie klonem Rybki.
  • 2011 – ICGA odbiera Rybce tytuły WCCC.
  • 2017 – AlphaZero , neuronowy automat cyfrowy oparty na sieci, pokonuje Sztokfisza 28-0 z 72 remisami w 100 meczach.
  • 2018 - Wydajnie aktualizowalna ocena sieci neuronowej (NNUE) została wynaleziona dla shogi komputerowego .
  • 2019 – Leela Chess Zero (LCZero v0.21.1-nT40.T8.610), silnik szachowy oparty na AlphaZero, pokonuje Stockfisha 19050918 w 100-meczowym meczu z wynikiem 53,5 do 46,5 i wygrywa sezon 15 TCEC .
  • 2020 - NNUE zostaje dodany do oceny sztokfisza , zauważalnie zwiększając jego siłę.

Kategoryzacje

Dedykowany sprzęt

Te systemy do gry w szachy zawierają niestandardowy sprzęt z około. daty wprowadzenia (z wyłączeniem dedykowanych mikrokomputerów):

Komercyjne komputery dedykowane

Boris Diplomat (1979) podróżny komputer szachowy
Fidelity Voice Chess Challenger (1979), pierwszy mówiący komputer szachowy
Wyjście mowy z Voice Chess Challenger
Milton Bradley Grandmaster (1983), pierwszy komercyjny samojezdny komputer szachowy
Novag Super Constellation (1984), znany z ludzkiego stylu gry
DGT Centaur (2019), nowoczesny komputer szachowy oparty na sztokfisie działającym na Raspberry Pi

Na przełomie lat 70. i 90. istniał konkurencyjny rynek dedykowanych komputerów szachowych. Rynek ten zmienił się w połowie lat 90., kiedy komputery z dedykowanymi procesorami nie mogły już konkurować z szybkimi procesorami w komputerach osobistych.

  • Boris w 1977 i Boris Diplomat w 1979, komputery szachowe z figurami i planszami, sprzedawane przez Applied Concepts Inc.
  • Chess Challenger, linia komputerów szachowych sprzedawanych przez Fidelity Electronics w latach 1977-1992. Modele te wygrały pierwsze cztery mikrokomputerowe mistrzostwa świata w szachach .
  • ChessMachine , dedykowany komputer oparty na ARM , który może obsługiwać dwa silniki:
  • Excalibur Electronics sprzedaje linię jednostek siłowych dla początkujących.
  • Mephisto , linia komputerów szachowych sprzedawanych przez Hegener & Glaser. Jednostki wygrały sześć kolejnych mistrzostw świata w szachach mikrokomputerowych .
  • Novag sprzedał linię silnych taktycznie komputerów, w tym marki Constellation, Sapphire i Star Diamond.
  • Phoenix Chess Systems produkuje jednostki w limitowanej edycji oparte na procesorach StrongARM i XScale z nowoczesnymi silnikami i emulującymi klasyczne silniki.
  • Saitek sprzedaje jednostki klasy średniej o średniej wytrzymałości. W 1994 roku wykupili Hegener & Glaser i jego markę Mephisto.

Ostatnio niektórzy hobbyści używają Multi Emulator Super System do uruchamiania programów szachowych stworzonych dla komputerów Fidelity lub Hegener & Glaser's Mephisto na nowoczesnych 64-bitowych systemach operacyjnych, takich jak Windows 10 . Autor Rebel , Ed Schröder, zaadaptował również trzy napisane przez siebie Hegener & Glaser Mephisto do pracy jako silniki UCI.

Programy DOS

Te programy mogą być uruchamiane w systemie MS-DOS i mogą być uruchamiane w 64-bitowym systemie Windows 10 za pośrednictwem emulatorów, takich jak DOSBox lub Qemu :

Znani teoretycy

Znani teoretycy szachów komputerowych to:

Rozwiązywanie szachów

Główny artykuł: Rozwiązywanie szachów

Perspektywy całkowitego rozwiązania szachów są ogólnie uważane za raczej odległe. Powszechnie przypuszcza się, że nie ma niedrogiej obliczeniowo metody rozwiązania szachów nawet w bardzo słabym sensie określenia z całą pewnością wartości pozycji wyjściowej, stąd idea rozwiązania szachów w silniejszym sensie uzyskania praktycznie użytecznego opisu Strategia idealnej gry dla obu stron wydaje się dziś nierealna. Jednak nie zostało udowodnione, że nie istnieje żaden tani obliczeniowo sposób określenia najlepszego ruchu w pozycji szachowej, ani nawet, że tradycyjna wyszukiwarka alfa-beta działająca na współczesnym sprzęcie komputerowym nie byłaby w stanie znaleźć początkowej pozycji w akceptowalnej ilości czas. Trudność w udowodnieniu tego ostatniego polega na tym, że o ile liczba pozycji na szachownicy, które mogą się zdarzyć w trakcie gry w szachy jest ogromna (rzędu co najmniej 10 43 do 10 47 ), trudno wykluczyć z matematyczną pewnością możliwość, że pozycja początkowa umożliwia którejkolwiek ze stron wymuszenie mata lub trzykrotne powtórzenie po stosunkowo niewielu ruchach, w którym to przypadku drzewo poszukiwań może obejmować tylko bardzo mały podzbiór zestawu możliwych pozycji. Udowodniono matematycznie, że szachy uogólnione (szachy rozgrywane dowolnie dużą liczbą bierek na dowolnie dużej szachownicy) są EXPTIME-complete , co oznacza, że ​​w najgorszym przypadku ustalenie strony wygrywającej w dowolnej pozycji szachów uogólnionych wymaga czasu wykładniczego ; jednak ten teoretyczny wynik nie daje dolnego ograniczenia ilości pracy wymaganej do rozwiązania zwykłych szachów 8x8.

Rozwiązano miniszachę Martina Gardnera , rozgrywaną na planszy 5×5 z około 10 18 możliwymi pozycjami na planszy; jego wartość teoretyczna w grze wynosi 1/2 (tzn. remis może być wymuszony przez każdą ze stron), a strategia forsowania do osiągnięcia tego wyniku została opisana.

Poczyniono również postępy z drugiej strony: od 2012 roku wszystkie 7 i mniej bierek (2 króle i do 5 innych bierek) zostały rozwiązane.

Silniki szachowe

Główny artykuł: silnik szachowy

„Silnik szachowy” to oprogramowanie, które oblicza i wydaje polecenia, które ruchy są najsilniejsze do zagrania na danej pozycji. Autorzy silników skupiają się na poprawie gry swoich silników, często po prostu importując silnik do graficznego interfejsu użytkownika (GUI) opracowanego przez kogoś innego. Silniki komunikują się z GUI za pomocą standardowych protokołów, takich jak wszechobecny obecnie uniwersalny interfejs szachowy opracowany przez Stefana Meyera-Kahlena i Franza Hubera. Istnieją inne, takie jak protokół komunikacyjny silnika szachowego opracowany przez Tima Manna dla GNU Chess i Winboard . Chessbase ma swój własny, zastrzeżony protokół, a kiedyś Millennium 2000 miał inny protokół używany przez ChessGenius . Silniki zaprojektowane dla jednego systemu operacyjnego i protokołu mogą być przeniesione do innych systemów operacyjnych lub protokołów.

Lokomotywy szachowe są regularnie dobierane ze sobą w turniejach poświęconych lokomotywom szachowym .

Szachowe aplikacje internetowe

W 1997 roku Internetowy Klub Szachowy wydał swojego pierwszego klienta Java do gry w szachy online przeciwko innym osobom w przeglądarce internetowej. Była to prawdopodobnie jedna z pierwszych szachowych aplikacji internetowych. Darmowy Internet Chess Server pojawił się wkrótce potem z podobnym klientem. W 2004 roku Międzynarodowa Federacja Szachów Korespondencyjnych otworzyła serwer sieciowy, aby zastąpić swój system oparty na e-mailach. Chess.com zaczął oferować Live Chess w 2007 roku. Chessbase / Playchess od dawna ma klienta do pobrania i dodał klienta internetowego w 2013 roku.

Inną popularną aplikacją internetową jest trening taktyczny. Nieistniejący już Chess Tactics Server otworzył swoją witrynę w 2006 roku, a następnie Chesstempo w następnym roku, a Chess.com dodało swojego Tactics Trainer w 2008 roku. Chessbase dodało aplikację internetową do trenowania taktyki w 2015 roku.

Chessbase udostępniło swoją bazę danych gier szachowych online w 1998 roku. Inną wczesną bazą danych gier szachowych był Chess Lab, który rozpoczął działalność w 1999 roku. New In Chess początkowo próbował konkurować z Chessbase , wypuszczając program NICBase dla Windows 3.x , ale ostatecznie zdecydował się na zrezygnować z oprogramowania i zamiast tego skupić się na swojej internetowej bazie danych, począwszy od 2002 roku.

Można było grać przeciwko silnikowi Shredder online od 2006 roku. W 2015 roku Chessbase dodało aplikację internetową play Fritz, a także My Games do przechowywania swoich gier.

Od 2007 roku Chess.com zaoferował swoim klientom treść programu szkoleniowego Chess Mentor przez Internet. Czołowi arcymistrzowie, tacy jak Sam Shankland i Walter Browne , wnieśli swoje lekcje.

Zobacz też

Uwagi

Bibliografia

Źródła

Dalsze czytanie

Zewnętrzne linki

Głoska bezdźwięczna