Du bist nicht angemeldet.

Werbeanzeige

Helmut

5x Contest-Sieger

  • »Helmut« ist der Autor dieses Themas

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

1

11.02.2015, 17:33

#17: "Blobby Volley KI", Spezial

#17: "Blobby Volley KI"
Typ: Spezial

Aufgabenstellung:
Außerirdische Gummibärchen fordern uns zu einem Volleyballturnier auf, und das müssen wir natürlich annehmen und den guten Ruf der Erde verteidigen!
Es gelten die üblichen Volleyballregeln mit einigen (außerirdischen) Änderungen. Unter Anderem:
- Es steht nur ein Gummibärchen auf jeder Seite.
- Der Ball kann mehrmals geschlagen werden.
- Wenn beide Spieler eine gewisse Zeit keinen Punkt machen, wird ein Ball zum Spielfeld hinzugefügt.

Du musst die KI für dein Gummibärchen schreiben. Diese kann z.B. so aussehen:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class AngsthaseKI : public KI
{
    // Die KI muss deterministisch sein. Wir benutzen also
    // einen standardisierten Zufallsgenerator (Ist in BlobbyVolleyKI.h)
    MTRand rand;
public:
    AngsthaseKI()
    {
        Reset();
    }
    virtual const char* GetKIName() const
    {
        return "Angsthase";
    }
    virtual void Reset()
    {
        //Hier müssen alle Member zurückgesetzt werden
        rand.seed(0);
    }
    virtual int CalculateNextStep(const GameState& GS)
    {
        if(TryDirection(0, GS)) return 0;
        if(TryDirection(K_Left, GS)) return K_Left;
        if(TryDirection(K_Right, GS)) return K_Right;
    
        return rand()%2 == 0 ? K_Left : K_Right;
    }
    bool TryDirection(int Keys, GameState GS)
    {
        //Wir kopieren den Spielzustand und simulieren eine Richtung
        int MyScore = GS.Players[0].Score;
        int EnemyScore = GS.Players[1].Score;
        for(int i = 0; i < 5 * FramesPerSecond; i++)//5 Sekunden vorausberechnen
        {
            GS.Move(Keys, 0, true);//Für den Gegner geben wir 0 an. Wir hoffen mal, dass er stehen bleiben wird.
            if(GS.Players[1].Score > EnemyScore)
                return false;//Gegner wird einen Punkt machen. So besser nicht bewegen
            if(GS.Players[0].Score > MyScore)
                return true;//Wir werden einen Punkt machen
        }
        return false;
    }
};


So sieht das Schlachtfeld aus:

Es kann mit der Plus- und Minus-taste die Geschwindigkeit angepasst werden.
Die angezeigten Werte bedeuten folgendes:
- Die oberste Zahl ist die Punktzahl. Wenn ein Spieler 15 Punkte erreicht, ist das Spiel beendet.
- Der CPU-Wert gibt die durchschnittliche Geschwindigkeit der KI in dem Spiel bisher an. Wenn beide KIs auf 100% sind ist das Spiel (wenn man die Renderzeit und sonstigen Aufwand vernachlässigt) gerade noch Echtzeit. Wenn der Wert z.B. 200% beträgt läuft das Spiel nur noch mit halber Geschwindigkeit.
- Der LS-Wert gibt die CPU-Auslastung der KI innerhalb der letzten Spielsekunde an.
- Der Std-Wert ist der Wichtigste. Er entspricht dem CPU-Wert multipliziert mit einem Faktor, der zu Beginn durch eine Kalibierung festgestellt wird. Dieser Faktor ist auf dem Computer, auf dem getestet wird, 1 und überall sonst abhängig von der Hardware. Theoretisch sollte der Std Wert also für eine KI auf jedem Computer den selben Wert haben. Er darf 200% nicht überschreiten (sonst wird die KI verlieren) und sollte unter 100% liegen (sonst gibt's Punktabzug).

Auswertung:
Es tritt jede eingesandte KI gegen jede andere KI einmal an. Ein Spiel läuft entweder so lange, bis ein Spieler 15 Punkte erreicht oder das Spiel vorzeitig von der Spiellogik beendet wird.
Dann wird die Punktzahl jedes Spieler mit dem Faktor clamp((200-Std)/100, 0, 1) multipliziert und anschließend aufgerundet. Wenn dann ein Spieler mehr Punkte hat, bekommt er zwei Punkte. Wenn die Punktzahl gleich ist, bekommt jeder Spieler einen Punkt
Nach Ablauf der Zeit für die erste Runde bekommt der Teilnehmer mit den meisten Punkten einen Punkt.
Dann beginnt die zweite Runde. Es werden alle Sourcecodes veröffentlicht und es können neue KIs eingesandt werden. Nach Ablauf der zweiten Runde wird wieder jeder gegen jeden antreten und der Teilnehmer mit den meisten Punkten bekommt 2 Punkte (weils die zweite Runde ist, in der n. Runde gibt's n Punkte).
Nach Ende der 5. und letzten Runde ist der Teilnehmer mit den meisten Punkten Gewinner.

Ich denke so ein Verfahren hat einige Vorteile:
- Man muss keine komplette KI schreiben, sondern kann sich eine Eingesandte nehmen und erweitern. (außer in der ersten Runde)
- Kleine schlaue Ideen werden stärker belohnt als aufwändige zeitintensive Implementierungen.
- Man kann mit wenig Aufwand und Zeit teilnehmen und hat trotzdem gute Chancen.

Regeln:
- Ablauf und Regeln
- Die KI muss deterministisch sein (sie muss bei gleichen Parametern jedes mal das gleiche Ergebnis liefern)
- Es darf nur Standard C++11 benutzt werden, nichts platformabhängiges, Compiler-spezifisches oder Undefiniertes. Ebenso verboten sind Fließkommazahlen.
- Keine statischen nicht-konstanten Variablen. Die sind aber auch nicht nötig, da ihr eine Klasse implementiert (ihr könnt Member anlegen).
- Maximal etwa 100MB Speicher dürfen allokiert werden.
- Kein Multithreading!
- C++ Zugriffsschlüsselwörter private und const dürfen nicht umgangen werden. Funktionen und Variablen, die laut Kommentar nicht benutzt werden dürfen, dürfen logischerweise nicht benutzt werden. :)
- Code darf nicht absichtlich unleserlich gemacht werden.
- Man muss damit einverstanden sein, dass der eingesandte Code von anderen verwendet wird.

Hinweise:
- Ich empfehle std::array statt normalen Arrays zu benutzen. Diese haben in der Releaseversion keine Performanceeinbußen, helfen aber sicherzustellen, dass kein undefiniertes Verhalten auftritt.
- Falls ihr std::sort und qsort benutzen wollt: Stellt sicher, dass eure Vergleichsfunktion eine eindeutige Reihenfolge definiert. Selbst wenn euch nur die korrekte Reihenfolge eines Members oder so interessiert. Ansonsten führt die Funktion zu compilerabhängigem Verhalten!
- Standard srand und rand dürfen gemäß der Regeln nicht benutzt werden. Siehe Beispielcode für eine Alternative.
- Wenn man den Code von wem anders übernimmt sollte man dies in einem Kommentar vermerken.
- Einsendungen, die nicht den Regeln entsprechen, können auch nachträglich disqualifiziert werden. Es werden dann alle folgenden Spiele erneut gespielt.
- Es können pro Runde maximal 7 Einsendungen von einem Teilnehmer gemacht werden.
- Ich werde die KIs mit dem Codelite Workspace mit Clang kompilieren und unter Windows laufen lassen.

Zeitplan:
1. Runde endet Sonntag 22.02.2015 23:59
2. Runde endet Sonntag 01.03.2015 23:59
3. Runde endet Sonntag 08.03.2015 23:59
4. Runde endet Sonntag 15.03.2015 23:59
5. Runde endet Sonntag 22.03.2015 23:59

Was gibt es zu gewinnen?
Dem Gewinner des Contests winkt ein besonderer Rang im Forum, unendlicher Ruhm und Ehre, sowie ein Amazon Gutschein im Wert von 50€!!

Was muss ich tun, um mitzumachen?
Paket hier herunterladen
Im Zip-Paket findet ihr einen CodeLite-Workspace (Windows+Linux) und eine Solution für Visual C++ 2010.
Informationen zu bereitgestellten Funktionen und Klassen findet ihr in BlobbyVolleyKI.h und das Grundgerüst für eure KI findet ihr in KIs.h.
Die Einsendung schickt ihr direkt an mich über PM hier im Forum. (bitte [ cpp] Tags nicht vergessen)
Falls euch die ganzen Regeln oder das Framework etwas einschüchtern, so kompliziert ist das alles nicht! Einfach mal probieren!

Bei Fragen/Problemen schreibt bitte in diesen Thread.
Viel Spaß!
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von »Helmut« (21.03.2015, 17:44)


2

11.02.2015, 18:30

Schönes Ding! Kenne ich noch von früher, auf der Technikerschule war das immer der Pausenfüller :)

Immer hin konnte ich dem Profi schon mal 2 Punkte abknöpfen.
Also eine Teilnahme an dem Contest könnte mich reizen weiß nur nicht ob ich die Zeit dazu finde was brauchbares zu schreiben.

Gruß Koschi
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

David Scherfgen

Administrator

Beiträge: 9 889

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

11.02.2015, 20:29

Sehr schön gemacht, Helmut!
Das mit der Rechenzeit wird hier allerdings ziemlich sicher zum Problem werden, denke ich - denn davon hängt ja die maximal mögliche Suchtiefe ab, jedenfalls wenn man mit einem graphbasierten Algorithmus arbeitet.
Ich schlage außerdem vor, das Startdatum mindestens um eine Woche zu verschieben. Jetzt ist nämlich Karneval, und der eine oder andere wird da vielleicht nicht dazu kommen. Außerdem gibt das dir mehr Zeit, um das Framework zu finalisieren und an der Bewertung zu feilen und uns mehr Zeit, um die erste KI zu schreiben.

4

11.02.2015, 22:00

Ich hab noch nie bei sowas mitgemacht... Wo krieg ich denn den vorgeschriebenen Code her?

David Scherfgen

Administrator

Beiträge: 9 889

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

Helmut

5x Contest-Sieger

  • »Helmut« ist der Autor dieses Themas

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

6

11.02.2015, 22:21

Stimmt, an Karneval hatte ich nicht gedacht. Dann würde ich sagen veröffentliche ich das Framework Sonntag und dann gibts pro Woche eine Runde.
Das mit der Rechenzeit klappt schon :D
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

Schorsch

Supermoderator

Beiträge: 4 930

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

7

12.02.2015, 10:21

Vielleicht finde ich diesmal ja Zeit für einen Contest:) Das Thema gefällt mir.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

TGGC

1x Rätselkönig

Beiträge: 1 708

Beruf: Software Entwickler

  • Private Nachricht senden

8

12.02.2015, 10:43

Ich wuerde eigentlich auch gerne mitmachen, bin aber leider etwas sekptisch.

Schorsch

Supermoderator

Beiträge: 4 930

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

9

12.02.2015, 12:29

Weshalb bist du denn skeptisch? Gehts ums Framework oder?
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

David Scherfgen

Administrator

Beiträge: 9 889

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

10

12.02.2015, 12:42

Nee, es geht immer noch um die Begrenzung der KI-Rechenzeit. Je nach Lösungsansatz möchte man die erlaubte Rechenzeit so gut wie möglich ausnutzen, aber Helmut verlangt 100% deterministische KIs. Das heißt, dass man nicht die Zeit stoppen kann, um die Suche nach der optimalen Aktion rechtzeitig abzubrechen. Im schlimmsten Fall gewinnt dann derjenige, der Helmuts Test-PC am besten einschätzen kann. Darum gab es den Vorschlag, die KI in einer VM-Sprache wie Lua zu schreiben und statt der Rechenzeit die Anzahl der Instruktionen und evtl. den Speicherverbrauch zu begrenzen. Das wäre dann unabhängig vom Test-PC.

EDIT: Ich glaube eine Lösung für das Dilemma gefunden zu haben. Details folgen gleich :-)

Werbeanzeige

Ähnliche Themen