Nim gra pytanie

Question

OK, muszę zrobić grę NIM i spróbować znaleźć strategię zawsze wygrać z następującym gry NIM:

21 meczów, odtwarzacz 1 i 2 każdy ma 1, 2, 3, 4 lub 5 dopasowań w każdej turze i nie można przyjąć takiej samej liczby dopasowań, jaką mają poprzedni gracz. Th eplayer wygrywa, jeśli/kiedy podejmie ostatni mecz.

Muszę coś w tym celu zaprogramować, ale nawet nie rozumiem, żeby zacząć. Jak mogę znaleźć zwycięską strategię w tego typu grze nim?

EDIT:

więc pomyślałem, że zawsze wygrać, kiedy dojdziesz do 7 meczach nadal w środku. Druga może zająć 2-5, a ostatnia może dodać do 7. kiedy drugi bierze 1, bierzesz 3 (drugi też nie może wziąć 3) i musisz wybrać 1 lub 2, w takim przypadku otrzymasz pierwszą i wygrasz.

jednak będzie od 21 do 7 jest zagadką dla mnie nie mogę dowiedzieć się, jak można być zawsze osoba dotarcie do 7.

EDIT 2: ok więc bez zasady, że nie można brać taki sam jak poprzedni gracz, wydaje mi się, że jest całkiem prosty.

Zrobiłbyś k = 5 + 1 = 6. to powinieneś wykonać pierwszy ruch tak, aby mecze pozostały wtedy% 6 = 0. Więc w tym przypadku weź 3 pierwsze, a następnie wypełnij ruch inny gracz do 6. Jednak w tym przypadku to nie zadziała, ponieważ drugi gracz może zająć 3, po których nie można zająć 3, aby wypełnić do 6. Więc jest mój problem. Jakieś pomysły?

Edit3:

ok, więc można powiedzieć mogę zmusić 7 meczów. Jednak przypuśćmy, że biorę to samo myślenie na krok 14-7 dopasowań. (wtedy jest kolej drugiej)

są wtedy dwa scenariusze: 1: bierze 2-5, a ja wypełniam go do siedmiu, które pozwalają na 7 i wygrywam. 2: bierze 1, więc pozostało 13. Kiedy weźmiesz 3, jak robię w (7-0) -stepie, to staje się 10. Potem bierze 5 i nie mogę już 5, aby zakończyć, a ja stracę.

Tu leży problem, w którym scenariusz 2 nie stanowi problemu w (7-0) -stepie jest teraz. Jak rozwiązać ten problem?

TAK, rozwiązanie:

btw, na speler 1 oznacza: po Gracz 1 kolej itd (jestem holenderski).

Ok więc próbowałem kilka rzeczy i myślę, że mam rozwiązanie. Musisz wziąć 1 mecz jako pierwszy gracz. Następnie inni faceci mogą wziąć 2-5 meczów. Dopasowujesz (kalambur przeznaczony) jego ilość do 7, więc zawsze będziesz miał (21-1-7 =) 13 meczów w środku. Następnie następuje powrót gracza 2 i istnieją dwa scenariusze: gracz 2 bierze 1,2,4, lub 5 meczów, w takim przypadku bierzesz tyle meczów, ile będzie 7 po lewej. (jak powiedzieliśmy wcześniej, kiedy bierzesz mecze w taki sposób, że 7 pozostało, zawsze wygrasz). Drugi scenariusz polega na tym, że gracz 2 bierze 3 mecze, w którym to przypadku jest 10 w środku, kiedy jest twoja kolej. Nie możesz wziąć 3, aby zrobić 7, ponieważ nie możesz wziąć 2 razy tyle samo. Więc weź 5, pozostało 5. Gracz 2 nie może wziąć 5, aby wygrać i musi wybrać 1-4, po czym możesz wziąć pozostałe i wygrać.

To jest rozwiązanie, jak sądzę.I jakoś przyszedł na nią, bo zauważył to:

Normal Nim grę z modulo etc:

P2 1 2 3 4 5 
P1 5 4 3 2 1 
------------------ 
    6 6 6 6 6 

Ale nie można zrobić 3,3 tu więc liek to:

p2 1 2 3 4 5 
p1 5 4 3 2 1 
--------------------- 
     7 7 7 7 

Tak możesz zrobić 7 za każdym razem, a 1 to specjalny przypadek. Nie wiem dlaczego, ale intuicyjnie zająłem 1 jako punkt wyjścia, ponieważ wydaje się, że trzeba podjąć inicjatywę, aby móc kontrolować ruchy innych. (nie można zrobić dwa razy 1, więc drugi musi wziąć 2-5, co daje ci kontrolę)

W każdym razie, DZIĘKI dużo za całą pomoc. Także dla całego programu, który został napisany. Nie mogłem go użyć, ponieważ nie skompilowałbym się jako brak dobrych umiejętności java :) i chciałem też rozwiązać go samodzielnie.

W każdym razie widziałem, że to wiki, powodzenia dla ludzi w przyszłości próbujących rozwiązać ten problem!

Answer 1

W grach takich jak ta, musisz utrzymywać niezmienność bycia w wygrywającej pozycji (jeśli już jesteś w jednym). Musisz więc wiedzieć, jak zacząć od zwycięskiej pozycji, a następnie powrócić do niej , niezależnie od tego, co poruszy twój przeciwnik.

Oto trzy wskazówki dla Ciebie:

1. Twój moveset i moveset przeciwnika, jest taka sama: Take 1, 2, 3, 4 lub 5 meczów.
2. Ta gra, gdy do niej dojdziesz, to gra dodająca.Tak, odejmujesz dopasowania, ale nadal pomagasz myśleć w kategoriach dodawania, gdy formułujesz swoją strategię.
3. Zacznij od tego: dla każdego ruchu przeciwnika X (gdzie X to 1, 2, 3, 4 lub 5), jaki ruch możesz zrobić, aby "anulować", które wyprowadzą?

Koncepcja, którą próbuję znaleźć, została wyjaśniona w koncepcji modular arithmetic, w przypadku, która pomaga.

---

Edit: Ograniczenie nie biorąc taką samą liczbę meczów sprawia, że ​​rzeczy interesujące, choć. Będziemy musieli zająć się tym jako przypadkiem narożnikowym później, ale najpierw zobaczmy, jak przychodzisz z tym, co do tej pory powiedziałem. Prosimy o komentarz na ten temat.

---

Edit 2: Jesteś poprawne z drugiej edycji w ogóle (jeśli reguła o braku powtarzanych ruchów nie było, mam na myśli). Ale twoja pierwsza edycja była na dobrej drodze: możesz sprawić, żeby rzeczy działały w 7-tych.

Wystarczy mieć wątpliwość i odpowiadając sobie pytanie:

Q: Jak mogę wiarygodnie wymusić wygraną AI poprzez AI wziąć ostatni mecz?
A: Zmusz sztuczną inteligencję do opuszczenia 7 meczów, a następnie użyj swojej strategii, aby zmusić sztuczną inteligencję do zabrania 7-tego. To dlatego, że możesz wymusić odjęcie dokładnie 7 dopasowań.
P: Jak więc wymusić zwycięstwo dla AI, upewniając się, że AI bierze ostatni mecz (ale siedem)?

Nie należy tego nadmiernie myśleć. Weź to, co już wiesz - co już możesz zrobić, aby sztuczna inteligencja się ... i zastosuj ten krok tyle razy, ile możesz.

---

Edit 3: To tylko drobna uwaga myślałem, że może pomóc uporać się z tym problemem można wymienić w swojej trzeciej edycji.

Jeśli dla wszystkich X w zestawie (1, 2, 3, 4, 5) pozostaną 2 x mecze, gdy nadejdzie kolej AI, wtedy możesz wymusić zwycięstwo, biorąc mecze X. (Ty szczegółowy sposób, chyba że inny gracz w swojej trzeciej edycji)

Niestety, to nie jest coś, co można wymusić, bo mówię istnienia 2X mecze przed turę AI, natomiast druga Warunki wygranej w strategii są zależne od pozycji po kolejce AI, po to, aby ruch AI mógł ją wymusić.

Podobnie, chcesz uniknąć konieczności wynik ruch AI w 2X pasuje do żadnej z tych X.

Answer 2

Użyj Minimax algorithm, potencjalnie z przycinaniem alfa-beta, jeśli chcesz ograniczyć czas pracy.

Zasadniczo wyczerpująco przeszukuj drzewo możliwych ruchów, a następnie cofnij się w górę, aby wybrać najlepszy wynik.

Edytuj: Oto kod, który pokazuje, jak łatwo można stworzyć idealnego agenta. Kodowanie trwało około 5 minut.

public class MinimaxNim { 

    public static int getBestMove(int matchesLeft, int lastVal) { 
     int max = Integer.MIN_VALUE; 
     int bestMove = matchesLeft > 0 ? 1 : 0; 
     for (int move = 1; move <= 5 && move <= matchesLeft; move++) { 
      if (move == lastVal) 
       continue; 
      int val = minValue(matchesLeft - move, move); 
      if (val > max) { 
       bestMove = move; 
       max = val; 
      } 
     } 
     return bestMove; 
    } 

    private static int maxValue(int matchesLeft, int lastVal) { 
     if (matchesLeft == 0) 
      return -1; //min has won 

     int max = Integer.MIN_VALUE; 
     for (int toTake = 1; toTake <= 5 && toTake <= matchesLeft; toTake++) { 
      if (toTake == lastVal) 
       continue; 
      int val = minValue(matchesLeft - toTake, toTake); 
      if (val > max) { 
       max = val; 
      } 
     } 
     return max; 
    } 

    private static int minValue(int matchesLeft, int lastVal) { 
     if (matchesLeft == 0) 
      return 1; //max has won 

     int min = Integer.MAX_VALUE; 
     for (int toTake = 1; toTake <= 5 && toTake <= matchesLeft; toTake++) { 
      if (toTake == lastVal) 
       continue; 
      int val = maxValue(matchesLeft - toTake, toTake); 
      if (val < min) { 
       min = val; 
      } 
     } 
     return min; 
    } 
} 

Można przetestować z tym:

public static void main(String[] args) { 
    int count = 21; 
    int move = -1; 
    for (;;) { 
     move = getBestMove(count, move); 
     System.out.println("Player 1 takes " + move); 
     count -= move; 
     if (count == 0) { 
      System.out.println("Player 1 has won"); 
      break; 
     } 
     move = getBestMove(count, move); 
     System.out.println("Player 2 takes " + move); 
     count -= move; 
     if (count == 0) { 
      System.out.println("Player 2 has won"); 
      break; 
     } 
    } 
} 

Ale chciałbym zaproponować zastąpienie albo gracz 1 lub gracz 2 z siebie, albo środek losowy, tak aby badać ruchy, że doskonały sprawia, że ​​gracz .

Ponownie, to nie pokazuje najlepszej strategii , ale będzie ona wykazywać optymalną grę przeciwko każdemu przeciwnikowi (choć nietestowanemu).

Edycja 2

W przypadku jesteś ciekawy, od stanu początkowego są tylko 26.705 stany końcowe (gdzie gracz wygrał), które muszą zostać zbadane. Staje się coraz mniej, gdy wykonujesz więcej ruchów. To, co sprawia, że ​​jest to idealne dla minimax, to fakt, że postęp jest zawsze wykonywany ... gdy masz już 15 meczów na stosie, nie możesz wrócić do 17, np. W grze takiej jak w szachy możesz uzyskać cykle w drzewie wyszukiwania, ponieważ gracze mogą po prostu tańczyć wokół planszy, powracając do poprzednich stanów, itp.

Answer 3

Podobnie jak kilka danych do rozważenia, wpadłem mojego agenta przed każdym możliwym scenariuszu można mieć w grze (1-21 kije pozostawione razy 5 możliwych ostatnich ruchów). Niektóre z tych stanów są niemożliwe (na przykład 20, przy czym ostatni ruch to 2). Usunąłem większość z nich ze stołu, ale prawdopodobnie pozostaną.

Jeśli istnieje wartość dla tej kombinacji, oznacza to, że rozgrywanie tego ruchu w tym momencie z pewnością spowoduje wygraną (zakładając kontynuację doskonałej gry).

Osoby oznaczone jako x oznaczają, że bycie w tym stanie z pewnością spowoduje stratę niezależnie od ruchu (przy założeniu doskonałej gry przeciwnika).

0 1 2 3 4 5 
21 1   
20 x   
19  3  
18 5 5 5  
17 4 4 5 
16 3 3 x 3 3 
15 2 1 1 1 1 
14 x 1 1 1 1 
13 x x x x x 
12 5 5 5 5 x 
11 4 4 4 x 4 
10 3 3 5 3 3 
9 2 3 2 2 2 
8 4 1 1 1 1 
7 x x x x x 
6 3 3 x 3 3 
5 5 5 5 5 x 
4 4 4 4 x 4 
3 3 3 x 3 3 
2 2 1 1 1 1 
1 x 1 1 1 1 

Więc jeśli utkniesz robi analizy, można odnośnika w tej tabeli, co (lub, jeśli istnieje wiele najlepsze ruchy) najlepsza akcja jest w danym państwie.

Jedną z rzeczy, na którą warto zwrócić uwagę jives z dotychczasową analizą: jeśli to Twój ruch, a pozostało ci 7 patyków, jesteś spieprzony! Ale zauważ także 13.