Skocz do zawartości

Gry a teoria


Jakim

Rekomendowane odpowiedzi

Dla chcących pogłówkować wrzucam mały problem do rozwiązania.

 

Rozważmy klasyczną wersję znanej gry Snake, która rozgrywa się na ustalonej planszy n x m (co najmniej 3 x 3). Do tej gry wprowadzamy nowego gracza, który na początku rozgrywki ustawia pozycję i kierunek początkowy węża (2 x 1), stawia pierwsze jabłko i przy każdym zebranym przez pierwszego gracza jabłka rozmieszcza według uznania kolejne. Pierwszy gracz natomiast ma nieograniczony czas na ruch węża w wybranym kierunku. Gracz pierwszy nie może powtórzyć swojego układu, tj. po pewnym czasie powrócić do swojego poprzedniego ułożenia węża na planszy; sytuacja taka traktowana jest jako zwycięstwo drugiego gracza.

 

Czy któryś z graczy ma strategię wygrywającą? Uzasadnij, przyjmując odpowiednie założenia co do gry.

 

Uwaga: samo napisanie algorytmu wygrywającego nie rozwiązuje problemu. Co więcej: jest to niepotrzebne.

Odnośnik do komentarza
Udostępnij na innych stronach

  • 2 tygodnie później...

Zaraz... jaki warunek musi być spełniony aby gracz pierwszy wygrał? Tego nie zaznaczyłeś, przez co można się domyśleć, iż to drugi gracz ma mieć strategię wygrywa.

Jeśli dobrze zrozumiałem, to jak można zachęcić węża do wykonania tego samego układu skoro jego długość się zmienia?

Odnośnik do komentarza
Udostępnij na innych stronach

Na tym polega trick, że szybko możemy stwierdzić, że któryś z graczy ma strategię wygrywającą (i wcale nie odwołujemy się do zasad gry) - określenie, który jest który, jest już trudniejsze.

 

plansza jest skończona, ilość strategii jest skończona, graczy jest dwóch więc jeśli dobrze kojarze to istnieje dowód matematyczny że którys z tych graczy posiada optymalna strategie która zawsze zapewni mu zwycięstwo.

 

Dowód można przeprowadzić samemu i nie trzeba kończyć Harvardów - zwykłe rozumowanie.

Odnośnik do komentarza
Udostępnij na innych stronach

  • 2 tygodnie później...

No ale co tu rozważać, to że któryś z graczy ma strategie wygrywającą jest oczywiste, bo jeden z graczy zawsze będzie grał tak żeby w następnym ruchu przeciwnik nie wygrał( w przeciwnym wypadku przegrywa ), teraz w zalezności od zasad gry może mu się to w końcu nie udać wtedy wygrywającą strategię ma gracz drugi lub będzie mu się to udawać aż do zakończenia gry( wtedy wygrywa ). Zakonczenie gry jest pewne poniważ gra ma skończoną ilość stanów.

Odnośnik do komentarza
Udostępnij na innych stronach

Twoje rozumowanie jest wadliwe i mętne, to że gracz będzie grać racjonalnie i starał się wygrać w ogóle nie mówi nic o tym, czy mu się to uda. Stwierdzasz: skoro pierwszy gracz nie ma strategii wygrywającej, to ma ją drugą, co akurat w tym przypadku jest prawdziwe, ale wymagałoby uzasadnienia. Np. w grze reszka/orzeł to nie przejdzie, a jest to dwuosobowa gra skończona bez remisu (ba, kończąca się po pierwszej turze).

 

Poza tym tak jak napisałem, nie ma potrzeby odwoływać się do zasad gry jako takich, tylko cech gry: dwuosobowa gra o skończonej liczbie decyzji w każdym ruchu i skończonej liczbie tur bez remisu z pełną informacją o grze. Nie wykorzystałeś wszystkich warunków w ogóle w swoim uzasadnieniu (a bez któregoś może nie istnieć gracz z pewnym zwycięstwem...).

 

Więc nie jest to takie oczywiste (dla Ciebie) jak piszesz.

Odnośnik do komentarza
Udostępnij na innych stronach

W każdej deterministycznej grze z własnością stopu, z pełną informacją, bez remisów i dwójką graczy można określić, który gracz ma strategię wygrywającą. Najprostszą, ale powolną metodą jest zbudowanie całego drzewa gry.

Ale wygląda na to, że ta gra nie ma własności stopu, bo gracz pierwszy może nieskończenie długo myśleć nad rucham.

Odnośnik do komentarza
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się
  • Ostatnio przeglądający   0 użytkowników

    • Brak zarejestrowanych użytkowników przeglądających tę stronę.
×
×
  • Dodaj nową pozycję...