Come scegliere una mossa / azione / elemento casuali non probabilisticamente?

Question

Come scegliere una mossa / azione / elemento casuali non probabilisticamente?

#1 da (9 voti)
#2 da (3 voti)
#3 da (2 voti)

4

Sto cercando di creare un'IA semplice che può giocare usando Ricerca dell'albero di Monte Carlo .

Questa domanda, tuttavia, è valida per tutti i giochi in cui i giocatori a turno fanno un'azione che, in media, riduce la quantità di azioni possibili da intraprendere in futuro. (Altri esempi potrebbero essere Tic Tac Toe, Connect 4 e un sacco di altri.), O qualsiasi situazione in cui abbiamo bisogno di " Scegli una possibilità casuale fino a quando non rientra nei parametri previsti ".

In Go, i giocatori a turno mettono una pietra del loro colore sul tabellone. Quando la scheda si riempie, alcune mosse non sono più valide (ad esempio perché potrebbe esserci già una pietra in quella posizione. *)

L'algoritmo dovrebbe scegliere una mossa a caso. Tuttavia, come possiamo garantire che la mossa che abbiamo scelto sia valida? Vedo le seguenti opzioni, ognuna con i propri svantaggi:

Quando lo spostamento non è valido, sceglierne uno nuovo casuale. Svantaggio: il programma è ora probabilistico; è molto probabile che selezioni solo le mosse non valide ripetutamente, e quindi non finisca mai di essere eseguito.
Quando la mossa non è valida, passa al quadrato successivo (avvolgendolo ai bordi della scacchiera). Svantaggio: quando c'è una vasta area del tabellone che è già occupata, la distribuzione delle mosse scelte non è più casuale: è molto più probabile che venga scelta la posizione proprio accanto all'area riempita, come quando il numero casuale cade in questo intervallo, questo è il quadrato scelto.
Per prima cosa ottieni un elenco di tutte le possibilità e scegli un elemento casuale da questo elenco. Ciò garantisce un'equa distribuzione delle probabilità. Svantaggio: Perché abbiamo bisogno di scorrere l'intera scheda e ottenere un elenco di tutte le mosse possibili, questo è inefficiente. Dato che l'algoritmo dovrebbe funzionare il più velocemente possibile (poiché vogliamo simulare il maggior numero possibile di giochi), è meglio evitare di ripetere l'intera scheda.

Ora, mi chiedo se esiste un altro metodo per scegliere una mossa a caso che:

Non favorisce in modo significativo determinati risultati rispetto ad altri.
terminerà.
Non ha bisogno di scoprire prima tutte le possibili mosse da una determinata posizione.

* (Le regole di Go hanno più condizioni perché una mossa sia valida, ma queste non cambiano questa domanda)

game-development random

posta Qqwy 10.06.2015 - 14:19

fonte

3 risposte

9

Gestisci e aggiorna la lista delle possibili mosse da scegliere.

Le modifiche a questa lista saranno piccole per mossa in media e spesso localizzate dove il pezzo è stato messo.

risposta data 10.06.2015 - 14:26

fonte

3

Che ne dici di utilizzare un approccio ibrido?

In primo luogo, stimare il numero di mosse valide disponibili. (Probabilmente basato sulla percentuale della tavola coperta da pietre / pioli / pedine.)

Se il numero di mosse valide disponibili è elevato, allora va bene seguire la strategia di provare le mosse a caso finché non viene trovata una valida, perché presto darà un risultato.

Se il numero di mosse valide disponibili è piccolo, allora sai che iterare sull'intera scacchiera e ottenere un elenco di tutte le mosse possibili non rappresenterà un sovraccarico enorme, quindi puoi andare avanti e costruire questo elenco e quindi scegli dalla lista una mossa che è già nota per essere valida.

risposta data 10.06.2015 - 14:24

fonte

Leggi altre domande sui tag game-development random

Gestione dei database di micro-servizi? L'ordine dei valori in? : espressione

score 2 · Accepted Answer

Proviamo ad analizzare i costi

When the move is not valid, pick a new random one.
Drawback: The program is now probabilistic; it is very possible that it picks only invalid moves repeatedly, and therefore never finishes executing.

è? Anche se giochi in una board 19x19 e hai solo una mossa rimasta, ti dà una possibilità 1/361 di prenderla e dovrai provare 1660 volte per avere una probabilità del 99% di terminare. Questo cade rapidamente; per la mossa precedente è 828 e per la stragrande maggioranza è di circa 20 quindi la media è di circa 27

il costo sarebbe ( pickMove + isValid ) * 27

Sì, il caso peggiore è inf , ma vogliamo il caso medio.

First obtain a list of all possibilities, and choose a random element from this list. This ensures an equal distribution of probabilities.
Drawback: Because we need to iterate over the whole board and obtain a list of all possible moves, this is inefficient. As the algorithm should run as fast as possible (As we want to simulate as many games as possible), iterating over the whole board should best be avoided.

quindi questo sarebbe: 361 * isValid + pickMove

Maintain and update the list of possible moves to pick from.

infine, questo sarebbe pickMove + updateList

Quindi ora abbiamo un'approssimazione dei costi, quale è migliore?
(pickMove + isValid)*27 vs 361 * isValid + pickMove vs pickMove + updateList

Sono d'accordo con ratchet freak che la soluzione con la lista sembra la migliore. Ma non lo so per certo; forse updateList diventa super slow dopo aver aggiunto tutte le regole di libertà e ko. Il secondo è migliore del primo? Forse no se pickMove è molto più veloce di isValid .

Ma forse possiamo evitare tutto questo; Ho la sensazione che il seguente algoritmo genererà una distribuzione uniforme:

seleziona una mossa, n
se non è valido, seleziona il quadrato n + 1
salta un quadrato e controlla il quadrato n + 3
se non è valido, vai a 4

l'idea è di saltare un quadrato in più per ogni quadrato non valido che incontri. Potrebbe non funzionare e richiede sicuramente più di un passaggio.

Quindi la mia risposta sarebbe: tracciarli. Questo non è un caso banale di usare quicksort su bubblesort. E, in effetti, a volte potrebbe non essere importante se usi bubblesort. Il che ci porta alla mia vera risposta: sai che è qui che dovresti concentrare i tuoi sforzi di ottimizzazione?

Forse la maggior parte del tempo è sprecato in una infrastruttura dati o in RNG. O forse un approccio consente la parallelizzazione oppure è possibile scrivere un linguaggio di basso livello più semplice, rendendo più veloce il numero. Sì, probabilmente è il tuo ciclo più interno, ma dovresti comunque implementare, testare e ottimizzare le prestazioni.