Negamax - il giocatore si sposta due volte

Question

Come gestisci i giochi in cui, se viene soddisfatta una condizione, si muove lo stesso giocatore?

Ho provato qualcosa di simile, ma non credo che sia giusto:

function negamax(node, depth, α, β, color) 
    if node is a terminal node or depth = 0 
     return color * the heuristic value of node 
    else 
     foreach child of node 
      if (condition is met) // the same player moves 
       val := negamax(child, depth-1, α, β, color) 
      else 
       val := -negamax(child, depth-1, -β, -α, -color) 
      if val≥β 
       return val 
      if val≥α 
       α:=val 
     return α 

Answer 1

Non provare a modificare l'algoritmo minimax per questo, modificare invece la rappresentazione del gioco per adattarla. Esistono fondamentalmente due soluzioni:

1. Rappresentano le sequenze di mosse eseguite da un singolo giocatore come una mossa. Funziona quando il gioco è semplice, ma non sempre. Ho scritto un motore di intelligenza artificiale per un gioco in cui la generazione di questo albero (descritta come una "mossa" nelle regole del gioco) è PSPACE dura (e aveva un grande n per i giochi reali), il che significa che non era fattibile da un punto di vista computazionale. D'altra parte, se la modellazione in questo modo è facile per il tuo gioco particolare, fallo in questo modo
2. Rappresenta le sequenze di mosse fatte da un giocatore come una sequenza di mosse alternate, dove l'altro giocatore fa qualcosa. Cioè, aggiungi un'informazione allo stato del gioco ogni volta che la tua condizione viene soddisfatta, in modo tale che l'unica mossa che l'altro giocatore può effettuare non cambia lo stato. Questo metodo è matematicamente corretto, e quando l'ho usato ha funzionato abbastanza bene nella pratica. L'unica complessità da tenere a mente è che se si utilizza iterative deepening si valuteranno alberi di gioco in cui un giocatore si muove più volte di seguito. Si può anche necessario fare attenzione quando si progetta l'euristica di storage da utilizzare con gli altri transposition table e hash

Non conosco nessun letteratura che discuses vostro problema particolare. Mi sono sentito intelligente quando ho trovato la soluzione 2 sopra, ma sospetto che molte altre persone abbiano inventato lo stesso trucco.

Devo dire che ottenere la famiglia minimax è sorprendentemente difficile. Un trucco per progettare le IA di ricerca di giochi in linguaggi di alto livello è testare i tuoi algoritmi di ricerca su giochi più semplici (dimensioni ridotte della scheda, usare tic-tac-toe, ecc.) Per garantire la correttezza. Se il gioco è piccolo, puoi farlo a. assicurati che i suoi risultati abbiano senso giocando il gioco a mano eb. testare algoritmi avanzati come negascout assicurandosi che diano la stessa risposta di naive negamax. È anche una buona idea cercare di mantenere il codice con un comportamento specifico del gioco (funzioni di valutazione, rappresentazioni della scheda, euristica di ricerca e archiviazione, ecc.) Lontano dal codice che esegue ricerche sugli alberi.

Answer 2

In negamax, si stanno esplorando una struttura ad albero in cui ogni nodo ha figli corrispondenti alle mosse fatte da un giocatore. Se in alcuni casi un giocatore può muovere due volte, probabilmente vorrai pensare alla "mossa" per quel giocatore come alla sequenza di due mosse che il giocatore fa. Più in generale, dovresti pensare ai bambini dello stato attuale del gioco come a tutti gli stati possibili in cui il giocatore attuale può inserire il gioco dopo il loro turno. Ciò include tutti gli stati di gioco raggiungibili con una mossa, più tutti gli stati di gioco raggiungibili in due mosse se il giocatore è in grado di effettuare due mosse in un turno. Pertanto, si dovrebbe lasciare invariata la logica di base di negamax, ma aggiornare il codice per generare stati successori per gestire il caso in cui un singolo giocatore può spostarsi due volte.

Spero che questo aiuti!

Answer 3

Quando la condizione è soddisfatta, non diminuire la profondità.