Backtrackingproblem

Tantor

Hallo zusammen,

ich überlege schon seit gestern an einem Backtrackingproblem, wo ich noch nicht einmal auf einen Lösungsansatz komme. Echt schlimm.

Ihr kennt doch sicherlich das "NIMM-Spiel"

NIMM-Spiel bedeutet:
ich habe einen rechteckigen Spielplan mit Münzen gefüllt, jeder Spieler darf beliebig viele Münzen aus einer Reihe ziehen, mindestens jedoch eine. Gewonnen hat wenn man die letzte(n) Münze(n) einer Reihe in einem Zug entfernen kann.

also ich habe einen Spielplan gefüllt mit Münzen und nun soll ich einen Algorithmus schreiben, der alle möglichen Zugmöglichkeiten durchtestet und mir dann sagt ob ich in einer Verluststellung bin oder nicht. Verlustsellung ist wenn keine Spiesteine mehr auf dem Brett sind. Ich darf immer nur Steine aus einer Reihe ziehen.
Ich habe aber keinen schimmer für nen Ansatz zum Backtracking, hört sich zumindest nach backtracking an.

Könnt ihr mir weiterhelfen ??

Vielen Dank

1ntrud0r

hmm du hast ja bestimmt das brett in einem vector abgespeichert ..
wenn jedes "Fach" des Vektors 0 beinhaltet hast du verloren .. !

1=stein , 0=kein stein ...

+ überprüfungs algorithmus = ergebnis ..

Affi

schreib dir doch eine bool funktion die in einer for schleife alle felder der reihe abläuft und wenn alle felder lehr sind oder weniger felder voll sind als weg kommen sollen soll sie dir einen true oder false liefern
Hoffe konnte dich auf eine Idee bringen
n Beispiel code bekommsu wenn du dein bisherigen code ma postest (oder wenigstens n stück)

cya Marco

hardy

tantor, backtracking macht keinen sinn, wenn du alle spielmöglichkeiten durchgehen sollst!
die ermittlung des gewinners ist recht einfach und am besten rekursiv zu lösen.
du könntest nun einfach eine fnuktion schreiben, die als parameter das spielfeld und den spieler, der gerade dran ist, hat. als rückgabewert kommt der gewinner des aktuellen planes in frage.
nun machst du folgendes :

1.gehe davon aus dass der andere spieler gewinnt
2.wenn auf dem brett noch münzen sind tue folgendes :
   für jede reihe
      für alle münzen in dieser reihe
         subtrahiere den wert von den münzen in der akt. reihe
         rufe die funktion wieder auf jedoch ist dann der andere spieler am zug
         prüfe ob der aktuelle spieler als sieger zurückkommt, wenn ja merken!
         addiere die weggenommenen münzen wieder drauf
3.gebe den ermittelten gewinner zurück

mache dir das an einfachen beispielen klar.

ps:wenn ich nicht ganz irre dann hast du noch 27h

[ Dieser Beitrag wurde am 13.03.2003 um 16:11 Uhr von hardy editiert. ]

Affi

Vergiss nicht mit poointern zu Arbeiten wenn du in der FUnktion variablen ändern lassen willst

hardy

ähm, affi.
in der funktion werden keine variablen geändert bzw. der alte stand wird immer wiederhergestellt und ausserdem wie würdest du das spielfeld (was wohl in 99,9% aller fälle ein array ist) sonst übergeben

Affi

gute frage nächste frage

hardy

wie du meinst

also nun die ha*****arf gefolgerte frage :
tantor, du machst deine ausbildung nicht zufällig in einer kölner firma ?

Krösus

Habe sowas ähnliches schon mal für VierGewinnt geschrieben, hier die beiden wichtigsten Funktionen meines C-Codes:

int CalcMove(void)
{
    //Setzt testweise auf alle 7 Linien einen Stein
    //und prueft durch Aufruf von Try() auf Gewinnstellung
    //...
}

//Die rekursive Try()-Funktion testet, ob ein Spieler gewonnen hat
//Wenn nicht, geht es eine Rekursionsstufe tiefer!
GameResult Try(Piece ePiece, GameResult eResult, Piece eOtherPiece, GameResult eOtherResult)
{
    char iLineFree;
    int iLine;
    GameResult eValue, eMinMaxValue;
    if(ImmediateWin(ePiece, eResult) >= 0)
        return eResult;
    eMinMaxValue = eOtherResult;
    eValue = CONTINUE_GAME;
    iLineFree = 0;
    for(iLine = 0; iLine < 7; iLine++)
    {
        if(s_bAbortCalc)
            return GAME_ABORTED;
        if(LineFree(iLine))
        {
            iLineFree++;
            Set(ePiece, iLine, 1);
            s_iRecursionDepth++;
            if(s_iRecursionDepth <= s_iRecursionLimit)
                //Here is the recursion!
                eValue = Try(eOtherPiece, eOtherResult, ePiece, eResult);
            s_iRecursionDepth--;
            Remove(iLine);
            if(eValue == eResult)
                return eResult;
            if(ePiece == PIECE_PLAYER)
            {
                if(eValue < eMinMaxValue)
                    eMinMaxValue = eValue;
            }
            else
            {
                if(eValue > eMinMaxValue)
                    eMinMaxValue = eValue;
            }
        }
    }
    return iLineFree ? eMinMaxValue : DRAW;
}

Muß nun bloß noch entsprechend auf das NIMM-Spiel angepaßt werden.
MfG, Krösus

hoffe es hat dir wenigstens geholfen MARCEL!!!

hardy

oje, das böse hat sich gemeldet