\documentclass[a4paper,11pt,titlepage]{report}

\usepackage{makeidx}
\usepackage{latexsym}
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{polski}

\usepackage{fancyhdr}
\usepackage{graphics}
\usepackage{pstricks}
\usepackage{amsmath}

\author{Adam Choma}
\title{Szachy}

\numberwithin{equation}{section}
\setlength{\headheight}{15pt}
\makeindex
\newcommand {\szer}{Badanie zbieżności szeregu}
\begin{document}
\maketitle
\fancypagestyle{plain}% ustawienia stylu strony fancy
{
\fancyhead{} % pusta główka
\fancyfoot{} % pusta stopka
}
\thispagestyle{empty}
\tableofcontents
\thispagestyle{empty}% strona w stylu empty
\newpage
\fancypagestyle{plain}% powrót do normalnego stylu strony
{
\fancyhead{} % główka pusta
\fancyfoot[C]{\thepage} % w stopce numer strony
}
\setcounter{page}{1}
\pagestyle{fancy}
\chapter{Szachy i komputery}
\section{Wstęp}
Szachy są dla szarych komórek tym, czym dla procesora program Orthos. W czasach zimnej wojny były wręcz potwierdzeniem statusu intelektualnego ,,narodu'' sowieckiego, a~apogeum ich popularności nastąpiło w~$1972$~roku, gdy z~Borysem Spasskim zmierzył się na~Islandii, w~meczu o~mistrzostwo świata, Amerykanin Robert James Fischer\index{Fischer}. Nic dziwnego, że~próby wykorzystania komputerów do~gry w~szachy mają swój początek ponad pół wieku temu.

Postaram się możliwie przystępnie pokazać zastosowanie komputerów w~szachach. Będzie trochę historii, przedstawię różne rodzaje oprogramowania szachowego i~ możliwości gry w~sieci, wyjaśnię sposób działania silników (łącznie z~przykładami ich słabych stron), nie zabraknie też skandali związanych z~komputerowym albo\ldots ludzkim wspomaganiem.

Artykuł jest skierowany przede wszystkim do Czytelników zainteresowanych wykorzystaniem technik informatycznych w~różnych dziedzinach, nie do szachistów chcących skuteczniej ich użyć w~swoim treningu, choć pewnie okaże się przydatny wielu niedzielnym graczom. Nie znajdziecie w nim szczegółowych instrukcji, jak korzystać ze statystyk szachowej bazy danych albo ustawić parametry silnika do gry z~innym silnikiem, nie będzie też zbyt wiele o~programowaniu silnika albo szczegółach protokołów serwerów do gry w szachy.

Niektóre rozdziały wymagają znajomości reguł gry i~zasad ustalania wyniku. Wprawdzie jest to~wiedza łatwo dostępna w~internecie, choćby na stronach Wikipedii, to jednak postanowiłem omówić podstawy (ostatni rozdział). Nie tylko przedstawiłem możliwie zwięźle zasady wykonywania posunięć i~cel partii szachowej, ale także opisałem mniej znane zasady kończenia partii (niekiedy należące nie tyle do reguł gry, co do regulaminu zawodów), co też jest niezbędne do pełnego zrozumienia rozdziału o~słabych stronach silników. W~artykule znalazł się także opis notacji szachowej, zarówno podstawowej, jak też w~postaci zrozumiałej dla oprogramowania, i~słowniczek wybranych pojęć, których nawet osoby umiejące grać w~szachy (znające zasady gry) nie muszą znać lub rozróżniać.
\newpage
\section{Początki}
W~tym rozdziale przedstawię w~dużym skrócie, jak komputery odgrywały coraz większą rolę w~szachach. Więcej przeczytacie w~innych rozdziałach, przede wszystkim w~tych poświęconych superkomputerom szachowym, sławnym meczom człowiek kontra maszyna i~rywalizacji silników\index{slinik}.

Jeśli nie liczyć trików z~człowiekiem ukrytym pod stołem z~szachownicą i~podobnych, próby użycia maszyn do~gry w~szachy podejmowano już ponad pół wieku temu. Na~początku, w~połowie XX~wieku, uważano, że nauczenie komputera, jak~grać, nie będzie miało praktycznego znaczenia, będzie jedynie punktem wyjścia do rozwiązania innych problemów. W~$1951$~roku, czyli jeszcze przed pojawieniem~się komputerów zdolnych do tak zaawansowanych obliczeń, sławny Alan Turing\index{Turing} zaprojektował (oczywiście wyłącznie na papierze) pierwszy program szachowy. Rok później, z~braku odpowiedniego sprzętu, rozegrał partię z~człowiekiem, symulując działanie programu we własnej pamięci. Wcześniej, pod sam koniec lat~$40$., Claude~Shannon\index{Shannon}, również matematyk, opracował podstawowe strategie silnika: analizę wszystkich posunięć do określonej głębi drzewa wariantów, którą nazwał~,,A'', i~analizę tylko wybranych, wyznaczonych na podstawie wiedzy szachowej, którą nazwał ,,B''.

Dietrich Prinz w~$1951$~roku zdołał nauczyć jeden z wczesnych komputerów znajdywania mata w~dwóch posunięciach.

Pod koniec lat~$50$. komputery nie tyle umiały grać w~szachy, co rozegrać partię zgodnie z~regułami. Taki program napisał w~$1958$ roku programista w~IBM-ie Alex Bernstein. W~tym samym czasie powstał program NSS\index{NSS}, opracowany przez Allena Newella, Herberta Simona i~Cliffa Shawa, wykorzystujący podstawowy algorytm liczenia wariantów i~,,odcinania'' wybranych (ang. \emph{alpha --- beta pruning}, patrz rozdział poświęcony silnikom szachowym) natychmiast po uznaniu ich za mniej obiecujące.

Wcześniej niedostateczne zasoby sprzętowe zmuszały do ograniczenia liczby pól. Pierwszym programem zdolnym rozegrać taką partię (na szachownicy bez gońców, roszady, promocji piona na gońca i~prawa do pierwszego ruchu pionem o~dwa pola) był stworzony w~$1956$~roku na programowalny superkomputer MANIAC~I program Los Alamos chess, uruchomiony, zanim MANIAC\index{MANIAC} rozpoczął obliczenia związane z~budową bomby atomowej. (Piszę: superkomputer, a~wcześniej o~tym, że brakowało mu mocy, ale kilka tysięcy lamp próżniowych miało bardzo niską wydajność).

W~latach $1959$--$1962$ kilku studentów MIT-u stworzyło program zdolny do pokonania szachisty amatora. Pracujący w~Micie programista Richard Greenblatt dodał do niego sporo wiedzy szachowej, co pozwoliło programowi MacHack VI działającemu na komputerze DEC-PDP-6 osiągnąć w~turnieju z udziałem ludzi ranking typowy dla przeciętnego amatora. Na początku lat $60$. mistrz świata w szachach Michaił Botwinnik, z~wykształcenia elektrotechnik, rozwinął na radzieckich komputerach, o~bardzo ograniczonych możliwościach, techniki wybierania najlepszych posunięć do analizy.

W~latach $1966$--$67$ rozegrano pierwszy mecz między komputerami: Kaissa --- Kotok-McCarthy.

Programy szachowe wykonały wielki skok w latach 70. Wtedy pojawiły się tak podstawowe dziś elementy, jak: książki otwarć, tablice transpozycji, tablice końcówek, a~także nowe algorytmy oceny pozycji (jak iteratywne pogłębianie) i~przede wszystkim plansze bitowe. (O~tym wszystkim przeczytacie w rozdziałach opisujących różne typy oprogramowania szachowego i działanie silnika).

Jednak w~latach~$70$. był okres, gdy najmocniejszy silnik, Chess, stosował metodę brutalnej siły w~czystej postaci, bo stosunkowo mało rozwinięte techniki ograniczania liczby wariantów do obliczenia nie zajmowały więcej zasobów niż liczenie wszystkich.

To także wtedy mikrokomputery zaczęły trafiać pod strzechy i~silniki szachowe stały się dostępne nie tylko naukowcom. Pierwsze silniki dostępne na domowe mikrokomputery były pisane przez hobbystów i~dostępne w~wersji do samodzielnego wpisania. Wkrótce pojawiły się komercyjne silniki na takie komputery, jak Apple II i TRS-$80$. W tym samym czasie, w~$1977$~roku, pionier komputerowych szachów Ken Thompson wraz Joe Condonem stworzyli pierwszy superkomputer przeznaczony specjalnie do gry w~szachy, Belle\index{Belle}, który w~obliczeniach szachowych był kilkadziesiąt razy szybszy od ówczesnych superkomputerów ogólnego przeznaczenia.

W~$1974$~roku rozegrano pierwszą edycję mistrzostw świata komputerów, World Computer Chess Championship. (W~latach~$1980$--$2001$ rozgrywano osobny cykl dostępny wyłącznie dla mikrokomputerów).

W~$1977$~roku powstała organizacja International Computer Chess Association (ICCA)\index{ICCA}, przemianowana w~$2002$~roku na International Computer Games Association (ICGA), mająca promować wykorzystanie komputerów w szachach i~organizować rozgrywki między nimi.

W~$1980$~roku silnik\index{silnik} Sargon na procesorze Z$80$ firmy Zilog\index{Zilog} (tę architekturę wykorzystano m.in. w ZX Spectrum) osiągnął poziom dość silnego amatora. Jedna z jego następnych wersji, zainstalowana na domowym pececie, pokonała w~$1989$~roku silnik działający na superkomputerze. W~tym czasie komputery i programy szachowe były już zdolne sporadycznie zagrozić utytułowanym graczom, na przykład HiTech i Deep Thought pokonały dwóch amerykańskich arcymistrzów: Arnolda Denkera i~Benta Larsena.

Jeszcze w połowie lat $80$. nie było zgody co do tego, czy komputer kiedykolwiek będzie zdolny pokonać gracza ze ścisłej czołówki. Tak naprawdę uwierzono w to dopiero na przełomie lat $80$. i~$90$., choć jak się okazało, trzeba było dopiero Deep Blue firmy IBM, specjalnie zbudowanego w~tym celu superkomputera o~setkach procesorów i~specjalnie zaprojektowanych układów, wywodzącego się z~projektu Deep Thought.
\newpage
\section{Silnik a człowiek}
Wybór ruchów --- kandydatów i~uszeregowanie ich według wstępnej oceny z~jednej strony pozwala nie liczyć posunięć słabych, z~drugiej łatwo o~przeoczenie najlepszego w~danej pozycji posunięcia, tyle że mniej oczywistego przy płytkiej ocenie. Oczywiście, człowiek ma ten sam problem, ale w~przeciwieństwie do maszyny, aby coś dostrzec, nie musi liczyć wszystkiego, co do tego prowadzi, poza tym doświadczenie, wiedza i~zdolność rozpoznawania schematów pozwalają mu często podejmować najlepsze decyzje bez głębokiego liczenia wariantów.

Człowiek ma zdolność rozpoznawania schematów i~dopasowywania ich do sytuacji na szachownicy. Człowiek będzie wiedział, zarówno na podstawie wiedzy dostępnej w~literaturze szachowej, jak i~własnego doświadczenia, czy w~danej pozycji różnopolowe gońce dają większe szanse na atak czy raczej na remis albo czy w~dłuższej perspektywie, na przykład w możliwej do uzyskania końcówce, goniec będzie słabszy od skoczka przeciwnika czy silniejszy. Silniki taką wiedzę mają w~szczątkowej postaci.

Sprawa jeszcze bardziej komplikuje się w~przypadku debiutów i~końcówek.

Liczba możliwych posunięć iskomplikowanie pozycji powstających po zaledwie kilku początkowych ruchach sprawiają, że ocena pozycji przez program musi być płytka, a~ wiedza debiutowa powstała przez ostatnich kilkaset lat jest ogromna. Dlatego programy na początku partii standardowo korzystają z~przygotowanych przez ludzi książek debiutowych, bez nich radzą sobie nie najlepiej. Oczywiście, silny szachista musi mieć tę wiedzę w~głowie: często gracze pierwszych $10$, $15$ albo więcej posunięć wykonują bardzo szybko, bo albo korzystają z~dostępnej wiedzy (nazywanej także teorią), albo grają przygotowane przez siebie, nowe warianty.

Ciekawie robi się też w~grze końcowej. Tu do głosu dochodzą schematy, ogólne zasady, których nieznajomości nie pozwoli nadrobić największa moc obliczeniowa, i~zwykła wiedza, powstała przez dziesięciolecia lub stulecia, że ta lub ta pozycja jest remisowa lub nie. Człowiek to wie, silnik --- nie, bo nie można mu zapisać wszystkich możliwych pozycji, a~człowiek dopasuje schemat. Człowiek może dostrzec końcową pozycję, na przykład po wymianie kilku bierek, bez liczenia kilkudziesięciu posunięć, silnik --- nie. Ale są opisane już tablice końcówek! Wprawdzie tylko dla sześciu bierek (przy czym tylko te najważniejsze zajmują setki gigabajtów), ale program może do nich sięgać nawet wtedy, gdy bierek na szachownicy jest więcej. Wystarczy, że samodzielnie dojdzie w obliczeniach do pozycji z~mniejszą liczbą bierek, która znajduje się w~tablicach.

Oczywiście komputer ma sporo przewag. Zasadniczo nie popełnia rażących błędów (jak strata materiału, tzw. podstawka, w~jednym lub kilku posunięciach), nie męczy się (a~na przykład mecz Kramnik --- Deep Fritz sprzed dwóch lat był rozgrywany w tempie siedmiogodzinnym!), w skomplikowanych, ale bardzo ,,taktycznych'' pozycjach, w~których decydujące jest liczenie wariantów, niemal zawsze będzie górą.

Zdarzają się jednak błędy programistyczne. Może to być niestandardowe zachowanie w~pewnych sytuacjach, takich jak powtarzanie posunięć, może to być luka w~książce debiutowej, czasem jednak błąd ujawnia się w~najbardziej niespodziewanych sytuacjach. Świetnym przykładem jest partia Lafuente --- Shredder z~$2005$~roku:
\begin{figure}
\centering
\includegraphics{rys/lafuente-shredder_2005.jpg}
\caption{(ruch czarnych)}
\end{figure}
Białe zbiły czarnego gońca na $b7$. Każdy silnik od razu widzi, że czarne muszą zbić białego gońca, a różnica w ocenie między tym a następnym na liście posunięciem jest od pierwszej sekundy ogromna: dwa --- trzy punkty. I~co zrobił Shredder, sławny taktyk? ,,Zapomniał'' zbić gońca\ldots Jak się okazało, Shredder myślał nad tym posunięciem trzy minuty, osiągnął głębię $20$~półruchów i\ldots zagrał co innego. Błąd, który wystąpił w~tablicy transpozycj, i i~którego nawet dało się odtworzyć, określono jako jeden na milion.
\newpage
\section{Lista zwycięźców}
Lista zwycięskich programów komputerowych w Mistrzostwach Świata. \\ \\
%
\begin{tabular}{c|c|l|l}
\hline
Lp & Rok & Miasto & Program\\ \hline\hline
1 & 1974 & Sztokholm & Kaissa\\ \hline
2 & 1977 & Toronto & Chess 4.6\\ \hline
3 & 1980 & Linz & Belle\\ \hline
4 & 1983 & Nowy Jork & Cray BLitz\\ \hline
5 & 1986 & Kkolonia & Cray Blitz\\ \hline
6 & 1989 & Edmonton & Deep Thought\\ \hline
7 & 1992 & Madryt & Chess Machine\\ \hline
8 & 1995 & Honh Kong & Fritz\\ \hline
9 & 1999 & Paderborn & Shredder\\ \hline
10 & 2002 & Maastrict & Deep Junior\\ \hline
11 & 2003 & Graz & Shredder\\ \hline
12 & 2004 & Ramat Gan & Deep Junior\\ \hline
13 & 2005 & Reykjavik & Zappa\\ \hline
14 & 2006 & Turyn & Junior\\ \hline
15 & 2007 & Amsterdam & Rybka\\ \hline
16 & 2008 & Pekin & Rybka\\ \hline
17 & 2008 & Pampeluna & Rybka\\ \hline
18 & 2010 & Kanazawa & Rybka\\ \hline
\end{tabular}
%
\newpage
\chapter{\szer}
{
Zadanie domowe na przedmiot Analiza Matematyczna --- zbadać zbieżność następującego szeregu:
\begin{equation}
\sum_{n=1}^{\infty}\frac{n!}{2^{n}lnn!}
\end{equation}
Rozwiązanie:
\center{Z kryterium d'Alemberta:}
\begin{equation}
\frac{n!}{2^{n}lnn!}:\frac{(n+1)!}{2^{n+1}ln(n+1)!}=
\end{equation}
\begin{equation}
\frac{n!}{2^{n}lnn!}\cdot\frac{2^{n+1}ln(n+1)!}{(n+1)!}=
\end{equation}
\begin{equation}
\frac{2}{n+1}\cdot\frac{ln(n+1)!}{lnn!}=
\end{equation}
\begin{equation}
\frac{2}{n+1}\cdot\frac{lnn!+ln(n+1)}{lnn!}=
\end{equation}
\begin{equation}
\frac{2}{n+1}\cdot(1+\frac{ln(n+1)}{lnn!})
\end{equation}
Pierwszy czynnik dąży do zera, drugi do jedynki. Całość do zera, a więc szereg jest zbieżny.
\newpage
\printindex
\end{document}