Historia silników szachowych

Historia szachów rozpoczęła się prawie 1500 lat temu, aw ciągu ostatnich półtora tysiąclecia gra zmieniła się drastycznie. Jednak żadna technologia ani strategia nie zmieniła szachów tak bardzo, jak wprowadzenie silników szachowych . Pomimo tego, że pojawił się dopiero w ciągu ostatnich 70 lat, wprowadzenie silników szachowych ukształtowało i zdefiniowało dzisiejszy sposób gry w najlepsze szachy.

Silniki z ery przedkomputerowej (- lata 40. XX wieku)

Przedstawienie „Turka”.

Mechaniczny Turek

Najwcześniejsza forma „silnika szachowego” pojawia się w XVIII wieku wraz z maszyną o nazwie Mechaniczny Turek . Stworzony przez węgierskiego wynalazcę Wolfganga von Kempelena Mechaniczny Turek, model człowieka naturalnej wielkości, zadebiutował w 1770 roku jako pierwszy na świecie autonomiczny robot szachowy. Mechaniczny Turek mógł grać w szachy i pokonywać przeciwników, posuwając się nawet do rozwiązania kultowej wyprawy rycerskiej łamigłówka szachowa. Od 1770 do 1854 Mechaniczny Turek działał, tylko po to, by ostatecznie spalić się. Lata po śmierci maszyn oszustwo zostanie odkryte, a człowiek będzie prawdziwym źródłem inteligencji Mechanicznego Turka przez cały czas.

El Ajedrecista

Pierwszy prawdziwy egzemplarz komputera szachowego pojawił się w 1912 roku wraz z automatem o nazwie El Ajedrecista zbudowanym przez Leonarda Torresa y Quevedo . W przeciwieństwie do mechanicznego Turka, El Ajedrecista był właściwie pierwszą autonomiczną maszyną zdolną do gry w szachy. El Ajedrecista mógłby rozegrać grę końcową białymi, w której białe mają króla i wieżę, a czarne tylko króla. Maszyna była w stanie zamatować czarnego króla (granego przez człowieka) za każdym razem i była w stanie zidentyfikować nielegalne ruchy. El Ajedrecista był pierwszym prawdziwym silnikiem szachowym i ogólnie wywołał wiele emocji na boisku.

Początek informatyki szachowej (lata 40. - 50. XX wieku)

II wojna światowa doprowadziła do zdumiewających przełomów technologicznych, z których największym było oczywiście wynalezienie/stworzenie komputera. Dwóch mężczyzn, Alan Turing i Claude Shannon byli pionierami tych innowacji i pod koniec drugiej wojny światowej obaj zainteresowali się programowaniem silnika szachowego. W 1949 roku Claude Shannon opublikował artykuł szczegółowo opisujący program, który potencjalnie mógłby grać w szachy przeciwko człowiekowi. Rok później Alan Turing stworzył pierwszy komputerowy algorytm gry w szachy, ale ówczesny sprzęt nie był wystarczająco wydajny. Turing testował swój algorytm ręcznie i chociaż sam algorytm był słaby, Turing i Shannon położyli podwaliny pod wielkość.

W 1951 roku bliski współpracownik Turinga, niejaki Dietrich Prinz , zdołał stworzyć i zaimplementować podstawowy algorytm szachowy, który był w stanie rozwiązywać mat na dwa. Algorytm działał na Ferranti Mark 1 , pierwszym komercyjnie dostępnym komputerze i chociaż nie miał mocy do rozegrania pełnej partii, posłużyłby jako dowód słuszności koncepcji obliczeń szachowych.

Wreszcie w 1957 roku inżynier IBM, Alex Bernstein, stworzył pierwszy na świecie w pełni zautomatyzowany silnik szachowy. Silnik został zbudowany dla komputera mainframe IBM 704 i zajmował około ośmiu minut na ruch. Ten silnik, zdolny do rozegrania całej partii, oznaczałby prawdziwy początek obliczeń szachowych.

Powstanie silników szachowych (lata 60. - 70. XX wieku)

Szybki postęp informatyki w latach 60. i 70. był kluczem do zwiększenia siły silnika szachowego, zarówno drastyczne innowacje w oprogramowaniu, jak i sprzęcie prowadzą do silniejszych silników.

Postęp w oprogramowaniu

Najbardziej kultowy algorytm gry ze wszystkich, algorytm Minimax i jego optymalizacja przycinania alfa-beta , był i pozostaje kluczem do programowania i optymalizacji szachów. Algorytm ten, po raz pierwszy sprawdzony w 1928 roku przez Johna von Neumanna , skupia się na maksymalizacji wyniku jednego gracza przy jednoczesnej minimalizacji pozostałych. Główne ulepszenia tego algorytmu zostałyby opracowane specjalnie do programowania szachów, a głównym celem byłoby zwiększenie głębokości wyszukiwania. Obejmowały one...

Techniki wyboru ruchu
Podejścia heurystyczne
Pogłębianie iteracyjne
Otwieranie/kończenie baz danych

W tym czasie niektórzy arcymistrzowie szachowi również poświęcali się doskonaleniu programowania szachowego, wykorzystując swoją zaawansowaną wiedzę o grze. Przede wszystkim poprzedni mistrz świata w szachach Michaił Botwinnik , który napisał kilka artykułów na ten temat, szczególnie związanych z technikami wyboru ruchów.

Postępy sprzętowe

Wcześniej najwięksi ogranicznicy, z jakimi musieli się zmierzyć ludzie, tacy jak Turing i Dietrich, sprzęt rozwijał się w zadziwiającym tempie. W 1965 roku Gordon Moore zauważył, że liczba tranzystorów w komputerach podwaja się co dwa lata, zwiększając szybkość sprzętu w tempie wykładniczym. Jest to powszechnie określane jako prawo Moore'a i nadal obowiązuje.

W tym czasie specjalny sprzęt szachowy stał się również widoczny w silnikach szachowych. W 1978 roku silnik szachowy o nazwie Belle wygrał Północnoamerykańskie Mistrzostwa Komputerowe w Szachach organizowane przez Association for Computing Machinery . Specjalny sprzęt silnika pozwolił mu przeanalizować około trzydziestu milionów pozycji w ciągu trzech minut. Jest to również wspomagane przez fakt, że Belle posiadała zarówno początkowe, jak i końcowe bazy danych, co znacznie zwiększyło szybkość sprzętu. Belle została pierwszym silnikiem szachowym, który dwa lata później otrzymał ocenę mistrzowską .

Zamykanie luki (1960 - 2000)

Wczesna konkurencja

Silniki szachowe z lat 60. i 70. nie mogły konkurować z najlepszymi szachistami. W 1968 roku międzynarodowy mistrz David Levy zaoferował 3000 $ każdemu silnikowi szachowemu, który mógłby go pokonać w ciągu następnych dziesięciu lat. W 1977 Levy zmierzył się z silnikiem szachowym Kaissa , wychodząc bez przegranej ani jednego meczu.

Deep Blue, na wystawie w IBM.

W latach 80. komputer zagościł w każdym gospodarstwie domowym, a szachy nagle stały się prawdziwym biznesem. W 1980 roku Edward Fredkin , profesor informatyki na Uniwersytecie Carnegie Mellon , oferował nagrody pieniężne za silniki szachowe, które miały przełamać bariery w szachowym świecie. Obejmowały one 10 000 $ za pierwszy silnik, który osiągnął poziom arcymistrza, oraz 100 000 $ za pierwszy silnik, który pokonał szachowego mistrza świata. Nagle rywalizacja w szachach komputerowych stała się bardzo realna, a do gry włączyły się najwybitniejsze umysły.

Głęboki błękit

Deep Blue zacznie się pod inną nazwą, ChipTest . ChipTest został opracowany i zbudowany przez Feng-hsiung Hsu , Thomasa Anantharamana i Murraya Campbella z Carnegie Mellon. Początkowo wprowadzili silnik do mistrzostw Ameryki Północnej w szachach komputerowych w 1986 roku i nie udało im się, ale wrócili w następnym roku z ulepszoną wersją i wygrali zawody w wyniku 4-0.

Od 1988 roku zespół opracowywał nową maszynę o nazwie Deep Thought . Deep Thought miał znaczną przewagę nad swoją poprzednią wersją i wyróżniał się na tle konkurencji. Stał się pierwszym silnikiem, który pokonał arcymistrza, grając z Bentem Larsenem w zwykłym meczu turniejowym w tym samym roku, w którym się pojawił. Deep Thought nadal wygrywał mistrzostwa świata w szachach komputerowych z niepokonanym rekordem 5-0 w następnym roku. Mimo to w dwóch meczach w tym samym roku nadal spadałby na Garry'ego Kasparowa, różnica między człowiekiem a maszyną pozostała. Przez następne lata Deep Thought pozostawał mistrzem silnika szachowego, ostatecznie zostając Deep Thought 2 i wygrywając po raz piąty North American Computer Chess Championship . W 1994 roku zespół został sponsorowany przez IBM , czas Deep Thought dobiegał końca.

Wreszcie w 1995 roku zespół IBM wypuścił nowy prototyp silnika szachowego, Deep Blue. Silnik zostanie ukończony w 1996 roku iw tym samym roku po raz pierwszy zmierzy się z mistrzem szachowym Garrim Kasparowem . Mecz z Kasparowem ostatnich sześciu meczach, w których Deep Blue przegrał 4-2. Ale to nadal oznaczało, że po raz pierwszy silnik szachowy pokonałby obecnego mistrza szachowego w zwykłym meczu. Jednak zaledwie rok później zespół IBM miał kolejną szansę, Deep Blue został zaktualizowany i pracował nad nim zarówno inżynierowie, jak i najlepsi szachowi arcymistrzowie. W meczu, który stał się ikoną, Deep Blue stałby się pierwszym silnikiem szachowym, który pokonał obecnego mistrza szachowego w pełnym meczu szachowym. Pomimo kontrowersyjnych twierdzeń w imieniu Kasparowa, że IBM oszukiwał, wynik był doniosłym osiągnięciem w szachach komputerowych.

Era nadludzkich silników (2000 - obecnie)

Klęska Kasparowa oznaczałaby koniec czasów, kiedy najlepsi ludzie mogli pokonać silniki. Pieniądze nadal napływały do komputerów szachowych, a branża kwitła, jednak nie bez kontrowersji. W 2011 roku czterokrotny mistrz silnika Rybka został zdyskwalifikowany z mistrzostw świata w szachach komputerowych za plagiat kodu. Pojawiły się również nowe zawody, a mistrzostwa Top Chess Engine zostały utworzone w 2010 roku z silniejszym naciskiem na zautomatyzowaną grę, dłuższe gry i mocniejszy sprzęt.

Aż do końca 2010 roku świat szachowych komputerów rozwijał się powoli, ale postęp był stały, a silniki silniejsze niż kiedykolwiek. Tak było do 2017 roku, kiedy zespół programistów z firmy Google DeepMind wypuścił zupełnie nowy silnik, AlphaZero .

Rewolucja w sieciach neuronowych

Pod koniec 2017 roku inżynierowie z DeepMind wypuścili silnik, który miał zaszokować szachowy świat. AlphaZero było zasadniczo oparte na innym podejściu do obliczeń szachowych, czymś, czego tak naprawdę nigdy wcześniej nie widziano. Podczas gdy poprzednie silniki polegały na przeszukiwaniu drzew i ocenie pozycji, AlphaZero polegała na głębokiej sieci neuronowej do swojej analizy. Zasadniczo oznaczało to, że AlphaZero może samodzielnie uczyć się gry w szachy.

Początkowe testy z AlphaZero były oszałamiające; w 100 meczach przeciwko najsilniejszemu obecnie silnikowi Stockfish , AlphaZero wygrał 28 gier i zremisował w pozostałych 72. Pod wieloma względami AlphaZero stanowiło przełom nie tylko dla szachowych obliczeń, ale ogólnie dla świata sztucznej inteligencji.

Od 2017 roku obecność sieci neuronowych w najlepszych silnikach szachowych na świecie tylko wzrosła. Wszystkie najlepsze obecnie silniki, Leela Chess Zero , Stockfish i Komodo, mają w swoich silnikach sieci neuronowe. Jednak uczenie się głębokiego wzmacniania stosowane w AlphaZero pozostaje rzadkością w najlepszych silnikach.

Zobacz także

Szachy komputerowe