Śladami Kempelena
Przegląd programów grających w szachy
Przemysław Grądalski
kwiecień 2001
Jak to naprawdę działa?
Z logicznego punktu widzenia szachy są grą mało skomplikowaną  reguły
są ściśle określone i stosunkowo proste. Rozgrywając partię szachową można
więc stosować następującą strategię: rozważamy wszystkie swoje posunięcia,
następnie posunięcia przeciwnika i tak na zmianę, aż uzyskany zostanie jeden
z trzech rezultatów  remis, wygrana lub porażka. Niestety liczba pozycji
przewijająca się przez tego typu  siłowe podejście jest tak duża, że dzisiaj
żaden komputer, więc tym bardziej człowiek, nie jest w stanie jej ogarnąć.
Wiadomo jednak, że sposób myślenia szachistów przebiega nieco inaczej
i jest zależny od siły gry. Generalnie polega to na tym, że przeglądane są
szczegółowo tylko posunięcia najbardziej obiecujące (subiektywny czynnik
oceny pozycji)), na zmianę dla białych i czarnych, z głębokością kilku (kil-
kunastu) ruchów do przodu. Tego typu strategii przeszukiwania komputer
trzeba nauczyć i w tym jest największy problem.
Każdy program szachowy powinien się składać, z grubsza mówiąc, z na-
stępujących funkcjonalnych części:
" sprawdzającej poprawność wykonywanych posunięć,
" oceniającej aktualną pozycję,
" zapamiętującej uzyskaną wiedzę na temat pozycji.
Opis każdej z części wymaga odpowiedniej reprezentacji figur, pozycji oraz
wiedzy na ich temat w języku zrozumiałym dla komputera. Taka reprezen-
tacja nie jest wygodna dla człowieka, ale dla maszyny jest niezbędna, gdyż
potrzebuje ona dokładnej, formalnej definicji rzeczywistości, w której ma się
poruszać.
1
Sprawdzanie poprawności posunięć
Pierwszym i najprostszym elementem programu szachowego jest część odpo-
wiedzialna za sprawdzanie poprawności wykonywanych posunięć. Związana
jest z tym konieczność odpowiedniego kodowania figur szachowych oraz ich
aktualnego położenia na szachownicy.
Kodowanie figur nie jest tak istot1ne i jest tutaj duża dowolność. Przykła-
dowo może ono wyglądać tak: 0  puste pole, 1(7)  biały (czarny) pionek,
2(8)  biały (czarny) skoczek, 3(9)  biały (czarny) goniec, 4(10)  biała
(czarna) wieża, 5(11)  biały (czarny) hetman, 6(12)  biały (czarny) król.
Szachownica zazwyczaj pamiętana jest w postaci tablicy dwuwymiarowej
(tabela 1). Wówczas polu d1 odpowiada wartość 14, polu b6 wartość 62, polu
g7 wartość 77, itd.
81 82 83 84 85 86 87 88
71 72 73 74 75 76 77 78
61 62 63 64 65 66 67 68
51 52 53 54 55 56 57 58
41 42 43 44 45 46 47 48
31 32 33 34 35 36 37 38
21 22 23 24 25 26 27 28
11 12 13 14 15 16 17 18
Tabela 1: Komputerowa reprezentacja szachownicy.
Dla wyżej opisanej reprezentacji początkowe ustawienie figur na szachow-
nicy przedstawia tabela 2.
10 8 9 11 12 9 8 10
7 7 7 7 7 7 7 7
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
4 2 3 5 6 3 2 4
Tabela 2: Kodowanie początkowego ustawienia figur.
Kolejnym krokiem jest opisanie komputerowi sposobu poruszania się fi-
gur po szachownicy. Przypuśćmy, że biały skoczek (2) stoi na polu c3 (33).
Wówczas może on skoczyć na pola: a2(21), a4(41), b1(12), b5(51), d1(14),
d5(54), e2(25), e4(45), tak jak zostało to przedstawione w tabeli 3.
2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 52 0 54 0 0 0 0
41 0 0 0 45 0 0 0
0 0 33 0 0 0 0 0
21 0 0 0 25 0 0 0
0 12 0 14 0 0 0 0
Tabela 3: Kodowanie ruchu skoczka.
Ogólnie ruchy skoczka stojącego na dowolnym polu x można zapisać wzo-
rem: x = x + r, gdzie x nowym polem skoczka, a r " {ą8, ą12, ą19, ą21}
reprezentuje możliwe skoki. Ważne jest, że przy przyjętym sposobie kodowa-
nia szachownicy ruch skoczka jest poprawny jedynie wówczas, gdy docelowe
pole x jest jedną z liczb z tabeli 1. W podobny sposób opisuje się ruchy dla
pozostałych figur.
Ostatnim krokiem jest uwzględnienie interakcji między poszczególnymi
figurami. Należy określić kiedy dane posunięcie może zostać wykonane, a kie-
dy nie. Istotne są tutaj takie szczegóły, jak szach, roszada, bicie pionkami,
itd. Reprezentacja tych informacji w formie zrozumiałej dla komputera nie
jest trudna, ale za to pracochłonna, bo wymaga rozważenia wielu czynników
równocześnie.
Ocena pozycji
Prawidłowa ocena pozycji jest kluczowa i ona tak naprawdę decyduje o sile
gry programu szachowego. Składa się na nią szereg czynników mniej lub bar-
dziej wymiernych, które w jakiś sposób trzeba przełożyć na język zrozumiały
dla maszyny. Należą do nich przewaga materialna oraz przewaga pozycyjna
(zajęte centrum, zajęte otwarte linie, przekątne, itp.).
Najprostszym pomysłem jest przypisanie wartości poszczególnym figu-
rom: pionek (100), skoczek (300), goniec (330), wieża (500), hetman (900),
król (20000). Takie podejście jest mniej więcej zgodne z naszymi intuicjami
- pionek jest najmniej wartościową figurą szachową, goniec jest nieznacznie
lepszy od skoczka, a król jest bezcenny. Dodatkowo z każdą z figur można
skojarzyć tablicę heurystyczną określającą premię punktową za ustawienie fi-
gury na danym polu. Ustawienie figury w centrum najczęściej oznacza dobrą
pozycję i liczone jest na plus. Przykładową tablicę heurystyczną dla białego
skoczka przedstawia tabela 4.
Ustawienie skoczka na polu d5(54) daje pozycję o 19 punktów lepszą niż
po ustawieniu go na polu h8(88).
3
-9 -7 -5 -4 -4 -5 -7 -9
-6 2 1 0 0 1 2 6
-4 3 6 8 8 6 3 -4
-4 6 8 10 10 8 6 -4
-5 2 6 7 7 6 2 -5
5 1 7 3 3 7 1 5
-8 -3 -1 -1 -1 -1 -3 -8
-9 -8 -7 -6 -6 -7 -8 -9
Tabela 4: Heurystyka ustawienia białego skoczka.
Ostateczna ocena pozycji jest sumą wszystkich wartości cząstkowych opi-
sujących pozycję białych pomniejszoną o odpowiednią wartość obliczoną dla
czarnych. Jasne jest, że wartość dodatnia oznacza lepszą pozycję dla białych,
a ujemna lepszą dla czarnych. Na jej podstawie program decyduje, którą
z możliwych kontynuacji ostatecznie wybrać.
Większość programów szachowych działa w zbliżony sposób, z tym że
uwzględniają one znacznie więcej czynników wpływających na ocenę danej
sytuacji. Te czynniki i przypisywane im znaczenie decydują o stylu i poziomie
prezentowanym przez program.
Zapamiętywanie pozycji
Właściwe przechowywanie wiedzy na temat pozycji mogących się pojawić
w czasie gry ma istotny wpływ na szybkość  myślenia programu. Informa-
cje te powinny być zapamiętywane w taki sposób, aby czas potrzebny do
sprawdzenia czy wiemy już coś na temat zaistniałej pozycji oraz na zapamię-
tanie nowej pozycji były minimalne. Strukturą danych posiadającą te wła-
sności i stosowaną w praktyce jest tzw. tablica haszująca (ang. hash-table).
Stąd niemal każdy program z czołówki światowej posiada możliwość określe-
nia pamięci RAM na nią przeznaczonej. Mniejszy rozmiar tablicy haszującej
wymaga od programu częstszego powtarzania tych samych obliczeń.
Podsumowanie
Jak widać konstrukcja programu szachowego jest dość skomplikowana, po-
mimo niewielkiej złożoności samej gry. Skorzystanie z wyżej zasugerowanych
rozwiązań i pomysłów pozwala na skonstruowanie własnego programu grają-
cego w szachy. Aby jednak mógł on skutecznie walczyć z najlepszymi, trzeba
się sporo napracować. Wzorem do naśladowania może być darmowy program
Crafty (patrz CHIP-CD) stworzony przez hobbystę, a grający tylko nieco
słabiej niż czołówka światowa.
4