Übungen zur Lehrveranstaltung
"Programmierkurs Java"
WS 2000/2001
FB Informatik
D. Boles
Übungsblatt 13
Ausgabe: 24.01.2001
Aufgabe 45 (Pakete): 20 Punkte
Schauen Sie sich die Klassen des JDK (Java Developer Kit) an. Sie finden die Paketbeschreibungen in vielen Büchern oder auch online bspw. auf dem Sun-Java-Server unter http://java.sun.com/products/jdk/1.2/docs/api/index.html.
Schreiben Sie folgende Programme, indem Sie existierende Klassen des JDK nutzen:
(1) Schreiben Sie ein Programm, das berechnet, wieviele Minuten Sie aktuell alt sind (siehe Klassen java.util.Calendar und java.util.Date).
(2) Schreiben Sie ein Programm, das die Ziehung einer Lottozahl (Zahl zwischen 1 und 49) realisiert (siehe Klasse java.util.Random).
(3) Schreiben Sie ein Programm, das drei Float-Objekte einliest, sie jeweils auf einen Stack legt und anschließend in der umgekehrten Reihenfolge wieder auf den Bildschirm ausgibt (siehe Klassen java.lang.Integer und java.util.Stack).
(4) Schreiben Sie ein Programm, das fünf
String-Objekte einliest, sie in einem Vector-Objekt speichert und sie anschließend wieder auf dem Bildschirm ausgibt (siehe Klassen java.lang.String und java.util.Vector).(5) Schreiben Sie ein Programm, das einen
double-Wert vom Benutzer einliest und den sinus, cosinus und tangens sowie die Quadratwurzel auf dem Bildschirm ausgibt (siehe Klasse java.lang.Math)Aufgabe 46 (Zugriffsrechte): 20 Punkte
Gegeben sei folgende Klasse:
//Verzeichnis: zugriff
//Datei: Zugriffsrechte.java
package zugriff;
public class Zugriffsrechte {
float attribute1;
private float attribute2;
public float attribute3;
protected float getAttribute2() { return this.attribute2; }
}
und folgendes Klassen-Gerüst:
//Verzeichnis: <verzeichnis>
//Datei: <datei>.java
package <verzeichnis>;
import zugriff.Zugriffsrechte;
public class Zugriffstest extends <oberklasse> {
Zugriffsrechte obj;
public void testen() {
this.attribute1 = 3.0F;
this.attribute2 = 5.6F;
this.attribute3 = obj.getAttribute2();
obj.attribute1 = 3.0F;
obj.attribute2 = 5.6F;
obj.attribute3 = this.getAttribute2();
} }
Ersetzen Sie dabei wechselseitig
und überlegen Sie: Wo liefert der Compiler Fehlermeldungen und wieso?
Aufgabe 47 (Abstrakter Datentyp / Zugriffsrechte): 20 Punkte
In einem Programm soll ein abstrakter Datentyp
Uhrzeit verwendet werden. Dieser soll Uhrzeitwerte bis zum Sekundenbereich verwalten. Schreiben Sie eine Klasse, welche diesen ADT implementiert. Wählen Sie jeweils geeignete Zugriffsrechte für die Variablen und Methoden!Auf dem Datentypen
Uhrzeit sollen folgende Funktionen möglich sein:a) Initialisieren eines neuen
b) Initialisieren eines neuen
Uhrzeit-Objektes mit einem bereits existierenden (Copy-Konstruktor).c) Clonieren eines
Uhrzeit-Objektes (Überschreiben der geerbten Methode clone von Object)d) Überprüfung, ob zwei
Uhrzeit-Objekte identische Uhrzeiten repräsentieren (Überschreiben der geerbten Methode equals von Object).e) Abfragen der Stunde einer Uhrzeit.
f) Erzeugen eines neuen
Uhrzeit-Objektes durch Addition zweier existierender Uhrzeiten.g) Addieren einer Minute zu einer Uhrzeit.
h) Konvertieren eines
Uhrzeit-Objektes in einen String in der Form XX:XX:XX. (Überschreiben der geerbten Methode toString von Object)i) Die Konstante "zwölf Uhr mittags".
Schreiben Sie ein kleines Testprogramm für den ADT
Uhrzeit, in dem alle Methoden der Klasse mindestens einmal aufgerufen werden!.Aufgabe 48 (PAROB-Spiel): 20 Punkte
Hinweis: Programme, die am PAROB-Turnier teilnehmen sollen, müssen mit den Namen der Team-Mitglieder bis spätestens Montag, den 29.01.2001 bei mir angemeldet werden!!! Die Programme selbst müssen bis Dienstag, den 06.02.2001, um 18.00 Uhr als jar-Datei an mich (
boles@informatik.uni-oldenburg.de) geschickt werden (was jar-Dateien sind, wird noch in der Vorlesung erläutert)!!! Weitere Hinweise zum Turnier folgen nächste Woche!Im Idealfall würde ein Spielprogramm folgendermaßen vorgehen: Zu einer gegebenen Stellung sucht es alle legalen Züge ("Denktiefe 1"). Dann sucht es für alle diese Züge jeweils alle möglichen Antwortzüge ("Denktiefe 2"), dann darauf wieder alle möglichen Antwortzüge ("Denktiefe 3"), usw. Jener (erste) Zug, bei dem alle möglichen Antworten zum Gewinn führen, wird ausgeführt. Angenommen, in einer Stellung sind durchschnittlich 15 Züge möglich. Dann ist die Zahl der Antwortzüge auf diese Züge 152 = 225 Züge. Die Zahl der Züge wäre dann 15Denktiefe. Soll unser Programm eine Denktiefe von nur 6 Zügen haben, d.h. jeder Spieler zieht 3 mal, so müsste es schon 156 = 11 Millionen Züge ausprobieren und diese Bedenkzeit wächst mit jeder zusätzlichen Denktiefe um das fünfzehnfache! Dies ist nicht mehr vollständig in akzeptabler Zeit zu berechnen.
Die meisten Spielprogramme arbeiten in etwa folgendermaßen: Für eine vorgegebene Denktiefe (z.B. 4) werden alle möglichen Zugfolgen berechnet. Die danach entstandenen Stellungen werden bewertet und dieser Wert als Wert der jeweiligen Zugfolge zurückgegeben. Der Zug, der die "beste" Bewertung der Zugfolge bekommt, wird als nächster Zug ausgewählt.
Schreiben Sie eine rekursive Methode
findeBestenSpielzug, die zu einem Spieler, der am Zug ist, zu einem gegebenen Brett, und einer Denktiefe den "besten" Zug (aus der Sicht des Programms) findet und ihn (zusammen mit einer Bewertung) zurückliefert. Dieser Zug kann dann von der Methode liefereNaechstenSpielzug Ihres Programms (siehe Aufgabe 40) zurückgeliefert werden. Die Methode ist bei geschickter Programmierung wesentlich kürzer, als Sie auf den ersten Blick denken mögen! Sie arbeitet folgendermaßen:Falls die Denktiefe den Wert 0 erreicht hat, wird der Stellungsbewerter aus Aufgabe 44 aufgerufen.
Ansonsten werden für den ziehenden Spieler alle legalen Züge ermittelt. Dann werden für alle diese legalen Züge jeweils folgende Anweisungen durchgeführt:
Das Brett wird kopiert, der Zug auf der Kopie ausgeführt und das entstandene Brett bewertet. Letzteres geschieht, indem die Methode
findeBestenSpielzug sich selber rekursiv aufruft (!), dann natürlich mit dem anderen Spieler am Zug und einer um eins verringerten Denktiefe. Falls dieser Zug besser war als der bisher beste (oder es der erste war, der probiert wurde), wird der Zug und die zugehörige Bewertung gemerkt.Wenn alle Züge so durchprobiert wurden, ist der beste Zug gefunden. Dieser wird von der Methode
findeBestenSpielzug zurückgegeben.Die Bewertung, wann ein Zug besser ist als ein anderer, folgt dem sogenannten Minimax-Prinzip, das an einem Beispiel verdeutlicht werden soll (das Prinzip ist auch für andere Spiele als PAROB gültig und wird hier nur am Beispiel des Schachspiels skizziert): In der Ausgangsstellung (siehe Abb. 1) sei Spieler A am Zug. Es soll gezeigt werden, wie die fettgedruckten Stellungswerte von unten nach oben ermittelt werden. Das Prinzip ist, dass sich der Wert eines Zuges aus den Werten aller möglichen Antwortzüge ergibt, oder, falls die vorgegebene Denktiefe erreicht wurde, aus dem Wert des Stellungsbewerters.
Abb.1: Spielbaum
Spieler A habe in der fiktiven Ausgangsstellung drei legale Züge: 6D, 7A und 8B. Wenn er 6D ziehen würde, hätte Spieler B darauf zwei legale Antwortzüge: 6E oder 3C. Auf den ersten Zug davon hat Spieler A wieder zwei Zugmöglichkeiten: 6F oder 7A. Diese werden nun mit dem Stellungsbewerter bewertet (die fest vorgegebene Denktiefe ist hier 3). Der Stellungsbewerter ermittele für die nach der Zugfolge 6D-6E-6F entstandene Stellung den Wert 1 (fettgedruckte Zahl), die nach der Zugfolge 6D-6E-7A den Wert 3. Da Spieler A immer den besten Zug machen möchte und eine größere Zahl eine bessere Stellung für Spieler A verspricht, würde Spieler A, falls vorher 6D-6E gezogen würde, Zug 7A wählen, also den Zug, der die meisten Punkte ergibt. Aus der nach 6D-6E entstandenen Stellung heraus kann Spieler A nun im besten Fall einen Zug machen, der eine Stellung mit Wert 3 erlaubt. Dies ist damit auch der Wert des Zuges 6E für Spieler B in der darüber liegenden Ebene! Dort versucht Spieler B natürlich eine Stellung mit möglichst kleiner Zahl zu erreichen, d.h. er wählt den Zug, gegen den Spieler A den schlechtesten Antwortzug hat! Nun wird also zunächst der Wert für den Zug 3C ermittelt. Der beste Zug, den Spieler A nach Ausführung von 6D-3C machen kann, ergibt eine Stellung mit dem Wert 6 und ist deshalb schlechter für Spieler B. Also wählt Spieler B den Zug, dessen Antwort nur maximal 3 Punkte zulässt: 6E. Dies ist dann wiederum auch der Wert des aller ersten Zuges für Spieler A: 6D. Spieler A versucht nun wiederum, den Stellungswert zu maximieren. Die Werte für die anderen Züge mögen mit dem gleichen Verfahren 2 und 0 ergeben. Diese sind alle kleiner, also schlechter für Spieler A. Deshalb wird Spieler A letztendlich den ersten Zug, nämlich 6D als den besten Zug wählen. Dies ist das Ergebnis der
findeBestenSpielzug-Methode und wird zusammen mit dem Wert 3 zurückgeliefert. Jetzt zeigt sich, wie gut Ihr Stellungsbewerter arbeitet! Ergeben zwei Züge den gleichen Wert, so ist es egal, für welchen man sich entscheidet. Hier könnte allerdings auch ein Zufallszahlengenerator entscheiden, so dass Ihre findeBestenSpielzug-Methode auch mal andere, gleichwertige Züge findet.Machen Sie sich klar, dass jeder Teilbaum einen rekursiven Aufruf der Methode
findeBestenSpielzug mit verändertem Brett und veränderter Denktiefe darstellt und nur die Blätter einen Aufruf des Stellungsbewerters darstellen. Lassen Sie sich durch die Rekursion nicht verwirren. Wählen Sie zum Testen kleine Denktiefen (<4)! Falls die Rechenleistung es zulässt, können Sie die Denktiefe erhöhen.Verbesserung: Diese Suchmethode, die ja alle Zugmöglichkeiten beachtet, wird in der Praxis "brute-force", Methode der brutalen Gewalt, genannt. Durch die Technik "alpha-beta-pruning", die gewisse Teile des Spielbaumes auslässt, lässt sich die Geschwindigkeit drastisch erhöhen.
Tip: Verbessern Sie Ihr Programm auf die Art und Weise, dass Sie inkrementell jeweils zwei Versionen entwickeln, diese gegeneinander antreten lassen, die schlechtere verwerfen und die bessere weiter verbessern. Oder lassen Sie Ihre Programme zum Test einfach gegen die Programme Ihrer Kommilitonen antreten.
Aufgabe 49 (PAROB-Spiel / Pakete / Zugriffsrechte): 20 Punkte
Organisieren Sie Ihr PAROB-Spiel als Paket und passen Sie die Zugriffsrechte Ihrer Variablen und Methoden an. Beachten Sie folgendes:
/user/fb10/dibo/java/dibo/parob/bin/parob X.Y <gegner>
Das heißt, hier wird immer der volle Klassennamen verlangt.
Wenn Sie kein eigenes PAROB-Spiel entwickelt haben, nehmen Sie bitte die in Aufgabe 39 zur Verfügung gestellten Klassen als Grundlage!