gioco di ricerca albero, Devo costruire l'albero prima?

Question

in gioco albero di ricerca ci sono molti algoritmi per ottenere la soluzione ottimale, come algoritmo minimax. Comincio imparare come risolvere questo problema con l'algoritmo minimax, l'algoritmo chiaro. ma sto confuso circa l'albero stesso, in giochi come tic tac toe numero di nodo non molto grande, ma su altri come gli scacchi ci sono molti nodi. Penso che questa esigenza grande spazio in memoria. Quindi non v'è alcun algoritmi per valutare e albero di compilazione nello stesso tempo?

Answer 1

Un albero di stati di gioco non è normalmente costruito come una struttura di dati completo. Invece, gli stati sono valutati come sono creati, e la maggior parte vengono scartati nel processo. torna spesso, una lista concatenata dallo stato in corso di valutazione allo stato attuale del gioco è mantenuta. Ma se una mossa è dimostrato di essere molto meglio di un altro, allora l'intera linea dei poveri mossa sarà scartato, quindi occuperà spazio nella memoria.

Un modo semplice per cercare lo spazio degli stati per un gioco come gli scacchi è quello di fare la ricerca in modo ricorsivo ad una certa profondità. In tal caso, pochissimi stati di gioco in realtà esistono in una sola volta, e quelle che esistono sono semplicemente riferimento al call-stack. Più sofisticati algoritmi creeranno un albero più grande, ma (soprattutto per gli scacchi) nessuno manterranno un albero di tutti gli stati possibili. Per gli scacchi, una ricerca in ampiezza può essere migliore, con una coda piuttosto che uno stack, e questo manterrà solo gli Stati ad una certa profondità nell'albero. Ancora meglio sarebbe una coda di priorità in cui i migliori stati sono conservati per un'ulteriore valutazione, e gli stati peggiori vengono scartate completamente.