Jeśli obaj gracze wybierają najlepsze posunięcia, to warcaby muszą
skończyć się remisem. Tak jak w najprostszej wersji gry w kółko i
krzyżyk. Wynik nie zależy od tego, czy pierwsze zaczną białe, czy
czarne piony - dowodzi w "Science" Jonathan Schaeffer, profesor
Uniwersytetu Alberty w Kanadzie. - To najbardziej skomplikowana gra,
która została rozpracowana przez komputer - komentuje David Levy,
prezydent Międzynarodowego Stowarzyszenia Gier Komputerowych w
Londynie.
Jego umysłem zawładnęły bity
Jonathan Schaeffer poświęcił rozpracowaniu warcabów prawie całe naukowe
życie. Sam za młodu grał w szachy, jako junior doszedł do tytułu
mistrza. Potem przez lata 80. zeszłego wieku próbował stworzyć
komputerowy program, który w szachach pokona człowieka. Bez sukcesów.
Jego algorytm był ledwie przeciętny. Nie tylko ludzie, lecz także
konkurencyjne programy grały lepiej.
I kiedy wydawało się, że jego kariera zjechała na ślepy tor, szczęśliwy
przypadek przestawił zwrotnicę. W 1989 r. jeden z kolegów zapytał przy
obiedzie Schaeffera o warcaby. Jak komputery radzą sobie z tą -
prostszą od szachów - grą?
Schaeffer niewiele wiedział o warcabach. Wśród programistów uchodziły
za grę, która już dawno temu została rozpracowana. Ale kanadyjski
naukowiec szybko odkrył, że to nieprawda. Rzeczywiście, w 1963 r.
sensację wzbudził program Arthura Samuela, napisany na maszynie IBM (w
tamtych czasach wielkości szafy), który pokonał świetnego ponoć gracza
Roberta Nealeya. Ta potyczka - może za sprawą służb prasowych IBM -
urosła niemal do rangi mitu. Od tamtej pory przyjęło się bowiem uważać,
że komputery umieją doskonale grać w warcaby, choć Nealey wcale nie był
wirtuozem tej gry, ledwie mistrzem stanu Connecticut w USA. W dodatku
przegrał, bo dał się wpuścić w doskonale znaną taktyczną pułapkę. Mimo
to kolejne generacje programistów zajęły się głównie szachami, uznając
ich prostszą kuzynkę za ograną.
Ta opinia była tak zakorzeniona, że Schaeffer, który postanowił
sprawdzić swoje siły w programach do warcabów, miał z początku kłopoty
z uzyskaniem pieniędzy na badania. - Po co wyważać otwarte drzwi? -
pytano.
Zresztą wydawało się, że o dobry program do tej gry faktycznie nie jest
trudno. Algorytm Schaeffera - najpierw zwany "bestią", a potem
Chinookiem (jak ciepły wiatr przypominający halny, który nawiedza
kanadyjskie Calgary) - już po dwóch miesiącach udoskonalania był tak
dobry, że pokonał jednego z byłych mistrzów Kanady. A jesienią 1989 r.
wygrał warcabową olimpiadę dla programów w Londynie.
Stary mistrz umiera niepokonany
Kiedy jednak Chinook trafił na najlepszych ludzkich graczy na świecie,
zaczął popełniać błędy i przegrywać. Nic dziwnego. Na planszy warcabów
piony mogą się znaleźć w ponad 500 trylionach (5 x 10^20) różnych
pozycji. W latach 90. ta ogromna liczba przerastała możliwości
obliczeniowe komputerów.
Program Schaeffera analizował konsekwencje każdego posunięcia na 27
ruchów do przodu. Jego atutem była do perfekcji opracowana końcówka.
Nie mógł się w niej pomylić. Korzystał z bazy danych, która zawierała
skutki wszystkich możliwych ruchów w sytuacji, kiedy na planszy
pozostały już ostatnie piony - początkowo tylko cztery, ale z czasem
więcej.
Dołożenie każdego kolejnego piona potęgowało jednak liczbę możliwych
końcowych posunięć. Do ich analizy naukowiec musiał zaprząc
kilkadziesiąt komputerów na raz, które pracowały bez przerwy całymi
latami. W szczytowym momencie na początku lat 90. grą w warcaby
zajmowały się co noc wszystkie komputery na jego uniwersytecie.
Codziennie, nawet podczas urlopu, Schaeffer nastawiał sobie budzik na
godz. 2 w nocy, by połączyć się z uczelnią i sprawdzić, czy obliczenia
idą zgodnie z planem. A jeśli zdarzyła się awaria - pojechać na
miejsce. Chinook stał się jego obsesją. I jak gorzko wspomina, żona nie
była tym zachwycona.
W 1992 r. Chinook był gotowy, by zmierzyć się z samym mistrzem świata.
Wtedy w amerykańskich warcabach dominował legendarny Marion Tinsley,
profesor matematyki i kaznodzieja. Od ponad czterech dekad praktycznie
niepokonany, gracz perfekcyjny. Na ponad tysiąc rozegranych w
turniejach partii przegrał ledwie trzy!
- Chinook został zaprogramowany przez Jonathana, ale ja miałem lepszego
programistę, Boga - mówił ufny w swe siły. I miał rację. Wprawdzie
zremisował z komputerem aż 34 partie i dwie przegrał (po raz pierwszy
od niepamiętnych czasów), ale cztery razy wygrał i nie stracił tytułu.
Dwa lata później doszło do rewanżu. W klasycznych warcabach każdy z
graczy przystępuje do gry z 12 pionami. Chinook dysponował już pamięcią
o wszystkich scenariuszach rozwoju sytuacji, kiedy na planszy pozostało
osiem pionów (brał pod uwagę prawie 500 mld ich możliwych ustawień). To
dawało mu wielką przewagę nad człowiekiem. Mimo to 67-letni Tinsley
zdołał zremisować sześć partii. Potem jednak nagle zapadł na zdrowiu,
oddał mecz walkowerem. Okazało się, że ma raka trzustki. Zmarł kilka
miesięcy później.
Kolej na pokera
Stary mistrz nie doczekał więc swego komputerowego pogromcy. Chinook
objął po nim panowanie w klasyfikacji amerykańskiej federacji warcabów,
ale nie był niezwyciężony. Zdarzało mu się przegrywać partie. Warcaby
wciąż nie dawały się ujarzmić, jakby składały daninę Tinsleyowi, który
zwykł mawiać: "Gra w szachy jest jak wpatrywanie się w bezbrzeżny
ocean, a warcaby to jak zaglądanie w bezdenną studnię".
Jednak w końcu prof. Schaeffer znalazł w nich dno. Jak pisze w
najnowszym "Science", wrócił do udoskonalania programu w roku 2001,
kiedy pojawiły się szybsze generacje procesorów. Dzięki nim
rozszyfrował wszystkie 40 bln scenariuszy gry z dziesięcioma pionami na
planszy (po skompresowaniu zajęły 237 gigabajtów pamięci). I
doprowadził do tego, że jego program już nie domyśla się, ale dokładnie
wie, który ruch jest najlepszy. Przy tym - raczej małostkowo - nie
omieszkał strącić z piedestału wielkiego przeciwnika: - Chinook jest
lepszy do Tinsleya, gdyż ten, jak wielkim by nie był, był tylko omylnym
człowiekiem.
Po warcabach prof. Schaeffer zabiera się za pokera (szachy pomija, bo
choć programy grają już w tą grę lepiej niż mistrzowie świata, to
całkowite rozgryzienie tryliona trylionów różnych pozycji na
szachownicy jest wciąż poza zasięgiem komputerów). Jego program Polaris
w przyszłym tygodniu zmierzy się z profesjonalnymi graczami Philem
Laakiem oraz Alim Eslamim. Stawką jest 50 tys. dol. - W warcabach czy
szachach cała sytuacja na planszy jest jawna, a w pokerze nie wiadomo,
jakie karty ma przeciwnik. Z punktu widzenia sztucznej inteligencji to
trudniejsza gra - mówi.
PS Na koniec trzeba zaznaczyć, że prof. Schaeffer rozpracowywał
warcaby w wersji angielskiej, w które gra głównie Ameryka i Wielka
Brytania (na szachownicy 64-polowej). W Polsce stosujemy nieco inne
zasady - np. bicie do tyłu nie jest zabronione, a damki mogą przesuwać
się o więcej niż jedno pole. Istnieje też odmiana sportowa - rozgrywana
na planszy o stu polach. Spodziewać się jednak należy, że i tu człowiek
nie ma szans z komputerem.
* Wszystko o warcabach (zasady gry, różne odmiany, nowinki):
http://www.warcaby.beep.pl/index2.html