Ein bisschen quatchen ist gut ;)

L-Wert
Beiträge: 10
Registriert: Do 1. Sep 2011, 13:16

Ein bisschen quatchen ist gut ;)

Beitragvon L-Wert » Mo 12. Sep 2011, 17:32

Hi,

Auch dieses mal bin ich interessiert in die Vorgehensweisen der Teams.
Im letzten Jahr haben wir ja schon so manch eine eigenartige Strategie gesehen.
Damit ich mich auch dieses mal bestens amüsieren kann, frage ich einfach mal rum.
Mit welcher Methodik wählt ihr den nächsten Zug aus? Oder. Mit welcher Methodik wolltet ihr es einst machen?

Gruß L-Wert

ZeroByte
Beiträge: 25
Registriert: Mi 14. Sep 2011, 21:08

Re: Ein bisschen quatchen ist gut ;)

Beitragvon ZeroByte » So 18. Sep 2011, 13:26

Moin,

ich will ja nur dezent darauf hinweisen, aber wenn jeder hier seine Strategie offenlegt, gehts nurnoch darum, wer das am efffizientesten umsetzt ;)
Momentan wähle ich den nächsten Zug per Zufall aus allen Permutationen aus. Was mir dabei irgendwie Sorgen macht, ist, dass mein Bot mit der Strategie immer gegen den mitgelieferten SimpleClient verliert :mrgreen: Scheint wohl daran zu liegen, dass ich den Zufallsgenerator nicht vernünftig einsetze (mt11213b, initialisiert mit std::time(0), Werte zwischen 0 und 100.000, dann per Modulo runtergebrochen).
Ich bin ansonsten noch etwas eim Debuggen. Momentan liege ich bei ca. einem Absturz auf 100 Spielen xD (was ich mir nicht erklären kann...)

Benutzeravatar
Christian Wulf
Beiträge: 27
Registriert: Mi 31. Aug 2011, 05:54

Re: Ein bisschen quatchen ist gut ;)

Beitragvon Christian Wulf » Mo 19. Sep 2011, 09:57

Wozu brauchst du Permutationen, wenn du nur den nächsten Zug berechnen willst? Und wenn du den Index der Permutationsliste/array zufällig bestimmen willst, halte dich am besten an die Java- und Delphi-Variante. Das heißt, setze den Index nicht fest (hier anscheinend auf 100.000), sondern nimm als obere Grenze natürlich die Listen/Arraylänge (ggf. minus 1).
Letztlich wird so dein Client aber erst einmal auch nur maximal so gut, wie der aktuelle SimpleClient. Wie willst du dann weiter vorgehen?

Schöne Grüße,
Christian

ZeroByte
Beiträge: 25
Registriert: Mi 14. Sep 2011, 21:08

Re: Ein bisschen quatchen ist gut ;)

Beitragvon ZeroByte » Mo 19. Sep 2011, 16:06

Die Permutationen (Slots * Städte * Segmente) abzüglich der durch Randbedingungen wegfallenden Möglichkeiten ergeben die Menge aller möglichen Züge aus einem gegebenen Spielstand. Ich kann mir nicht vorstellen, dass der Java-/Delphi-Client auf dem Array der erzeugten Zugmöglicheiten noch einen Shuffle durchführt, damit sie wirklich in zufälliger Reihenfolge vorliegen. Sollte dem jedoch nicht so sein, so ist der Zug an der Stelle array.size() -1 nicht zufällig.

Die 100.000 bezogen sich auf die Random-funktion:

Code: Alles auswählen

boost::random::mt11213b gen;
bool seeded = false;

int random(int start, int end){
    if(!seeded){
        gen.seed(static_cast<unsigned int>(std::time(0)));
        seeded = true;
    }
    boost::random::uniform_int_distribution<> dist(0, 100000);
    int rand = dist(gen);
    rand = rand % end + start;

    return rand;
}


Ich werde erstmal zusehen, dass mein Client bei xhundert Testdurchläufen nichtmehr abstürzt (momentan stürzt er aus mir unbekannten Gründen ca. 1 mal bei 100 Testläufen ab). (übrigens auch mit irrXML => es liegt definitiv an meiner Implementierung. btw.: irrXML ist wirklich genial). Danach werde ich die eigentliche Strategie implementieren. Wenn die fertig ist, spendiere ich ihr ein paar algorithmische Optimierungen. Ganz zum Schluß gibt es - vielleicht - dann die Optimierung auf OS-Ebene. (X-Compiling)

Benutzeravatar
Christian Wulf
Beiträge: 27
Registriert: Mi 31. Aug 2011, 05:54

Re: Ein bisschen quatchen ist gut ;)

Beitragvon Christian Wulf » Di 20. Sep 2011, 12:37

Die Permutationen (Slots * Städte * Segmente) abzüglich der durch Randbedingungen wegfallenden Möglichkeiten ergeben die Menge aller möglichen Züge aus einem gegebenen Spielstand.

Die möglichen, gültigen Züge gibt in Java die Methode GameState.getPossibleMoves() zurück. Das muss man also dort gar nciht selbst implementieren, wenn man nicht will.

Ich kann mir nicht vorstellen, dass der Java-/Delphi-Client auf dem Array der erzeugten Zugmöglicheiten noch einen Shuffle durchführt, damit sie wirklich in zufälliger Reihenfolge vorliegen.

Das ist ja auch nicht nötig. Stattdessen wird der Index zufällig gewählt und dann auf das Element der Zugliste mit diesem Index zugegriffen. Damit wird ebenso zufällig ein Zug aus der Menge gewählt. Das macht jedenfalls der aktuelle SimpleClient.

Aus diesem Grund verstehe ich gerade auch nicht, was du gerade vorhast. Deinen SourceCode verstehe ich daher auch nicht so ganz. Zum Beispiel könnte das Ergebnis von deiner random-Funktion mit

Code: Alles auswählen

random(2,100)

größer als 100 sein, wenn ich mich nicht irre. Wenn rand = 99 gewählt würde, ergebe deine Zeile

Code: Alles auswählen

rand = rand % end + start;

99 mod 100 + 2 = 101. Das ist nicht im Sinne der Semantik der random-Funktion.

Gruß,
Christian

mind_in_a_box
Beiträge: 15
Registriert: Mi 31. Aug 2011, 19:26

Re: Ein bisschen quatchen ist gut ;)

Beitragvon mind_in_a_box » Di 20. Sep 2011, 15:03

99 mod 100 + 2 = 101. Das ist nicht im Sinne der Semantik der random-Funktion.


Das wäre richtig:

Code: Alles auswählen

value % range + min


So wie es auch in der Dokumentation steht:
http://www.cplusplus.com/reference/clib ... dlib/rand/

Also:

Code: Alles auswählen

/** Random value */
int Rand(int min, int max)
{
   return rand() % (max-min) + min;
}

ZeroByte
Beiträge: 25
Registriert: Mi 14. Sep 2011, 21:08

Re: Ein bisschen quatchen ist gut ;)

Beitragvon ZeroByte » Di 20. Sep 2011, 16:11

Und um ganz genau zu sein:

Code: Alles auswählen

/** Random value */
int Rand(int min, int max)
{
   return rand() % (max-min+1) + min;
}


Danke für den Hinweis - habs gefixt und gleich noch Asserts hinzugefügt.
Ich habe meinen Clienten nochmal dahingehend umgeschrieben, dass man die Strategie für das Updaten des GameStates ändern kann. Leider ist der Bug mit dem Absturz immernoch nicht gefunden :X Habe jetzt nochmal 300 Testläufe gemacht und dabei ist es genau einmal abgestürzt :X

Mir ist btw. noch Folgendes aufgefallen:
a) Wenn man einzelne Spiele in der ServerGUI startet, kommt es häufiger mal vor, dass der "Weiter"-Button ausgegraut ist. Geht man dann auf "Zurück" und dann nochmals auf "Vorwärts", so is die Ausgrauung verschwunden. Manchmal lässt sie sich jedoch gar nicht austricksen. Schaue ich in den parallel offenen Log meines Clienten, so sehe ich, dass mein Client bei einer Ausgrauung erst gar keine Zuganfrage erhalten hat.

b) Startet man Testläufe, so werden die Prozesse nach jedem Test nicht beendet, sondern laufen weiter. Ich beobachte gerade, wie die Liste im Taskmanager immer länger mit "Manhatten.exe" wird (aktueller Stand: 186 Prozesse auf meinem Laptop xD). Das Problem tritt im Einzelspielmodus nicht auf.
Das lässt sich bei mir bisher nur so lösen, indem ich das Interface einmal schließe.

mind_in_a_box
Beiträge: 15
Registriert: Mi 31. Aug 2011, 19:26

Re: Ein bisschen quatchen ist gut ;)

Beitragvon mind_in_a_box » Di 20. Sep 2011, 19:31

Und um ganz genau zu sein:
[...]


Stimmt, stimmt. Die +1 war mir entfallen ;-)

ZeroByte
Beiträge: 25
Registriert: Mi 14. Sep 2011, 21:08

Re: Ein bisschen quatchen ist gut ;)

Beitragvon ZeroByte » Mi 21. Sep 2011, 15:16

So, wie von mir vermutet, liegt der Fehler irgendwo im inkrementellen Update. Da das sowieso nicht _den_ Unterschied macht, update ich jetzt bei jedem Zug eben _alles_. Die paar Millisekunden werde ich noch grad so verkraften ;) Strategie, ich komme!
Wie weit seid ihr eigentlich so?

L-Wert
Beiträge: 10
Registriert: Do 1. Sep 2011, 13:16

Re: Ein bisschen quatchen ist gut ;)

Beitragvon L-Wert » Do 22. Sep 2011, 11:40

Also wir haben am Montag endlich eine evaluate Funktion implementiert und spielen gerade ein bisschen mit den Werten. Wir haben uns ausserdem ein bisschen mit Suchen wie MinMax beschäftigt und lernen die Sprache Java gerade noch ein bisschen. In der nächsten Zeit werden wir warscheinlich versuchen die MinMax Suche zu implementieren. Ansonsten ist nicht so viel los.