Qual è la migliore struttura dati per rappresentare una scacchiera quando la velocità è la preoccupazione principale?

Question

Attualmente sto implementando qualcosa di abbastanza simile a dama. Quindi, ho questo gioco da tavolo e ci sono sia pezzi bianchi che neri. Dove non ci sono né pezzi bianchi o neri, non hai pezzi.

Attualmente sto facendo il metodo GetValidMoves() che restituirà tutti i movimenti correnti che si possono fare con la scheda corrente.

Mi sto chiedendo quale potrebbe essere il modo migliore per rappresentare il consiglio. L'approccio ingenuo sarebbe quello di avere una matrice con 0's 1 e 2's (per nessun pezzo, pezzo bianco e pezzo nero).

Altra idea sarebbe quella di una rappresentazione a matrice della scheda, avere 2 liste (o qualsiasi altra struttura dati): una per pezzi neri, l'altra per il bianco.

Sto implementando questo gioco per testare alcuni algoritmi di intelligenza artificiale, quindi la mia preoccupazione principale è la velocità. Fonderò fondamentalmente 2 giocatori IA che si giocano, per ogni turno ogni giocatore dovrebbe avere una lista di tutte le sue mosse valide e poi sceglierà quale mossa fare, questo succede sempre fino alla fine del gioco (qualche giocatore vince o c'è un cravatta).

PS: Non sto chiedendo circa l'algoritmo di intelligenza artificiale, voglio solo sapere cosa sarebbe la migliore struttura di dati per gestire il bordo, in modo che lo rende facile da

1. cercare tutti i mosse valide per il giocatore attuale
2. Fai una mossa
3. Verifica che il gioco non sia finito (è finita quando un giocatore ha perso tutti i suoi pezzi o un giocatore ha raggiunto l'altro lato del tabellone).

Answer 1

Considerare l'utilizzo di una bitmap: due integer a 64 bit senza segno, uno per il bianco e uno per il nero. Quindi è possibile rappresentare le mosse e le posizioni della tavola come una funzione da (W x B) -> (W x B) dove W, B rappresentano l'insieme di possibili posizioni bianche e possibili nero rispettivamente.

Quindi la maggior parte delle informazioni sulla posizione delle schede può essere eseguita con l'aritmetica dei numeri interi, che è il più veloce possibile.

Answer 2

Vorrei usare anche una bitmap per questo. Le funzioni per controllare 1, 2 e 3 saranno un po 'non intuitive da scrivere, ma dovrebbero essere molto veloci.

Ovviamente, è necessario fare attenzione ai casi limite e una soluzione rapida probabilmente coinvolgerà alcuni numeri interi e aritmetici modulari sugli indici.

Answer 3

Un modo comune per farlo è con una rappresentazione binaria del tipo long per ogni giocatore.
(dato che ci sono 64 caselle sul tabellone) .. Come Charlie già detto ..
Ecco un molto buono (ma reather generale) wiki article.

L'utilizzo è semplice, ad esempio, se si desidera controllare se tutti i pezzi possono spostarsi verso l'alto e verso destra, spostare la rappresentazione dei pezzi del giocatore di 7 bit a sinistra e controllare se ci sono pezzi dell'avversario lì, quindi spostarli 7 bit ancora di nuovo, e controllare se quei quadrati sono chiari ...
L'ho usato in una competizione Reversi una volta, e posso dire che l'implementazione non è stata troppo difficile.
HTH.

Answer 4

In termini di elenchi, consiglio vivamente di non utilizzare una struttura che utilizza elenchi collegati in questa situazione. Probabilmente conoscerai già le posizioni che vuoi investigare (coordinate x-y), e quindi una lista collegata richiederebbe il tempo O(n) per prendere semplicemente il valore dello spazio della scacchiera. Come hanno già detto altre risposte, un approccio bitmap o lungo sarebbe l'ideale.

In termini di organizzazione dei dati, immagino che un'implementazione in cui sia il bianco e il nero siano memorizzati nella stessa struttura sarebbe l'ideale. Avrai un po 'di overhead dal momento che la memorizzazione di 2 e 3 in binario richiede la stessa quantità di memoria, anche se stai scrivendo pedine, probabilmente avrai comunque bisogno di memorizzare i dati "reali". Avere la possibilità di verificare se uno spazio è aperto eseguendo una singola ricerca dovrebbe fornire un significativo vantaggio in termini di prestazioni.

Spero che questo aiuti.

Answer 5

Prima di tutto, vale la pena notare che nella dama, la metà delle piazze sulle schede non possono mai essere utilizzati, quindi è davvero solo bisogno di una serie di 32 articoli, non 64. Prendendo re in considerazione, si ottiene possibilità da 0 a 4 invece di 0 a 2 (anche se quando l'ho fatto, ho trovato più semplice usare da -3 a +3, quindi i valori per il rosso e il nero hanno la stessa magnitudine e segni opposti).

Answer 6

dipende da ciò che gli algoritmi di intelligenza artificiale stanno per fare. La maggior parte degli algoritmi di intelligenza artificiale effettuerebbero una sorta di ricerca sulle possibili mosse almeno diversi passi avanti. In questo caso realizzerai molte copie della tua rappresentazione della scheda e ha senso cercare di mantenerla in piccolo mentre il tempo di copiare la struttura dei tuoi dati domina il tempo per ottenere un elenco di possibili mosse oltre a limitare la profondità a che puoi cercare.

Tuttavia, se non si sta cercando vorrei creare un pezzo di classe e memorizzare il colore, la posizione e se il pezzo è un re. Avrei quindi una matrice bidimensionale 8 per 8 di riferimenti a Pezzi e una lista concatenata di pezzi neri e una lista concatenata di pezzi rossi. Ogni elemento dell'array punta ad un pezzo dalla lista rossa o nera o ad un pezzo "Vuoto" (null funzionerebbe per questo). Quando sposti un pezzo, devi semplicemente aggiornare l'oggetto Piece nell'elenco e spostare il riferimento dalla posizione corrente alla nuova posizione, impostando la vecchia posizione sul pezzo vuoto. Per un leggero aumento del costo di un aggiornamento si ottiene un modo efficace per iterare su entrambi i lati pezzi e una costante ricerca del tempo dello stato di qualsiasi punto particolare sulla scheda.

Si dovrebbe ripetere l'elenco completo per rimuovere un pezzo morto, tuttavia questo può anche essere reso efficiente con una leggera modifica al pezzo. È possibile memorizzare un bool "morto" nell'oggetto Piece. Quando un pezzo viene ucciso, imposta dead su true e rimuovilo dal board sostituendo il riferimento ad esso con il pezzo vuoto. Quando si scorre su una lista di pezzi semplicemente rimuovere qualsiasi pezzo contrassegnato come morto dalla lista.