Come simulare la battaglia tra due giocatori?

Question

Ho due giocatori e voglio simulare una partita tra di loro. Entrambi hanno alcuni attributi (potere, intelligenza ...) e azioni diverse. Il risultato di alcune azioni si basa sui valori degli attributi e sul fattore di fortuna.

Algoritmo:

• Costruisci un albero da gioco di tutte le possibili mosse per entrambi i giocatori
  • Game Tree avrebbe probabilmente una profondità limitata
  • Ogni livello apparterebbe a un giocatore diverso
• Usa alcune euristiche ai nodi foglia per scoprire la probabilità di vincere per il giocatore che deve fare una mossa
• Propagare le probabilità (come fa algoritmo Minimax)
• Scegli una mossa con la massima probabilità
• Continua all'inizio di questo algoritmo

Quindi, fondamentalmente questo è algoritmo Minimax. Ho qualche domanda però:

1. Come prendere la fortuna in contabilità?
2. Quando faccio una mossa, devo eseguire di nuovo l'intero algoritmo? (Costruire l'albero con una profondità +1 e nuovo nodo radice, calcola nuove probabilità ...)
3. Qualche altra idea per simulare una battaglia?

Grazie.

Answer 1

Sebbene generalmente il tuo algoritmo abbia senso che non possiamo garantire che questo algoritmo sia il migliore. Ad esempio, immaginiamo due giochi:

1. Nel primo gioco ogni giocatore ha 2 azioni: fuoco con una pistola e colpire con una spada. In questo gioco ogni passaggio non influisce su altri passaggi, quindi costruire un muovere l'albero Non avrò alcun senso qui. Ogni giocatore deve solo scegliere l'arma e continuare a sparare/colpire e gridare 'con lo scudo o su di esso!'Fino alla morte o vincere.
2. Il secondo gioco ha anche una terza azione - rubare lo scudo dell'avversario. In questo caso muovere l'albero Avrà più senso poiché è abbastanza chiaro che se hai deciso di rubare lo scudo nemico comunque, avrà più senso rubarlo prima di colpire con una spada.

Quindi se ne hai bisogno muovere l'albero o non dipende fortemente dalle regole del gioco.

L'opzione principale riguardante Fattore di fortuna Come vedo è se includere la sua influenza in muovere l'albero o no. Dipende se se Fattore di fortuna colpisce ogni azione allo stesso modo. Se è vero, allora il fattore di fortuna può essere omesso durante il calcolo muovere l'albero e poi applicato quando calcolerai il risultato dell'azione scelta. Altrimenti se il fattore di fortuna influisce su diverse azioni in modo diverso (ad esempio anche il perdente completo è in grado di girare un nemico con una pistola ma Uccidi con un cucchiaio L'abilità richiede buona fortuna) allora dovrebbe essere preso in considerazione il fattore di fortuna mentre si calcola le probabilità nell'albero di spostamento.

Che tu abbia bisogno o meno di ricalcolare l'intero albero dopo che ciascun nodo dipende dal fatto che sia possibile prevedere il risultato dell'azione scelta con il 100%. Ad esempio negli scacchi puoi prevedere che se hai deciso di spostare un pedone, quel pedone si muoverà sicuramente dove hai deciso. Ciò ti consente di prendere il ramo scelto nell'albero di mossa e calcolare un'altra mossa per ogni scenario in esso invece di ricalcolare l'albero completo dal nulla. Ma questo non è applicabile se il giocatore può decidere di sparare con una pistola, ma a causa del giorno sfortunato si sparerà a una gamba.

Answer 2

Dovresti esaminare la ricerca sull'albero di Monte Carlo, sembra che se si adatta perfettamente al tuo problema.

Piuttosto che usare un euristico, gestisce un gioco completo usando giocatori casuali in ogni ramo prima di espandere l'albero. La cosa buona di questo è che stai effettivamente costruendo un albero di probabilità e non devi espandere l'albero fino alla fine o un po 'di taglio con euristica come Minmax.

MCTS è anche il miglior metodo attuale del gioco, e attualmente migliore a giocare con regole sconosciute. Per un effetto extra, è possibile utilizzare alcuni agenti a macchina a stato finito anziché i giocatori casuali per rendere la probabilità più accurata. E puoi anche ridurre il fattore di ramificazione utilizzando un decisore che salta determinati rami, usando un euristico derivato dall'apprendimento automatico. (Ma è qualcosa che faresti per ultimo per aumentare la velocità della tecnica)

Se riesci a fare Minmax, puoi fare MCT senza troppi problemi :) E MCTS può giocare a giochi molto più complessi di quanto Minmax lo farà mai, a causa della sua complessità notevolmente ridotta in confronto. (Buono se si intende espandere continuamente le regole del gioco)

Dai un'occhiata qui se sei interessato:

http://www.aaai.org/papers/aiide/2008/aiide08-036.pdf

E sì, devi farlo ad ogni mossa per ogni giocatore. Quindi sia Minmax che MCT saranno lenti; Tutte le tecniche basate su Game Tree sono lente.

Con Minmax puoi comunque preservare un po 'del tuo albero; Passa al ramo che è il tuo nuovo stato e rimuovi i suoi genitori e i sottostrutici che sono collegati ad esso. Quindi espandi una profondità nel sottostruttura che rimane. Ma questa è speculazione; Tuttavia, non ho mai avuto il tempo di farlo :) (Preservare gli errori nei tuoi calcoli di probabilità)

Bene di queste tecniche, è che quando le hai costruite funzionano. Le tecniche di apprendimento automatico sono molto più veloci, ma richiedono ore se non giorni di allenamento prima dell'uso;)

Answer 3

Quello che stai chiedendo è molto "vasto" ... ma è stato fatto da molti sviluppatori.

Consigli di iniziare a leggere un libro sul design del gioco come questo:http://www.amazon.com/game-design-practice-wordware-developers/dp/1556229127/ref=cm_cr_pr_product_top

... e cerca anche www.codeproject.com e www.codeplex.com Per esempi di implementazioni di giochi.

Buona fortuna,