//
JAK”MYŚLI” PROGRAM?

Celowo użyłem cudzysłów ponieważ jak większość czytelników zapewne wie, żadne programy nie myślą(co nie znaczy ,że kiedyś nie będą myśleć J) choć trzeba przyznać programistom ,że nauczyli je trochę emulować umysł ludzki w królewskiej grze. Skoro jednak  program nie myśli podobnie jak człowiek to jak się dzieje ,że gra tak jak człowiek a nawet lepiej. W skrócie można by powiedzieć ,że silnik szachowy wykonuje pewne ,ustalone przez programistę sekwencje poleceń obliczeniowych według konkretnej „receptury” ustalonej na bazie odpowiednich modeli matematycznych, oraz dorobku wieloletniej teorii i praktyki szachowej .
Niezbędnym elementem struktury każdego silnika szachowego jest moduł implementacji zasad gry, który zawiera bitową mapę danych dzięki której program „widzi” szachownicę a dokładniej wirtualna szachownica zostaje zamieniona na kod używany przez program. W tym module zawarte są takie informacje jak:

  • lista i położenie poszczególnych bierek
  • która strona  jest na posunięciu
  • stosunek dotychczasowego przebiegu partii do zasady 50 posunięć (dla przypomnienia mówi ona o tym ,że jeśli w partii nie nastąpiło bicie ani żaden ruch pionem w ciągu ostatnich 50 posunięć następuje automatyczny remis)
  • możliwość wykonania roszady przez obie strony
  • możliwość wykonania bicia w przelocie

Drugą niezwykle ważną częścią tego modułu jest generator posunięć, który dostarcza silnikowi informacji o tym jakie możliwe są posunięcia w danej pozycji. Od szybkości działania generatora w znacznej mierze zależy optymalizacja działania całego programu gdyż funkcja przeszukująca drzewa wariantów musi do każdej analizowanej pozycji uzyskać od generatora informacje o możliwych posunięciach aby kontynuować przeszukiwania drzewa.
Bazą działania każdego programu szachowego jest algorytm min-max , który polega na tym ,ze obie strony wykonują ruchy, które najbardziej oddalają je od porażki a przybliżają do zwycięstwa. Nawet jeśli przegrana jest nieunikniona program będzie wykonywał posunięcia które oddalają go od niej.  Jeśli więc silniki będą grać do końca i na szachownicy zostanie np. oprócz króli tylko hetman białych, to będą one wykonywać posunięcia które najszybciej doprowadzą do mata zaś czarne odpowiadać będą tak aby jak najbardziej oddalić przegraną.
Najprostsza metodą pisania silników jest  algorytm brute force czyli siły brutalnej w której maszyna liczy wszystkie możliwe ruchy do ustalonej liczby posunięć czyli głębi przeszukiwań drzewa wariantów zależnej od mocy obliczeniowych i czasu jaki jej damy, a następnie każdemu wariantowi prowadzącemu do określonej pozycji nadaje wartość i   wybiera ten najlepszy o najwyższej przypisanej wartości. Metoda ta choć daje nam pewność ,że program wybierze w miarę swoich możliwości najlepszy ruch ma jednak sporo wad ponieważ ilość drzew wariantów rośnie bardzo szybko wraz z kolejnymi ruchami zakładając ,że w przeciętnej pozycji można wykonać ok.32 posunięcia  przeciwnik może również odpowiedzieć na ok. 32 różnych sposobów, w ten sposób jak łatwo sobie wyobrazić po kilku posunięciach liczba drzew wariantów osiągnie potężne wartości a to wciąż za mało żeby grać na poziomie mistrzowskim. Bo liczenie kilku posunięć do przodu nie jest większym problemem dla średniozaawansowanego amatora szachów. Po za tym licząc wszystko silnik niepotrzebnie marnuje czas i swoje moce obliczeniowe na warianty prowadzące do przegranej pozycji np. bezpodstawne ofiarowanie  figur, monotonne ruchy jedną figurą  itp.
Posługując się prostym porównaniem  należałoby stwierdzić ,że konieczne jest oddzielenie ziarna od plew aby uzyskać lepsze rezultaty pracy programu. Algorytm oparty na tym założeniu odkrył John McCarthy w 1956 roku, nazwano go algorytmem cięć alfa-beta, z grubsza ujmując jego działanie polega na blokowaniu obliczeń danego wariantu jeśli pojawił się wariant lepszy. Na przykład liczymy kilka wariantów: w jednym prowadzimy równą grę w drugim wygrywamy na czysto pionka a w trzecim gońca, obliczenia wariantu prowadzącego do równej gry zahamujemy gdy zobaczymy kontynuację wygrywającą pionka ,ale i ten odrzucamy w chwili gdy obliczymy ,że w kolejnym drzewie wariantu zdobywamy na czysto skoczka. Koncentrujemy się na rozwijaniu tej właśnie trzeciej gałęzi. Przekładając to na język programu, silnik zaprzestaje obliczeń wariantu ,prowadzącego do pozycji której funkcja oceniająca przypisała wartość np. 1.24, jeśli w toku obliczeń w tej samej głębi posunięć pojawi się wariant dzięki któremu uzyskano pozycję o wartości większej od 1.24, przy czym wartość ta nie musi być dokładnie precyzowana na tym etapie poszukiwań wystarczy ,że jest po prostu większa.
Algorytm alfa-beta wykorzystuje różne inne techniki przydatne do selektywnego przeszukiwania drzewa wariantów do jednej z nich należy pogłębianie iteracyjne. Polega ono na tym ,że program liczy warianty w pewnej ustalonej kolejności od najlepszych po najsłabsze, początkowo odbywa się to w niewielkiej głębokości posunięć, wybierane są warianty najbardziej obiecujące, następnie wybrane kontynuacje z racji tego ,że jest ich mniej podlegają dalszej pogłębionej analizie dzięki czemu mogą być odrzucone, gdyż w perspektywie większej głębi posunięć okazały się słabe lub dopuszczone do  dalszych analiz w wyniku których zostaje wybrany optymalnie dla programu najlepszy wariant. Takich iteracji ,które można porównać do selekcji  może być kilka w zależności od możliwości programu ,konfiguracji sprzętowej komputera oraz czasu trwania partii  . To rozwiązanie eliminuje sporo gałęzi które nie muszą być dalej pogłębiane gdyż prowadza do ewidentnie złych czy nawet przegranych pozycji, dzięki tej funkcji moc obliczeniowa procesora może być znacznie bardziej efektywnie wykorzystana.
Obok pogłębiania iteracyjnego stosuje się tak zwane tablice ruchów zabójców (z ang. killer move), są to posunięcia które w danym drzewie wariantu spowodowały na tej samej głębokości odrzucenie innych gałęzi, czyli  „ruch zabójca” z racji swojej dużej wartości likwiduje inne gałęzie . W analizie partii szachowej dokonywanej przez ludzi moglibyśmy powiedzieć ,że jest (lub są to) posunięcie ,które prowadzi do obalenia analizowanego wariantu ,gdyż znaleziono posunięcie lepsze. Jeśli takie posuniecie jest na tyle dobre ,że obala dany wariant i zmusza nas do poszukiwania lepszego to silnik je zapamiętuje i dzięki temu kolejne gałęzie wariantów mogą być liczone od tego właśnie posunięcia które może spowodować ,że inny wariant będzie lepszy.
Late move reduction (z ang. redukcja późniejszych posunięć czyli rozpatrywanych w następnej kolejności) to kolejna metoda selektywnego przeszukiwania drzew wariantów w której priorytetowo traktowane są te posunięcia które rokują najlepiej, one są liczone w pierwszej kolejności kosztem redukcji obliczeń pozostałych. Oczywiście warianty słabsze  nie są całkowicie pomijane ale maleje ich głębokość poszukiwań.
W programowaniu silników szachowych stosuje się również niedozwolone w normalnej grze puste posunięcia lub inaczej zezwolenie stronie przeciwnej na wykonanie dwóch posunięć naraz. Jeśli bowiem w rozpatrywanym wariancie pusty ruch odcina inne gałęzie, to z dużym prawdopodobieństwem znajdziemy ruch już normalny ,który doprowadzi do tego samego efektu, gdyż w przeważającej większości przypadków wykonywanie posunięcia jest korzystniejsze niż wstrzymanie się od niego (choć tylko w teorii bo w praktyce jak wiadomo jest to zabronione). W tym przypadku program wraca do korzenia wariantu bez uruchamiania generatora posunięć co oszczędza czas i moc obliczeniową. Ale spokojnie, żaden prawidłowo napisany silnik nie poprosi nas o tu żebyśmy wykonali dwa posunięcia, a co się dzieje w krzemowych zakamarkach to już inna sprawa.
Jak powszechnie wiadomo w szachach aby uzyskać konkretną pozycje nie koniecznie trzeba trzymać się ustalonej sekwencji posunięć. Tłumacząc z polskiego na nasze aby dojść do określonej pozycji można zagrać różne warianty, ważne aby schodziły się one w jednym miejscu. Jest wiele debiutów, które zaczynają się w sposób charakterystyczny dla np. obrony sycylijskiej a potem dochodzi do teoretycznej pozycji znanej z obrony francuskiej, mówimy wtedy ,że zawodnicy grali obronę francuską z przestawieniem posunięć. W programach  szachowych nazywa się to tablicą transpozycji i jest to zbiór pozycji ,które już silniki obliczył i przypisał im odpowiednią ocenę, wraz z wariantami prowadzącymi do niej. Dzięki temu program już nie musi liczyć po raz kolejny innego drzewa które prowadzi do tej samej , już ocenionej pozycji, a to oczywista oszczędność czasu. Tablice te mają określony rozmiar żelazny od parametrów silnika oraz pamięci operacyjnej  którą dysponuje nasz komputer najczęściej jest to 128-512 kB. Gdy pamięć się już zapełni pozycjami, starsze tablice są usuwane aby zrobić miejsce dla nowszych.
Najwięcej „wysiłku” jak nie trudno się domyślić program wkłada na początku partii gdyż wówczas jest największa ilość figur i możliwych posunięć a przede wszystkim jak twierdzą eksperci wynik wielu partii zależy od rozegrania debiutu. Gdybyśmy zaprzęgli do gry  dwa silne  programy (choć program może grać równie dobrze sam z sobą) i kazali im grać klasycznego blitza czyli każdemu dalibyśmy 5 min do namysłu to zauważymy ,że na pierwszy ruch niektóre silniki zużywają nawet 20-25 sekund. Dla szachisty „pykającego” na kurniku szybkie partie to oczywista strata czasu ponieważ zna on podstawowe debiuty(które zwykle grywa) przynajmniej do kilku posunięć. Niestety „goły”  program szachowy nie zna wieloletniego  dorobku teorii szachowej w kwestii debiutów i traktuje pierwsze posunięcie jak każde inne. Można oczywiście tę sytuację zmienić dołączając do silnika tak zwaną książkę debiutów. Jest to nic innego jak rodzaj ściągi, która podpowiada silnikowi jaki debiut wybrać, niektóre warianty są opracowane nawet do 25 posunięć i więcej, do każdej pozycji jest zapisana jej wartość a więc program nie musi już tego przeliczać, tylko gra automatycznie wybierając warianty ,których prawdopodobieństwo użycia będzie największe, co nie znaczy oczywiście ,że nie zagra inaczej ale ten boczny wariant będzie miał mniejsze szanse na wybór. Podobna sytuacja jest w świecie ludzkich szachów najczęściej białymi grywa się 1.e4 lub 1.d4 , rzadziej 1.c4 czy 1.Sf3 a tylko sporadycznie 1.f4 czy 1.b4 oczywiście mówimy o partiach granych na  profesjonalnym poziomie bo tylko takie są brane pod uwagę przy tworzeniu książki debiutów.
W grze końcowej silnik może się też wspomagać tablicami końcówek, są to zapisane w pamięci komputera wszystkie możliwe pozycje z określoną liczbą figur na szachownicy oraz warianty prowadzące w tych końcówkach do mata lub remisu, jeśli program je wykorzystuje praktycznie po pojawieniu się określonej liczby figur nie musi już oceniać danej pozycji gdyż ocenę tę zawierają tablice. Bez tablic końcówek na przykład większość słabszych programów nie potrafi matować skoczkiem i gońcem a nawet światowa czołówka ma z tym problemy, będę zresztą poruszał to zagadnienie nieco później.  Wielkość tablic końcówek jest ograniczona gdyż są one bardzo pamięciochłonne, tablice z pięcioma figurami zajmują ok. 8 GB zaś z sześcioma już 1200 GB czyli używanie ich na standardowym komputerze domowym jest praktycznie niemożliwe tablice z 7 bierkami dopiero są w opracowaniu i zajmą trudną do wyobrażenia liczbę pozycji. Do niedawna standardem były Tablice Nalimova, obecnie jednak wraz z gwałtownym rozwojem silników dostępnych bez żadnych opłat autorzy coraz częściej stosują również darmowe Tablice Gaviota.

Poniższy schemat przedstawia uproszczoną strukturę typowego silnika szachowego

Funkcja oceny pozycji jest to niezbędny w każdym silniku szachowym element, decydujący w znacznym stopniu o tym z jaka siłą będzie grał program. Ocena pozycji choć jest rzeczą subiektywną odgrywa poważną rolę w podejmowaniu decyzji co do dalszej gry i tworzenia nowych gałęzi wariantów. W zasadzie można powiedzieć ,że ocena pozycji szachowej to pewna część wiedzy szachowej zdobywanej i nieustannie rozwijanej od kilkuset lat złożona z takich elementów jak teoria debiutów, gra końcowa, taktyka i strategia szachowa itd. Ta olbrzymia wiedza, która zawarta jest w setkach książek szachowych oraz milionach rozegranych partii decyduje o sile gry człowieka, oczywiście w toku treningu szachowego profesjonalny zawodnik nie musi jej zgłębić w całości, ale musi poznać jej najważniejsze elementy. Podobnie jest z programem, aby mógł dobrze grać powinien dobrze ocenić pozycję i tutaj do roboty nie wystarczy już sprawny programista potrzebny jest jeszcze silny szachista aby podpowiedzieć temu drugiemu jak „nauczyć” program prawidłowej oceny pozycji. Ocena pozycji na szachownicy składa się z dwóch zasadniczych elementów : oceny materialnej i pozycyjnej.

Ocena materialna polega na tym ,że przypisuje się  figurom i pionkom będącym w dyspozycji obu stron odpowiednie wartości najczęściej wygląda to tak:

Pionek -1
Skoczek , goniec – 3
Wieża – 5
Hetman – 9
Król – w niektórych sytuacjach podaje się bardzo dużą wartość np. 200

Wartości te dotyczą białych bierek, czarne będą liczone identycznie ale ze znakiem „minus”. Jeśli zatem silnik oceni nam pozycję na +2 , będzie to oznaczać ,że białe mają przewagę odpowiadającą przewadze dwóch pionów na czysto bez żadnej rekompensaty. Jeśli zaś poda wartość np. -0.83 w tej sytuacji czarne mają nieznaczną przewagę ale mniejszą niż jeden pion w ujęciu materialnym.
Sprawa jednak zaczyna się komplikować gdy weźmiemy pod uwagę konkretną pozycje tutaj do gry wchodzi ocena pozycyjna bardzo subtelna, niełatwa do określenia i często zależna od stylu gry danego szachisty. Wiemy np. ,że w pozycjach otwartych para gońców z reguły jest lepsza niż para skoczków lub skoczek z gońcem.  Wówczas nasze gońce mogą mieć wartość np. 3.2 (przypomina się stare powiedzenie niektórych szachistów „para gońcy cię wykońcy”)  , jeśli natomiast goniec w pozycji zamkniętej jest zablokowany i zupełnie nieaktywny w grze ,jego ocena wartości materialnej może nawet spaść do 1.5. Pionek z kolei w pozycji wyjściowej ma wartość jeden, ale w końcówce wszak im mu bliżej do ostatniej linii tym jest groźniejszy a wiec z każdym ruchem do przodu jego wartość powinna rosnąć, w pewnym momencie i specyficznej pozycji  może nawet przekroczyć wartość wieży. Oczywiście takich subtelności jest znacznie więcej np. ocena pozycji króla, pionki wolne, izolowane, zdublowane, struktura centrum, współpraca figur, wiązania itp. Ileż to pozycji znanych chociażby z zadań szachowych wygląda materialnie na miażdżącą przewagę a realnie prowadzą one do remisu lub nawet porażki mocniejszej materialnie strony. Do obliczania wartości konkretnej pozycji stosuje się też wagi które odpowiadają za to jakie znaczenie silnik nada odpowiednim cechom bierek, w danej sytuacji na szachownicy np. biały król w centrum w końcówkach pionowych to silna strona pozycji białych, ale taka marszruta w grze środkowej to już niemal pewna porażka.
Wszystko tkwi w złożoności obliczeniowej szachów i cechach charakterystycznych danej pozycji, dlatego też ten element silnika jest najtrudniejszy do zaprogramowania i ciągle udoskonalany po przez testowanie odpowiednich wartości funkcji oceniającej. O błędach w ocenie pozycji przez silniki szachowe będzie jeszcze mowa w dalszej części tego rozdziału.
Spróbujmy się teraz skoncentrować na różnicach w grze człowieka i silnika szachowego, wiemy już w jaki sposób program przeszukuje drzewo i z jakich dodatków może korzystać. Silny szachista bo takich będziemy teraz brać pod uwagę, ma pewien zasób wiedzy szachowej popartej doświadczeniem, potrafi sie uczyć również na własnych i cudzych błędach oraz w przyszłości stara się ich unikać. Program jak już wspomnieliśmy nakazuje procesorowi wykonywać pewną sekwencję poleceń i obliczeń zapisanych w kodzie. Silnik ma zapisaną pewną mapę bitową która jest jakby cyfrową i czysto wirtualną szachownicą, generator posunięć podaje po każdym półruchu kolejne możliwe posunięcia, moduł przeszukujący drzewa współpracując z funkcją oceny pozycji wybiera najkorzystniejsze posunięcia.  Człowiek patrzy na szachownicę inaczej ,ma zapisane w mózgu pewne schematy myślowe i setki pozycji podobnych z którymi miał już do czynienia. Selekcja posunięć które człowiek bierze pod uwagę odbywa się zupełnie inaczej gdyż są posunięcia i warianty których w ogóle nie bierze pod uwagę, ponieważ tak mu podpowiada logika i doświadczenie nabyte przy szachownicy. W debiucie jak wiemy liczy się teoria, każdy dobry szachista musi mieć książkę debiutów w głowie, nie wszystkich oczywista ale tych które grywa białymi i tych na które musi odpowiedzieć czarnymi, program może choć nie musi używać takiej książki w tym wypadku może dokładniej byłoby napisać bazy otwarć debiutowych. W grze środkowej gdzie decyduje już taktyka i strategia szachowa program pokazuje swoje mocne strony zwłaszcza w obliczeniach wariantów skomplikowanych i czasochłonnych dla człowieka. Końcówki to również znajomość pewnych schematów i reguł które nimi rządzą,  dobry szachista taką wiedzę posiada,  zaś program nadrabia to swoimi możliwościami obliczeniowymi, lub też korzysta z tabel gry końcowej musimy pamiętać bowiem, że gdy na szachownicy jest mniejsza liczba figur i pozycja ulega uproszczeniom silnik ma mniej roboty a zatem może liczyć głębiej uruchamiając kolejne iteracje. Naturalną cechą ludzkiego umysłu , jest to że człowiek wyciąga pewne konsekwencje ze swoich porażek i wychodzą mu one raczej na korzyść w przyszłych partiach, program natomiast tej możliwości póki co jest pozbawiony, ale przecież to człowiek pisze kod programu i może go w każdej chwili poprawić analizując jego  partie.
Warto jeszcze kilka słów poświecić na tak zwany horyzont obliczeń, otóż są sytuacje na szachownicy , których program nie jest w stanie dostrzec gdyż jego głębokość poszukiwań nie jest wystarczająca natomiast człowiek znając pewne schematy widzi jak będzie wyglądała ,mniej więcej pozycja za np. 15 posunięć, gdy zagra jakiś wariant prowadzący do forsownych wymian, zdarza się czasem tak ,że  program podaje ocenę pozycji na 5.0 czyli zdecydowana wygrana a pozycja na szachownicy jest remisowa gdyż strona mająca przewagę w żaden sposób nie może przebić się przez obronę przeciwnika, człowiek zaproponuje remis ,program będzie grał na upartego bo ciągle funkcja oceny pozycji będzie mu podpowiadała między 4.5 a 5.5, oczywiście nie ma to żadnego wpływu na wynik partii bo i tak po np. trzykrotnym powtórzeniu posunięć będzie automatyczny remis, ale ocena programu może być błędna.

Dyskusja

Brak komentarzy.

Dodaj komentarz

Kategorie