********************************************************************** * Vier gewinnt * * * * Ein kleines Spektakulum * * von Claus Brod und Meinhard Ullrich * ********************************************************************** NEIN, NICHT SCHON WIEDER! ------------------------- Recht haben Sie. Spielchen wie unser 'Vier gewinnt' gibt es nun wirklich bei jedem B„cker und fr jeden Rechner. Warum wir so ein Paraphernalium trotzdem in die Welt setzen? 'Vier gewinnt' ist ein vom theoretischen Standpunkt her interessantes Spielchen, weil es so einfach ist. Wir haben daran ausprobiert, wie sich verschiedene Bewertungsfunktionen auf die Leistung eines Strategiespielprogrammes auswirken. Aužerdem diente es als Referenzprogramm bei einem kleinen Vier-gewinnt-Turnier, das im Wintersemester 1990/91 im Rahmen der Vorlesung 'Programmierung neuronaler Netze' an der Uni Erlangen stattfand. Dabei spielte es aužer Konkurrenz gegen einige auf neuronalen Netzen basierende Programme und gewann haushoch. Was Sie davon haben? Einerseits bilden wir uns ein, daž dieses Programm verteufelt gut spielt, obwohl es eine einfache Strategie verfolgt. Andererseits ist es voll in GEM eingebunden, wobei wir auf saubere Programmierung Wert legten. Frucht dieser Bemhungen: Unser 'Vier gewinnt' l„uft als Accessory oder Programm auf allen ST-Rechnern sowie auf dem TT, und das in allen Aufl”sungen (naja, 80 Zeichen horizontal sollten's schon sein). DAS SPIEL --------- Die Regeln von 'Vier gewinnt' sind sehr einfach. In ein matrixf”rmiges Spielfeld mit sieben Spalten und sechs Zeilen setzen zwei Spieler abwechselnd Spielsteine ihrer Farbe. Erlaubt sind dabei in jeder Spalte nur die jeweils untersten, freien Positionen. Man k”nnte sich das bildlich so vorstellen, daž jeder Spieler einen Stein seiner Farbe in eine Spalte wirft, der nach unten rutscht, bis er auf ein Hindernis trifft. Natrlich darf nur dann ein Stein in eine Spalte geworfen werden, wenn in dieser Spalte noch mindestens eine Position frei ist. Ziel des Spiels ist es, vier Steine der eigenen Farbe horizontal, vertikal oder diagonal aneinanderzureihen. Wer als erster Spieler eine solche Vierermhle besitzt, hat gewonnen. Da das Spielfeld nur 42 Felder hat, ist das Spiel nach sp„testens 21 Zgen beendet. Bei erfahrenen Spielern f„llt die Entscheidung oft sehr sp„t. H„ufig ist es so, daž beide Spieler in derselben Spalte (oder sogar auf dem- selben Feld) mit einer Vierermhle drohen und ein Spieler dem anderen durch Zugzwang den Weg ebnen muž. Ein Tip: Es ist wichtig, sich w„hrend der Er”ffnung eine gute Position in der mittleren Spalte zu verschaffen! BEDIENUNG --------- 'Vier gewinnt' ”ffnet ein GEM-Fenster mit einem Verschiebebalken und einem Schliežknopf. Wie Sie damit umgehen, wissen Sie sicher. Wenn Sie gegen den Rechner spielen wollen, starten Sie 'Vier gewinnt' durch Doppelklick oder aber durch Anklicken im Desk-Men, wenn es als Accessory l„uft. 'Vier gewinnt' versteht auch die spezielle Nachricht, die GEMINI bei einem Doppelklick auf ein installiertes Accessory verschickt. Danach stellen Sie den Schwierigkeitsgrad in der 'Limit'-Box ein. Wenn Sie selbst anfangen wollen, klicken Sie einfach in die Spalte auf dem Spielfeld, in die Sie einen Stein setzen wollen. Soll der Rechner anfangen, klicken Sie auf 'Neues Spiel'. Dabei wird das Spielfeld geleert (das ist es im Moment natrlich sowieso schon), und Sie werden gefragt, ob der Rechner beginnen soll. Im folgenden wird abwechselnd gezogen. Wenn Sie einen Stein versehentlich an die falsche Stelle gesetzt haben, k”nnen Sie Ihren Zug mit 'Hoppla' zurcknehmen. Dabei mssen Sie dann aber auch ein tadelndes Wort ertragen... Im 'Limit'-Feld haben Sie die Auswahl, ob das Programm nur bis zu einer bestimmten Halbzugtiefe rechnen oder innerhalb einer gegebenen Zeit zu einem Beschluž kommen soll. Voreingestellt sind 10 Sekunden Bedenkzeit fr das Programm, was fr eine passable Leistung ausreicht. Wenn Sie sich fr ein Halbzuglimit entscheiden, sollten Sie dem Programm mindestens vier Halbzge geben, alles andere l„uft auf eine Kastration hinaus. Bei einer Beschr„nkung auf eine bestimmte Bedenkzeit wundern Sie sich bitte nicht, wenn die eingestellte Bedenkzeit gelegentlich leicht berschritten wird. Sie genau einzuhalten, bedeutet einen erheblich gr”žeren Programmieraufwand, der sich nicht lohnt. Des ”fteren wird sie auch nicht komplett ausgenutzt, so daž sich das ausgleicht. Im 'Info'-Feld geben verschiedene Felder Auskunft ber die aktuelle Denktiefe des Programms in Halbzgen, die fr die Berechnung des n„chsten Zuges bisher verbrauchte Zeit in Millisekunden, sowie die Bewertung des Programmes fr die aktuelle Stellung aus seiner Sicht. TECHNISCHES ----------- 'Vier gewinnt' ist ein Public-Domain-Programm. Jeder darf es sich kopieren, solange auch diese Anleitung kopiert wird. Wer sich fr den Quellcode interessiert, kann ihn von uns bekommen, wenn er uns eine Diskette in einem frankierten Rckumschlag schickt und 10 DM beilegt. 'Vier gewinnt' ist relativ spielstark; wir kennen jedenfalls kein besseres Programm. Es beruht auf einem optimierten Alpha-Beta- Algorithmus, der sich wiederum auf eine extrem schlanke Bewertungsfunktion verl„žt. Wir haben dabei auf die Erfahrungen aus unserer Studienarbeit, in der wir verschiedene Mhleprogramme implementierten, zurckgegriffen. Unsere Forschung setzen wir derzeit als Diplomarbeit fort. Geschrieben ist das Programm in hohem C (ST-Version: TC 2.03). Natrlich k”nnte man die Suchroutinen auch in Assembler verfassen, aber das bringt einerseits weniger als eine weitere Verfeinerung des Algorithmus und andererseits verhindert es, daž dieses Programm einmal auf anderen Rechnern l„uft. Zur Zeit gibt es noch eine Version fr den Amiga, allerdings ohne grafische Oberfl„che; einer Portierung auf Workstations oder PCs steht nichts im Wege. Fr Fehlverhalten unseres Programms, eventuelle Sch„den, die durch unser Programm verursacht werden, und fr destruktive psychologische Greuel, die es bei seinen Gegnern anrichtet, wenn es Spiel um Spiel gewinnt, bernehmen wir keinerlei Verantwortung. Euer Bier. Claus Brod Am Felsenkeller 2 8772 Marktheidenfeld 09391-3206 csbrod@medusa.informatik.uni-erlangen.de Meinhard Ullrich Birkenstraže 4 8771 Urspringen 09396-1508 mdullric@faui09.informatik.uni-erlangen.de