Zweiter freiesMagazin-Programmierwettbewerb gestartet

Aufgrund der guten Resonanz auf den ersten Programmierwettbewerb im April 2009 starten wir heute, am 27. September 2009, den zweiten freiesMagazin-Programmierwettbewerb.

Der Wettbewerb richtet sich wieder an (Hobby-)Programmierer, die sich diesmal mit einer Künstlichen Intelligenz zur Wegfindung beschäftigen dürfen. Die Teilnehmer können sich für eine der drei Schwierigkeitsstufen (leicht, mittel und schwer) entscheiden und in dieser ein Programm in einer beliebigen Programmiersprache einreichen, welches einen Robotor sicher durch eine Fabrikhalle mit sich bewegenden Elementen zum Ziel leitet. In einer vierten Kategorie sind vor allem Grafiker gefordert, die eine 3-D- oder Isometrie-Ansicht für die Fabrikhalle programmieren sollen, in der sich der Roboter dann bewegen kann. Anzumerken ist, dass jeder Teilnehmer nur an einer der vier Kategorien teilnehmen kann.

Als Preise werden Buchgutscheine für die jeweiligen Gewinner in den vier Kategorien in Höhe von 10 Euro (leicht), 20 Euro (mittel), 30 Euro (schwer) und 50 Euro (3-D-Ansicht) vergeben.

Alle wichtigen Informationen zum Wettbewerb findet man auf der eigens dafür eingerichteten Seite, auf der man auch die notwendigen Dateien zur Teilnahme herunterladen kann.

Wir freuen uns auf zahlreiche Einsendungen und wünschen allen Teilnehmern viel Erfolg.

Und natürlich ist dies auch die Auflösung unseres kleinen Ratespiels.

Ihre freiesMagazin-Redaktion

Oh, cool ein neuer

Oh, cool ein neuer Wettbewerb. Und gute zwei Monate bis man fertig sein muss. Toll. Eigentlich dachte ich mir ja, dass meine KI-Bau-Kenntnisse zu schlecht werden würden (sind sie vermutlich auch :P) - aber die Idee gefällt mir gut, ich werd mitmachen.

Richtig genial finde ich die Einteilung in mehrere Klassen. Da muss man sich schon vorher taktisch überlegen, wo man denn dran teilnehmen will. Schön fände ichs noch, wenn man "außer Konkurrenz" auch in anderen Klassen teilnehmen darf. Die KIs aus der schweren Klasse haben ja keine Probleme mit den leichteren, auch wenn sie nicht wirklich optimal sein werden...

"Eine" kleine Frage noch zu den Spielfeldern: Wie wahrscheinlich treten die einzelnen Elemente auf? Oder wird das nicht verraten? Werden diese zufällig erstellt?

Grüße, Keba.

PS: Ach ja, ihr habt vergessen zu sagen, dass es Bookzilla-Gutscheine sind, die man gewinnen kann ;)

Re: Oh, cool ein neuer

> Schön fände ichs noch, wenn man "außer Konkurrenz" auch in anderen Klassen teilnehmen darf.

Spätestens, wenn die Ergebnisse online sind und die Gewinner bekannt gegeben wurden, kann man die Ergebnisse der eigenen KI auch in den anderen Schwierigkeitsstufen testen und vergleichen. Die Wertung ist nicht geheim, daher kann das also jeder selbst nachvollziehen.

> Wie wahrscheinlich treten die einzelnen Elemente auf? Oder wird das nicht verraten? Werden diese zufällig erstellt?

Die Spielbretter sind handerstellt, daher gibt es keine Wahrscheinlichkeiten.

> Ach ja, ihr habt vergessen zu sagen, dass es Bookzilla-Gutscheine sind, die man gewinnen kann ;)

Es müssen ja nicht zwingend Bookzilla-Gutscheine sein. ;)

Dominik Wagenführ
freiesMagazin-Redaktion

Winziger Fehler

Ihr habt - glaub ich zumindest - einen winzigen Fehler in der Spielbrett-Beschreibung.

Bei der Erklärung der Wände, steht da in der Tabelle:
7 = h = links, rechts und unten
Wenn nun aber links = 1, rechts = 2 und unten = 8, dann wäre das 11 = k anstatt 7 = h. Oder aber ihr meint "links, rechts und oben". ;)

Oder hab ich da einen Denkfehler?

Gruß, Raxxor

Re: Winziger Fehler

Vielen Dank, ich habe den Fehler behoben. Es sollte natürlich "links, rechts und oben" heißen.

Dominik Wagenführ
freiesMagazin-Redaktion

Frage zu LibAccess

Hallo,

zuerst einmal: Großen Lob für die Idee zum 2. Programmierwettbewerb! Find die Idee echt super!
Hab auch schon den ersten Wettbewerb mit Interesse verfolgt und hab mir nun mal gedacht ich versuchs einfach auch mal...

... leider hapert mein Umsetzungsdran an den libs.

Wie kann ich denn auf die libs (also z.B. die libcards.a) in C zugreifen?
Wäre super wenn mir da jemand eine Hilfestellung geben könnte!

Danke schön schonmal!

Re: Frage zu LibAccess

Schauen Sie sich am besten das Makefile der Referenz-KI im Ordner "KIs/robots-ki_dir" an. Sie müssen die Header-Dateien eigentlich nur mit "#include NAME.hh" in die jeweilige C++-Datei einbinden und dann beim Kompilieren die jeweilige Library mit angeben. Wie gesagt, am besten ins Makefile schauen.

Dominik Wagenführ
freiesMagazin-Redaktion

Fragen, Kommentare &Freude

Ah, ein neuer Wettbewerb.
Da hab ich nach dem ersten Durchblick der Regeln gleich einige Fragen:

1. Verhält sich ein Schieber, der in Richtung einer direkt am Schieberfeld angrenzenden Wand zeigt wie eine Schrottpresse (wird durch gutes Lvl-Design verhindert :) )?

2. Sind Schrottpresse und Schieber zum Teil wie Mauern? Kann man z.B. eine Schrottpresse "M" nur von unten oder oben durchqueren, oder von allen Seiten?

3. Wird man beim Rutsch durch ein Ölfeld auf das am letzten Ölfeld angrenzende Feld gesetzt, oder bleibt man auf dem letzten Ölfeldfeld stehen?

5. Falls zwei Förderbänder in der Richtung aufeinander zeigen, und man wird von einem auf das andere Band geschoben, wird man dann um 180° gedreht (wird durch gutes Lvl-Design verhindert :) )?

6. Per Förderband gelangt man auf ein Ölfeld, nach dessen Durchrutschen man auf ein weiteres, aber andere Richtung zeigendes Förderband gelangt: Wird man dann auch gedreht? (Frage gilt nur falls man auf angrenzende Felder nach einem Ölrutsch gesetzt wird).

Dann noch eine Anmerkung zum Schwierigkeitsgrad:
"Mittel" und "Schwer" unterscheiden sich meines Erachtens zu wenig. Sobald man in "Mittel" das Loch gemeistert hat, ist es ein einfaches in der KI des Bots das vorhandene Spielfeld einfach mit einem Ring aus Löchern zu umgeben. Durch so einen einfachen Kniff hat man also schon einen Bot für zwei Schwierigkeitsstufen.

Der Wettbewerb selbst begeistert dieses mal auch!!! Habe mich selbst aber noch nicht entschieden ob ich KI oder Grafik machen mag. Beides würde wieder Gelegenheit geben eine neue Skriptsprache, bzw. eine grafische Schnittstelle kennen zu lernen :)

Re: Fragen, Kommentare &Freude

Interessante Fragen. :)

1. Nein, denn ich habe mir eine abstruse Ausrede einfallen lassen: Der Bot ist maximal ein halbes Feld breit. Ein Schieber geht genau bis zur Hälfte eines Schiebers. Das heißt, wenn der Schieber komplett ausgefahren ist, dotzt der Bot leicht gegen die Wand, aber es passiert nicht Schlimmes. Wenn keine Wand da ist, rutscht er auf das nächste Feld.

2. Ja, das haben wir vergessen zu erwähnen. Man kann nicht durch einen Schieber oder eine Schrottpresse von deren geschlossene Seite fahren.

3. Ja, man landet auf dem letzten Feld nach der Ölspur (soweit keine Wand vorher stoppt).

4. Hey, wo ist Punkt 4?

5. Nein, wird man nicht. Das mit der Drehung auf den Förderbändern kommt daher, dass diese "untrennbar" verbunden sind und eigentlich grafisch einen Bogen beschreiben sollte. Das war aber zu umständlich zu realisieren. Stellt man es sich in real vor, wird man auf einem Gepäckförderband auch gedreht, wenn es um die Kurve geht. Aber man wird sicherlich nicht gedreht, wenn man auf einem Förderband steht, was gegen ein anderes läuft. Da fällt man maximal um.

6. Ich habe das gerade einfach mal in einem Spielfeld programmiert und geschaut, was passiert, da ich es selbst nicht wusste:

6 6
T>OOv 
     Z
      
      
      
      

Derzeit wird der Bot auch gedreht, wenn er von einem Fließband über eine Ölspur auf ein anderes Fließband geschoben wird. Das klingt etwas ungewöhlich, aber ich glaube, das lassen wir so.

Zum Schwierigkeitsgrad: Von der Technik stimmt es natürlich, was sie sagen. Aber die Wahl der Bewegungen wird schon stark eingeschränkt, weil es öfters Fließbänder gibt, die über den Spielfeldrand zeigen. Im Beispielfeld chop.dat sind es schon fünf Felder, auf denen man nicht stehen bleiben sollte in der höchsten Stufe, weil man sonst vom Rand geschoben wird. Und es heißt ja nicht, dass dieses "Problem" nicht noch auf die restlichen 41 Randfelder erweiterbar wäre. ^^ Das heißt, bei der höchsten Schwierigkeitsstufe ist man - abhängig vom Spielbrett - stark in der Bewegung auf den äußeren Felder eingeschränkt.

Dominik Wagenführ
freiesMagazin-Redaktion

Förder-Öl-Förder-Dreh-Bug

Kann davon ausgegangen werden, dass der "Bug", dass sich der Roboter um 90° dreht,
wenn er von einem Förderband über Öl wieder auf ein anderes Förderband kommt,
auch in der finalen Bewertung der KIs existieren wird?
Für die Berechnung der Zugfolge kann das ja durchaus entscheidend sein.

Re: Förder-Öl-Förder-Dreh-Bug

Ja, diese kleine Besonderheit ("It's not a bug, it's a feature.") wird auch zum Wettbewerb noch im Programm sein. Eine Änderung würde all die Teilnehmer durcheinanderbringen, die ggf. den alten Code noch nutzen.

Dominik Wagenführ
freiesMagazin-Redaktion

Ich werd's auf jeden Fall probieren

Coole Idee mit dem Wettbewerb. Hab das Spiel früher schon gespielt. Will auf jeden Fall probieren, ein Programm dafür zu schreiben. Ob ich das dann auch einschicke weiß ich allerdings nicht.

Karten anzeigen

Hi, ich habe gerade die Demo laufen lassen. Echt gut geworden. Aber einen kleinen Verbesserungsvorschlag hätte ich noch. Es wäre hilfreich, wenn die 5 ausgewählten Karten eingeblendet werden und die aktuelle hervorgehoben wird.

Gruß
burli

Re: Karten anzeigen

Wenn die GUI gemeint ist: Diese weiß nicht, welche Karten ausgewählt wurden, da die GUI nur die Sequenz aus der Spiele-Engine erhält und verarbeitet. Dies ist mit Absicht so, damit man nicht von bestimmten Auswahlmechanismen abhängig ist.

Die Spiele-Engine selbst wiederum gibt die Karten aber aus. Da es aber ein Konsolenprogramm ist, sieht man das auch nur im Terminal. In kurz: Starten Sie die GUI im Terminal, dann sehen sie auch immer das ausgewählte Deck (Deck:) und die Bewegungsfolge, die die Engine draus macht (Sequence:).

Dominik Wagenführ
freiesMagazin-Redaktion

Logisch starte ich sowas aus

Logisch starte ich sowas aus der Konsole ;) und ich habe auch die Ausgabe gesehen. Es ist allerdings schwierig, gleichzeitig Konsole und GUI zu beobachten und zu interpretieren, was da gerade läuft (vor allem im Vollbild). Zumindest der aktuelle Schritt sollte der GUI bekannt sein und könnte angezeigt werden (nur ein Vorschlag)

Re: Logisch starte ich sowas aus

Da ich die GUI nicht programmiert habe, kann ich dazu keine endgültige Aussage treffen. Ich werde die Engine aber so anpassen, dass zumindest theoretisch die Möglichkeit besteht, eine Karte einer bestimmten Sequenz zuzuordnen. Ob das dann auch in der GUI landet, weiß ich nicht.

Dominik Wagenführ
freiesMagazin-Redaktion

Ich habe der GUI nun eine

Ich habe der GUI nun eine Übersicht über die aktuellen Karten spendiert.
Viel Vergnügen!

Noch 'n paar Fragen

Nette Sache. Könnte gut sein, dass ich da mitmache. Aber ein paar Fragen:

- Wie groß werden die Spielfelder so sein? Signifikant größer als die chop.dat?
- Wenn schon nur 6 Sekunden pro Spiel zur Verfügung stehen, gibt's dann eventuell ein wenig Vorlaufzeit für jedes neue Spielfeld? Naja, vielleicht gehts auch so, wenn sie nicht zu groß sind ;)
- Ist es erlaubt, dass der Bot während des Spiel Dateien schreibt, um sich bisschen was zu merken? Ich finde es etwas seltsam, dass der Bot für jeden einzelnen Zug neu gestartet werden soll.

Alsdann!

Re: Noch 'n paar Fragen

1. Die Wettbewerbsspielfelder werden wohl alle eine Größe von 12x12 Felder haben.

2. Also 6 Sekunden war schon sehr großzügig - natürlich auf meinem Rechner. Wer seine KI auf einem 486er schreibt, wird wohl auch mit 20 Sekunden am Wettbewerb teilnehmen können. ;)

3. An Dateien darf man abspeichern, was man möchte, natürlich. :) Dadurch, dass KI, Engine und ggf. GUI nicht alle gleichzeitig arbeiten können, musste ein Weg gefunden werden, der eine Interaktion erlaubt. Die Schnittstelle über Dateien war da am praktischsten, da so gut wie jede Sprache auf Textdateien zugreifen kann. (Sollte es hier eine andere Lösung geben, die keine Programmiersprache benachteiligt, bin ich an einer Lösung interessiert, da das Dateihandling einen großen Teil der 6 Sekunden ausmacht.)

Dominik Wagenführ
freiesMagazin-Redaktion

Kommunikation

Man könnte doch einfach über stdin/stdout kommunizieren. Damit kommt jede Programmiersprache zurecht. (Es eröffnet sogar die Möglichkeit, das ganze in Brainf*ck zu schreiben ...)
Man würde dann die KI starten, als erstes einmal das Spielfeld auf die Standardeingabe schreiben, dann eine Trennsequenz (bspw. ---- oder eine leere Zeile), anschließend könnte man immer die acht Karten, die Trennsequenz, dann Position und Ausrichtung schreiben, und anschließend die fünf gespielten Karten von der Standardausgabe des Programms lesen. Dann die neuen Karten und die neue Position, u. s. w.
Dadurch kann der KI-Prozess durchgängig laufen und das Spielfeld (welches sich ja -- zumindest bisher -- nicht verändert) muss nicht immer neu eingelesen werden.

Liebe Grüße,
Christoph

Re: Kommunikation

Das Prinzip ist mir klar, ich verstehe nur noch nicht, wie die Spiele-Engine den KI-Prozess durchgängig am Laufen halten kann. Sprich, wie ruft die Engine eine KI auf? Ein Minimalbeispiel könnte da sicher beim Verständnis helfen. Also einfach ein Programm X, welches ein Programm/Skript Y einmalig aufruft und mit diesem kommunizieren kann.

Dominik Wagenführ
freiesMagazin-Redaktion

Also die Schnittstelle über

Also die Schnittstelle über die Dateien würde ich auch beibehalten. Einfach und übersichtlich.
Um trotzdem nicht für jeden Zug die KI neu laden zu müssen (wäre für meine Lieblingssprache Java wohl nicht so toll...) würde ich so vorgehen:
1. Die Engine startet die KI wie gehabt mit dem entsprechenden Spielfeld. Die KI wartet auf die acht möglichen Züge.
2. Die Engine schreibt die möglichen Züge nach cards.txt und die Position nach bot.txt. Die Engine startet ihr Timeout (6s).
3. Die KI wählt fünf Züge aus und schreibt sie nach ccards.txt (benutzt dazu natürlich/hoffentlich bot.txt) und wartet auf die nächsten Züge / die nächste Position.
4. Die Engine liesst ccards.txt falls das timeout nicht überschritten ist, aktualisiert das UI und weiter bei 2.
D.h. die Engine muss die KI nicht am laufen halten. Die KI läuft einfach durch und wartet auf Eingaben von der Engine bzw. der Datei Schnittstelle. Man könnte die Vereinbarung treffen, dass sich die KI durch eine Leerzeile in bot.txt (z.B.) beenden läßt.
Hier ein Java Beispiel Sender/Empfänger über eine Datei:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class Sender {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = null;
        PrintWriter writer = null;
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            writer = new PrintWriter(new BufferedWriter(new FileWriter(args[0])));
            String line;
            while (null != (line = reader.readLine())) {
                writer.println(line);
                writer.flush();
                if (0 == line.length())
                    break;
            }
        } finally {
            try {
                reader.close();
            } catch (Exception e) {}
            try {
                writer.close();
            } catch (Exception e) {}
        }
    }
}
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.PrintWriter;
public class Receiver {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = null;
        PrintWriter writer = null;
        try {
            reader = new BufferedReader(new FileReader(args[0]));
            writer = new PrintWriter(System.out);
            String line;
            while (true) {
                line = reader.readLine();
                if (null == line) {
                    Thread.sleep(100);
                } else {
                    if (0 == line.length())
                        break;
                    writer.println(line);
                    writer.flush();
                }
            }
        } finally {
            try {
                reader.close();
            } catch (Exception e) {}
            try {
                writer.close();
            } catch (Exception e) {}
        }
    }
}

Der Sender ließt aus stdout, schreibt in eine Datei (Parameter beim Aufruf). Der Empfänger ließt aus dieser Datei (Parameter beim Aufruf) und schreibt nach stdout. Alles zeilenweise, Leerzeile beendet Sender/Empfänger.

Änderung der Redaktion: Code besser formatiert.

In Python funktioniert bspw.

In Python funktioniert bspw. folgende KI/Engine-Kombination:
Die KI liest Zahlen bis in einer Zeile ---- steht, was der KI anzeigt, das keine Zahlen mehr kommen. Dann rechnet die KI die Summe der eingelesenen Zahlen aus und gibt diese aus. Dann liest die KI wieder eine Zeile, falls diese END lautet, weiß die KI, dass das Spiel zu Ende ist, falls dort NEXT steht, weiß sie, dass es weitergeht.

Die Engine startet die KI und generiert fünf Runden lang eine zufällige Anzahl von Zufallszahlen, schreibt diese auf STDIN der KI, schreibt dann ---- um der KI zu signalisieren, dass nichts mehr kommt und wartet auf Antwort. Dann überprüft die KI die Antwort und erhöht einen Punktezähler, falls diese richtig ist. Falls noch Runden gespielt werden müssen, wird dann NEXT, gefolgt von den nächsten Zahlen an die KI geschickt, usw.

Die KI wird also einmal gestartet und läuft durchgehend, trotzdem entsteht ein »Dialog«: Die Engine fragt, die KI antwortet, die Engine fragt, die KI antwortet, usw.

Die Kommunikation über STDIN/STDOUT würde natürlich erfordern, dass die Engine entsprechend umprogrammiert wird und dass ein eindeutiges Protokoll für den Dialog festgelegt wird. Ist also erst mal ein nicht zu unterschätzender Mehraufwand. Aber das müsst letztendlich ja ihr entscheiden ;-)
Für die KI-Programmierung ist es kein Mehraufwand, man liest halt von STDIN und schreibt nach STDOUT anstatt aus/in Dateien.

Wie die entsprechenden Funktionen unter C++ heißen, weiß ich nicht, selbst die Python-Lösung ist stark zusammengefrickelt und kann wahrscheinlich noch einiges eleganter geschrieben werden. Aber das ganze ist ja eh nur ein Proof-of-Concept.

Liebe Grüße,
Christoph

(Leider werden, trotz code-Tags, die führenden Leerzeichen entfernt. (Zumindest in der Vorschau.) Ich habe daher die Einrückungen durch ersetzt. In vim kann man dies mit :%s/ /____/g (____ = vier Leerzeichen) wieder rückgängig machen.)

#### engine.py ####

#!/usr/bin/python

from subprocess import *
import random

ki = Popen(['python', '-u', 'ki.py'], stdin=PIPE, stdout=PIPE)
rounds = 5
score = 0

while (rounds > 0):
    random_numbers = [random.randint(0, 20) for x in range(random.randint(3, 6))]
    print 'Numbers:'
    for nr in random_numbers:
        print nr
        ki.stdin.write(str(nr) + '\n')
    ki.stdin.write('----\n')
    answer = ki.stdout.readline()
    print 'Answer:\n' + answer.strip()
    if (int(answer) == sum(random_numbers)):
        score += 1
    rounds -= 1
    if rounds > 0:
        ki.stdin.write('NEXT\n')

ki.stdin.write('END\n')
print 'Score: ' + str(score)

#### ki.py ####

#!/usr/bin/python

import time

def read_numbers():
    read_nrs = True
    numbers = []
    while (read_nrs):
        input = raw_input().strip()
        if (input == '----'):
            read_nrs = False
        else:
            numbers.append(int(input))
    return numbers

ende = False

while (not ende):
    numbers = read_numbers()
    time.sleep(2)
    print str(sum(numbers))
    if (raw_input().strip() == 'END'):
        ende = True

Ein mögliches »Spiel«:

$ python engine.py                        [1]
Numbers:
17
0
19
4
Answer:
40
Numbers:
9
8
19
18
8
Answer:
62
Numbers:
9
19
12
Answer:
40
Numbers:
2
6
16
15
3
Answer:
42
Numbers:
0
3
13
17
20
Answer:
53
Score: 5

Änderung der Redaktion: Code besser formatiert.

Re: In Python funktioniert bspw.

Vielen Dank für die beiden Lösungen. Für den nächsten Wettbewerb (wann und was immer das auch sein wird) werden wir vielleicht auf diese Möglichkeit zurückgreifen. Bis dahin muss ich nur herauskriegen, wie das unter C++ zu realisieren ist bzw. muss die Engine in einer anderen Sprache geschrieben werden.

Ein "Nachteil" hat das Ganze nur: KI-Programmierer, die mitmachen wollen, müssen auch wissen, wie sie den Sender schreiben können. Für mich wäre das wohl ein kleines Hindernis, um nicht am Wettbewerb teilnehmen zu können.

Dominik Wagenführ
freiesMagazin-Redaktion

PS: Ich habe die Listings in den beiden Postings besser formatiert. Wieso das code-Tag die Leerzeichen entfernt, ist mir noch unklar.

Redundante Zeichen

Hallo,

mir ist gerade eine Kleinigkeit aufgefallen. Es gibt das Leerzeichen für ein leeres Feld und es gibt das Zeichen "a" für ein Feld ohne Wände.
Stellen diese zwei Zeichen das gleiche dar, oder gibt es irgend einen Unterschied zwischen diesen Feldern?

Andy

Re: Redundante Zeichen

Ja, die Felder sind identisch. Der Grund ist einfach, dass die erste (linke) Wand nicht bei "b" anfangen sollte. Wenn also ein "a" gelesen wird, ist das wie ein leeres Feld.

Dominik Wagenführ
freiesMagazin-Redaktion

Förderbänder

Bei mehreren Förderbänder nebeneinander z.B.
Z

^
^
^

S

Wenn der Roboter das unterste Förderabend betritt, wird er dann ganz nach oben geschoben? Je nach dem wie ich die einzelnen Förderbänder nacheinander bearbeite, wandert er nach oben oder eben nicht. Muss ich nun Reihen von Förderbänder in der richtigen Reihenfolge bearbeiten oder nicht?

Re: Förderbänder

Das kommt im Text wahrscheinlich wirklich nicht so gut heraus. Die Antwort ist nein. Der Roboter wird pro Phase (also nach dem Ausspielen einer einzelnen Karte) nur immer ein Feld auf dem Förderband geschoben und nicht bis ans Ende. Das hat vor allem den Grund, dass es ja auch Förderbänder geben kann, die im Kreis fahren. Der Roboter würde so nie mehr stillstehen blieben.

Dominik Wagenführ
freiesMagazin-Redaktion

cards.txt

Hallo,

diesen Wettbewerb find ich cool. Habe mir sogar schon die Quelldateien heruntergeladen und dazu gleich mal eine Frage. In der Datei cards.txt scheinen nicht nur die 8 Karten zu stehen, aus denen man auswählen kann, sondern der ganze restliche Stapel.
Darf die KI diese Information benutzen?

Gruß, Tom

Re: cards.txt

Genau genommen ist es sogar die Aufgabe der KI die Datei cards.txt einzulesen. Der Nachteil (für Sie): Wenn die KI dran ist, stehen in der Datei nicht mehr alle Karten des Stapels, sondern nur die 8, die zur Auswahl stehen. Sie haben daher keine Möglichkeit alle Karten komplett einzulesen - zumindest sollten Sie, wenn die Engine keine Lücke hat. ;)

Dominik Wagenführ
freiesMagazin-Redaktion

GUI Probleme

Hallo

bin ich der Einzige der Probleme mit der GUI hat? Kann sie nicht starten


[frank@Naxos freiesMagazin-2009-10-wettbewerb]$ ./robots-gui-helper
gtk_gui/main.rb:33: invalid multibyte char (US-ASCII)
gtk_gui/main.rb:33: invalid multibyte char (US-ASCII)
gtk_gui/main.rb:33: syntax error, unexpected $end, expecting ')'
super("Öffne Datei",
^
[frank@Naxos freiesMagazin-2009-10-wettbewerb]$

Nutze ArchLinux, die ruby-gnome2 und gosu pakete sind installiert.

Vielen Dank für Tips

Sie sind der bis jetzt

Sie sind der bis jetzt einzige, der nur Ruby 1.9 und nicht 1.8 installiert hat. Für die Verwendung von der GUI muss aber eine Version von Ruby 1.8 installiert sein, mindestens Ruby 1.8.6.

Mit freundlichen Grüßen,
Dominik Honnef

klappt

Nach manuellem Downgrade auf ruby 1.8 funktioniert die GUI.

Vielen Dank

Toller Wettbewerb!

Ich finde die Idee von diesem Wettbewerb richtig gut. Ich werde auf jeden Fall versuchen mit an dem Wettbewerb teilzunehmen.

Außerdem hätte ich noch eine Idee, um die Zeit für das Schreiben der Dateien zu minimieren: Man könnte das Verzeichnis einfach als tmpfs mounten und den Wettkampf dann in diesem austragen. Ich habe das getestet und es ist wirklich etwas schneller gewesen.

Würde ziemlich einfach mit folgendem Befehl funktionieren.
# mount -t tmpfs -o size=50M tmpfs ./Verzeichnis
Jetzt nur noch die ganzen Dateien hineinkopieren.

Re: Toller Wettbewerb!

Hey, das ist ne super Idee. Ich werde versuchen das so machen, da wird meine Festplatte auch etwas geschont. ;)

Und wir freuen uns auf Ihre Teilnahme.

Dominik Wagenführ
freiesMagazin-Redaktion

Bewegung über Ölfelder

Wenn man direkt vor einer langen Reihe von Ölfeldern steht und, sagen wir einmal, drei Felder nach vorn geht, landet man trotzdem auf dem ersten Feld nach dem Öl oder geht man dann noch zwei Schritte weiter?

Re: Bewegung über Ölfelder

Man macht einen Schritt, rutscht bis auf das erste Feld nach der Ölspur und geht dann noch zwei Schritte weiter.

Dominik Wagenführ
freiesMagazin-Redaktion

Wand am Spielfeldrand

Moin,

ich habe zwei Dinge anzumerken:

  1. Sehr schöne Idee, dieses tolle (und hierzulande leider vergriffene) Spiel zu einem Programmierwettbewerb zu nutzen.
  2. Mir ist aufgefallen, dass Wände am Spielfeldrand von der Engine offenbar nicht berücksichtigt werden. Im Modus
    hard ist es wichtig zu wissen, ob sich der Roboter am Rand des Abgrunds auf das Geländer verlassen
    kann oder nicht. Provozieren lässt sich so ein Absturz z.B. mit folgender Karte:

    3 12
    pipppppppppp
    cVfefefefefZ
    ciijijijijif

    Da Ihr die Engine während des laufenden Wettbewerbs vermutlich nicht noch ändern wollt, wäre
    wohl ein Hinweis in der Beschreibung des Spiels (oder in der FAQ) die beste Lösung.

Re: Wand am Spielfeldrand

zu 2. Da das ein schwerwiegender Bug ist (es hat die Abfrage gefehlt, ob eine Wand zwischen Abgrund und Spielbrett ist), wird das noch heute im Laufe des Tages geändert. Vielen Dank für den Hinweis!

Dominik Wagenführ
freiesMagazin-Redaktion

Rückwärts fahren

Ich nehme doch an wenn ich rückwärts auf ein Förderband fahre, daß beim Beispielfeld
(X=Robot schaut nach oben und fährt dann ein Feld rückwärts), der Roboter danach nach links schaut oder ?

X^
>^

Viele Grüße

Re: Rückwärts fahren

Wenn Sie ein

2 2
U^
>^

draus machen und dazu einen Kartenstapel, wo einfach nur 8 mal MB drin steht, dann können Sie das auch einfach leicht mit der Referenz-KI testen.

Die kurze Antwort: Ja, der Roboter schaut danach nach links.

Dominik Wagenführ
freiesMagazin-Redaktion

In Presse geschoben werden?

Hallo!

In der Beschreibung steht, dass Schieber und Presse gleichzeitig aktiviert werden.
Wenn der Roboter nun von einem Schieber in eine Presse geschoben wird, was passiert dann?
a) er wird zerstört, weil die Presse einen Tick später presst.
b) er wird nicht zerstört, weil die Presse schon wieder offen ist.
c) er kann das Feld nicht betreten, weil die geschlossene Presse wie eine Wand wirkt (eher unwahrscheinlich)

Gruß
Björn

Re: In Presse geschoben werden?

Ich wähle Antwort B. "Ob ihr wirklich richtig steht, sehr ihr, wenn das Licht angeht ..." ;)

Realistisch wäre natürlich Antwort C, aber das würde einen unnötigen Programmieraufwand erfordern.

Da sich Presse und Schieber gleichzeitig bewegen, kann man also nie direkt von einem Schieber in eine Presse geschoben werden.

Dominik Wagenführ
freiesMagazin-Redaktion

Startzeiten der KI

Hallo,

Ich habe mal getestet, wielange es dauert, die KI aufzurufen, die dazu nur das Spielfeld und die 8 Karten einliest und dann sofort Schluß macht.
Dazu habe ich diese sh Datei im Verzeichnis KIs gepinselt
:Test.sh

#!/bin/bash
for (( I=0; $I <= 999; I++ ))
do
#Meine Kui anschmeissen
 ./MeineKI
done
exit 0

Und diese im Terminal nit "time sh Test.sh" aufgerufen

# time sh Test.sh

real    0m1.979s
user    0m0.584s
sys     0m1.176s
#

Also kann das Programm etwa 500 mal in der Sekunde aufgerufen werden.
Vielleicht können andere Teilnehmer damit auch mal kurz testen, ob der Aufruf der eigenen KI wirklich elend lange braucht.
Vielleicht ist das ein Anhaltspunkt für die Startzeiten:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=hello&lang=all

 
Sprache              Sekunden um Hello world auszugeben
C GNU gcc #3         0.0012	
Pascal Free Pascal   0.0014 //uups habe ich benutzt
Python               0.0329	
BASIC FreeBASIC      0.0040	
Perl                 0.0067
Ruby                 0.0107	
Python               0.0329	
Java 6 -client       0.0846
Java 1.4-server      0.1787

Wenn man in jedem Zug im Schnitt dem Ziel um einen Schritt näher kommt, müßte es in 24 Zügen machbar sein ( spekuliere ich mal , es ist kein Labyrinth )
Bei 6 Sekunden sind das 0.25 Sekunden pro Zugauswahl.
Das ist mit Java 1.4 Server fast nicht zu machen, da die Auswertung auch ihre Zeit braucht.
Brute Force werde ich wohl sein lassen ;-)

12.10.2009, 06:29 Uhr: Code-Tags korrigiert, Dominik Wagenführ

Re: Startzeiten der KI

Die Idee ist ja nicht schlecht, man muss dann aber darauf aufpassen, dass die KI keinerlei Fehlermeldung ausgibt. Des Weiteren sollte man von der echo-Ausgabe nicht zwingend auf die Berechnungszeit der KI schließen. Es ist zwar ein Indiz, aber kein Beweis. Darüber hinaus zählt time bei Ihnen auch die Bash-Schleife mit und nicht nur die KI-Aufrufe. Sie müssten das time vor den KI-Aufruf hängen und nur dieses zählen. (Ich habe nicht getestet, ob es etwas ausmacht.)

Ein bessere Test ist es daher, sich wie beschrieben 100 Kartendecks zu erstellen und einmal den Wettbewerb durchlaufen zu lassen und davon die Zeit zu messen. Erst dann hat man einen realistischen Anhaltspunkt.

Und ich versichere Ihnen, dass niemand disqualifiziert wird, wenn er 11 Minuten braucht - bei 20 Minuten sieht das dann aber schon anders aus.

Viele Grüße,

Dominik Wagenführ
freiesMagazin-Redaktion

Hallo, Wie wäre ein

Hallo,

Wie wäre ein Probelauf mit der vorhandenen Minimal KI

Ich habe mal start_contest.sh geändert:

#!/bin/bash

GAMES=$1
DECKS=`find decks -name "*.dat" | sort`
LEVEL=$2

# Umleitung der Ausgaben von time in die Datei time.txt  >> heißt anhängen
# time gibt seine Daten scheinbar ueber StdErr aus Umleitung auf StdOut 2>&1
# Aufruf mit der umleitung in die gleiche Datei
# /usr/bin/time ./start_contest gameboards/chop.dat easy|normal|hard >>time.txt

#Ersteinmal loeschen
rm time.txt

date
for GAME in $GAMES
do
    for DECK in $DECKS
    do
        echo "./robots-contest $GAME $DECK $LEVEL"
        /usr/bin/time ./robots-contest $GAME $DECK $LEVEL 2>&1 >>time.txt
    done
done# 
date

exit

Aufruf mit

/usr/bin/time ./start_contest gameboards/chop.dat easy >time.txt
ergab:
1453.27user 518.16system 35:05.55elapsed 93%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+56248228minor)pagefaults 0swaps

Die Ausgabe in time.txt ist etwas merkwürdig.
Also sind es 1971.43 Sekunden für 31913 iterations gewesen und entsprechen viele Aufrufe der KI.
Da diese KI nun wirklich nichts macht, ausser card.txt kürzen, ist das wohl eine minimale Aufruf- und Verarbeitungszeit der roboter-engine.
Das sind 61,775 ms pro Aufruf mit Verarbeitung. ( 2.3 Ghz AhtlonX2 ) die einem selbst dann fehlen.

Gruß Horst

Re: Hallo, Wie wäre ein

Ich bin nicht sicher, ob ich Ihnen folgen kann, aber 35:06 min sind bei mir 2106 Sekunden. Ich weiß nicht, wie Sie auf 1972.43 kommen. Und 31913 ist die Anzahl der Runden oder Züge? Ich hoffe Runden.

Nehmen wir also an, es ergeben sich als 62 ms pro Runde/KI-Aufruf. Haben Sie auch ausgerechnet, wie viel Zeit Sie dann noch für die KI-Berechnung übrigen haben? Es sind 538 ms, die noch verbleiben, wenn man von durschnittlich 10 Runden pro Spiel ausgeht, was schon gut bemessen ist. (Bzw. ist es noch etwas mehr, da mein Rechner etwas schneller ist als ihrer und die 10 Minuten für die 100 Spieler für meinen Rechner gelten.) Das sollte eigentlich reichen.

Dominik Wagenführ
freiesMagazin-Redaktion

Startzeit der reference-KI

Hallo,

Ich habe jetzt die reference-KI gestoppt, eine leere Schleife braucht fast keine Zeit ( 1 ms oder so ):
Alles im robot Verzeichnis
org_deck.txt:
MF 1
MF 2
MF 3
MB
RL
RR
RU
MF 1

dummy-test.sh:

#!/bin/bash
for (( I=0; $I <= 999; I++ ))
do
 #Kopiert einen vorbereiten Kartenstapel mit 8 Karten
 cp org_deck.txt cards.txt
done

exit 0

Test.sh:

#!/bin/bash
for (( I=0; $I <= 999; I++ ))
do
 cp org_deck.txt cards.txt
 #Die KI des eigenen Vertrauens
 ./KIs/robots-ki-reference hard
done

exit 0

testlauf.sh:

echo Leerschleife nur Erzeugung der Kartenstapel
time sh dummy-test.sh
echo Erzeugung der Kartenstapel und Aufruf der Referenz-KI
time sh Test.sh
exit 0

Aufruf mit

sh testlauf.sh

Hier einmal als Gag mit 31913 Aufrufen wie beim kompletten contest easy
Leerschleife nur Erzeugung der Kartenstapel

real 0m54.438s
user 0m21.069s
sys 0m31.310s
Erzeugung der Kartenstapel und Aufruf der Referenz-KI

real 3m28.759s
user 2m6.560s
sys 1m25.697s

Dann braucht nur die KI zum starten,lesen und schreiben 208,759-54,438 = 154,331 s also etwa 4,8 ms

also braucht allein die Auswertung/ neuen Kartenstapel/Roboterstellung ausgeben etwa 55 ms pro Zug.

Das kommt mir merkwürdig langsam vor.
Habe ich falsch kompilert?

Re: Startzeit der reference-KI

Nein, es kann sehr gut sein, dass die Engine so langsam ist. Dies kann zwei Gründe haben: Zum einen wird sie per Standard als DEBUG-Version erstellt, bei der jede Optimierung fehlt. Zum anderen wird sehr viel von Platte gelesen und geschrieben. Vor allem die "decks.txt" mit den 5600 Zeilen dauert einige Zeit, um gelesen und gespeichert zu werden.

Punkt 1 wird mit einer baldigen Version korrigiert, bei der dann RELEASE Standard ist. Punkt 2 wird dadurch behoben, dass der Wettbewerb nicht auf einer HD, sondern in einem tmpfs stattfinden wird, wie weiter oben zu lesen. Beides bringt bei mir einen Verbesserung von mehr als 50% (von 1137 Sekunden runter auf 514 Sekunden). Das macht dann eine Engine-Ausführungszeit von ca. 19 ms pro Runde bei mir.

Dominik Wagenführ
freiesMagazin-Redaktion

Hallo, ich habe meine KI in

Hallo,

ich habe meine KI in der 4.ten Version jetzt laufen.
Die testet stumpfsinnig alle bis maximal 370 Zugfolgemöglichkeiten( es wären 6720, wenn keine der 8 Karten doppelt wäre, was bei 7 Karten aber immer der Fall ist) auf dem Brett und nimmt die nächste zum Ziel.
Die Laufzeit innerhalb des Programmes( Zeit messen, alles einlesen, verarbeiten ausgeben, Differenzzeit messen) ist maximal 1.7 ms gewesen.
Lange Rede keinen Sinn.
Selbst mit Java/Python sollte es machbar sein, da ein Spiel mit dem primitivsten Vorgehen im Schnitt nur 4 Runden hat.
Gruß Horst

Re: Hallo, ich habe meine KI in

Wir haben bereits Einsendungen in Java und diese Erfüllen die Zeitbedingung ohne Probleme. Daher sollte das auch bei anderen KIs kein Problem sein.

Zur Rundenzahl: Das trifft auf das Beispielbrett "chop.dat" tatsächlich zu. Der Schnitt liegt bei fast exakt vier Runden. Bei anderen Spielbrettern sieht das aber etwas anders aus. ;)

Wir freuen uns jedenfalls auf Deine Einsendung.

Dominik Wagenführ
freiesMagazin-Redaktion