Jak to się stało, że umysł poległ w grze szachowej…

No i mamy grudzień, czas adwentu, tysięcy promocji, przy których głębszej analizie okazuje się, że płacimy cenę sprzed miesiąca, wspomaganych masowym i masywnym uderzeniem świątecznych piosenek płynących z supermarketowych głośników. Jest to też czas ciemnych poranków i powrotów z pracy po zachodzie Słońca. Jest to również czas zaskoczeń pogodowych dla drogowców i testów cierpliwości dla najmłodszych pt. “jak nie spałaszować całego kalendarza adwentowego pierwszego grudnia”. 😉

Czas spokoju, czas oczekiwania, planów świątecznych, ale także niespokojny czas w Europie i na Hawajach, gdzie właśnie wybuchł najwyższy na świecie aktywny wulkan tarczowy. Mowa tu o Mauna Loa (w języku hawajskim “Długa Góra”). Wulkan ten w swojej podwodnej części liczy 4975m wysokości a w nawodnej kolejne 4170m co daje razem aż 9145m. Jest to także jeden z najaktywniejszych wulkanów i przejawia rozmaite formy aktywności średnio co 3 lata. Do ostatniej erupcji doszło w 1984 roku. Wulkany tarczowe to wulkany o szerokim i spłaszczonym stożku i o kącie nachylenia nie większym niż 8°. Wśród innych typów wulkanów wymienić można wulkany stożkowe (gdzie magma wypływa ze stromego stożka) oraz liniowe gdzie lawa wypływa wzdłuż pęknięcia.

Obecnie na Ziemi mamy około 800 aktywnych wulkanów z czego połowa przypada na lądy. Szacuje się, że w przeciągu ostatnich 10 tys. lat doszło na Ziemi do 7900 erupcji. W Polsce nie mamy obecnie aktywnych wulkanów ale ślady wskazują, że np. kilkanaście milionów lat temu w Górach Świętokrzyskich mieliśmy bardzo aktywny wulkan. Dodatkowo ślady dawnego wulkanizmu można odnaleźć na Śląsku od Nysy Łużyckiej po Górę Świętej Anny oraz w Pieninach, Beskidzie Sądeckim i w południowej części Wyżyny Olkuskiej.

Zanim przejdziemy do naszego dzisiejszego tematu tradycyjnie krótka relacja co dzieje się w ogrodzie. Spadł śnieg i temperatury zeszły poniżej zera. Podjęta trzy tygodnie temu decyzja o uruchomieniu ptasiej jadłodajni okazała się ze wszech miar słuszna i ptasie eskadry masowo atakują karmniki ogrodowe. Wieść o uruchomieniu ptasiego spa rozeszła się szybko po okolicznym polskich i niemieckich gminach 😉 i zleciał się bogaty zestaw gości od sikor i mazurków zaczynając, poprzez kosy i sierpówki a na sójkach zakończywszy. Niestety pojawił się także kot sąsiadów zwabiony obecnością ptaków i tu wzmożone patrole musiał podjąć pies, którego śnieg nie zraża. Co ciekawe psy reagują na śnieg jak dzieci. Widać u nich radość jak tylko pojawia się biały puch, a łapanie kul śnieżnych w locie jest jedną z najlepszych psich zabaw na śniegu. Oczywiście kończy się to przyklejonymi kulami śnieżnymi do sierści, ale co tam, wiszący ozór i pełen garnitur zębów w psim uśmiechu wyraźnie mówią, że było warto. 🙂

Czym dzisiaj się zajmiemy? W czasach retrokomputerów doszło do przełomu, którego rezultatem była przegrana szachowego mistrza świata Garriego Kasparowa z komputerem. Jak do tego doszło i jak komputery z tego okresu grały w szachy? Na to pytanie postaramy się dzisiaj odpowiedzieć i zobaczycie, że wcale nie jest to jakaś czarna komputerowo-szachowa magia. Szykujcie aromatyczną kawę w rozmiarze XXL, z racji temperatur kubek powinien zostać uprzednio podgrzany, a ciepły koc przygotowany. Jeżeli aromat kawy zmieszany z cynamonem rozchodzi się już w powietrzu, a koc swym kształtem upodobnił się do ludzkiej postaci to możemy zaczynać! 🙂

***

Od stuleci człowiek marzył o maszynie, z którą mógłby zagrać w szachy. Wydawało się, że marzenie to urzeczywistniło się w XVIII wieku za pomocą pokazanej po raz pierwszy w 1769 r. maszyny zwanej “Mechanicznym Turkiem”. Autorem jej był węgierski wynalazca baron Wolfgang von Kempelen. Mechaniczny Turek u szczytu swojej popularności rozegrał pojedynki z takimi postaciami jak Benjamin Franklin, Charles Babbage czy Napoleon Bonaparte. Była to jednak mistyfikacja, w rzeczywistości maszyną sterował ukryty w jej wnętrzu mistrz szachowy. 🙂

Kolejną maszynę nazwaną El Ajedrecista (hiszp. szachista), będącą już prawdziwym automatem, skonstruował w 1912 roku Hiszpan Leonardo Torres Quevedo. Maszyna rozgrywała końcówki szachowe wyposażona w króla i wieżę, natomiast człowiek miał do dyspozycji króla. Maszyna wzbudziła ogromne zainteresowanie i może być uznana za pierwszą na świecie grę komputerową. Dalszy postęp nauki i techniki powodował, iż świat ze zdumieniem zaczął obserwować kolejne kroki zmierzające do budowy maszyny zdolnej grać w szachy, a kalendarz wydarzeń w tym zakresie był następujący…

W 1941 Niemiec Konrad Zuse opracowuje pierwsze algorytmy szachowe. W 1948 roku Brytyjczycy Alan Turing i David Gawen Champernowne tworzą na papierze pierwszy program szachowy nazwany Turochamp. Niestety zaproponowany algorytm był zbyt skomplikowany w stosunku do możliwości ówczesnych komputerów i próby ukończenia dzieła poprzez uruchomienie programu na komputerze zostały przerwane śmiercią Turinga w 1954 roku.

W 1949 roku amerykański naukowiec Claude Shannon wydaje dwie bardzo ważne publikacje, w pierwszej określa złożoność drzewa możliwości gry szachowej na poziomie 10 do potęgi 120, która w przypadku metody siłowej analizy (ang. brute force) wszystkich możliwych kombinacji daje ogromną liczbę wymaganych obliczeń. Drugim jego dziełem była publikacja: “Programming a Computer for playing Chess” (ang. “Programowanie komputera do gry w szachy”), gdzie opisywał procedurę bazującą na ocenie punktowej pozycji i wyborze ruchu oraz sposób ograniczenia złożoności obliczeniowej.

W tym okresie pojawiły się pierwsze programy szachowe uruchamiane na ogromnych komputerach lampowych, jednak ich poziom gry pozostawiał wiele do życzenia. Dopiero w roku 1957 Alex Bernstein wspólnie z grupą złożoną z Michaela de V. Robertsa, Timothy’ego Arbuckle i Martina Belsky’ego opracowuje program “The Bernstein Chess Program” dla komputera IBM 704, który staje się pierwszym programem szachowym zdolnym rozegrać całą partię. W latach 1959-1962, grupa studentów Massachusetts Institute of Technology (MIT): Elwyn Berlekamp, Alan Kotok, Michael Lieberman, Charles Niessen i Robert A. Wagner napisali pod kierownictwem Johna McCarthy’ego, (twórcy algorytmu alpha-beta, o którym jeszcze sobie powiemy), pierwszy program szachowy, który grał już na przyzwoitym poziomie. Został on napisany w języku Fortran na maszynie IBM 7090 i działał całkiem nieźle, gdyż analiza kolejnych ruchów zajmowała mu tylko od 5 do 25 minut.

Z tym programem związany jest pierwszy pojedynek szachowy pomiędzy dwoma komputerami. W 1964 roku McCarthy (już wtedy związany z Uniwersytetem Standforda w Kalifornii) odwiedził Związek Sowiecki i grupę tamtejszych naukowców z laboratorium Aleksandra Kronroda z Instytutu Fizyki Teoretycznej i Eksperymentalnej w Moskwie. Grupa ta zaproponowała pojedynek pomiędzy swoim programem szachowym pracującym na sowieckiej maszynie M-2 a programem McCarthy’ego. Amerykanin podjął rękawicę i doszło do korespondencyjnego pojedynku pomiędzy maszynami.

Mecz ten był rozgrywany przez 9 miesięcy na przełomie 1966-67r. a komunikacja odbywała się drogą telegraficzną. Grupa sowiecka korzystała ze wsparcia mistrza szachowego Aleksandra Bitmana i trzykrotnego mistrza świata Michaiła Botwinnika. Amerykanie przegrali pojedynek wynikiem 1:3. Dodać tu należy jednak, iż zaangażowanie Botwinnika w grupie sowieckiej dawało jej ogromną przewagę. Botwinnik był nie tylko szachistą, ale także elektronikiem, naukowcem w dziedzinie maszyn liczących, prekursorem komputerowych szachów, a także nauczycielem trzech kolejnych szachowych mistrzów świata: Karpowa, Kasparowa i Kramnika.

W 1968 roku szkocki międzynarodowy mistrz szachowy David Levy zakłada się z pionierami sztucznej inteligencji szachowej: Johnem McCarthy’m i Donaldem Michie o 500 funtów szterlingów, że żaden komputer nie pokona go przez następne 10 lat. 🙂

W 1970 roku zorganizowane zostają pierwsze zawody szachowe komputerów Ameryki Północnej – North American Computer Chess Championship w Nowym Jorku. Zwycięzcą zostaje napisany dla superkomputerów Control Data Corporation program Chess 3.0. Autorami jego byli Amerykanie Larry Atkin, David Slate i Keith Gorlen z Northwestern University.

W 1974 roku David Levy, Ben Mittman i Monty Newborn organizują pierwszy światowy konkurs programów szachowych: World Computer Chess Championship w Sztokholmie, gdzie wśród 13 programów pierwsze miejsce zajmuje sowiecka Kaissa (Caïssa – bogini szachów), następczyni programu, który wygrał wspomniany wcześniej pojedynek korespondencyjny z programem McCarthy’ego.

W 1975 roku David Levy wspólnie z Irlandczykiem Kevinem O’Connellem zakładają Philidor Press.

W 1976 roku Kanadyjczyk Peter R. Jennings wypuszcza pierwszy na świecie komercyjny program szachowy przeznaczony dla mikrokomputerów o nazwie Microchess, a rok później pojawia się pierwszy komputer szachowy wyprodukowany przez Fidelity Electronics – Chess Challenger i również w 1977 roku pojawia się wydany przez Applied Concepts: “Boris” – dedykowany komputer szachowy ze składaną szachownicą.

Pod koniec 1977 David Levy zostaje zaangażowany jako konsultant w Texas Instruments, który planuje wypuszczenie komputera TI99/4 i chce opracować dla niego program szachowy. David pomaga zespołowi TI pracującemu nad tym projektem podążać we właściwym kierunku. Wypuszczony na kartridżu program, okazuje się być jednym z najlepiej sprzedających się na tej platformie sprzętowej.

W 1978 roku szwajcarski fizyk i przedsiębiorca Eric Winkler zwraca się do Levy’ego o pomoc w opracowaniu oprogramowania szachowego. Po udanej początkowej współpracy z tandemem Levy/O’Connell Eric zakłada firmę SciSys-W Ltd. W tym także roku po dziesięciu latach od zakładu David Levy staje się właścicielem 500 funtów, wygrywając składający się z sześciu partii pojedynek z programem Chess 4.7 wynikiem 4,5 do 1,5. Zdarzyło się tu jednak coś historycznego przegrana Levy’ego w czwartej rundzie jest pierwszym odnotowanym przypadkiem wygranej partii szachów przez komputer z mistrzem szachowym. 🙂 We wrześniu tego roku podczas zawodów mikrokomputerowych programów szachowych zorganizowanych przez czasopismo ‘Personal Computer World’ napisany przez amatora Mike’a Johnsona program “Mike” wygrywa zawody pokonując m.in. komercyjny komputer Boris”. Program Mike’a, ładowany z taśmy działał na komputerze opartym o 8-bitowy procesor Motorola 6800 taktowany zegarem 1 MHz z 16KB pamięci RAM. Długo nie trzeba było tu czekać na reakcję Levy’ego i O’Connell’a, którzy dostrzegłszy talent zatrudnili Johnsona u siebie. W grudniu tego roku w Waszyngtonie dochodzi do jeszcze jednego wydarzenia, a mianowicie w Północnoamerykańskich Zawodach Komputerów Szachowych program ‘Mike’ odnotowuje trzy remisy i zostaje pokonany tylko przez program ‘Belle’ pracujący na komputerze typu mainframe. To ogromny sukces programu Mike’a Johnsona.

Współpraca z Mike’em zaowocowała wypuszczeniem w 1979 roku komputera szachowego ‘Chess System III’ opartego na znanym z Atari XL i Commodore C64 8-bitowym procesorze MOS 6502.

W tym roku doszło także do transmisji w niemieckiej telewizji pojedynku szachowego pomiędzy Davidem Levy’m a programem Chess 4.8 uruchomionym na jednym z najsilniejszych w owym czasie superkomputerów używanym m.in. przez amerykańskie lotnictwo opracowanym przez firmę Control Data Corporation (CDC):  Cyber 176. Pojedynek składający się z aż 89 posunięć zakończył się remisem. W tym także roku podczas kolejnej edycji zawodów mikrokomputerowych programów szachowych pod egidą ‘Personal Computer World’ drugie miejsce zajmuje kolejny amatorski program: ‘Vega’ napisany dla procesora Z80. Jego autor David Broughton wkrótce staje się pracownikiem Philidor Software Davida Levy’ego i Kevina O’Connella. 🙂

W 1980 roku pojawia się kolejny opracowany przez zespół Davida Levy’ego komputer szachowy ‘Intelligent Chess’ podłączany tym razem do telewizora, na którym wyświetlana była szachownica z aktualnym stanem gry.  Do zespołu Levy’ego dołącza także ekspert od mikroprocesorów serii 6502 – Mark Tylor. W tym także roku pojawia się pierwszy komputer szachowy z serii ‘Mephisto’ bawarskiej firmy Hegener & Glaser.

Z ciekawostek w tym czasie amerykańska federacja szachowa  (ang. US Chess Federation) czując, że kwestią czasu jest dominacja komputerów w szachach, zabroniła uczestnictwa maszyn w turniejach szachowych poza jedynie meczami pokazowymi, a amerykański naukowiec profesor Edward Fredkin ustanawia nagrodę 100.000 USD dla systemu, który pokona szachowego mistrza świata.

W roku 1981 program Blitz napisany przez Roberta Hyatta, Harry’ego L. Nelsona i Alberta Gowera dla superkomputera Cray, wygrywa, jako pierwszy komputer, stanowy turniej szachowy w Missisipi. W tym także roku zespół Davida Levy’ego opracowuje dla SciSys komputer szachowy: Chess Champion Mark V, którego autorami są nowozatrudnieni: Mark Taylor i autor Vegi – David Broughton. Komputer ten zostaje wkrótce laureatem drugiej edycji turnieju World Microcomputer Chess Championship, która odbywa się w Niemczech.

W tym czasie SciSys koncentruje się jednak na marketingu swoich aktualnych produktów i spada jego zainteresowanie usługami R&D, które oferował zespół Levy’ego i O’Connella. W związku z tym postanawiają oni rozluźnić relacje z SciSys i poszukać biznesu gdzie indziej. Firma Philidor Software zostaje przemianowana na Intelligent Software. W międzyczasie do Levy’ego telefonuje przedstawiciel amerykańskiej firmy Milton Bradley zajmującej się grami planszowymi (znanej między innymi z tytułu Twister). Milton Bradley prosi Levy’ego o pomoc w opracowaniu swojego komputera szachowego. Levy leci do Massachusetts i po podpisaniu stosownych klauzul poufności wchodzi do pomieszczenia, w którym stoi prototyp maszyny. Levy otwiera oczy szeroko ze zdumienia, maszyna przesuwa figury szachowe bez ich dotykania. Levy jest pod wrażeniem i zgadza się na uczestnictwo w projekcie. Ma na to 5 miesięcy i taki potrzebny czas na szczęście potwierdza także jego dyrektor techniczny. Prace startują. Maszyna wyposażona zostaje w procesor 6502A z 2KB RAM i 16KB ROM. Termin zostaje dotrzymany, ‘Milton Bradley Phantom’ wchodzi do produkcji pod koniec 1982 roku i ląduje na półkach sklepowych na początku roku 1983.

Sekretem działania tej maszyny jest schowany pod szachownicą ploter X-Y z głowicą elektromagnetyczną, która przesuwa figury na planszy.

Rozwój mikrokomputerów powodował, że komputerom szachowym wyrosła poważna konkurencja w postaci programów szachowych. Zespół Levy’ego i O’Connella był tego świadomy. W 1981 roku Mark Tylor napisał program PETChess 4000 wydany na Commodore PET i C64. We wrześniu tego roku w Londynie odbywa się turniej European Microcomputer Chess Championship. Laureatem zostaje napisany przez Richarda Langa program Cyrus. Krótko po turnieju Intelligent Software zatrudnia Richarda Langa. Dodatkowo Intelligent Software postanowiło zatrudnić także innego uczestnika tego turnieju, a mianowicie Martina Bryanta, autora dziesiątego programu w klasyfikacji – ‘White Knight’a’.

Cyrus był szczególnie efektywny w szachach błyskawicznych. Pomimo, iż był napisany pod procesor 8-bitowy – Z80, był w stanie wygrać z ‘Blitz’em’ opartym na superkomputerze Cray oraz Chess 4.5 opartym na komputerze typu mainframe. Intelligent Software zbudowało na bazie tego programu komputer szachowy La Regance, który w trzeciej edycji turnieju European Microcomputer Chess Championship (1982) w Londynie zajął wysokie drugie miejsce. Wkrótce potem Cyrus Richarda Langa pojawił się także na platformie Sinclair ZX Spectrum jako ‘Cyrus-IS-Chess’. Ten program wziął także udział w naszym “turnieju po latach” 🙂 (więcej możecie przeczytać na ten temat w poprzednim wpisie).  ‘White Knight’ Martina Bryanta został wydany na platformie Apple, a następnie na komputerze BBC Micro. Krótko po tym Martin rozpoczął pracę nad swoi kolejnym dziełem – Colossus Chess, jednym z najlepiej sprzedających się programów szachowych w historii, wydanym na wszystkie znaczące platformy mikrokomputerowe lat 80-tych i 90-tych XX wieku.

Program ten w wersji X został laureatem naszego turnieju po latach, a w wersji 4.0 na platformie C64 był w stanie nawet pokonać amerykańskiego ‘Chessmaster’a 2000’ uruchomionego na platformie 16-bitowej – Atari ST! 🙂  To że udało mu się to samo z ‘Battle Chess’ na Amidze raczej nie dziwiło, gdyż piękny amigowski konkurent z mocnego silnika szachowego raczej nie słynął. 🙂 Wracając do ‘White Knight’a’ i ‘Cyrus’a’ to oba te programy zajęły czwarte miejsce w rozegranej w 1983 roku czwartej edycji turnieju European Microcomputer Chess Championship. W 1982 roku Intelligent Software podjął się opracowania komputera domowego Elan. Niestety zlecająca firma, nie dostarczyła zamówionych 80.000 komputerów na czas i całe przedsięwzięcie zakończyło się fiaskiem doprowadzając Intelligent Software do upadku w 1986 roku na skutek nieprzekazania przez zlecającego dużej części należnego wynagrodzenia.

W 1984 roku Richard Lang zakończył współpracę z Intelligent Software i rozpoczął pracę nad programem szachowym na nowy procesor Motorola 68000. Związał się z firmą PSION i napisał program szachowy ‘Psion Chess’ dla pierwszego komercyjnego komputera z tym procesorem, a mianowicie Sinclair’a QL, który to jako komputer okazał się niewypałem (więcej możecie przeczytać na ten temat tutaj). W odróżnieniu od komputera QL program odniósł sukces podczas czwartej edycji turnieju World Microcomputer Chess Championship, który odbył się w 1984r. w Glasgow. W naszym turnieju po latach również zaszedł wysoko ulegając w finale programowi swojego kolegi Martina Bryanta – ‘Colossus Chess X’. 🙂

W 1986 roku na rynku pojawił wspomniany powyżej drugi najlepiej sprzedający się program szachowy wszech czasów: ‘Chessmaster 2000’ z silnikiem szachowym Amerykanina Davida Kittingera. Cała seria zaliczyła do roku 2002 pięć milionów sprzedanych egzemplarzy. Silnik szachowy Davida Kittingera został także użyty w komputerach szachowych firmy Millennium 2000 z Monachium, których to przedstawiciel widoczny obok wziął także udział w naszym turnieju po latach. 🙂

W 1987 roku, Frederic Friedel i Matthias Wüllenweber zakładają działającą do dziś firmę Chessbase GmbH z siedzibą w Hamburgu, zajmującą się tworzeniem programów szachowych i baz danych z rozgrywkami szachowymi.

W 1988 roku dochodzi do przełomowego wydarzenia. Opracowany przez zespół: Feng-hsiung Hsu, Thomas Anantharaman, Mike Browne, Murray Campbell i Andreas Nowatzyk komputer szachowy Deep Thought pokonuje po raz pierwszy w historii w turnieju duńskiego arcymistrza szachowego Benta Larsena, a w roku następnym rozbija w pojedynku (4-0) Davida Levy’ego wygrywając ustanowioną przez Levy’ego nagrodę dla pierwszego komputera, który go pokona.

W 1993 roku komputer Deep Thought 2 przegrywa rewanżowy pojedynek z Bentem Larsenem.

W 1994 roku podczas turnieju Intel Grand Prix World Championship Series w Londynie program szachowy ‘Chess Genius’, napisany przez wspomnianego Richarda Langa, wygrywa 2-rundowy pojedynek rezultatem 1,5:0,5 z Garrim Kasparowem.

W 1995 roku program Fritz 3 napisany dla Chessbase przez Holendra Fransa Morscha i uruchomiony na zwykłym komputerze PC z procesorem Pentium 90MHz wygrywa ósmą edycję World Computer Chess Championship w Hongkongu pokonując m.in. programy z platform: Cray, mainframe’owych komputerów IBM serii RS6000 i jeszcze wtedy prototypu Deep Blue.

W 1996 roku IBM kończy opracowywać komputer Deep Blue bazujący na superkomputerze RS/6000 SP z 30 procesorami PowerPC 604 “High 1” 120 MHz i 480 wyspecjalizowanymi procesorami szachowymi, opracowanymi w technologii VLSI (ang. Very Large Scale Integration – miliardy tranzystorów w układzie). W lutym tego roku dochodzi do pojedynku pomiędzy Deep Blue a szachowym mistrzem świata Garrim Kasparowem. Tytuł mistrza świata zostaje jednak obroniony, Kasparow wygrał rezultatem 4-2. IBM nie poddaje się, w 1997 opracowuje kolejną wersję komputera nazwaną Deeper Blue z podwojoną mocą obliczeniową (zastosowano 30 procesorów PowerPC 604e “High 2” 200 MHz) pozwalającą na analizę 200 milionów pozycji szachowych na sekundę. Tym razem lepszy okazuje się komputer. Garri Kasparow przegrywa pojedynek rezultatem 3,5-2,5. Tym sposobem w roku 1997 komputer ostatecznie w normalnym turniejowym pojedynku pokonuje szachowego mistrza świata. Od tego czasu minęło już 25 lat, komputery stały się jeszcze szybsze, algorytmy bardziej rozwinięte, do tego doszły elementy związane sieciami neuronowymi, uczeniem się maszyn (Machine Learning), przetwarzaniem równoległym itd. Dla dzisiejszych programów szachowych uruchamianych na naszych zwykłych komputerach wygranie nawet z mistrzem świata nie jest już szczególnym wyzwaniem.

***

A jak komputerowe programy szachowe działają? Jak analizują jaki ruch wybrać? Jak oceniają sytuację? Co tam się w środku dzieje i co jest potrzebne aby program mógł grać w szachy? Postaramy się odpowiedzieć na to pytanie. Potrzebnych jest przynajmniej kilka elementów:

1. Reprezentacja wewnętrzna planszy – komputer musi mieć wewnętrzną reprezentację planszy szachowej i zgodnych z zasadami ruchów.
2. Interfejs użytkownika – kolejnym potrzebnym elementem jest interfejs do komunikacji z użytkownikiem, decydujący o tym czy będzie się grało wygodnie i przyjemnie. Może to być ekran komputerowy, klawiatura lub myszka, ale może to być też szachownica z sensorami w przypadku komputerów szachowych.
3. Księga otwarć – będąca istotnym elementem. Komputer analizując określone ruchy przeciwnika i mając zapisane w swojej pamięci najpopularniejsze otwarcia szachowe, jest w stanie odpowiednio reagować i nie potrzebuje do tego dużej ilości obliczeń, a po za tym jest w stanie odpowiedzieć prawidłowo na bardziej “strategiczny” sposób gry przeciwnika a dodatkowo jest w stanie rozpocząć grę poruszając się białymi.
4. Wyszukiwarka najlepszych posunięć. Tu sytuacja zaczyna się komplikować bo ilość potrzebnych obliczeń może znacząco wzrosnąć. Algorytmów możliwych do zastosowania jest sporo, ja przedstawię tylko dwa najprostsze:
   Algorytm Minimax:
   Zacznijmy od reprezentacji wartości punktowej figur szachowych, przyjmijmy następujące wartości:
   

   Kolejnym krokiem jest analiza możliwych ruchów do kilku poziomów w dół w zależności od mocy obliczeniowej maszyny. Weźmy hipotetyczny przykład i zastosujmy dwa poziomy analizy możliwych ruchów. Po narysowaniu grafu możliwych sytuacji rozpoczynamy analizę od najniższego poziomu. W naszym przypadku jest to ruch przeciwnika dlatego poszukujemy najniższej możliwej wartości punktacji na danej gałęzi.

   

   Na lewej dolnej gałęzi najniższą punktację ma skrajna prawa sytuacja gdzie tracimy gońca, a zatem uzyskaną dla tego zdarzenia wartość -80 przenosimy o poziom wyżej. Na prawej gałęzi wszystkie punktacje są równe i wynoszą -50, a zatem tę wartość, jako najniższą przenosimy o poziom wyżej.
   Na wyższym poziomie mamy nasz ruch (białe), a zatem szukamy maksymalnej na tej gałęzi wartości, w naszym przypadku jest to -50, które przenosimy o poziom wyżej i z działania algorytmu wychodzi, że najkorzystniejszym ruchem jest zbicie czarnego gońca. Przy następnym ruchu wykonujemy podobną analizę. Jeżeli bardziej rozbudujemy poziomy analizy to musimy pamiętać, iż na przemian będziemy mieli poziomy Min i Max, gdzie będziemy szukać odpowiednio wartości najniższych i najwyższych i te wartości przenosić poziom wyżej.
   Analiza tego typu nazywa się analizą wyczerpującą (ang. Exhaustive Search) nazywaną także metodą siłową (ang. Brute Force) i polega na sprawdzeniu wszystkich, na które pozwala moc obliczeniowa sytuacji.

   Algorytm Alpha-Beta
   Aby zmniejszyć złożoność obliczeniową algorytmu Minimax wspomniany wcześniej John McCarthy zaproponował jego modyfikację nazwaną Alpha-Beta Pruning. W naszym przypadku jego działanie polega na zaprzestaniu dalszej analizy lewej gałęzi, ponieważ po znalezieniu w niej wartości -80, dalsza analiza nie ma już sensu bo i tak ta gałąź zostanie odrzucona wobec wartości -50 z prawej gałęzi, po prostu na wyższym poziomie, oznaczonym żółtym kolorem, szukamy wartości Max, a zatem wchodzenie w obliczenia czegoś co i tak Max nie będzie nie ma sensu.

   

   Zysk w zmniejszeniu złożoności obliczeniowej przy dużej liczbie poziomów jest ogromny –  przy Minimax liczba możliwych gałęzi do przeanalizowania wynosi b^n (gdzie ‘b’ to założona liczba ruchów w danym węźle a ‘n’ to głębokość analizy), natomiast przy Alpha-Beta Pruning jest to już tylko: b^⌈n/2⌉ + b^⌊n/2⌋ – 1, przy b =40 mamy:

   głębokość n	b^n	b^⌈n/2⌉ + b^⌊n/2⌋ – 1
   0	1	1
   1	40	40
   2	1,600	79
   3	64,000	1,639
   4	2,560,000	3,199
   5	102,400,000	65,569
   6	4,096,000,000	127,999
   7	163,840,000,000	2,623,999
   8	6,553,600,000,000	5,119,999

5. Aby program działał lepiej każda pozycja figury na szachownicy może otrzymać swoją dodatkową punktację, promującą określone pozycje, np. Hetman ma następującą punktację w zależności od swojej pozycji:

   -20,-10,-10, -5, -5,-10,-10,-20,
   -10,  0,  0,  0,  0,  0,  0,-10,
   -10,  0,  5,  5,  5,  5,  0,-10,
    -5,  0,  5,  5,  5,  5,  0, -5,
     0,  0,  5,  5,  5,  5,  0, -5,
   -10,  5,  5,  5,  5,  5,  0,-10,
   -10,  0,  5,  0,  0,  0,  0,-10,
   -20,-10,-10, -5, -5,-10,-10,-20

   Widać tu zdecydowanie, że dla Hetmana pola centralne planszy szachowej są zdecydowanie lepiej punktowane niż skrajne. Innym przykładem może być skoczek:

   -50,-40,-30,-30,-30,-30,-40,-50,
   -40,-20,  0,  0,  0,  0,-20,-40,
   -30,  0, 10, 15, 15, 10,  0,-30,
   -30,  5, 15, 20, 20, 15,  5,-30,
   -30,  0, 15, 20, 20, 15,  0,-30,
   -30,  5, 10, 15, 15, 10,  5,-30,
   -40,-20,  0,  5,  5,  0,-20,-40,
   -50,-40,-30,-30,-30,-30,-40,-50,
   
   

   Ciekawą punktację ma wieża:

     0,  0,  0,  0,  0,  0,  0,  0,
     5, 10, 10, 10, 10, 10, 10,  5,
    -5,  0,  0,  0,  0,  0,  0, -5,
    -5,  0,  0,  0,  0,  0,  0, -5,
    -5,  0,  0,  0,  0,  0,  0, -5,
    -5,  0,  0,  0,  0,  0,  0, -5,
    -5,  0,  0,  0,  0,  0,  0, -5,
     0,  0,  0,  5,  5,  0,  0,  0

   Goniec raczej wygląda bardziej klasycznie:

   -20,-10,-10,-10,-10,-10,-10,-20,
   -10,  0,  0,  0,  0,  0,  0,-10,
   -10,  0,  5, 10, 10,  5,  0,-10,
   -10,  5,  5, 10, 10,  5,  5,-10,
   -10,  0, 10, 10, 10, 10,  0,-10,
   -10, 10, 10, 10, 10, 10, 10,-10,
   -10,  5,  0,  0,  0,  0,  5,-10,
   -20,-10,-10,-10,-10,-10,-10,-20,

   Pion wygląda dosyć osobliwie:

    0,  0,  0,  0,  0,  0,  0,  0,
   50, 50, 50, 50, 50, 50, 50, 50,
   10, 10, 20, 30, 30, 20, 10, 10,
    5,  5, 10, 25, 25, 10,  5,  5,
    0,  0,  0, 20, 20,  0,  0,  0,
    5, -5,-10,  0,  0,-10, -5,  5,
    5, 10, 10,-20,-20, 10, 10,  5,
    0,  0,  0,  0,  0,  0,  0,  0

   A sam król ma następującą punktację (w środku gry):

   -30,-40,-40,-50,-50,-40,-40,-30,
   -30,-40,-40,-50,-50,-40,-40,-30,
   -30,-40,-40,-50,-50,-40,-40,-30,
   -30,-40,-40,-50,-50,-40,-40,-30,
   -20,-30,-30,-40,-40,-30,-30,-20,
   -10,-20,-20,-20,-20,-20,-20,-10,
    20, 20,  0,  0,  0,  0, 20, 20,
    20, 30, 10,  0,  0, 10, 30, 20

   natomiast pod koniec partii wartości związane z pozycją króla przybierają następując wartości:

   -50,-40,-30,-20,-20,-30,-40,-50,
   -30,-20,-10,  0,  0,-10,-20,-30,
   -30,-10, 20, 30, 30, 20,-10,-30,
   -30,-10, 30, 40, 40, 30,-10,-30,
   -30,-10, 30, 40, 40, 30,-10,-30,
   -30,-10, 20, 30, 30, 20,-10,-30,
   -30,-30,  0,  0,  0,  0,-30,-30,
   -50,-30,-30,-30,-30,-30,-30,-50

6. Kolejnym elementem jest tzw. księga końcówek, jej zastosowanie pozwala komputerowi na efektywne zakończenie partii.

Takim sposobem poznaliśmy 6 podstawowych elementów w jaki powinien być wyposażony przyzwoity program szachowy. 🙂

Oczywiście przedstawione elementy to tylko mały czubek góry lodowej. Szachowe algorytmy mogą być naprawdę dużo bardziej skomplikowane, ale nie będziemy już intensywniej zgłębiać tego tematu, bo zrobi nam się podręcznik do programowania. 🙂 Jeżeli ktoś chciałby jednak wejść głębiej w ten temat to polecam portal chessprogramming.org jako doskonałe kompendium wiedzy w tym zakresie. Polecam także dwie książki.  Pierwsza autorstwa Feng-Hsiung Hsu, zaangażowanego w prace nad maszynami DeepThought i DeepBlue, to – “Behind Deep Blue”. Druga natomiast to polecona mi przez kolegę – Michała, miłośnika szachów (którego serdecznie pozdrawiam 🙂 ) – “Ostatni Bastion Umysłu” autorstwa Garriego Kasparowa. A że zbliżają się Mikołajki, więc może warto jeszcze szybko napisać list do Św.Mikołaja, oczywiście nie zapominając dodać, że byliśmy bardzo grzeczni i tę dziurę w ścianie, którą szpachlujemy od 2 lat na pewno przed Świętami naprawimy, oraz że szuflada z dokumentami także przed Świętami zostanie uporządkowana. 😉

***

Czas kończyć nasz dzisiejszy wpis, który zrobił się naprawdę obszerny, ale temat okazał się ogromny. Jak zacząłem go “skrobać” robiąc research, to pod pierwszą warstwą pojawiały się kolejne fascynujące pokłady informacji. Jeżeli nie graliście jeszcze w szachy to bardzo polecam tę grę, a jeżeli kiedyś graliście, to może czas pomyśleć o powrocie? Jest wiele serwisów internetowych, gdzie można pouczyć się gry w szachy za pomocą darmowych lekcji i zagrać zarówno z komputerem jak i człowiekiem, tym ostatnim z dowolnego miejsca na Ziemi, pod warunkiem, że jest tam Internet. Trzymajcie się ciepło! 🙂

p.s. Serdeczne podziękowania dla Mike’a Wattersa za udostępnienie zdjęć! 🙂