
% Ćwiczenia na Newtona o grach

\mainlanguage[pl]

\usetypescript[pagella]
\setupbodyfont[pagella]

\def\todo#1{{\em \kap{do dopisania}: #1}}

\enablemode[nauczyciel]

\def\startteacher{\grabbufferdata[teacher][startteacher][stopteacher]}
\doifmodeelse{nauczyciel}{\def\stopteacher{\getbuffer[teacher]}}{\def\stopteacher{}}

\def\startanswer{\grabbufferdata[answer][startanswer][stopanswer]}
\doifmodeelse{nauczyciel}{\def\stopanswer{\blank[small]{\sl Odpowiedź.} \getbuffer[answer]}}{\def\stopanswer{}}

\def\putdotafter#1{#1.}
\setuphead[subsubject][style=bold,after={},alternative=text,distance=0.25em,textcommand=\putdotafter]
\setuphead[section][numbercommand=\putdotafter]
\setuphead[chapter][numbercommand=\putdotafter,page=no]

\defineitemgroup[exercises]
\setupitemgroup[exercises][1][n][before={},inbetween={\blank[medium]}]

\def\ppauza{\unskip\kern.2em--\hskip.2em\ignorespaces}

\starttext

\startalignment[middle]
  \tfb Gry (materiały na ćwiczenia w~czwartek)
  \par\blank[big]
\stopalignment

\completecontent


\startchapter[title={Gry macierzowe}]

\startexercises
  \startitem
    Jakie są strategie optymalne dla obu graczy w~grze o~poniższej
    macierzy?
    \startformula
      \startmathmatrix[n=2,left={\left(\,},right={\,\right)},align=right]
        \NC 1 \NC 2 \NR
        \NC 3 \NC 4 \NR
      \stopmathmatrix
    \stopformula
    \startanswer
      Pierwszy gracz, wybierając drugi wiersz, w~każdym wypadku
      wygrywa więcej, niż gdyby wybrał pierwszy; powinien więc wybrać
      drugi wiersz (dominujący).  Drugi gracz, wybierając pierwszą
      kolumnę, w~każdym przypadku traci mniej, niż gdyby wybrał drugą;
      powinien więc wybrać pierwszą (dominującą) kolumnę.
    \stopanswer
  \stopitem
  \startitem
    Rozważmy grę z~następującą macierzą:
    \startformula
      \startmathmatrix[n=3,left={\left(\,},right={\,\right)},align=right]
        \NC 4 \NC 1 \NC -1 \NR
        \NC 0 \NC 1 \NC  6 \NR
        \NC 3 \NC 2 \NC 5  \NR
      \stopmathmatrix
    \stopformula
    Jaka jest optymalna strategia dla każdego z~graczy?
    \startanswer
      Żaden wiersz ani kolumna nie są dominujące, ale ponieważ
      \math{2} w~trzecim rzędzie i~drugiej kolumnie jest {\em
        najmniejszą} wartością w~swoim rzędzie i~{\em największą}
      wartością w~swojej kolumnie, optymalną strategią dla I~gracza
      jest trzecia, a~dla II~gracza druga.
    \stopanswer
  \stopitem
  \startitem
    Gra {\em parzyste czy nieparzyste} polega na tym, że dwóch graczy
    wybiera (równocześnie) liczbę \math{1} lub~\math{2}.  Jeśli suma
    wybranych liczb jest nieparzysta, wygrywa gracz~I; jeśli jest
    parzysta, wygrywa gracz~II.  Gracz, który przegrał, oddaje
    drugiemu kwotę równą sumie wybranych liczb.  Narysuj macierz tej
    gry.  Jaka jest optymalna strategia każdego z~graczy?  Czy gra
    jest sprawiedliwa?
    \startanswer
      Macierz:
      \startformula
        \startmathmatrix[n=2,left={\left(\,},right={\,\right)},align=right]
        \NC -2 \NC  3 \NR
        \NC  3 \NC -4 \NR
        \stopmathmatrix
      \stopformula
      Powyższa macierz nie ma strategii dominujących ani punktów
      siodłowych, trzeba więc zastosować inną metodę.

      Załóżmy, że gracz~I wybiera~\math{1}
      z~prawdopodobieństwem~\math{p} i~\math{2}
      z~prawdopodobieństwem~\math{1-p}.  Wyznaczymy~\math{p} tak, żeby
      gracz~I wygrywał przeciętnie {\em tyle samo}, obojętnie, co
      zrobi gracz~II.

      Jeśli gracz~II wybierze~\math{1}, przeciętna wygrana~I wynosi
      \math{-2p+3(1-p)}.  Jeśli II wybierze~\math{2}, przeciętna
      wygrana~I wynosi~\math{3p-4(1-p)}.  Aby wartości te były równe,
      musi być \math{p=\frac{7}{12}}.  Zatem gracz~I powinien
      wybrać~\math{1} z~prawdopodobieństwem \math{\frac{7}{12}},
      a~\math{2} z~prawdopodobieństwem~\math{\frac{5}{12}}.  Jego
      przeciętna wygrana wynosi
      \math{-2\frac{7}{12}+3\frac{5}{12}=3\frac{7}{12}-4\frac{5}{12}=\frac{1}{12}}.

      Prowadząc podobną analizę dla gracza~II widzimy, że ta sama
      strategia pozwala mu uzyskać przeciętną
      stratę~\math{\frac{1}{12}}.  Wynika stąd, że znalezionej
      strategii nie da się ulepszyć, a~gra nie jest sprawiedliwa
      (preferuje I~gracza).
    \stopanswer
  \stopitem
  \startitem
    Rozważmy wariant gry {\em parzyste czy nieparzyste}, w~którym
    każdy z~graczy wybiera jedną z~liczb~\math{\{0,1,2\}}.  Spróbuj
    wyliczyć optymalną strategię dla pierwszego gracza.
    \startanswer
      Nie ma ani strategii dominujących, ani punktów siodłowych.
      Postępujemy jak w~poprzednim ćwiczeniu \todo{rozpisać układ
        równań}; okazuje się, że I~gracz powinien wybierać~\math{1}
      z~prawdopodobieństwem~\math{\frac{1}{2}} i~pozostałe liczby
      z~prawdopodobieństwem~\math{\frac{1}{4}}.  Uwaga: ta metoda {\em
        nie działa dla każdej macierzy}!
    \stopanswer
  \stopitem
\stopexercises

\stopchapter

\startchapter[title={Nim-suma liczb całkowitych nieujemnych}]

\startexercises
  \startitem
    Przelicz następujące liczby w~zapisie dwójkowym na system
    dziesiątkowy:
    \startitemize[r,columns,two][left=(,right=),stopper={}]
      \startitem
        \math{(101)_2}
      \stopitem
      \startitem
        \math{(101011)_2}
      \stopitem
    \stopitemize
  \stopitem
  \startitem
    Przelicz następujące liczby na system dwójkowy:
    \startitemize[r,columns,two][left=(,right=),stopper={}]
      \startitem
        \math{10}
      \stopitem
      \startitem
        \math{77}
      \stopitem
    \stopitemize
  \stopitem
\stopexercises
\stopchapter

\startchapter[title={Kombinatoryczne gry symetryczne}]
  
\stopchapter


\startchapter[title={Przykładowe gry}]

\startsection[title={Zakreśl do piętnastu (20~minut)}]
  \startsubsubject[title={Zasady gry}]
    Wypisujemy na kartce liczby od~\math{1} do~\math{9}.  Gracze na
    przemian zakreślają liczbę (każdy swoim kolorem).  Gracz, który
    jako pierwszy wśród \quotation{swoich} liczb będzie miał trójkę
    liczb, których suma wynosi~\math{15}, wygrywa.
  \stopsubsubject
  \startsubsubject[title={Zadania}]
    \startexercises
      \startitem
        Jakimi wynikami może zakończyć się gra?
        \startanswer
          Wygraną jednego z~graczy lub remisem.
        \stopanswer
      \stopitem
      \startitem
        Rozegrajcie kilka\ppauza kilkanaście gier.  Czy pierwszy gracz
        może zawsze wygrać?  A~drugi?
        \startanswer
          Nie, gdy obaj gracze grają optymalnie, gra kończy się
          remisem.  (Optymalną strategię znajdziemy za chwilę.)
        \stopanswer
      \stopitem
      \startitem
        Wypiszcie wszystkie trójki liczb ze zbioru
        \math{\{1,2,\dots,9\}}, które sumują się do~\math{15}.  Jak
        wypisać je \quotation{po kolei}, czyli tak, by żadnej nie
        pominąć i~żadnej nie wypisać więcej niż jeden raz?  Ile ich
        jest?  Które liczby ile razy występują w~tych trójkach?
        \startanswer
          \math{(1,5,9)}, \math{(1,6,8)}, \math{(2,4,9)},
          \math{(2,5,8)}, \math{(2,6,7)}, \math{(3,4,8)},
          \math{(3,5,7)}, \math{(4,5,6)}.  Każda trójka wypisana jest
          rosnąco i~wypisane są w~porządku leksykograficznym.  Trójek
          jest \math{8}, a~poszczególne liczby występują w~nich:
          \math{5} czterokrotnie, \math{2,4,6,8} trzykrotnie,
          \math{1,3,7,9} dwukrotnie.
        \stopanswer
      \stopitem
      \startitem
        Jak ułożyć liczby od \math{1} do~\math{9}, żeby było łatwiej
        grać, tj. żeby trójki sumujące się do~\math{15} były
        \quotation{dobrze widoczne}?
        \startanswer
          Ułożenie ich np. w~następującym {\em kwadracie magicznym}
          \starttabulate[|c|c|c|][before={},after={}]
            \NC 2 \NC 9 \NC 4 \NC\NR
            \NC 7 \NC 5 \NC 3 \NC\NR
            \NC 6 \NC 1 \NC 8 \NC\NR
          \stoptabulate
          pokazuje, że rozważana gra jest {\em izomorficzna}
          z~\quotation{kółkiem i~krzyżykiem}.
        \stopanswer
      \stopitem
    \stopexercises
  \stopsubsubject
\stopsection

\startsection[title={Kółko i~krzyżyk (30~minut)}]
  \startsubsubject[title={Zasady gry}]
    Znane każdemu (?).
  \stopsubsubject
  \startsubsubject[title={Zadania}]
    \startexercises
      \startitem
        Jakie są możliwe wyniki w~grze w~{\em Kółko i~krzyżyk}?
        \startanswer
          Wygrana jednego z~graczy lub remis.
        \stopanswer
      \stopitem
      \startitem
        Narysuj kilka początkowych poziomów drzewa gry.  Narysuj kilka
        gałęzi aż do zakończenia gry.
      \stopitem
      \startitem
        Oszacuj liczbę możliwych rozgrywek w~{\em Kółko i~krzyżyk}.
        \startanswer
          \startitemize[a,packed][stopper=)]
            \startitem
              Prostym ograniczeniem górnym jest \math{9!=362\,880}.
            \stopitem
            \startitem
              Jeśli wziąć pod uwagę symetrie w~początkowych dwóch
              ruchach (w~późniejszych ruchach staje się to bardziej
              skomplikowane), można postępować następująco.  Pierwszy
              ruch można wykonać na \math{3} sposoby (środek, róg,
              bok).  Jeśli pierwszy ruch był w~środku, drugi ruch może
              zostać wykonany na \math{2} sposoby; jeśli w~rogu lub na
              boku, na \math{5} sposobów.  Zatem pierwsze dwa ruchy
              można wykonać na \math{1\cdot 2+2\cdot 5=12} sposobów,
              a~pozostałe siedem na nie więcej niż \math{7!=5040}
              sposobów; zatem wszystkich gier może być najwyżej
              \math{12\cdot 7!=60\,480}.
            \stopitem
            \startitem
              Jeśli wziąć pod uwagę symetrie do trzeciego ruchu,
              analogiczne rozumowanie pokazuje, że liczba możliwych
              rozgrywek nie przekracza
              \startformula
                (2\cdot4+2\cdot4+3\cdot7)\cdot 6!=30\,960.
              \stopformula
            \stopitem
            \startitem
              Powyższa analiza nie bierze pod uwagę ani możliwych
              symetrii w~dalszych ruchach, ani tego, że niektóre gry
              kończą się przed zapełnieniem planszy.  W~2002 roku
              obliczono, że dokładna liczba rozgrywek w~{\em kółko
                i~krzyżyk} wynosi \math{26\,830}.
            \stopitem
          \stopitemize
        \stopanswer
      \stopitem
      \startitem
        Rozegrajcie kilka gier.  Co powinien zrobić pierwszy gracz?
        Jaki ruch pierwszego gracza {\em gwarantuje} mu wygraną,
        niezależnie od tego, jak gra drugi gracz?  A~jaki {\em
          gwarantuje} przegraną, jeśli drugi gracz gra optymalnie?
        \startanswer
          Obojętnie, co zrobi pierwszy gracz w~pierwszym ruchu, jeśli
          w~dalszym ciągu będzie grał optymalnie, nie przegra; jednak
          żaden ruch nie gwarantuje mu wygranej.  \todo{dokładniejsza
            rozpiska}
        \stopanswer
      \stopitem
      \startitem
        Jak wygląda macierz gry w~{\em kółko i~krzyżyk}?
        \startanswer
          \quotation{Strategiami} każdego z~graczy będą funkcje, które
          każdej {\em sytuacji} na planszy przyporządkowują {\em
            ruch}.  Oczywiście, różne układy strategii I i~II gracza
          będą prowadzić do różnych wyników gry.
        \stopanswer
      \stopitem
      \startitem
        Opisz własności gry w~kółko i~krzyżyk.
        \startanswer
          Jest dwóch graczy; gracze wykonują ruchy kolejno, a~nie
          jednocześnie (chyba, że przez \quotation{ruch} będziemy
          rozumieć \quotation{wybór strategii} (w~sensie poprzedniego
          zadania)); gracze dysponują pełną informacją; gra kończy się
          po skończenie wielu ruchach (maksymalnie dziewięciu);
        \stopanswer
      \stopitem
      \startitem
        Opisz optymalną strategię w~{\em kółko i~krzyżyk} dla I i~II
        gracza.
        \startanswer
          Oto przykładowy zapis strategii optymalnej (co ciekawe,
          działający dla każdego gracza).  W~każdej sytuacji należy
          sprawdzać, czy kolejne punkty mają zastosowanie, i~jeśli
          tak, wykonać opisaną w~nich akcję.
          \startitemize[a,packed][stopper=)]
            \startitem[a]
              Jeśli masz dwa symbole w~rzędzie, a~trzecie miejsce jest
              puste, zakreśl to puste miejsce; {\em wygrywasz}.
            \stopitem
            \startitem
              Jeśli przeciwnik ma dwa symbole w~rzędzie, a~trzecie
              miejsce jest puste, zakreśl to puste miejsce.
            \stopitem
            \startitem
              Jeśli możesz, stwórz {\em zagrożenie}, czyli sytuację,
              w~której masz {\em dwa} rzędy z~dwoma swoimi symbolami
              i~trzecim pustym miejscem.
            \stopitem
            \startitem
              Jeśli w~następnym ruchu przeciwnik będzie w~stanie
              utworzyć {\em zagrożenie}, utwórz sytuację opisaną
              w~\in{punkcie}{)}[a].
            \stopitem
            \startitem
              Jeśli środek jest wolny, zagraj w~nim.
            \stopitem
            \startitem
              Jeśli przeciwnik zagrał w~narożniku i~przeciwległy
              narożnik jest wolny, zagraj w~nim.
            \stopitem
            \startitem
              Jeśli którykolwiek narożnik jest wolny, zagraj w~nim.
            \stopitem
            \startitem
              Zagraj gdziekolwiek.
            \stopitem
          \stopitemize
        \stopanswer
      \stopitem
      \startitem
        Wymyśl kilka wariantów {\em kółka i~krzyżyka}.
        \startanswer
          Do znanych wariantów należą np. {\em kółko i~krzyżyk} na
          planszy \math{4\times 4} (do wygranej trzeba mieć \math{4}
          swoje symbole w~wierszu, kolumnie lub na przekątnej), {\em
            gomoku} (do wygranej trzeba mieć \math{5} symboli, plansza
          ma rozmiar \math{19\times19}), {\em kółko i~krzyżyk}
          trójwymiarowe (i~w~wyższych wymiarach), {\em anty-kółko
            i~krzyżyk}, gdzie gracz, który ma trzy symbole w~rzędzie,
          przegrywa, {\em kwantowe} kółko i~krzyżyk i~wiele innych.
        \stopanswer
      \stopitem
    \stopexercises
  \stopsubsubject
\stopsection

\startsection[title={Wythoff (20~minut)}]
  \startsubsubject[title={Zasady gry}]
    Na dwóch kupkach układamy kamienie (kupki nie mogą być
    równoliczne).  Gracze wykonują ruchy na przemian.  Ruch polega na
    zabraniu dowolnej liczby kamieni (co najmniej jednego, być może
    wszystkich) z~dowolnej kupki bądź zabraniu {\em tej samej} liczby
    kamieni (co najmniej jednego) z~{\em obu} kupek.  Gracz, który
    weźmie ostatni(e) kamień(nie), wygrywa.
  \stopsubsubject
  \startsubsubject[title={Zadania}]
    \startexercises
      \startitem
        Rozegrajcie kilka partii (dla różnych liczebności początkowych
        kupek).  Jakimi wynikami może się zakończyć Wythoff?
        \startanswer
          Wygraną któregoś z~graczy\ppauza remis jest niemożliwy.
        \stopanswer
      \stopitem
      \startitem[2]
        Czy są takie liczebności kupek, dla których gracz
        rozpoczynający ma zagwarantowaną wygraną (obojętnie, jak gra
        drugi gracz)?
        \startanswer
          Tak, przykładowo \math{(1,2)}, \math{(3,5)}.
        \stopanswer
      \stopitem
      \startitem[3]
        Rozważmy następującą grę.  Na pewnym polu szachownicy
        ustawiamy pionek.  W~każdym ruchu można przesunąć go o~dowolną
        liczbę pól w~dół, w~lewo bądź ukosem w~lewo-dół.  Zauważ, że
        gra ta jest izomorficzna z~Wythoffem.
      \stopitem
      \startitem
        Opisz układy początkowe, które gwarantują wygraną I~graczowi.
        \startanswer
          Oprócz tych wymienionych w~odpowiedzi do \in{punktu}{.}[2],
          układy takie to m.in. \math{(4,7)}, \math{(6,10)} itd.
          Każdy taki układ powstaje z~poprzedniego w~następujący
          sposób: bierzemy najmniejszą liczbę naturalną~\math{n_1},
          która dotąd nie wystąpiła w~żadnym układzie\ppauza będzie to
          liczba kamieni w~mniejszej kupce; w~większej kupce będzie
          \math{n_2=n_1+d} kamieni, gdzie różnica~\math{d} jest
          o~jeden większa niż różnica liczebności kupek w~poprzednim
          układzie.

          Takie pary liczb mają odpowiednie własności.  Po pierwsze,
          nie można (zabierając kamienie zgodnie z~zasadami) przejść
          od żadnego z~tych układów do żadnego z~poprzednich: ponieważ
          każda liczba naturalna występuje wśród opisanych układów
          dokładnie raz (dlaczego?), zabierając kamienie z~{\em
            jednej} kupki nie jesteśmy w~stanie przejść do jednego
          z~poprzednich układów; ponieważ zaś {\em różnice} również
          się nie powtarzają, zabierając kamienie z~{\em obu} kupek
          również nie dojdziemy do żadnego z~poprzednich układów.

          Po drugie, jeśli startujemy z~układu innego niż któryś
          z~powstałych w~opisany sposób, zawsze możemy dojść do
          któregoś z~nich; najłatwiej zobaczyć to rysując je na
          szachownicy i~korzystając z~wersji Wythoffa opisanej
          w~\in{punkcie}[3].

          Własności te powodują, że każdy z~opisanych układów prowadzi
          do wygranej gracza, którego ruch akurat przypada, a~każdy
          inny układ do jego przegranej.
        \stopanswer
      \stopitem
      \startitem
        Wymyśl kilka wariantów Wythoffa; sprawdź, jak się w~nie gra.
        \startanswer
          Można zwiększyć liczbę kupek, zabronić zabierania kamieni
          z~obu kupek jednocześnie, wprowadzić maksymalną liczbę
          kamieni, jakie można zabrać w~jednym ruchu, zmienić warunek
          wygranej na przeciwny (przegrywa gracz, który weźmie ostatni
          kamień) i~in.  (Prowadzi to m.in. do gry {\em Nim}
          i~rozmaitych jej wariantów.)
        \stopanswer
      \stopitem
    \stopexercises
  \stopsubsubject
\stopsection

\startsection[title={Hex (20~minut)}]
  \startsubsubject[title={Zasady gry}]
    Gra toczy się na planszy w~kształcie rombu złożonej
    z~sześciokątnych pól.  Gracze na przemian zagrywają swoje piony
    (gracz~I białe, gracz~II czarne) na tych polach; raz położony na
    planszy pion pozostaje w~tym samym miejscu do końca gry.
  \stopsubsubject
\stopsection

\stopchapter


\startchapter[title={Projektowanie własnej gry}]
  
\stopchapter


\stoptext
