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