archiv.galad.com

Solitaire Brute Force Problemanalyse Umsetzung Erläuterungen Ergebnisse Download

Umsetzung

Das Spielfeld wird aufgrund seiner binären Stelleninformation in zwei 32 Bit unsigned Integern (ULONG) gespeichert. Die Variable ulField enthält die Bits 0 bis 31, die Variable ulBit32 das restliche 32ste Bit. Die Zuordnung zwischen Feldpositionen und Bits sieht folgendermaßen aus:

Diese Zuordnung erlaubt eine einfache Drehung und Spiegelung des Felds mit binären Basisoperationen. Das mittlere Bit 32 ist davon nicht betroffen.

tULONG ulFieldSymTurn (tULONG ulField)
{
    return ( ((ulField & 0x001ff1ff) << 3) | ((ulField & 0x00e00e00) >> 9) |
             ((ulField & 0x3f000000) << 2) | ((ulField & 0xc0000000) >> 6)
           );
}

tULONG ulFieldSymMirror (tULONG ulField)
{
    return ( ((ulField & 0x11041041) << 2) | ((ulField & 0x44104104) >> 2) |
             ((ulField & 0x00008008) << 8) | ((ulField & 0x00800800) >> 8) |
             ((ulField & 0x00010010) << 6) | ((ulField & 0x00400400) >> 6) |
             ((ulField & 0x08020020) << 4) | ((ulField & 0x80200200) >> 4) |
              (ulField & 0x22082082)
           );
}

Zur Berechnung des symmetrischen Normals (Symmetric Integer Normal - SIN) wird aus allen 8 Permutationen der größte ulField-Wert gewählt. Bit 32 ist auch hierfür nicht von Bedeutung.

tULONG ulFieldSymNormal (tULONG ulField)
{
    tULONG ulMax = ulField;

    if ( (ulField = ulFieldSymTurn  (ulField)) > ulMax ) ulMax = ulField;
    if ( (ulField = ulFieldSymTurn  (ulField)) > ulMax ) ulMax = ulField;
    if ( (ulField = ulFieldSymTurn  (ulField)) > ulMax ) ulMax = ulField;
    if ( (ulField = ulFieldSymMirror(ulField)) > ulMax ) ulMax = ulField;
    if ( (ulField = ulFieldSymTurn  (ulField)) > ulMax ) ulMax = ulField;
    if ( (ulField = ulFieldSymTurn  (ulField)) > ulMax ) ulMax = ulField;
    if ( (ulField = ulFieldSymTurn  (ulField)) > ulMax ) ulMax = ulField;

    return (ulMax);
}

Auf ähnliche Weise kann durch direkte Zählung der Symmetrietyp ermittelt werden.

tCOUNT cnFieldSymType (tULONG ulField)
{
    tULONG ulF = ulField;
    tCOUNT cnC = 1;

    if ( (ulField = ulFieldSymTurn  (ulField)) == ulF ) cnC++;
    if ( (ulField = ulFieldSymTurn  (ulField)) == ulF ) cnC++;
    if ( (ulField = ulFieldSymTurn  (ulField)) == ulF ) cnC++;
    if ( (ulField = ulFieldSymMirror(ulField)) == ulF ) cnC++;
    if ( (ulField = ulFieldSymTurn  (ulField)) == ulF ) cnC++;
    if ( (ulField = ulFieldSymTurn  (ulField)) == ulF ) cnC++;
    if ( (ulField = ulFieldSymTurn  (ulField)) == ulF ) cnC++;

    return ( 8 / cnC );
}

Die Zuordnung erlaubt außerdem die einfache Initialisierung und die einfache Überprüfung auf den gewünschten Endzustand.

tVOID vFieldGetStart (tpULONG pulField, tpULONG pulBit32)
{
    *pulField = 0xffffffff;
    *pulBit32 = 0;
}

tBOOL bFieldIsWinning (tULONG ulField, tULONG ulBit32)
{
    return ( (ulField == 0) && (ulBit32 == 1) );
}

Die Hashkeys werden aus ulField berechnet. Bit 32 wird der Einfachheit halber direkt in den Hashkey übernommen und kann auch aus diesem wieder zurückgewonnen werden. Dadurch muss in den Hashtabellen nur ulField eingetragen werden. Als Hashfunktion wurde eine einfache Addition gewählt, die in keinster Weise optimiert oder auf Gleichverteilung getestet wurde.

tCOUNT cnFieldGetHash (tULONG ulField, tULONG ulBit32)
{
    tCOUNT cnHash;

    cnHash = ((ulField      ) & 4095) +
             ((ulField >> 12) & 4095) +
             ((ulField >> 24) & 4095);

    while (cnHash > 2047)
        cnHash = (cnHash & 2047) + (cnHash >> 11);

    return ( cnHash | ((ulBit32 & 1) << 11) );
}

tULONG ulFieldGetBit32 (tCOUNT cnHash)
{
    return ((cnHash >> 11) & 1);
}

Zusammen mit dem jeweiligen Feld werden zwei Spielweg-Zähler abgespeichert. Der erste Zähler zählt die Spielwege im Gesamt-Baum, indem für jedes Feld jeder mögliche Zug durchgeführt und entsprechend gezählt wird. Der zweite Zähler zählt die Wege im Normal-Baum. Alle Züge, die dasselbe Zielfeld ergeben, werden zusammengefaßt als ein einzelner Zug gezählt.

Die Zähler wurden dynamisch implementiert und passen sich automatisch an die benötigte Bitanzahl an, die mit fortschreitender Suche zunimmt. Dadurch und durch die ebenenweise Berechnung ergab sich eine programmberechnete maximale Speicheranzeige von etwa 94MB. In dieser Zahl ist nur die reine Datenmenge berücksichtigt, nicht jedoch der Overhead der dynamischen Speicherverwaltung des Compilers sowie die freien Blöcke, die Löcher im Heap bilden.

Abhängig vom System sollten ab 128MB Speicher also keine Probleme auftreten. Auf einem Pentium II 400 mit 256MB unter Windows NT 4 wurde die Berechnung in weniger als vierzig Minuten durchgeführt. Für den verwendeten Compiler wurden keinerlei Optimierungen aktiviert.