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

[jasnoniebieski.5]

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ą???

[alsor]

Zapomniałeś napisać jaki jest cel gry - co trzeba zrobić aby wygrać?

[jasnoniebieski.5]

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]

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...

[jasnoniebieski.5]

"po postawieniu pionków na plansze te pionki nie należą już do żadnego z
graczy"... :)

[rozbitek_65]

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.