Gazeta Wyborcza >  Artykuły

A A A Wyślij     Wydrukuj     Podyskutuj na forum Gazeta Wyborcza RSS

Z komputerem już nie wygrasz w warcaby

Piotr Cieśliński
2007-07-20, ostatnia aktualizacja 2007-07-20 12:46

Dzisiejsze "Science" prezentuje program, który nigdy nie przegrywa w warcaby. Człowiek może z nim co najwyżej zremisować, jeśli oczywiście nie popełni jakiegoś ludzkiego błędu

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

* Zagraj z Chinookiem: http://www.cs.ualberta.ca/~chinook