Paweł i Gaweł 2 (omówienie)

30.04.2011

Jeśli nie jesteś zapoznany z pojęciami takimi jak strategia wygrywająca lub teoria gier, polecam artykuły wprowadzające w tę tematykę! Między zwycięstwem a porażką oraz Teoria gier

Będziemy przyglądać się pozycjom w grze, które powstają, gdy jeden z graczy zdjął już ostatni kamień z pewnego stosu (czyli gdy pewien stos znika). Zaprezentujemy rozwiązanie w złożoności czasowej i pamięciowej O(n2A), gdzie A to maksymalna wartość Ai.

Niech L[i][j][x] opisuje sytuację, w której stosy od i+1 do j są pełne (równe Ai+1, Ai+2, ..., Aj) , a na stosie i znajduje się dokładnie x kamieni (1 <= x <= Ai). Jest to pozycja, którą osiągamy, gdy zostanie w pełni zdjęty j+1 stosik, a poprzednie posunięcia doprowadziły do sytuacji, w której na stosie i-tym pozostało x kamieni.

Analogicznie niech R[i][j][x] opisuje sytuację, w której stosy od i do j-1 są pełne (równe Ai, Ai+1, ..., Aj-1) a na stosie j znajduje się dokładnie x kamieni (1 <= x  <= Aj).

Chcemy obliczyć wartość L oraz R - równą 1 jeśli gracz dysponujący ruchem w tej pozycji ma strategię wygrywającą, a 0 w przeciwnym razie. Wartości L i R obliczamy wedle rosnącej wartości j-i, gwarantując sobie, że wszystkie podprzedziały (a więc i pozycje, do których możemy dojść - co wyniknie za chwilę) rozważanego w danym momencie przedziału mają już policzoną wartość.

Jeśli j = i to oczywiście L[i][i][x] = R[i][i][x] = 1. Jeśli zaś j=i+1 to L[i][j][x]  = 1 <=> Aj = x i R[i][j][x] = 1 <=> Ai = x

Gdy  j>i+1 działamy następująco: zauważmy, że dla każdego podprzedziału zawierającego się właściwie w [i,j] znamy już odpowiedzi (kolejność liczenia). Zatem gracze tak naprawdę grają w to, po czyim ruchu zniknie kolejny stos i czy taka pozycja będzie wygrywająca. Mamy więc dwie możliwości:

1. Można doprowadzić do klęski przeciwnika w jednym ruchu. Jest to możliwe (gdy liczymy L[i][j][x]) , jeśli L[i][j-1][x] = 0 (możemy zabrać cały j-ty stos i przeciwnik będzie w sytuacji przegrywającej) lub gdy R[i+1][j][Aj] = 0 (jak poprzednio, ale zabieramy stosik z lewej). Dla R postepujemy analogicznie z zamianą stron.

2. W przeciwnym razie możemy myśleć podobnie jak w 1. - żaden gracz nie może dopuścić, aby po jego ruchu przeciwnik "dokończył" jeden ze stosów i pozostawił gracza w sytuacji przegrywającej. Zatem gracz musi upewnić się, że po jego ruchu taka opcja nie zachodzi. Dla obu stosów zewnętrznych można wyznaczyć liczby kamieni, które pozwalają wygrać przeciwnikowi poprzez zabranie przeciwległego stosu - np. jeśli rozważamy stan L[i][j][15] i wiemy, że L[i][j-1][9] = 0 to nie możemy zabrać 6 kamyków ze stosu i, gdyż przeciwnik odpowie zabierając cały stos j i doprowadzając nas do pozycji L[i][j-1][9]. Podobnie, jeśli na przykład Aj = 30 a R[i+1][j][19] = 0 to nie możemy zabrać z prawego stosu 11 kamieni, bo przeciwnik odpowie wzięciem reszty kamieni ze stosu i-tego, stawiając nas w pozycji R[i+1][j][19].

Wszystkie pozostałe liczby kamieni na obu zewnętrznych stosach możemy opisać jako "bezpieczne". Zatem jeśli nie zachodzi punkt 1. to obie aktualne liczby na stosach są bezpieczne i teraz gracze na przemian usuwają kamienie z zewnętrznych stosów dbając o to, aby pozostawić bezpieczne liczby na obu z nich. Zatem jeśli na stosie lewym mamy a bezpiecznych możliwych liczb, do których można zredukować ten stos, a na stosie prawym takich jest b, to redukujemy się do gry w NIM na liczbach a i b (Zastanów się, dlaczego!) A taka gra jest już prosta do policzenia.

Pozostaje zauważyć, że zarówno L[i][j][x] jak i R[i][j][x]  przy ustalonych i oraz j możemy liczyć dla rosnących wartości x i porównywać liczbę pozycji bezpiecznych ze stałą liczbą takich pozycji na przeciwległym stosie. Takie działanie daje nam żądaną złożoność czasową.

Pozostaje odzyskać odpowiedź o to, czy rozpoczynający gracz ma strategię wygrywającą - jest to oczywiście wartość L[0][n-1][A0].

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com