Algoritmo di Minimax:Costo/funzione di valutazione?

Question

Un progetto della scuola, mi ha iscritto una Data gioco in C++ (ad esempio a http://www.cut-the-knot.org/Curriculum/Games/Date.shtml), dove il giocatore deve implementare un algoritmo di Minimax con la potatura alfa-beta.Finora, posso capire che l'obiettivo è dietro l'algoritmo in termini di massimizzare il potenziale di guadagni, supponendo che l'avversario minimizzare loro.

Tuttavia, nessuna delle risorse che ho letto mi ha aiutato a capire come progettare la funzione di valutazione del minimax basi di tutte le decisioni del.Tutti gli esempi hanno avuto arbitraria numeri assegnati ai nodi foglia, però, ho bisogno di assegnare valori significativi di tali nodi.

L'intuizione mi dice che sarebbe qualcosa di simile a +1 per la vittoria nodo foglia, e -1 per una perdita, ma come fare i nodi intermedi valutare?

Qualsiasi aiuto sarebbe molto apprezzato.

Answer 1

La maggior parte di base minimax valuta solo i nodi foglia, marcatura vittorie, sconfitte e pareggi, e effettua tali valori la struttura per determinare il nodo intermedio valori.Nel caso In cui la struttura del gioco è intrattabile, è necessario utilizzare un taglio profondità come parametro aggiuntivo minimax funzioni.Una volta che la profondità è raggiunta, è necessario eseguire un qualche tipo di funzione di valutazione incompleta stati.

Più funzioni di valutazione in una minimax di ricerca sono di dominio specifico, in modo da trovare la guida per il gioco particolare, può essere difficile.Basta ricordare che la valutazione deve restituire un qualche tipo di percentuale attesa la posizione che è stata una vittoria per un solo giocatore (di solito max, se non quando si utilizza un negamax attuazione).Qualsiasi meno ricercato gioco sta andando ad assomigliare un altro più ricercate di gioco.Questo legame molto stretto con il gioco pickup sticks.Utilizzando minimax alfa e beta solo, direi che il gioco è trattabile.

Se è necessario creare una funzione di valutazione per i non terminali, qui è un po ' di aiuto con l'analisi dei bastoni di gioco, che si può decidere se il suo utile per la data di gioco o meno.

Iniziare la ricerca di un modo per forzare un risultato, cercando una posizione terminale e tutte le mosse che può portare a quella posizione.I bastoncini di gioco, un terminale di posizione con 3 o meno di bastoni rimanenti su l'ultima mossa.La posizione che procede immediatamente che la posizione del morsetto è quindi lasciando 4 bastoni per il vostro avversario.L'obiettivo è ora di lasciare il tuo avversario con 4 bastoni non importa cosa, e che può essere fatto da 5, 6 o 7 bastoncini di essere lasciato per voi, e si desidera forzare l'avversario a lasciare in una di quelle posizioni.Il luogo il tuo avversario deve essere in ordine per voi per essere in 5, 6 o 7 è 8.Continuare questa logica e un modello diventa disponibili molto rapidamente.Lasciare sempre il vostro avversario con un numero divisibile per 4 e si vince, niente altro, si perde.

Questo è un piuttosto banale gioco, ma il metodo per determinare l'euristica è ciò che è importante perché può essere applicato direttamente al vostro incarico.Dal momento che l'ultimo a muoversi va in primo luogo, e si può cambiare solo 1 data attributo alla volta, sai che per vincere c'è bisogno di essere esattamente 2 si sposta a sinistra...e così via.

In bocca al lupo, facci sapere che cosa si finisce per fare.

Answer 2

Il caso più semplice di una funzione di valutazione è +1 per la vittoria, 1 per una perdita e 0 per tutti i non-finito di posizione.Dato che il vostro albero è abbastanza profondo, anche questa semplice funzione vi darà un buon giocatore.Per tutti i non-banale giochi, con alto fattore di ramificazione, in genere è necessario un funzionamento migliore, con alcune euristiche (ad es.per gli scacchi si potrebbe assegnare pesi a pezzi e trovare una somma, etc.).Nel caso della Data di gioco, vorrei solo utilizzare la più semplice funzione di valutazione, con 0 per tutti i nodi intermedi.

Come nota a margine, minimax non è il miglior algoritmo per questo particolare gioco;ma immagino che tu lo sappia già.

Answer 3

Da quello che ho capito del gioco Data è legata, sembra che il solo risultati possibili per un lettore vincere o perdere, non c'è in mezzo (per favore mi corregga se sbaglio).

In questo caso, è solo una questione di assegnazione di un valore di 1 per una posizione vincente (corrente giocatore ottiene al 31-Dic -) e un valore di -1 per le posizioni in perdita (altro giocatore ottiene al 31-Dic -).

Algoritmo di minimax (senza la potatura alfa-beta) sarebbe simile a questa:

A_move(day):
   if day==December 31:
       return +1
   else:
       outcome=-1
       for each day obtained by increasing the day or month in cur_date:
           outcome=max(outcome,B_move(day))
       return outcome

B_move(day):
   if day==December 31:
       return -1
   else:
       outcome=+1
       for each day obtained by increasing the day or month in cur_date:
           outcome=min(outcome,A_move(day))
       return outcome