Gry a teoria

[Jakim]

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.

[en_6280]

To proste wystarczy, że pierwszy gracz zje wężem drugiego gracza.

[Jakim]

Niby jak? :)

[Danielus]

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.

[I am Żyd and Lewak]

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?

[Jakim]

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.

[Danielus]

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.

[Jakim]

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.

[Platyna]

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.