Come adattare il mio albero di ricerca Minimax per gestire un gioco a termine?

Question

Devo realizzare un progetto in cui è necessario implementare il gioco da tavolo mancala, e quindi implementare anche l'intelligenza artificiale.

Ci è stato comunicato che è necessario modificare o modificare un albero minimax per poter lavorare con mancala poiché nel gioco è possibile che un giocatore abbia più turni di fila.

Ho già implementato la mia logica di gioco e la GUI, ma ora prima di iniziare con l'intelligenza artificiale vorrei provare a farmi un'idea della teoria che ci sta dietro. Ho cercato in rete per alberi mini max non basati su turni e non riesco a trovare nulla. Ma ho visto molte persone parlare dell'utilizzo di minimax per mancala.

Ora capisco il normale albero minimax e come ogni livello si alterna tra un nodo minimo e un nodo massimo. Con l'albero di cui ho bisogno ora, dovrei dire: min > max > max > min > max se il 2 ° giocatore ha ottenuto DUE turni?

Dobbiamo anche essere in grado di specificare la profondità dello strato dell'albero Minimax. Abbiamo anche bisogno di eseguire l'alfa beta, ma lo farò più tardi, una volta che avrò effettivamente un albero.

Answer 1

Se un lato può avere più mosse in un turno, deve esserci un modo per rilevarlo. Quando viene rilevato, il generatore di mosse per l'avversario genera una lista che contiene solo una mossa nulla, cioè una mossa che non fa nulla. L'avversario sarà costretto a giocare quella mossa (non fare nulla) e il primo giocatore potrà quindi calcolare la sua prossima mossa.

Answer 2

Per quanto ho capito, il tuo problema principale è il seguente: ti è stato mostrato come usare il minimax in una situazione in cui il ciclo di minuti/min va avanti e ora hai un gioco dove a volte un giocatore può fare più mosse in una riga.

Ti spiegherò l'approccio generale che funziona praticamente per qualsiasi gioco, e poi aggiungerò un paio di cose che possono essere fatte in modo diverso per mancala.

Così l'approccio generale

Minimax standard va in questo modo:

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 

Dove si inizializza la chiamata minimax con max/min e poi cambia costantemente. Nel tuo caso hai solo bisogno di aggiungere un piccolo assegno.

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 

Dove la funzione freeTurn si ritorna se si dispone di un turno libero dopo la mossa corrente. Nota che non esiste alcuna differenza per questo algoritmo se puoi fare solo 2 mosse di fila o 5 mosse di fila.

Per quanto riguarda Mancala

Ci sono molte variazioni di mancala, ma il fattore di ramificazione del gioco è piuttosto piccolo (in quello che so è < = 6). Supponiamo ora di avere tre movimenti A, B, C, D e spostare C consente di giocare ancora una volta. Dalla posizione C è possibile eseguire le mosse C1, C2. Quindi puoi combinarli (C + C1, C + C2) e trattarli come una sola mossa (si dovrebbe fare una piccola contabilità per ricordare che si tratta in realtà di due mosse).Così adesso si finisce con i tuoi Min Max iterazioni in cui si dispone non 4 ma 5 mosse: A, B, C + C1, C + C2, D. In realtà non c'è niente di sbagliato nell'usare questo approccio per i giochi con un fattore di ramificazione più grande.