Techniki informatyczne w szachach

Szachy i komputery

Początki

W tym rozdziale przedstawię w dużym skrócie, jak komputery odgrywały coraz większą rolę w szachach. Więcej przeczytacie w innych rozdziałach, przede wszystkim w tych poświęconych superkomputerom szachowym, sławnym meczom człowiek kontra maszyna i rywalizacji silników.

Jeśli nie liczyć trików z człowiekiem ukrytym pod stołem z szachownicą i podobnych, próby użycia maszyn do gry w szachy podejmowano już ponad pół wieku temu. Na początku, w połowie XX wieku, uważano, że nauczenie komputera, jak grać, nie będzie miało praktycznego znaczenia, będzie jedynie punktem wyjścia do rozwiązania innych problemów. W 1951 roku, czyli jeszcze przed pojawieniem się komputerów zdolnych do tak zaawansowanych obliczeń, sławny Alan Turing zaprojektował (oczywiście wyłącznie na papierze) pierwszy program szachowy. Rok później, z braku odpowiedniego sprzętu, rozegrał partię z człowiekiem, symulując działanie programu we własnej pamięci. Wcześniej, pod sam koniec lat 40., Claude Shannon, również matematyk, opracował podstawowe strategie silnika: analizę wszystkich posunięć do określonej głębi drzewa wariantów, którą nazwał „A”, i analizę tylko wybranych, wyznaczonych na podstawie wiedzy szachowej, którą nazwał „B”.

Dietrich Prinz w 1951 roku zdołał nauczyć jeden z wczesnych komputerów znajdywania mata w dwóch posunięciach.

Pod koniec lat 50. komputery nie tyle umiały grać w szachy, co rozegrać partię zgodnie z regułami. Taki program napisał w 1958 roku pracownik IBM-a Alex Bernstein. W tym samym czasie powstał program NSS, opracowany przez Allena Newella, Herberta Simona i Cliffa Shawa, wykorzystujący podstawowy algorytm liczenia wariantów i „odcinania” wybranych (ang. alpha-beta pruning, patrz rozdział poświęcony silnikom) natychmiast po uznaniu ich za mniej obiecujące.

Wcześniej niedostateczne zasoby sprzętowe wymagały ograniczenia liczby pól. Pierwszym programem zdolnym rozegrać taką partię (na szachownicy 6 × 6, bez gońców, roszady, promocji piona na gońca i prawa do pierwszego ruchu pionem o dwa pola) był Los Alamos chess, stworzony w 1956 roku na programowalny superkomputer MANIAC I, uruchomiony, zanim MANIAC rozpoczął obliczenia związane z budową bomby atomowej. (Piszę: superkomputer, a wcześniej o tym, że brakowało mu mocy, ale kilka tysięcy lamp próżniowych miało bardzo niską wydajność).

W latach 1959–1962 kilku studentów MIT-u napisało kod zdolny do pokonania szachisty amatora. Pracujący w Micie Richard Greenblatt dodał do niego sporo wiedzy szachowej, co pozwoliło programowi MacHack VI działającemu na komputerze DEC-PDP-6 osiągnąć w turnieju z udziałem ludzi ranking typowy dla przeciętnego gracza. Na początku lat 60. mistrz świata w szachach Michaił Botwinnik, z wykształcenia elektrotechnik, rozwinął na radzieckich komputerach, o bardzo ograniczonych możliwościach, techniki wybierania najlepszych posunięć do analizy.

W latach 1966–67 rozegrano pierwszy mecz między komputerami: Kaissa – Kotok-McCarthy.

Oprogramowanie wykonało wielki skok w latach 70. Wtedy pojawiły się tak podstawowe dziś elementy, jak: książki otwarć, tablice transpozycji, tablice końcówek, a także nowe algorytmy oceny pozycji (takie jak iteratywne pogłębianie) i przede wszystkim plansze bitowe. (O tym wszystkim przeczytacie w rozdziałach opisujących różne typy oprogramowania szachowego i działanie silnika).

Jednak w latach 70. był okres, gdy najmocniejszy silnik, Chess, stosował metodę brutalnej siły w czystej postaci, bo stosunkowo mało rozwinięte techniki ograniczania liczby wariantów do obliczenia nie zajmowały więcej zasobów niż liczenie wszystkich.

To także wtedy mikrokomputery zaczęły trafiać pod strzechy i silniki szachowe stały się dostępne nie tylko naukowcom. Pierwsze przeznaczone na domowe mikrokomputery były pisane przez hobbystów i dostępne w wersji do samodzielnego wpisania. Wkrótce pojawiły się komercyjne silniki działające na takich komputerach, jak Apple II i TRS-80. W tym samym czasie, w 1977 roku, pionier komputerowych szachów Ken Thompson wraz Joe Condonem stworzyli pierwszy superkomputer zaprojektowany pod tym właśnie kątem, Belle, który w takich obliczeniach był kilkadziesiąt razy szybszy od ówczesnych superkomputerów ogólnego przeznaczenia.

W 1974 roku rozegrano pierwszą edycję mistrzostw świata komputerów, World Computer Chess Championship. (W latach 1980–2001 rozgrywano osobny cykl dostępny wyłącznie dla mikrokomputerów).

W 1977 roku powstała organizacja International Computer Chess Association (ICCA), przemianowana w 2002 roku na International Computer Games Association (ICGA), mająca promować wykorzystanie komputerów w szachach i organizować rozgrywki między nimi.

W tym samym roku pojawił się Chess Challenger, pierwszy domowy komputer szachowy. Pierwsze urządzenia tego typu grały na poziomie początkującego.

W 1980 roku silnik Sargon we współpracy z procesorem Z80 firmy Zilog (tę architekturę wykorzystano m.in. w ZX Spectrum) osiągnął poziom dość silnego amatora. Jedna z jego następnych wersji, zainstalowana na domowym pececie, pokonała w 1989 roku silnik działający na superkomputerze. W tym czasie komputery i programy szachowe były już zdolne sporadycznie zagrozić utytułowanym graczom, na przykład HiTech i Deep Thought pokonały dwóch amerykańskich arcymistrzów: Arnolda Denkera i Benta Larsena.

Jeszcze w połowie lat 80. nie było zgody co do tego, czy komputer kiedykolwiek będzie zdolny pokonać gracza ze ścisłej czołówki. Tak naprawdę uwierzono w to dopiero na przełomie lat 80. i 90., choć jak się okazało, trzeba było dopiero Deep Blue firmy IBM, specjalnie zbudowanego w tym celu superkomputera o setkach procesorów i specjalnie zaprojektowanych układów, wywodzącego się z projektu Deep Thought.