Programmieren KI Contest

Programmieren KI Contest

Beitragvon A1m » Di 15. Dez 2009, 18:43

Hi Kommilitone,

wie viele bestimmt schon mitbekommen haben, möchten wir aus Spaß unter uns Studenten einen KI Contest austragen, die Diskussion dazu gab es in diesem Thread: viewtopic.php?f=7&t=100

Ich kann eh nicht sogut Programmieren
Einfache KIs sind auch sehr einfach! Ihr müsst nicht gewinnen, dabei sein ist alles! ;-) Und es ist sicher eine gute Übung zum vertiefen eurer Kentnisse für die Abschlußaufgabe. Für eine KI werden keine Ultrakentnisse über alle möglichen Java Code/Stretegien gebraucht, sogar OOP kommt nicht so stark zum tragen. Im großen und ganzen ist eure logik entscheidend, wenn ihr gute Ideen habt, solltet ihr das mit unserem Wissensstand eigentlich umsetzen können. Probiert es einfach mal!
Hier im Thread gibt es außerdem im folgenden noch ein Video und Beispiel KIs an dennen ihr euch orientieren könnt! :-)
Ich hab dafür nicht genug Zeit
Die Abgabe bzw. Austragung der Spiele wird vorerst auf den 11.1 gelegt, also wenn ihr lust habt solltet ihr warscheinlich genug Zeit haben in den Ferien. :)

Damit euch das durchwühlen des ganzen Threads erspart bleibt werde ich hier in möglichster Kürze zusammenfassen worum es geht. Außerdem hat xZise dazu ein Klasse Video gemacht, dass euch das ganze Technische sehr schnell nahebringen sollte, scheut euch nicht zu Fragen.
http://www.youtube.com/watch?v=XZVv_zIpleA

Kurz was im Video erklärt wird:
Eigentlich müsst ihr nur genau eine Klasse mit genau einer Methode erstellen die genau Wert ausgibt. Eure Klasse muss von Player erben, eure Methode muss abstract askThrow() überschreiben und euer Wert muss ein Integer innerhalb der Spielfeldbreite sein.
Das waren schon so ziemlich alle technischen Vorgaben die wir euch machen!
Wie ihr auf das Spielfeldarray und Spielerfarben zugreift wird im Video beschrieben.

Meldet euch hier im Thread kurz mit eurem Namen + die Ernsthaftigkeit (Ihr wollt ganz sicher mitmachen, schon lust aber wenig Zeit, nur wenn ihr zufällig lust bekommt, ihr wollt sicher mitmachen aber ihr schafft es bis zum Termin nicht ... etc.) und erwartung (Ultra-KI kicks your ass, mal probieren wasmöglich ist, nur zum Spaß um dabei zu sein ... etc.) an.

Zu den Regeln:

- 4 Gewinnt
- 8x8 Board
- Keine Datenbank erlaubt
Unter einer Datenbank verstehen wir alles was in irgendeiner Form vor Spielbeginn Spielzüge/situationen eingespeichert hat!
- Pro Spielzug darf die KI nicht länger als ca. 1 sekunde brauchen.
Damit soll bruteforcen vermieden werden, d.h. man betrachtet einfach für die nächsten 20 Züge alle möglichen Spielsituationen. Euer Algorythmus soll denken, nicht durchprobieren!
- Man sollte so ehrlich sein und wirklich alles selbst machen ohne sich im Internet über KI zu informieren.


Zur Durchführung:

Wir werden uns warscheinlich im ATIS treffen und dort die Spiele austragen.
- jede KI tritt 20 mal gegen jede an.
- die jeweils ersten Steine der Runde werden zufällig bereits auf das Board gelegt (Vermeided identische Partien)
- Sollte ne KI abstürzen, falsche Werte zurückgeben oder länger brauchen als erlaubt ist gewinnt der Gegner diese Partie.
- Könnt ihr nicht persönlich zum Termin erscheinen schickt ihr die KI jemandem der mitmacht.


Als Beispiel hier eine einfache KI von mir: (Im video gibts noch ne dümmere =) )
(nicht getestet, evtl. buggy!)
Code: Alles auswählen
    public class easyKI extends Player{
       
       int lastSlotIThrownIn = 999;

            @Override
       public int askThrow() {
          if(lastSlotIThrownIn == 999) {
             // suche nach einem deiner eigenen Steine wenn du vorher noch nichts gemacht hast
             boolean ownStoneFound = false;
             for (int i=0; i < field[].length && !ownStoneFound; i++) {
                for (int j=0; j < field.length && !ownStoneFound; j++) {
                   if (field[j][i] == getColor()) {
                      lastSlotIThrownIn = j;
                      ownStoneFound = true;
                   }
                }
             }
          }
         
          if (lastSlotIThrownIn + 1 < field.length && field[lastSlotIThrownIn + 1][field[].length -1] == 0) {
             // wenn der nächste Slot noch im Spielbereich liegt und da noch ein Stein reinpasst dort einwerfen
             lastSlotIThrownIn++;
             return lastSlotIThrownIn;
          }
          if else (lastSlotIThrownIn - 1 >= 0 && field[lastSlotIThrownIn - 1][field[].length -1] == 0) {
             // links daneben gleicher Versuch
             lastSlotIThrownIn--;
             return lastSlotIThrownIn;
          }
          if else(field[lastSlotIThrownIn][field[].length -1] == 0) {
             // versuchs oben drauf ;)
             return lastSlotIThrownIn;
          }
          else {
             // suche irgendein leeres Feld zum einwerfen
             for (int i = 0; i < field.length; i++) {
                if(field[i][field[].length -1] == 0) {
                   lastSlotIThrownIn = i;
                   return lastSlotIThrownIn;
                }
             }
          }
         
          return 0; // board ist voll ihr Schwachköpfe! :(
         
         
       }
       
    }



Die offiziele Player.java, das 4 Gewinnt Spiel und Gamecontroll editiere ich nachträglich noch in den Post.
Benutzeravatar
A1m (Andi M)
regelt das!
regelt das!
 
Beiträge: 426
Registriert: Mi 11. Nov 2009, 20:16
Wohnort: Leimen
Danke gegeben: 45
Danke bekommen: 94 mal in 45 Posts
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon A1m » Di 15. Dez 2009, 18:44

Anmeldungsliste:

A1m - Andi. Wenn eclipse in den Ferien funktioniert ^^ - Gute KI
nalvori - Folrian. Wenn die Zeit reicht - Gute KI
Manu. Sicher dabei - Gute KI
xZise. Wenn die Zeit reicht - Gute KI
Zünni. Sicher dabei - Gute KI
Benutzeravatar
A1m (Andi M)
regelt das!
regelt das!
 
Beiträge: 426
Registriert: Mi 11. Nov 2009, 20:16
Wohnort: Leimen
Danke gegeben: 45
Danke bekommen: 94 mal in 45 Posts
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon DuKeTHeReaL » Di 15. Dez 2009, 20:30

Auf welchem Rechner wird das ganze laufen?
Ist wichtig um zu wissen wie viele Züge man mit bruteforce vorrausberechnen darf um noch in der 1 Sekunde zu liegen.


Grüße
DuKeTHeReaL (Max )
ist überzeugend
ist überzeugend
 
Beiträge: 161
Registriert: Sa 21. Nov 2009, 00:56
Wohnort: Südoststadt
Danke gegeben: 17
Danke bekommen: 51 mal in 15 Posts
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon nalvory » Mi 16. Dez 2009, 11:19

Wenn's die Zeit zulässt bin ich am Start und kick euch in den ass!
nalvory (Florian )
kann lesen und schreiben
kann lesen und schreiben
 
Beiträge: 5
Registriert: Sa 21. Nov 2009, 21:18
Danke gegeben: 4
Danke bekommen: 0 mal in 0 Post
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon Manu » Do 17. Dez 2009, 12:09

Bin natürlich dabei und habe gestern meine erste KI gedraftet.

Ich habe dafür die MatchBox Klasse etwas umgeformt um eine Statistik ausrechnen zu lassen. Mit 100 tausend Spielen hat man ein ziemlich konstantes Ergebnis :lol:

Dabei ist mir aufgefallen, dass der Spieler, der Anfängt, einen statistischen Vorteil hat. (lass RandomGuy vs RandomGuy antreten, dann bekommst du 55% für X und 45% für O) Daraufhin hab' ich den Spieler jedes zweite Spiel abgewechselt, und siehe da, das Ergebnis ist bei je 49-50%

Meine Eigene KI spielt jetzt Konstant 19% sieg, 4% lose und 2% unentschieden gegen RandomGuy. Bis jetzt ist sie aber auch noch 'Blind' in dem Sinne, dass sie nur betrachtet, welcher nächste Spielzug am wahrscheinlichsten zum Sieg führt. Sie kümmert sich noch nicht um die konsequenzen ihrer Taten. ;)

Ich lasse meinen Draft mal eben gegen dein Beispieldings antreten :D

Achja im MatchBox Grundgerüst fehlt in der Game Klasse eine Funktion, um die Höhe des Spielfeldes und die Winlength zu erfassen. (Ich schreibe einen generellen Algorithmus, nicht 4 Gewinnt auf 8x8...)

Edit: uah dein Ding ist zu verbuggt :D das kompiliert nichtmal, hab ein paar Bugs rausgefixt aber jetzt gibts Access Violations, also nene das funktioniert so nicht xD
  • Informatik Student, Nebenfach Mathe
  • C# Programmierer
  • HiWi am SCC/Rechenzentrum
  • Übungsleiter Trampolin
Benutzeravatar
Manu (Manu )
hat mächtig Ahnung
hat mächtig Ahnung
 
Beiträge: 214
Registriert: Fr 13. Nov 2009, 14:32
Wohnort: シ ツ
Danke gegeben: 7
Danke bekommen: 9 mal in 7 Posts
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon A1m » Do 17. Dez 2009, 13:34

Meine Eigene KI spielt jetzt Konstant 19% sieg, 4% lose und 2% unentschieden gegen RandomGuy


aha? :P komische statistik :D Aber gegen Randomguy müsste doch wirklich 100% ziemlich einfach sein ? ^^



yo mein Beispiel basiert noch auf einem älteren Player und auf meiner eigenen Game class. :-/ Ich werd mal ein lauffähiges reinstellen wenn ich mal richtig damit anfange, bisher hat ich leider noch keine Zeit was richtiges "auf Bildschirm" zu bringen :P

Es zeigt aber zumindest den Ansatz wie man an sowas rangehen kann, also hoffe ich es hilft :-)
Benutzeravatar
A1m (Andi M)
regelt das!
regelt das!
 
Beiträge: 426
Registriert: Mi 11. Nov 2009, 20:16
Wohnort: Leimen
Danke gegeben: 45
Danke bekommen: 94 mal in 45 Posts
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon Manu » Do 17. Dez 2009, 14:15

hab mich irgendwie vertippt... 92% ist es..


Altaaaa was geht denn? xD

Ich wechsle ja jetzt die Spieler immer ab, sodass die Chancen theoretisch gleich sind, lasse dann meine KI gegen meine KI antreten, und kriege als Ergebnis: X:50%, O:27% und 22% Unentschieden >_<

wat?? Das ist die gleiche AI mit gleichen Chancen, wie kann ich auf so ein Ergebnis kommen??
  • Informatik Student, Nebenfach Mathe
  • C# Programmierer
  • HiWi am SCC/Rechenzentrum
  • Übungsleiter Trampolin
Benutzeravatar
Manu (Manu )
hat mächtig Ahnung
hat mächtig Ahnung
 
Beiträge: 214
Registriert: Fr 13. Nov 2009, 14:32
Wohnort: シ ツ
Danke gegeben: 7
Danke bekommen: 9 mal in 7 Posts
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon xZise » Do 17. Dez 2009, 15:53

Also ich habe hier auch eine (etwas klügere KI, als die im Video :D ) programmiert. WIE gut die ist, kann ich noch nicht beurteilen, besonders weil ich sie gestern umgeschrieben habe, und noch er quasi beide Varianten beachtet (wenn mach der neuen nix sinnvolles rauskommt, dann geht er dazu über mit dem alten Algo zu testen). Und naja damals war die KI noch dumm (sie hatte mir den Stein passend gelegt) und inzwischen habe ich bisher ein unentschieden gegen sie gespielt.

Die aktuelle MatchBox ist auch noch nicht kompatibel, da die ersten beiden Würfe nicht zufällig sind. Aber Manu könntest du nicht mal deinen Code veröffentlichen? Dann kann ich das in die aktuelle MatchBox integrieren.

MfG
Fabian
Opensource ftw:
Jabber, SVG, PNG, 7Zip, VLC media player, GIMP, OpenGL, Subversion, GIT, Inkscape, Mumble, phpBB, Wikipedia, Miranda, Big Buck Bunny, Elephants Dream, Ubuntu, Eclipse, Firefox, Thunderbird, TV-Browser, Notepad++, OpenTTD, OpenOffice.org, …
Benutzeravatar
xZise (Fabian Neundorf)
1337
1337
 
Beiträge: 800
Registriert: Sa 14. Nov 2009, 00:11
Wohnort: Bad Schwartau/Reichenbach (Waldbronn)
Danke gegeben: 6
Danke bekommen: 73 mal in 50 Posts
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon A1m » Do 17. Dez 2009, 16:21

Manu hat geschrieben:Ich wechsle ja jetzt die Spieler immer ab, sodass die Chancen theoretisch gleich sind, lasse dann meine KI gegen meine KI antreten, und kriege als Ergebnis: X:50%, O:27% und 22% Unentschieden >_<

wat?? Das ist die gleiche AI mit gleichen Chancen, wie kann ich auf so ein Ergebnis kommen??


Würd mich jetzt auch interessieren ^^ wie xZise schon sagt, post mal deine MatchBox :)

Und Manu, wer war dein Freund der auch mitmacht?

Anmelden Leute !
Benutzeravatar
A1m (Andi M)
regelt das!
regelt das!
 
Beiträge: 426
Registriert: Mi 11. Nov 2009, 20:16
Wohnort: Leimen
Danke gegeben: 45
Danke bekommen: 94 mal in 45 Posts
Auf dem Campus:
:
:
:
:
:

Re: Programmieren KI Contest

Beitragvon the_one » Do 17. Dez 2009, 18:10

Moin,
ich wär auch dabei, natürlich mit dem Ziel eine gute KI zu schreiben. Meine aktuelle Version liegt bei 99,99 (ca. 1000000 Spiele) gegen Random, läuft also schon ganz gut...

Zwei Fragen:
Was ist bei einem unentschieden? Könnten wir vielleicht ein Mechanismus einbauen, der die jeweilige "Denkzeit" wie beim Schach stoppt und so der schneller Algorithmus im Zweifelsfall gewinnt?

Ich hab ja in meiner Playerklasse die Möglichkeit auf das aktuelle Spielbrett zuzugreifen, oder? Wie kann ich mir das klonen, so dass ich für mich ein Spielfeld hab, mit dem ich mehr oder weniger machen kann was ich will, also testweise Steine reinwerfen und wieder rausnehmen, etc.?

Gruß Thomas
the_one (Tom )
ist engagiert
ist engagiert
 
Beiträge: 76
Registriert: So 15. Nov 2009, 15:53
Danke gegeben: 13
Danke bekommen: 40 mal in 9 Posts
Auf dem Campus:
:
:
:
:
:

Nächste

Zurück zu Neuigkeiten

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron