GRA Z PERŁAMI - taktyka wygrywajaca

[_el_doopa]

nalezy okreslic kiedy i dla ktorego gracza istnieje taktyka wygrywajaca i najlepiej podac ta taktyke

w grę grają 2 osoby, ruchy wykonywane są na zmiane,
do gry potrzebne sa 3 worki w kazdym jest pewna ilosc pereł,
w kadzym ruchu gracz moze zabrac dowolna całkowitą ilosc pereł z dowolnego worka,
przy czym nie moze wyciagac pereł z kilku worków naraz,
przegrywa ten gracz ktory wyciagnie ostatnia perłę

mozna to rozszerzyc na dowolna całkowita ilosc worków.

zadanie to nie jest zadnym zadadniem olimpiskim,natknąłem się jedynie na taką gre i chciałbym wiedzieć jak grac by wygrac, napisalem program ale brute-force ze przy danych rzedu 10, 10, 10 po godzinie nie wypluwa wyniku, licze jednak ze da sie to zrobic sila ludzkiego umyslu.

[arigo]

daj na poczatek mniejsze dane zeby zobaczyc czy algorytm jest poprawny
pozniej mozesz probowac optymalizacji algorytmu dla wyzszych wartoci parametrow na podstawie wynikow uzyskanych dla ich nizszych wartosci
btw algorytm napisany iteracyjnie czy rekurencyjnie ?

[_el_doopa]

jest poprawny sprawdzalem
rekurencyjnie,
ale to jest glupi bruteforce bo mozna robic bruteforce byle inteligentnie, a ten jest akurat debilny... ,
wolalbym jednak rozwiazanie bez uzycia komputera...
btw zoptymalizuje ten program bo naprawde jest idiotyczny....

[Arbooz]

Hmm, ciekawe zagadnienie...
Póki co doszedłem do czegoś takiego:

Sytuacja A: w każdym z worków mamy po jednej perle. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja B: jeden worek pusty, w dwóch pozostałych mamy po dwie perły. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja C: w jednym worku jedna perła, w drugim worku dwie perły, w trzecim worku trzy perły. Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja D: jeden worek pusty, w dwóch pozostałych równa ilość pereł (większa od 1). Osoba, która teraz wyciąga perły, PRZEGRYWA.
Sytuacja E: jeden worek pusty, w drugim worku jedna perła, w trzecim worku dowolna ilość pereł (większa od 0). Osoba, która teraz wyciąga perły, WYGRYWA.

Moim zdaniem, strategię wygrywającą, może przyjąć gracz, który wykonuje ruch jako pierwszy. W sytuacji, gdy na początku w dwóch workach jest taka sama liczba pereł wyciągamy wszystkie perły z trzeciego worka doprowadzając tym samym do sytuacji D. WYGRALIŚMY
Tą sytuację zostawmy więc, jest ona zbyt prosta

Załóżmy więc, że w każdym worku jest różna ilość pereł. Załóżmy także, że w każdym worku jest conajmniej jedna perła (w przeciwnym razie w pierwszym ruchu moglibyśmy doprowadzić do sytuacji D tym samym WYGRYWAJĄC). Załóżmy także, że w przynajmniej dwóch workach znajduje się więcej niż 3 perły (w przeciwnym razie w pierwszym ruchu moglibyśmy doprowadzić do sytuacji C tym samym WYGRYWAJĄC).

Zatem w tej sytuacji proponuję zacząć od wyciągnięcia pereł z worka, w którym jest ich najmniej, tak, by została w nim jedna perła. Teraz:
a) Jeśli nasz przeciwnik wyciągnie tą jedną perłę, którą my zostawiliśmy, w naszym ruchu możemy doprowadzić do sytuacji D tym samym WYGRYWAJĄC.
b) Jeśli nasz przeciwnik wyciągnie taką ilość pereł, że wyrówna ilości pereł w dwóch pozostałych workach, to my wyciągamy tą jedną perłę, cośmy ją na początku zostawili otrzymując sytuację D kopiąc tym samym przeciwnikowi tyłek (znaczy się WYGRYWAJĄC;))
c) Jeśli nasz przeciwnik będzie się wystrzegał zagrań z wersji a) i b) będzie musiał wyciągać perły z dwóch pozostałych worków tak by liczba pereł w tych workach pozostawała różna. Podobnie będziemy musieli postępować my, żeby role się nie odwróciły Takie granie doprowadzi w końcu do sytuacji A lub C. Pozostaje nam teraz ustalić, jak to rozegrać, żeby wygrać

Póki co mam tyle, ale myślę dalej...

[mgol]

Podobna gra, tylko z odwróconymi warunkami wygrywającymi i przegrywającymi (i zamiast worków z perłami słupki kwadratów, ale to to samo) to NIM.

[_el_doopa]

dokladnie, juz to znalazlem z miesiac temu o ty nimie i bardzo prosto wygooglalem sobie i taktyke znalazlem.