Nächste mögliche Züge für ein Spiel

1. offizieller Beitrag
    • Offizieller Beitrag

    Heyho,

    Dieses Jahr mache ich bei der Software Challenge 2011 in Kiel mit. Das ist eine seit ein paar jahren existierene Veranstaltung die jedes Jahr ein neues Spiel benutzt, welches Schüler wie ich und du Spielen sollen. Bzw, nicht wir sollen es spielen, sondern wir sollen Programme schreiben, die es für uns Spielen (Bots, aber diesmal keine Bösen ;D) Da der Server offen ist, habe ich veruscht es mit AutoIt zu bewerkstelligen, was mir auch gut gelang, bis ich zu einem Problem stoß.

    Aber erstmal: Es geht um das Spiel "Schäfchen ins Trockene bringen" - andere kennen es evtl. unter "Fang den Hut", ist aber mehr oder weniger das gleiche.
    Der Server existiert schon, und würfelt jede Runde 3 Würfel, die per Random gewürfelt werden. Nun will ich die möglichen Züge rausfinden, die meine Schäfchen machen können. Was ich habe:

    • Position aller meiner Schäfchen
    • Alle Felder (0-64) und die Felder die direkt drum herum liegen (z.B. bei 0, dem Feld in der Mitte, 10, 15, 5 und 20 (siehe ScreenShot))


    Auf dem Screenshot wurde eine Fünf, eine Sechs und eine Vier gewürfelt. Die rot umrandeten Felder sind die Möglichen Züge vpn dem Schaaf 4, aber leider nur in der GUI drin. Diese rot umrandeten Felder will ich eben mit AutoIt rausfinden, und ich habe dafür die oben genannten Informationen.

    Hat jemand eine Idee? Es gibt eine Java und eine Delphi Umsetzung, leider tue ich mir etwas schwer damit, den Algorhytmus herauszufinden, wie die möglichen Züge ausgelesen werden.
    Falls jemand damit was anfangen kann, weitere Information, so wie di Sourcecodes gibt es hier:
    http://www.informatik.uni-kiel.de/software-challenge/2011/download/

    Ich hoffe mir kann jemand helfen, wäre echt super danke, geht um eine Abschlussarbeit in der Schule ;)

    Gruß
    Max
    [/list]

    • Offizieller Beitrag

    Erste Idee: Bau das Feld als ungerichteten Graphen auf (dann lernst du auch was :D) und leg dir in einem Array eine Adjazenzmatrix/-liste an. Da kannst du dann mit einem Backtracking-Algorithmus (beachten, ob bereits belaufene Wege noch mal genommen werden dürfen…) 4, 5, 6 Schritt gehen und dir die Felder merken, die rauskommen.

    Könnte aber auch möglich sein, die Felder durchzunummerieren und eine Formel zu finden (mit Modulo-Rechnung und ähnlichen Tricks), die die Lösung direkt rauswirft. Auf den ersten Blick fällt mir da keine ein, aber mag es geben.

    Viel Spaß!
    Johannes

    Also wenn du eine funktion hast die dir stets alle umliegen felder eines feldes zurückgibt kannst du daraus einen algorithmus bauen ich habe sowas erst gemacht in einem kleinen spiel habe dort auch rekursiv alle anliegen felder mit gleicher farbe ermittelt du müsstest eben nurnoch eine art counter einbauen wann die gewürfelte zahl erreicht ist.

    Hier mal die Funktion die ich geschrieben hatte:

    Spoiler anzeigen
    [autoit]

    Func _getButtonsRek($btn_NrInArr)
    Local $btnsFinalArr[1], $btnsToCheckArr[2], $neighbourBtns[4]
    $btnsToCheckArr[1] = $btn_NrInArr
    $btnsFinalArr[0] = $btn_NrInArr
    While UBound($btnsToCheckArr) > 1
    $neighbourBtns = _getNeighbourBtns($btnsToCheckArr[1])
    _ArrayDelete($btnsToCheckArr, 1)
    For $i = 0 To UBound($neighbourBtns) - 1 Step 1
    If _ArraySearch($btnsFinalArr, $neighbourBtns[$i]) == -1 And $neighbourBtns[$i] <> -1 Then
    _ArrayInsert($btnsToCheckArr, 1, $neighbourBtns[$i])
    EndIf
    Next
    For $i = 0 To UBound($btnsToCheckArr) - 1 Step 1
    If UBound($btnsToCheckArr) <= 1 Then
    ExitLoop
    EndIf
    If $btnArr[$btn_NrInArr][1] == $btnArr[$btnsToCheckArr[1]][1] Then
    _ArrayAdd($btnsFinalArr, $btnsToCheckArr[1])
    ExitLoop
    Else
    _ArrayDelete($btnsToCheckArr, 1)
    EndIf
    Next
    WEnd
    For $i = 0 To UBound($btnsFinalArr) - 1 Step 1
    If $btnsFinalArr[$i] == "" Then
    _ArrayDelete($btnsFinalArr, $i)
    EndIf
    Next
    Return $btnsFinalArr
    EndFunc ;==>_getButtonsRek

    [/autoit]


    in meinem $btnArr habe ich 104 Buttons drin an $btnArr[x][0] immer das control und an $btnArr[x][1] die Farbe

    Wenn du willst kannst ja mal pm dann schick ich dir das ganze Skript

    • Offizieller Beitrag

    Hallo,

    Habs jetzt mal Rekursiv versucht, aber ich bekomme es einfach nicht hin. Den ersten Zug zeigt er mir richtig an (alle 3 Möglichkeiten). Aber beim zweiten Zug hardert es dann schon, dort ist meistens keins richtig, ab und zu aber eins.
    Hier mal den Source Code, falls jemand den kompletten Source + Java Server zum Testen haben will, einfach mal bescheid sagen, würde mich sehr freuen :)
    Ich komm nämlich einfach nicht weiter :S

    Spoiler anzeigen
    [autoit]

    Func _test2($iSheep)
    Global $SC_ARR_GETPOSSIBLE[1];Setze die Globale Varialbe GetPossible (== Mögliche Züge) zurück
    Local $i
    Local $iPlace = $SC_ARR_SHEEP[$iSheep][5];Der momentane Platz des Schaafes, z.B. 61
    Local $aAlready[1] = [$iPlace];Die, die schon geprüft wurden

    [/autoit] [autoit][/autoit] [autoit]

    $aAlready = _test($iPlace, $aAlready, 1, $SC_ARR_DIE[0]);SC_ARR_DIE[0] gibt den ersten würfel zurück, z.B. 5

    [/autoit] [autoit][/autoit] [autoit]

    ;Hier wird dann nochmal alles was in aAlready drin ist aus der Gobalen Varaible zurück gelöscht
    For $i = 0 To UBound($aAlready) - 1
    $iAS = _ArraySearch($SC_ARR_GETPOSSIBLE,$aAlready[$i])
    If $iAS > -1 Then _ArrayDelete($SC_ARR_GETPOSSIBLE,$iAS)
    Next
    ;Gibt die globale variable zurück
    Return $SC_ARR_GETPOSSIBLE
    EndFunc ;==>_test2

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func _test($iPlace, $aAlready, $zaehler = 0, $iTo = 6)
    Local $i2
    $aNeighbour = _SC_GetNeighbourPlaces($iPlace);gibt die nachbarsplätze eines platzes aus in einem array (array[0] = anz)
    For $i2 = 1 To $aNeighbour[0];schleife
    If $zaehler = $iTo Then;wenn zaehler = wuerfel dann schreibe in das globae array (SC_ARR_GETPOSSIBLE)
    If _ArraySearch($aAlready, $aNeighbour[$i2]) = -1 And $aNeighbour[$I2] <> '' Then
    Local $iUb = UBound($SC_ARR_GETPOSSIBLE)
    ReDim $SC_ARR_GETPOSSIBLE[$iUb + 1]
    $SC_ARR_GETPOSSIBLE[$iUb] = $aNeighbour[$i2]
    EndIf
    Else;wenn zaehler < wuerfel dann schreibe das momentane feld in ein array und finde davon wieder die nachbars felder (rekursion)
    If _ArraySearch($aAlready, $aNeighbour[$i2]) = -1 Then
    Local $iUb = UBound($aAlready)
    ReDim $aAlready[$iUb + 1]
    $aAlready[$iUb] = $aNeighbour[$i2]
    _test($aNeighbour[$i2], $aAlready, $zaehler + 1, $iTo);zaehler +=1
    EndIf
    EndIf
    Next
    Return $aAlready;gibt aalready zurück für _test2
    EndFunc ;==>_test

    [/autoit]

    Habs versucht so gut wie möglich zu Dokumentieren, falls noch fragen sind, beantworte ich sie natürlich schnell.

    Gruß
    Spider

    Könntest du einmal die "_SC_GetNeighbourPlaces" Funktion posten?
    Gerade da der 1. Zug richtig ist denke ich es könnte hieran liegen
    Wenn diese nicht 100% funktioniert gibts nur Probleme das hatte ich lange...

    Dein Algorithmus zur ermittlung der Felder sieht soweit ich das sehen kann nämlich richtig aus

    2 Mal editiert, zuletzt von Milla (13. Dezember 2010 um 21:40)

    • Offizieller Beitrag

    Hallo,

    Die Globale Variable $SC_ARR_PLACES sieht wie folgt aus:
    $SC_ARR_PLACES[65][5]
    Die erste Dimension ( das [65]) sind die Feldnummern. Die zweite ( [5] ) zeigt die Nachbarn an. [0] = GRASS/SAVE (Grass bedeutet normales Feld, Save bedeutet sicheres Feld) [1] = 1. Nachbar, [2] = 2. Nachbar, [3] = 3. Nachbar und [4] = 4. Nachbar. Wenn ein Feld z.B. nur 2 Nachbarn hat (wie unten im Beispiel Feld 8 ) werden nur [1] und [2] gefüllt und [3] und [4] sind leer.

    Ankommen kommt es über TCP/IP so (Hier im Beispiel Für Feld 0 und für Feld 8 :(

    Spoiler anzeigen
    Code
    <node index="0" type="GRASS">
        <neighbour>5</neighbour>
        <neighbour>20</neighbour>
        <neighbour>10</neighbour>
        <neighbour>15</neighbour>
      </node>
     <node index="8" type="GRASS">
        <neighbour>7</neighbour>
        <neighbour>9</neighbour>
      </node>

    Auslesen tu ich das dann so (Funktionstüchtiges Beispiel):

    Spoiler anzeigen
    [autoit]

    #include <Array.au3>
    Global $SC_ARR_PLACES[65][5]
    Global Const $SC_RECV_REGEX_PLACE = '(?s)<node index="(\d*?)" type="(.*?)">(.*?)</node>'
    Global Const $SC_RECV_REGEX_PLACE_NEIGHBOUR = '(?s)<neighbour>(\d*?)</neighbour>'
    ;[..]
    ;Beispiel für $sRecv
    $sRecv = '<node index="0" type="GRASS">' & @CRLF & _
    ' <neighbour>5</neighbour>' & @CRLF & _
    ' <neighbour>20</neighbour>' & @CRLF & _
    ' <neighbour>10</neighbour>' & @CRLF & _
    ' <neighbour>15</neighbour>' & @CRLF & _
    ' </node>' & @CRLF & _
    ' <node index="8" type="GRASS">' & @CRLF & _
    ' <neighbour>7</neighbour>' & @CRLF & _
    ' <neighbour>9</neighbour>' & @CRLF & _
    ' </node>'
    $aRegEx = StringRegExp($sRecv, $SC_RECV_REGEX_PLACE, 3)
    If Not @error Then
    ConsoleWrite("Places Ubound: " & (UBound($aRegEx)) / 3 & @CRLF)
    For $i = 0 To UBound($aRegEx) - 1 Step 3
    Local $aRegEx2 = StringRegExp($aRegEx[$i + 2], $SC_RECV_REGEX_PLACE_NEIGHBOUR, 3)
    $SC_ARR_PLACES[$aRegEx[$i]][0] = $aRegEx[$i + 1]
    For $i2 = 0 To UBound($aRegEx2) - 1
    $SC_ARR_PLACES[$aRegEx[$i]][$i2 + 1] = $aRegEx2[$i2]
    Next
    Next
    EndIf
    _ArrayDisplay($SC_ARR_PLACES)

    [/autoit]

    Die Funktion "_SC_GetNeighbourPlaces" sieht dementsprechend so aus:

    Spoiler anzeigen
    [autoit]

    Func _SC_GetNeighbourPlaces($iPlace)
    Local $aReturn[1] = [0], $i
    For $i = 1 To 4
    If $SC_ARR_PLACES[$iPlace][$i] <> '' Then
    ReDim $aReturn[$i + 1]
    $aReturn[0] += 1
    $aReturn[$i] = $SC_ARR_PLACES[$iPlace][$i]
    EndIf
    Next
    Return $aReturn
    EndFunc ;==>_SC_GetNeighbourPlaces

    [/autoit]


    Das ist jetzt ziemlich viel Input, aber vielen Dank schonmal für deine Zeit die du hier reinpackst :)

    Gruß
    Spider

    Hey,
    bau dir ein zweidimensionales Array, dass das Spielfeld repräsentiert (das is hier ein bisschen komplizierter, weil du die Felder rund angeordnet hast). Schreibe in jedes Feld eine 1 und dort wo kein Feld ist eine 0. Jetzt kannst du relativ gut entscheiden welches Feld welchen Nachbarn hat.

    Jetzt ganz normale Rekursion.
    Da du die ganze Sache rund gebaut hast, hast du für jedes Feld 8 Nachbarn.

    Code
    .   .   .
.   .   .
.   .   .

    Du brauchst eine Funktion

    Func checkenachbar($counter, $richtung)

    In der Funktion rufst du die Funktion wieder 8 mal auf und prüfst vorher welche Felder im Array überhaupt Spielfelder sind. Gleichzeitig musst du mit dem Parameter $richtung noch schauen, dass du nicht in die Richtung zurückgehts aus der du gekommen bist. Den $counter musst du mit jedem Aufruf um 1 erniedrigen. Der bildet dann gleichzeitig deine Terminierungsbedingung, wenn der $counter 0 geworden ist, weist du dass du jetzt an deinem Ziel angelangt bist und kannst die Koordinate speichern.

    Das wars eigentlich schon.
    Wenn du keine eigene Idee hast, dann mach mal das Spielfeld als Array, ich schreib dir die Funktion.

    Was berechnet denn die angrenzenden Felder?
    Sind diese wirklich immer 100% korrekt?
    Bzw sind beim Aufruf der Funktion "_SC_GetNeighbourPlaces" in $SC_ARR_PLACES auch immer die richtigen Angrenzenden?
    Wann/Wo wird das Auslesen der angrenzenden aufgerufen?

    Weil so wies für mich jetzt aussieht werden einmal am anfang die angrenzenden des 1. Feldes in $SC_ARR_PLACES geschrieben und dann nie wieder das würde auch erklären wieso nur das 1. Feld funktioniert

    5 Mal editiert, zuletzt von Milla (14. Dezember 2010 um 08:44)