Entwickler-Ecke :: Thema anzeigen - A/AGS 2010/11

Kha - Mo 02.05.11 22:31
Titel: A/AGS 2010/11 - Paranuss-Auswertung

PARANUSS - PREISVERLEIHUNG 2011

Was für eine Paranuss-Verleihung dieses Jahr, kein Teilnehmer geht leer aus :D . Das dürfte dann auch erklären, warum wir nur eine Finalrunde brauchten :gruebel: ... deswegen rede ich auch nicht weiter um den heißen Brei, sondern präsentiere euch prompt die Platzierungen:

ForceUser (zip, 19.04 KB) von der organist
OmaKI (zip, 18.41 KB) von Oliver Marx
Tilsiter (zip, 15.59 KB) von Tilman

Alle drei erhalten wie versprochen...
je eine Eintrittskarte zu den Delphi-Tagen 2011 in Köln [http://www.amiando.com/delphitage.html] :party: !

Auf ihre Awards im Profil müssen sie sich noch bis zum Wochenende gedulden, also bitte nicht über die Jahreszahl in den obigen Grafiken wundern ;) . Dafür dürft ihr direkt die Final-Replays [http://kha.github.com/nusski-replayer/] und die Implementierungen im Anhang begutachten :) .

Wir gratulieren den dreien und allen anderen Preisträgern und danken allen Mitspielern für den Einsatz! :party: :beer:

Viele Grüße und bis zum nächsten Mal,
Euer Eckenteam

der organist - Mo 02.05.11 22:54

Vielen Dank, ich muss sagen, ich habe nicht damit gerechnet. An dieser Stelle danke ich auch nochmal Hidden: Lieber Daniel, ohne dich hätte ich niemals so schnell begriffen, wofür diese Units (zum Downloaden) da sind.

Dann gleich noch zwei Dinge dazu:
1. etwas Kritik: Ich glaube, es hätten mehr Menschen teilgenommen, wenn es etwas erklärt worden wäre, wie der Client funktioniert. Ob das im Sinn des Gewinnspiels ist, weiss ich nicht.

2. Ich habe ein Problem, meinen Gewinn einzulösen. Ich müsste mir zusätzlich ein Flugticket von Finnland hin und zurück buchen und dann wäre ich immer noch nicht sicher, ob meine Freundin in Finnland das sooo toll fände (Freund aufn Delphi-Tagen und lässt einen dafür allein zurück ;) ) Daher kann ich meinen Preis gleich weiter geben. Ich hoffe, das ist möglich...Falls ja, dann wird es auch nicht der Erstbeste sein, sondern jemand, der auch noch Schüler ist, sonst nicht hinfahren würde oder sonst etcppwasauchimmer...

Gruss, Lukas

An dieser Stelle noch ein Zitat, das wir an diesem Abend eindrucksvoll oberflächlich widerlegt haben:

"Man kann keinen Gewinn machen, ohne einem anderen Verlust zuzufügen." Publilius Syrus, Sententiae L6

Hidden - Mo 02.05.11 23:26

Moin,

Eigentlich von jedem, den ich mal dazu angeschrieben habe, habe ich das hier gehört.

Alle bis auf endlich viele haben geschrieben:

Ich habe leider viel zu wenig Zeit :-(

Daraus schließen wir: Vielleicht hilft es, noch mehr vorzuimplementieren, auch wenn das schon dieses Mal fast alles war. Vielleicht noch einen Thread vorschreiben, der die Berechnung dann ausführen kann. :gruebel:
Dann, ja, irgendwann dann nehmen sich vielleicht das eigentliche(algorithmische) Problem ein paar mehr vor.

Ich glaube aber ehrlichgesagt nicht, dass die sich den Quelltext überhaupt einmal länger angesehen haben: Schöner ging es kaum, und das war vielleicht kaum einem klar: GUI und Serverkommunikation waren komplett fertig. Man brauchte nur 1-2 Änderungen in den drei Source-Units zu machen und konnte eine Klasse von TUIClient ableiten, der bereits alle Methoden zur Verfügung stellte. Dann nur noch überschreiben, in zwei Edits 'Von' und 'Nach' eintragen und am Ende ein Button1.Click;. :mrgreen:

Mein Eigener Ansatz sah natürlich so aus: Wir überlegen uns Algorithmen, legen haufenhaft Datentypen an und implementieren Strukturarrays und inverese Strukturarrays, um möglichst komprimierte Zugerzeugung möglich zu machen.
Danach stellen wir fest, dass wir uns total verzettelt haben und löschen in Nacht und Nebel inverse Arrays, etc, wieder heraus, um das ganze debugbar zu bekommen :?

(Obwohl ich alles schön im GUI ausgeben lassen habe, war es mies zu debuggen)

lg (:

Edit: Anhang wieder gelöscht, ich arbeite noch ein wenig dran und fände es irritierend wenn jetzt viele mit meinem Nick auf dem Server sein würden :P

Martok - Mo 02.05.11 23:38

der organist hat folgendes geschrieben :

Dann gleich noch zwei Dinge dazu:
1. etwas Kritik: Ich glaube, es hätten mehr Menschen teilgenommen, wenn es etwas erklärt worden wäre, wie der Client funktioniert. Ob das im Sinn des Gewinnspiels ist, weiss ich nicht.

Ach, dabei hab ich mir doch so viel Mühe mit den Kommentaren gegeben...
Im Serverprotokoll wäre auch noch mal viiieeel Text gewesen. Nur dass da wohl keiner gesucht hat... :(

Und dann hätte es ja auch noch die Möglichkeit gegeben, in der dazugehörigen Sparte ganz laut "Hääää!?" zu rufen :D

Hidden hat folgendes geschrieben :

Ja, das mit den Threads hatten wir uns erst hinterher überlegt. Da wars für die Clients schon etwas eng. Jedenfalls in Delphi, .NET ha/ätte da nicht so Probleme.

Thom - Di 03.05.11 00:12

Erst einmal herzlichen Glückwunsch an die drei Gewinner - ähm... Teilnehmer!

Wenn ich mir die drei Spiele anschaue, ärgere ich mich im Nachhinein, daß ich mein Programm nicht abgeschickt habe. Denn DAS hätte meine KI auch hinbekommen... :P
Da sind ja teilweise absolut sinnfreie Spielzüge dabei! :shock:

P.S.:

OmaKI läßt sich nicht comilieren, da hier offensichtlich eine ältere Indy-Version benutzt wurde (EIdNotConnected gibt's nicht mehr oder steht in einer anderen Unit).
Tilsiter muß erst Unicode-tauglich gemacht werden.

Ich werde die Sachen morgen mal Delphi XE - fähig machen.

Marc. - Di 03.05.11 12:58

Herzlichen Glückwunsch an die drei Teilnehmer! :zustimm:

Ich hätte wirklich sehr gerne teilgenommen, wäre da nicht die "böse" Uni, die mir die Zeit raubte, um mich intensiv mit dem Thema zu beschäftigen - Bachelor sei Dank. :lol:
Einige scheinen aber etwas programmiert zu haben, haben es dann aber doch nicht abgeschickt. Da fragt man sich, weshalb? :)
Anderen erschien die Aufgabe wohl zu komplex. Informationen und Anleitungen zur KI-Programmierung gibt es sicher, wie Sand am Meer. Vielleicht wäre trotzdem zur Motivation eine offizelle (grobe) Einführung hier im Forum gar nicht verkehrt gewesen. :les: :lupe:

Beste Grüße

Hidden - Di 03.05.11 16:14

Moin,

Mein AlphaBeta ist noch nicht ganz fertig, ich lade ihn später hoch :)
user profile icon

Martoks AlphaBeta hat alle eingesandten Bots geschlagen :zwinker:

Besonders(!) bei diesem Spiel sind übrigens Hashtabellen wichtig, weil die Redundanz einfach gigantisch ist: Jeder Einzelzug mit gleichem Zielfeld führt zur selben Stellung. :shock:

Die Interpretation des Kopierens bei selbem Zielfeld als unterschiedlichen Zug ist schon etwas unhandlich für eine Tiefensuche :lol:

lg,

Horst_H - Di 03.05.11 17:19

Hallo,

Zitat:

Jeder Einzelzug mit gleichem Zielfeld führt zur selben Stellung.

Diese habe ich von vornherein nicht in der Zugliste aufgenommen.
Zu Beginn der Zuglistenerstellung der Einzelzügen bekommt eine boolsche 9x9 Matrix den Wert für "nicht belegt", diese wird dann mit den möglichen Zügen aktualisiert.

Ich dachte, es wäre wichtig, wenn bei eigenem Zug Feld A zuerst und im folgendem eigenem Zug Feld B belegt wird und dies nun in umgekehreter Reihenfolge passiert, ohne dass der zwischenzeitliche Zug des Gegeners etwas an der Stellung/Anzahl der eigenen Steine ändert, dann wäre B->A schon in der Untersuchung zu A->B schon komplett enthalten. Entsprechend C>A>B in A->B->C ....
Wie wird der Hashwert bestimmt?

Gruß Horst

Hidden - Di 03.05.11 17:53

Horst_H hat folgendes geschrieben :

Wie wird der Hashwert bestimmt?

Wer meine ersten Versuche zu einer Schach-KI verfolgt hat, der kennt schon diese Links:
http://www.bauer-schweitzer.de/index.html?minimax/index_minimax.html
http://www.scleinzell.schachvereine.de/p_basiswissen/hash.shtml

Grundsätzlich besteht der Stellungsbaum solcher Spiele aus zwei Aktionen: Einen Stein zu platzieren oder einen wegzunehmen. (Das Platzieren beinhaltet dabei noch kein Konvertieren.)

Zug A -> B in diesem speziellen Spiel:

1:
2:
3:
4:
5:
6:

Platziere(B);
if Doppelzug(A,B) then Entferne(A);
for U in Grenzsteine(B) do begin
  if Farbe(U) <> Farbe(B) then
    U := B;  //Konvertieren
end;

Für unseren Hash seien nun zu jedem Feld des Spielbretts zwei Zufallszahlen gegeben, eine pro Spieler, darunter keine Kollisionen. Der Startstellung wird auch eine Zufallszahl zugeordnet.
Wenn wir jetzt in Platziere und in Entferne jeweils den aktuellen Stellungshash mit der Zufallszahl[Feld, Steinfarbe] verknüpfen, erhalten wir für verschiedene Stellungen wahrscheinlich verschiedene Hashs.

Wenn die Verknüpfung kommutativ ist(z.B. '+', '*', ..) und selbstinvers [http://de.wikipedia.org/wiki/Involution_%28Mathematik%29], so hat die selbe Stellung hier unabhängig von der Zugreihenfolge den selben Hash. Wir nehmen xor, der Wertebereich ist auf zufälligem Input gleichverteilt und es ist leicht zu berechnen.

Wenn es jetzt noch vorkommen kann, dass ein anderer Spieler am Zug ist aber die Stellung auf dem Brett die selbe, dann nehmen wir eine Weitere Zufallszahl dazu die wir nach jedem Wechsel des Zugrechts mit dem vorigen Hash verknüpfen.
Achtung hier: Wenn der Gegner wie bei diesem Spiel aussetzen muss, wechselt das Zugrecht entsprechend nicht.

Beim Schach muss zusätzlich noch der Figurentyp mit eingehasht werden, sonst würde z.B. das Verwandeln eines Bauern in eine Dame den Hash nicht ändern :rofl:

lg,

Flamefire - Di 03.05.11 21:39

Ich fand es auch sehr komplex für mal zwischendurch.
Hatte auch nicht mitbekommen, dass es die Zeitverlängerung nun wirklich gab. Wo stand das?
Dann hätte ich meine doch sehr effektive AlphaBeta-Suche dann zumindest in dieser Fassung noch Abgabetauglich gemacht.
Im Anhang mal mein Programm, mit dem ich die KI entwickelt habe und die KI selbst. Ist nur nicht an die Gewinnspielsoftware angebunden. Auch sind ein paar Einstellungen noch vom Testen und es gibt 2 KI-Dateien. Eine davon war mein Versuch vor die andre nach der Optimierung. Sieht man aber schon ;)

Hashtabellen habe ich übrigens nicht verwendet. Hätte man aber recht einfach noch machen können. Hab 6 Cardinals zum Speichern der Positionen genommen.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!