optimaler datencontainer

hallo

ich programmiere gerade eine simulation eines brettspieles, wo ich auch eine ai implementiere. nun soll diese ai für alle freien flächen auf dem spielbrett alle möglichkeiten (pro figur, ergo werden pro spielzug mehrere zyklen gemacht) notieren und dann nach einem ausschlussverfahren den nächsten zug auswählen. ich bin mir nicht ganz sicher was ich für einen container für die berechnung der möglichkeiten nehmen soll.

ich schwanke zwischen:
map<coords, vector<possible_tiles> >
map<coords, set<possible_tiles> >
vector<vector<possible_tiles> >
vector<set<possible_tiles> >

die seitenlängen des bretts sind bekannt, ebenso wie die anzahl an möglichen belegungen pro feld. welcher der vorschläge ist der laufzeit-performanteste? wenn keiner, was gibt es für alternativen?

der speicher ist mir ansich egal (solange es sich in nem gewissen bereich hält), die geschwindigkeit ist aber kritisch, da bei mehreren figuren pro zug mit mehreren distanzen und richtungen schon einige berechnungen durchgeführ werden müssen.

gruss

SeppJ

Die Antwort hängt auch stark davon ab, was das genau für ein Spiel ist (insbesondere Anzahl der Felder) und was du später genau mit der information tun möchtest. Ich hätte nach deiner Beschreibung (zu den Feldern alle möglichen Züge notieren) spontan folgendes vorgeschlagen:

array<anzahl_der_felder, array<anzahl_der_felder, datentyp_für_mögliche_züge_zB_int>>

Du mappst alle Felder auf einen Index im Array. Jedem Feld hast du somit ein komplettes Spielfeld (das innere Array) zugewiesen, auf dem du dann die möglichen Züge markieren kannst.

flabahz schrieb:

der speicher ist mir ansich egal (solange es sich in nem gewissen bereich hält), die geschwindigkeit ist aber kritisch

Das ist ein Irrtum. Den Speicher lesen ist fast immer Flaschenhals, ausserdem new ist sehr langsam.

Bei dir kommt es auf die Art von Brettspiel an:

const int breite=X, höhe=X;
enum Figur { ... };
std::array<Figur, breite*höhe> // wenn Feld sehr voll
std::array<Figur, std::pair<int,int> > // wenn wenig Felder besetzt

Für den Speicher würde ich mir einen einfachen Memory Pool schreiben (oder std::vector/std::deque verwenden, die sind oft ausreichend). Wichtig ist, dass der Speicher schnell verfügbar ist und die Daten kompakt gehalten werden (im Cache liegen).

knivil

der speicher ist mir ansich egal

Schaetze doch mal wie tief/breit der Baum wird, also wieviel Moeglichkeiten es gibt. Sind sie mehr als 50'000'000 warden Speicherprobleme auf dich zukommen.

pro figure

Wuerde ich nicht machen. Der allgemeinste Ansatz ist, von einem Zustand des Feldes zum naechsten zu gehen, der Uebergang ist durch den Zug beschrieben. D.h. deine Knoten im Graph sind Spielzustaende (Spielbrettkonstellation, Geld, Zustand der Mitspieler) und die Kanten sind deine (moeglichen) Zuege. Hat damals bei meinem General Game Playing Project gut funktioniert.

@kescher: Nein, die Anzahl der Moeglichkeiten ist der Knackpunkt, Daten im Cache ... lol ... ein Spielbaum sprengt den allemal.

knivil schrieb:

@kescher: Nein, die Anzahl der Moeglichkeiten ist der Knackpunkt, Daten im Cache ... lol ... ein Spielbaum sprengt den allemal.

Kommt auf seinen Algorithmus drauf an. Wenn der so angepasst ist, dass es in den Speicher passt gilt immer noch:
Doppelt so viel Daten im Cache = doppelt so viel Geschwindigkeit

danke für die schnellen antworten

nunja anhand der vorgeschlagenen lösungen erkenne ich, dass ich die genaue art des spiels hätte erwähnen sollen. es geht um sudoku ( und sudoku-variatonen, die ich teilweise mit dem selben schema lösen kann). jedoch hab ich versucht, das ganze relativ allgemein zu halten, so habe ich auch templates für die parametrisierung des spielfeldes verwendet.
meine aktuelle vorgehensweise ist hier recht einfach nachzuvollziehen:
http://commons.wikimedia.org/wiki/File:Sudoku_problem_1_%26_candidate.svg

ich glaube, das erübrigt automatisch auch das mit den bäumen, wird hier nicht gefragt sein. (da der nächste spielzug unabhängig vom übernächsten ist)

nun, jetzt wo ihr wisst, worum es geht, schildere ich meinen vorschlag nochmals:
ein container, der für alle noch leeren felder, alle möglichkeiten notiert (das wären auf einer situation wie auf dem bild die zahlen 1 - 9). nun werden alle vollen felder durchiteriert und die möglichkeiten für die leeren felder werden dabei gestrichen.

knivil

http://norvig.com/sudoku.html

ein container, der für alle noch leeren felder, alle möglichkeiten notiert

Einfaches int[9][9]. Und alle noch offenen Moeglichkeiten sind durch das entsprechende gesetzte Bit im int erkennbar.