4. Array mit möglichst wenig Speicherbelegung(Bitfelder!?)

Array mit möglichst wenig Speicherbelegung(Bitfelder!?)

  • ?

    Hallo!

    Ich bin dabei eine KI für ein 4 Gewinnt Spiel zu erstellen.
    Dabei hat das Spielfeld insgesamt 8 Spalten, und 6 Zeilen.
    Es ergibt sich also ein Array von der Größe 8x6=48.
    Die möglichen Werte für einen Arrayinhalt sind: 0,1,2.
    Wenn ich als Datentyp char verwende, habe ich ganze 256 Möglichkeiten, ich brauch aber nur 3 ==> extreme Speicherverschwenung.

    Für die KI verwende ich einen Baum, der sich pro Knoten 8mal verzweigt(enspr. der 8 Spalten).
    Bei einer Tiefe von nur 4 Ebenen(inkl. Wurzel) erhalte ich 585 Knoten bzw. Blätter welche ich mit dem Array auffüllen muss, das ergibt knapp 27kb!!!

    So, jetzt mögt ihr Euch vllt. denken, 27kb, na und!? Ich programmiere das ganze für den TI200( http://www.ti-taschenrechner.com/images/TI_Voyage.gif ), und da ist bei 64kb endgültig Schluß, aber bereits 27kb sind ein Riesenbrocken.

    Gibt es nun eine Möglichkeit dieses Array zu verkleinern? Kann man die beiden Dinge Bitfeld und Array vllt. irgendwie vereinen? Oder sonst irgendwelche Ideen?

    Grüße,
    Harri

    0
  • G

    Nunja, du müsstest dir Zugriffsfunktionen für das Array schreiben, die den Index und Wert entsprechend umrechnen, damit zB 2 Bit pro Element genutzt werden können. Du kannst zwar auch Bitfelder nehmen, in Verbindung mit Arrays wird das aber ziemliches Gewurschtel, imo. Du solltest ausserdem bedenken, dass auch Performancenachteile entstehen können, weil viele Prozessoren nunmal am besten auf Bytebasis arbeiten und nicht auf Bitbasis.

    0
  • ?

    Nagut dann belass ich es mal bei einem char.
    Eine größere Tiefe als 4 bekomm ich sowieso nicht zusammen für den KI Baum am TI200.

    Grüße,
    Harri

    0
  • G

    Ich würde dir trotzdem empfehlen, den Zugriff auf das Array entsprechend zu abstrahieren. Dann kannst du bei Bedarf relativ einfach die 2 Bit pro Element Variante implementieren und schauen was wichtiger ist, der Speicherbedarf oder die Performance.

    0
  • N

    ich irgendwo noch'n code für bit arrays rumliegen, ach, da ist er schon:

    char memory[100]; // 800 bits

// bit setzen
void setbit (char *mem, int pos)
{
    int bytepos = pos>>3;
    int bitpos = pos - (bytepos<<3);
    mem[bytepos] |= (1<<bitpos);
}

// bit löschen
void clearbit (char *mem, int pos)
{
    int bytepos = pos>>3;
    int bitpos = pos - (bytepos<<3);
    mem[bytepos] &= ~(1<<bitpos);
}

// bit lesen
int getbit (char *mem, int pos)
{
    int bytepos = pos>>3;
    int bitpos = pos - (bytepos<<3);
    return !!(mem[bytepos] & (1<<bitpos));
}

    du brauchst zwar immer zwei bits, aber vielleicht kannste damit was mit anfangen...
    :xmas2:

    0
  • ?

    Danke für Eure Ratschläge.

    Ich hab das Grundgerüst der KI jetzt soweit fertig implementiert, nur an der Bewertungsfunktion muss ich noch herumwerken.

    Bin draufgekommen dass es im Spiel nur Sinn macht, immer in 2er Schritten nach vorne zu blicken, also entweder schau ich 2 Züge in die Zukunft, oder 4, oder 6,...
    3 Züge in die Zukunft(entspricht der ursprünglichen Baumtiefe 4) bringt also nix, und 4 Züge(Baumtiefe 5) in die Zukunft geht nicht(der Ti200 ist mit seinen 12MHz ja schließlich kein Großrechner 😉 ), also bleibt mir eh nix anderes über als "nur" 2 Züge in die Zukunft zu blicken. Interessanterweise schafft die KI aber bereits mit dieser kleinen Tiefe die meisten Bedrohungssituationen zu erkennen, sogar ohne dass die Bewertungsfunktion implementiert ist!!! Tja, und die restlichen Bedrohungen werden dann über die Bewertungsfunktion abgewehrt 😃

    Lange Rede kurzer Sinn: Bei 2 Zügen, also einer Baumtiefe von 3, gibt es insgesamt 1+8+64=73 Knoten. Das ist absolut kein Performance- und auch kein Speicherproblem, insofern kann ich auf eine Verkleinerung des Arrays verzichten.

    Interessehalber werde ich die gepostete Funktion trotzdem ausprobieren.

    Grüße,
    Harri

    0
Anmelden zum Antworten