Jak dostosować drzewo wyszukiwania Minimax do gry bez terminów?

Question

Muszę wykonać projekt, w którym musimy wprowadzić mancala, a następnie zaimplementować sztuczną inteligencję.

Zostaliśmy pouczeni, że musimy zmodyfikować lub zmienić drzewo minimax, aby móc pracować z mancala, ponieważ w grze jest możliwe, że gracz ma wiele zakrętów pod rząd.

Mam już zaimplementowaną logikę gry i GUI, ale teraz, zanim zacznę z AI, chciałbym spróbować poznać teorię, która za tym stoi. Szukałem w sieci dla niezwiązanych z linią drzew mini max i nie mogę niczego znaleźć. Ale widziałem wielu ludzi mówiących o używaniu minimax dla mancala.

Teraz rozumiem normalne drzewo minimax i sposób, w jaki każdy poziom zmienia się między węzłem minimalnym a węzłem maksymalnym. Z drzewem, którego teraz potrzebuję, czy powiem: min > max > max > min > max, czy drugi gracz ma DWÓŻ zakrętów?

Musimy również być w stanie określić podaną głębokość drzewa Minimax. Musimy również wykonać przycinanie alfa-beta, ale to na później, gdy już będę miał drzewo.

Answer 1

Jeśli strona może mieć wiele ruchów w turze, to musi być jakiś sposób, aby to wykryć. Po wykryciu, generator ruchu dla przeciwnika generuje listę zawierającą tylko ruch zerowy, tzn. Ruch, który nic nie robi. Przeciwnik zostanie zmuszony do wykonania tego ruchu (nie rób nic), a pierwszy gracz może obliczyć następny ruch.

Answer 2

Z tego co rozumiem, Twój główny problem jest następujący: pokazałeś, jak używać minimax w sytuacji, gdy max/min idą w cyklu, a teraz masz grę, w której czasami jeden gracz może wykonywać wiele ruchów w wiersz.

Wyjaśnię ci ogólne podejście, które działa dla praktycznie każdej gry, a następnie dodam kilka rzeczy, które można zrobić inaczej dla mancala.

Tak ogólne podejście

Standardowy minimax idzie tak:

function minimax(node, depth, maximizingPlayer) 
    if depth = 0 or node is a terminal node 
     return the heuristic value of node 
    if maximizingPlayer 
     bestValue := -∞ 
     for each child of node 
      val := minimax(child, depth - 1, FALSE) 
      bestValue := max(bestValue, val) 
     return bestValue 
    else 
     bestValue := +∞ 
     for each child of node 
      val := minimax(child, depth - 1, TRUE) 
      bestValue := min(bestValue, val) 
     return bestValue 

Gdzie zainicjować połączenie minimax z max/min, a potem ciągle się zmienia. W twoim przypadku wystarczy dodać tylko jeden drobny czek.

function minimax(node, depth, maximizingPlayer) 
    if depth = 0 or node is a terminal node 
     return the heuristic value of node 
    if maximizingPlayer 
     bestValue := -∞ 
     for each child of node 
      # here is a small change 
      if freeTurn(child): 
       isMax := TRUE 
      else: 
       isMax := FALSE 
      val := minimax(child, depth - 1, isMax) 
      bestValue := max(bestValue, val) 
     return bestValue 
    else 
     bestValue := +∞ 
     for each child of node 
      # here is a small change 
      if freeTurn(child): 
       isMax := FALSE 
      else: 
       isMax := TRUE 
      val := minimax(child, depth - 1, isMax) 
      bestValue := min(bestValue, val) 
     return bestValue 

Jeżeli czynność freeTurn powraca ty czy masz wolnego obrotu po aktualnym ruchu. Zauważ, że nie ma różnicy dla tego algorytmu, czy możesz wykonać tylko 2 ruchy w rzędzie lub 5 ruchów z rzędu.

chodzi mancala

Istnieje wiele odmian Mancala, ale rozgałęzienia czynnikiem w grze jest dość mała (w tym jeden, który znam jest < = 6). Teraz załóżmy, że masz trzy ruchy: A, B, C, D i przeniesienie C pozwala ci grać jeszcze raz. Z pozycji C można wykonywać ruchy: C1, C2. Możesz więc łączyć je (C + C1, C + C2) i traktować je jako jeden ruch (należy przeprowadzić małą księgowość, aby pamiętać, że są to właściwie dwa ruchy).Tak więc w tej chwili kończysz swoją min max iteracjami, w których nie masz 4, ale 5 ruchów: A, B, C + C1, C + C2, D. W rzeczywistości nie ma nic złego w stosowaniu tego podejścia w grach o większym współczynniku rozgałęzienia.