Struttura dati per giochi di carte bidimensionali in linguaggi funzionali

Question

Struttura dati per giochi di carte bidimensionali in linguaggi funzionali

#1 da (6 voti)
#2 da (5 voti)

9

Sto creando una semplice implementazione MiniMax nel linguaggio di programmazione funzionale Elixir. Poiché ci sono molti giochi di conoscenza perfetta (tic tac toe, connect-four, dama, scacchi, ecc.), Questa implementazione potrebbe essere una struttura per la creazione di IA di gioco per uno qualsiasi di questi giochi.

Un problema che sto affrontando, tuttavia, è come memorizzare correttamente uno stato di gioco in un linguaggio funzionale. Questi giochi si occupano principalmente di schede di gioco bidimensionali, dove sono frequenti le seguenti operazioni:

Leggi i contenuti di una posizione specifica della board
Aggiorna il contenuto di una specifica posizione della scheda (quando si restituisce una nuova possibilità di spostamento)
Considerando il contenuto di una o più posizioni collegate alla posizione corrente (ovvero le posizioni orizzontali, verticali o diagonali precedenti o precedenti)
Considerando il contenuto di più posizioni collegate in qualsiasi direzione.
Considerando il contenuto di interi file, ranghi e diagonali.
Rotazione o mirroring della scheda (per verificare le simmetrie che forniscono lo stesso risultato di una cosa già calcolata).

La maggior parte dei linguaggi funzionali utilizza elenchi collegati e tuple come elementi costitutivi di base delle strutture di dati a più elementi. Tuttavia, questi sembrano molto mal fatti per il lavoro:

Gli elenchi collegati hanno il tempo di ricerca O (n) (lineare). Inoltre, poiché non è possibile "scansionare e aggiornare la scheda" in un'unica operazione sulla lavagna, l'uso delle liste sembra molto poco pratico.
Tuple hanno O (1) (costante) tempo di ricerca. Tuttavia, rappresentare la scacchiera come una tupla a dimensione fissa rende molto difficile iterare su ranghi, file, diagonali o altri tipi di quadrati consecutivi. Inoltre, sia Elixir che Haskell (che sono le due lingue funzionali che conosco) mancano di sintassi per leggere l'elemento n di una tupla. Ciò renderebbe impossibile scrivere una soluzione dinamica che possa funzionare per schede di dimensioni arbitrarie.

Elixir ha una struttura di dati Mappa incorporata (e Haskell ha Data.Map ) che consente l'accesso agli elementi a O (log n) (logaritmico). In questo momento io uso una mappa, con x, y tuple che rappresentano la posizione come chiavi.

Questo "funziona", ma è sbagliato abusare delle mappe in questo modo, anche se non so esattamente perché. Sto cercando un modo migliore per memorizzare una bacheca di gioco bidimensionale in un linguaggio di programmazione funzionale.

functional-programming data-structures

posta Qqwy 15.06.2016 - 22:26

fonte

2 risposte

Leggi altre domande sui tag functional-programming data-structures

Preparazione allo sviluppo del Web e flusso di lavoro dell'intero progetto Scegliere un JavaScript Async-Loader [chiuso]

score 6 · Answer 1

Un Map è esattamente la giusta struttura dati di base qui. Non sono sicuro del perché ti farebbe sentire a disagio. Ha una buona ricerca e tempi di aggiornamento, è di dimensioni dinamiche, ed è molto facile creare strutture di dati derivative da. Ad esempio (in haskell):

filterWithKey (\k _ -> (snd k) == column) -- All pieces in given column
filterWithKey (\k _ -> (fst k) == row)    -- All pieces in given row
mapKeys (\(x, y) -> (-x, y))              -- Mirror

L'altra cosa che è difficile da comprendere per i programmatori quando iniziano a programmare con la massima immutabilità è che non è necessario attenersi a una sola struttura di dati. Di solito scegli una struttura dati come la tua "fonte di verità", ma puoi creare tutti i derivati che vuoi, anche i derivati delle derivate, e sai che rimarranno sincronizzati finché ne avrai bisogno.

Ciò significa che puoi utilizzare Map al livello più alto, quindi passare a Lists o Arrays per l'analisi delle righe, quindi Arrays indicizzato nell'altro modo per l'analisi delle colonne, quindi maschere di bit per l'analisi del modello, quindi Strings per la visualizzazione. I programmi funzionali ben progettati non passano attorno a una singola struttura di dati. Si tratta di una serie di passaggi in cui una struttura dati viene inserita e ne viene emesso uno nuovo adatto al passaggio successivo.

Se riesci a uscire dall'altra parte con una mossa in un formato che il livello superiore può comprendere, non devi preoccuparti di quanto devi ristrutturare nel frattempo. È immutabile, quindi è possibile tracciare un percorso verso la fonte della verità al massimo livello.

score 5 · Answer 2

L'ho fatto di recente in F # e ho finito per usare un elenco unidimensionale (in F #, che è un elenco a link singolo). In pratica, la velocità di O (n) list indexer non è un collo di bottiglia per le dimensioni delle schede utilizzabili dall'uomo. Ho fatto esperimenti con altri tipi come array 2d, ma alla fine, è stato il compromesso tra scrivere il mio proprio codice di controllo dell'uguaglianza di valore o una traduzione di rank e file per indicizzare e tornare indietro. Quest'ultimo era più semplice. Direi che prima funziona, quindi ottimizza il tuo tipo di dati in un secondo momento, se necessario. Non è probabile che faccia una differenza abbastanza grande da contagiare.

Alla fine la tua implementazione non dovrebbe avere importanza finché le operazioni della tua scheda sono correttamente incapsulate dal tipo di scheda e dalle operazioni. Ad esempio, ecco come possono apparire alcuni dei miei test per configurare una scheda:

let pos r f = {Rank = r; File = f} // immutable record type
// or
let pos r f = OnBoard (r, f) // algebraic type
...
let testBoard =
    Board.createEmpty ()
    |> Board.setPiece p (pos 1 2)
    |> ...

A questo codice (o qualsiasi altro codice chiamante), non importa come fosse rappresentata la scheda. La scheda è rappresentata dalle operazioni su di essa più che dalla struttura sottostante.