
% ��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
