Blobby Volley KI Contest auf spieleprogrammierer.de

Neuigkeiten und Ankündigungen rund um ZFX, Spieleentwicklung, Software, Programmierung und Computer.
Forumsregeln
Themen in diesem Forum werden als Neuigkeiten auf der Startseite, auf unserer Facebook-Seite und auf Twitter bekannt gemacht.
Antworten
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Helmut »

Hallo,
wollte euch nur kurz darauf aufmerksam machen, dass ich zur Zeit einen kleinen KI Contest hier veranstalte:
https://www.spieleprogrammierer.de/32-p ... 015-23-59/
Es geht um eine KI für ein einfaches Spiel. Die Beispiel KI sieht so aus:

Code: Alles auswählen

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;
    }
};
Ich hab versucht die Regeln so zu konzipieren, dass eine Teilnahme auch mit wenig Zeit möglich ist. Vielleicht hat ja der ein oder andere Lust, mitzumachen. :)
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Alexander Kornrumpf »

Wie wirst du prüfen ob nur 100MB allokiert wurden?

Ich breche die Frage auf ein paar cases runter:

1) Meine Klasse macht nichts anderes als einmal bei Konstruktion malloc(1024*1024*100). OK?
2) Meine Klasse macht nichts anderes als einmal bei Konstruktion void* p = malloc(1024*1024*100). OK?
3) Falls 2 nicht ok ist, wie steht es mit void* p = malloc(1024*1024*100-sizeof(p))?
4) Falls 1-3 nicht ok ist, wie steht es mit dem C++ äquivalent? Was ist überhaupt das C++ Äquivalent? new char[1024*1024*100]?
5) Was ist mit const char* = "gibberish, continues for 1024*1024*100 characters. If you like make that -1 to accout for terminal 0 ..."?
6) Falls 5 ok, was ist mit const char* = "gibberish for more than 100 MB"?
7) Falls 5 oder 6 nicht ok, was ist mit einer (generierten) Funktion der folgenden Art

char fake_const_array(size_t index)
{
switch (index)
{
case 0: return 'g';
case 1: return 'i';
case 2: return 'b';
case 3: return 'b';
//usw.
}
}



Ich denke man kann erkennen, was ich damit abklopfen will.
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Helmut »

Alexander Kornrumpf hat geschrieben:Wie wirst du prüfen ob nur 100MB allokiert wurden?

Ich breche die Frage auf ein paar cases runter:

1) Meine Klasse macht nichts anderes als einmal bei Konstruktion malloc(1024*1024*100). OK?
2) Meine Klasse macht nichts anderes als einmal bei Konstruktion void* p = malloc(1024*1024*100). OK?
3) Falls 2 nicht ok ist, wie steht es mit void* p = malloc(1024*1024*100-sizeof(p))?
4) Falls 1-3 nicht ok ist, wie steht es mit dem C++ äquivalent? Was ist überhaupt das C++ Äquivalent? new char[1024*1024*100]?
5) Was ist mit const char* = "gibberish, continues for 1024*1024*100 characters. If you like make that -1 to accout for terminal 0 ..."?
6) Falls 5 ok, was ist mit const char* = "gibberish for more than 100 MB"?
7) Falls 5 oder 6 nicht ok, was ist mit einer (generierten) Funktion der folgenden Art

char fake_const_array(size_t index)
{
switch (index)
{
case 0: return 'g';
case 1: return 'i';
case 2: return 'b';
case 3: return 'b';
//usw.
}
}



Ich denke man kann erkennen, was ich damit abklopfen will.
Also erstens denke ich nicht, dass überhaupt eine KI so speicherhungrig sein wird, zweitens werde ich im Zweifel die KI natürlich nicht disqualifizieren, wenn sie ein MB zu viel allokiert. Wenn jemand eine KI schreibt, die tatsächlich ans Limit kommt, kann er mir die auch gerne zuschicken und vor Ende der Runde fragen, ob sie ok ist, aber wie gesagt denke ich nicht, dass es dazu überhaupt kommt.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Alexander Kornrumpf »

Ich vermute das Spiel ist klein genug, dass man es mit Q-learning in den Griff bekommen kann. Wenn man keine Bits schubsen will, braucht man ein char um die Aktion abzubilden. Wenn man also die Policy in einer Tabelle ablegen will und diese Tabelle gilt als Allokation, kann der State Space maximal 2^20 * 10^2 Zustände umfassen. Es gibt natürlich noch mehr Gründe warum man keinen wesentlich größeren State Space will, vor allem weil es ewig dauern wird, das Ding zu trainieren und weil man für das Training State-Action Values speichern muss, was den Speicherbedarf im Training nach meiner Rechnung mindestens versechzehnfacht.

Jedenfalls trainiert man dann offline und schaut im Wettbewerb nur in der Tabelle nach, so meine Idee. Ob es klappt kann ich nicht sagen.

Klar ist, dass die Intelligenz nur darin steckt wie man den State-Space enkodiert um mit einer gegebenen Anzahl von Zuständen auszukommen. Was meiner Meinung nach der interessantere Contest gewesen wäre und euch viel von eurer Diskussion drüben erspart hätte. Insbesondere ist eine KI die nur einen lookup macht per Definition natürlich deterministisch.

Um das kurz zu präzisieren, vielleicht willst Du die Idee ja aufgreifen für eine mögliche Wiederholung:

Jeder gibt Teilnehmer gibt dem Ausrichter 100MB seiner Wahl, die in ein char-Array geladen werden. Die abzugebene Funktion besteht darin, aus dem GameState in seiner jetzigen Form einen Index in dieses Array zu berechenen. Dabei sind beliebige arithmetische Operationen erlaubt, aber keine Pseudozufallszahlen und keine Traversion über den Spielbaum. Der berechnete Index wird im Array nachgeschlagen und der gefundene Wert als Aktion übergeben.
Benutzeravatar
Sternmull
Establishment
Beiträge: 264
Registriert: 27.04.2007, 00:30
Echter Name: Til
Wohnort: Dresden

Re: Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Sternmull »

Offtopic: Das Verb heißt allozieren und nicht allokieren. Ich sehe das immer wieder und es nervt mich. Deshalb geb ich das hier und jetzt mal kund :)
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Helmut »

Alexander Kornrumpf hat geschrieben:Ich vermute das Spiel ist klein genug, dass man es mit Q-learning in den Griff bekommen kann. Wenn man keine Bits schubsen will, braucht man ein char um die Aktion abzubilden. Wenn man also die Policy in einer Tabelle ablegen will und diese Tabelle gilt als Allokation, kann der State Space maximal 2^20 * 10^2 Zustände umfassen. Es gibt natürlich noch mehr Gründe warum man keinen wesentlich größeren State Space will, vor allem weil es ewig dauern wird, das Ding zu trainieren und weil man für das Training State-Action Values speichern muss, was den Speicherbedarf im Training nach meiner Rechnung mindestens versechzehnfacht.
Zugegebenermaßen kenne ich Q-learning nicht, aber wie kommst du auf 2^20 * 10^2? Ich denke die Anzahl der Spielzustände (das meinst du oder?) ist wesentlich größer, weil immer ein Ball hinzugefügt wird, wenn kein Spieler für 30 Sekunden einen Punkt macht.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Alexander Kornrumpf »

Ich habe mich missverständlich ausgedückt. Auf 100MB kann man trivial für 2^20*10^2 Zustände eine Aktion speichern, wenn die einzelne Aktion jeweils ein Byte belegt. Real belegt sie weniger, aber ich will da nicht subbyte rumpuzzlen.

Das heißt: Es gilt erstens ein Mapping der potentiell viel mehr Zustände auf die o.g. Anzahl an Äquivalenzklassen zu finden. Das ist der schwere Teil. Und zweitens dann zu erlernen welches die beste Reaktion auf die einzelnen Äquivalenzklassen ist. Das kostet Rechenzeit ist aber prinzipiell nicht sehr schwer wenn man den ersten Teil gelöst hat, zumindest ist das meine Vermutung, für dieses recht einfache Spiel.

Mit so einer Liste der Aktionen in Abhängigkeit vom Zustand (Policy) in der Hand kann die KI mehr oder weniger in konstanter Zeit reagieren. Eure Diskussionen zur Rechenzeit wären damit umgangen.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Alexander Kornrumpf »

Im Übrigen hatte ich es so verstanden, dass man sich nichts [variables] frameübergreifend merken darf. Ich dachte dafür sei die Reset Funktion.

David hatte drüben geschrieben er würde den Suchbaum weiterverwenden. Da waren die Regeln vielleicht nicht ganz klar.
Helmut
Establishment
Beiträge: 237
Registriert: 11.07.2002, 15:49
Wohnort: Bonn
Kontaktdaten:

Re: Blobby Volley KI Contest auf spieleprogrammierer.de

Beitrag von Helmut »

Alexander Kornrumpf hat geschrieben:Ich habe mich missverständlich ausgedückt. Auf 100MB kann man trivial für 2^20*10^2 Zustände eine Aktion speichern, wenn die einzelne Aktion jeweils ein Byte belegt. Real belegt sie weniger, aber ich will da nicht subbyte rumpuzzlen.
Das Spiel dürfte aber wesentlich mehr als 100*1024*1024 Zustände haben. Allein die Position eines Balls benötigt etwa 32Bit, und es können mehrere Bälle dazukommen.

Heute um Mitternacht ist übrigens Abgabe für die vorletzte Runde. Wenn ihr heute was abgebt habt ihr gute Chancen auf den Sieg. Hier eine kurze Anleitung, was dazu notwendig ist:
- Framework hier runterladen
- Das Projekt öffnen (mit CodeLite oder VS) und im Projekt KIs.h öffnen
- Die Klasse MyNicknameKI enthält den Code der aktuell besten KI. Leicht modifizieren.
- Kompilieren und Starten
- 1, Enter, 2, Enter drücken
- Wenn eure KI nun HelmutKI7 schlägt, Code einsenden! Ansonsten nochmal leicht ändern :)
Antworten