Dodaj do ulubionych

[pascal] Strategia wygrywająca - o co chodzi???

26.01.06, 15:35
Witam
Chciałem zapytać o strategię wygrywającą - wogóle nie jestem w stanie jej
pojąć - czytałem o grze "hex" i pochodnych w których stosuje się ją, ale nadal
nie potrafię jej pojąć. Mam zadanie:
Mam planszę o wymiarach n x 1 gdzie n to dlugość planszy. Jest dwóch graczy,
każdy ma do dyspozycji kilka pionków. Na starcie rozstawiają je na dowolne
pole, ale dwa nie mogą stać na tym samym. I teraz przesuwają te pionki o
dowolną parzystą liczbę. Jak dojść do tego, który z nich ma strategię
wygrywającą???
Obserwuj wątek
      • jasnoniebieski.5 Re: [pascal] Strategia wygrywająca - o co chodzi? 27.01.06, 18:17
        Napiszę pełną treść tego zadania:

        Jest kilka pionków, które można przesuwać (skakać nimi) o dowolną parzystą
        liczbę pól. Gra rozgrywana jest przez dwóch graczy na pro-
        stokątnej planszy o wymiarach n × 1. Pola planszy ponumerowane są kolejnymi
        liczbami naturalnymi od 1 do n.
        Przed rozpoczęciem gry na planszy umieszczanych jest "k" ponków na losowo
        wybranych polach. Na każdym polu może znajdować się co najwyżej jeden pionek.
        Gracze na przemian wykonują ruchy, wskazując
        pionek oraz pole, na które ma ono wykonać skok. Z pola o numerze "i" pionek może
        wykonać skok tylko na pola o numerach większych niż "i", jednak nie większych
        niż "n". Gdy pionek dostanie polecenie skoku na pole zajęte przez inny pionek,
        wykonuje wskazany ruch lądując na drugim pionku. Taki skok powoduje, że tymi
        dwoma pionkami nie można dalej grać, dlatego zostają usunięte z planszy.
        Przegrywa gracz, który jako pierwszy nie może wykonać ruchu zgodnie z zasadami
        gry. Pierwszy gracz to gracz, który wykonuje pierwszy ruch w grze. Mówimy, że
        pierwszy gracz posiada strategię wygrywającą, gdy niezależnie od posunięć
        drugiego gracza zawsze może wygrać.

        Wejście
        W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna m
        (1 ≤ m ≤ 1000), określająca liczbę zestawów danych. Opis każdego zestawu składa
        się z dwóch wierszy. W pierwszym wierszu każdego zestawu znajdują się dwie
        liczby naturalne oddzielone pojedynczym odstępem: n i k (1 ≤ k ≤ 100000, k ≤ n ≤
        1000000000), oznaczające odpowiednio: długość planszy oraz liczbę pionków.
        W drugim wierszu każdego zestawu znajduje się k liczb naturalnych oddzielonych
        pojedynczym odstępem, oznaczających numery pól zajmowanych przez pionki przed
        rozpoczęciem gry.

        Wyjście
        Twój program powinien wypisać na standardowe wyjście m wierszy – po jednym dla
        każdego zestawu
        danych. Wiersz o numerze i powinien zawierać wynik dla i-tego zestawu danych –
        napis TAK – gdy gracz
        pierwszy posiada strategię wygrywającą albo napis NIE – w przeciwnym przypadku.
        Przykład
        Dla danych wejściowych:
        2
        8 4
        1 4 5 8
        8 3
        3 5 7
        poprawnym wynikiem jest:
        NIE
        TAK

        Oczywiście nie chodzi mi o to, żeby ktoś mi napisał kod, tylko wytłumaczyl
        ludzikim głosem, dlaczego w pierwszym zestawie jest odpowiedz TAK a w drugim NIE
        - jak zabrac sie za analize tego zadania???
        Pozdrawiam
        • alsor Re: [pascal] Strategia wygrywająca - o co chodzi? 31.01.06, 01:06
          Tłumaczysz to jak... Zabłocki na mydle.

          - chyba są dwa rodzaje pionów - dla każdego gracza inny
          - skaczą tylko do przodu o parzystą liczbę pól, na swój pion nie można wskoczyć
          - wygrywamy po zablokowaniu przeciwnika

          Bicie nic tu nie daje - zmniejsza się jedynie liczba pionów.

          Trzeba w takie coś trochę pograć, wtedy będzie wiadomo jak to działa.

          Dla 1000 pól i kilkunastu pionów można wyliczyć wszystkie kombinacje...
            • rozbitek_65 Re: [pascal] Strategia wygrywająca - o co chodzi? 09.02.06, 02:14
              Wygląda na to, że nie można wykonać ruchu, gdy:
              a) na planszy został tylko jeden pionek, i znajduje się on na polu "n" (czyli
              na końcu planszy).
              b) na planszy nie ma żadnego piona.

              Interpretacja zagadnienia: dla 3 pionów rozstawionych w opisany sposób (pola
              3,5,7) na 8-polowej planszy istnieje strategia wygrywająca, dla 4 na polach
              1,4,5,8 takiej samej planszy taka strategia nie istnieje.

              Zakładając, że nie mamy do udowodnienia żadnego twierdzenia z zakresu teorii
              gier algorytm powinien:
              1. "rozegrać" wszystkie możliwe partie
              2. wykazać, że przy określonej sekwencji swoich ruchów gracz A zawsze wygrywa,
              bez wględu na ruchy wykonywane przez B.

Popularne wątki

Nie pamiętasz hasła

lub ?

 

Nie masz jeszcze konta? Zarejestruj się

Nakarm Pajacyka