von H.Schönfeld und B.Spellenberg KI in QUICK? ============ WICHTIG: steht für das Semikolon Normalerweise bezeichnet man Computer als strohdumme Maschinen (was sie auch sind), die nur wissen, was ihnen vorher ein Mensch beigebracht hat. Jetzt wollen wir einmal zeigen, daß es auch anders geht: Das Spiel-Programm "Surround", das wir in den nächsten Ausgaben entwickeln wollen, hat die Fähigkeit aus jeder Niederlage zu lernen. Man spricht in diesem Fall von sog. selbstlernenden Programmen. Surround - Die Spielregeln Das Spiel ist ein Variante des Wolf und Schafe - Spiels (bei dem die Schafe den Wolf einsperren müssen), das auf dem folgenden Spielfeld stattfindet: 02-05-08 / öÖ ö/ öÖ 01-03-06-09-11 Ö ö/ öÖ ö/ 04-07-10 Das Spiel beginnt mit den Schafen auf den Plätzen 1,2 und 4. Der Wolf besetzt den Platz 6 in der Mitte. Beide Spieler ziehen abwechselnd. Die Schafe beginnen. Ein Zug führt jeweils entlang einer Linie zum nächsten Platz, der unbesetzt sein muß. Dabei unterliegen die Schafe jedoch einer wichtigen Einschränkung: Sie dürfen nicht zurück! Züge wie z.B. 7 nach 4, 8 nach 6 oder 6 nach 2 sind für die Schafe also verboten. Für den Wolf gelten keine Einschränkungen. Die Schafe können bei klugem Spiel immer gewinnen. Die drei möglichen Gewinnstellungen sind 8,9,10-11 2,6,8-5 und 4,6,10-7. Der Wolf gewinnt, wenn er nach 15 Zügen von den Schafen noch nicht umzingelt ist. Das Spielkann aber auch dann schon abgebrochen werden, wenn für die Schafe keine Gewinnchancen mehr bestehen: Die Feldnummern der Schafe sind größer als die des Wolfs. In der einfachsten Version von Surround spielt der XL/XE den Wolf. Er macht zunächst reine Zufallszüge und es ist leicht ihn zu schlagen. Aus jeder Niederlage aber lernt der Computer und wird rasch ein ernstzunehmender Gegner. So lernt der Atari Als erstes sollte man sich auf einem Blatt Papier ein Spielfeld aufzeichnen, um den folgenden Erläuterungen besser folgen zu können. Nehmen wir an, nach dem ersten Pro- grammstart, ergibt sich der folgende, zufällige Spielverlauf: 1,2,4-6 2,3,4-6 2,3,4-8 2,3,6-8 2,3,6-11 2,3,8-11 2,3,8-9 2,6,8-9 2,6,8-11 2,8,10-11 2,8,10-9 6,8,10-9 6,8,10-11 8,9,10-11 Nach dem letzen Zug der Schafe ist also die Stellung 8,9,10-11 entstanden. Der Computer merkt nun, daß er keinen gültigen Zug mehr ausführen kann. Damit hat er also verloren. Um aus seinem Fehler zu lernen, muß sich der Computer nun eine Verluststellung merken. Welche? Würde man sich, wie man vielleicht vermutet, die Stellung 8,9,10-11 merken, so wäre daß sinnlos, weil ja nicht der Computer (Wolf) gezogen ist um diese Stellung zu erreichen, sondern die Schafe. Er muß sich also die Stellung vor dem letzten Zug der Schafe (6,8,10-11) merken. In diese ist ja er hineingezogen, d.h er könnte sie vermeiden. Er setzt also diese Stellung auf die Schwarze Liste. Vor jedem Zug innerhalb eines Spieles überprüft der Computer alle erlaubten Züge, ob sie auf eine Stellung führen, die in dieser schwarzen Liste vermerkt wurde. Er wählt seinen Zug dann natürlich aus den Stellungen aus, die nicht vermerkt sind. Sollten allerdings nur Züge möglich sein, die in eine Verluststellung führen, so ist die derzeitige Stellung offensichtlich auch eine Verluststellung! Also wird wieder die Stellung vor dem letzten Zug der Schafe in der Schwarzen Liste vermerkt, um sie zukünftig zu vermeiden und aus den Alternativen wird zufällig ein (schlechter) Zug ausgesucht. Auf diese Weise baut der Computer also selbständig eine immer komplettere Scwarze Liste auf, in der immer mehr Verluststellungen vermerkt sind. Die Struktur der Schwarzen Liste In der Schwarzen Liste müssen eventuell alle überhaupt möglichen Stellungen vermerkt werden können, also 11*10*9*8/2/3 = 1320 Stück. Eine naheliegende aber schlechte Möglichkeit wäre, jeweils die 4 Zahlen, die die Positionen der Schafe und des Wolfs angeben nacheinander in ein ARRAY zu schreiben. Der Vorteil ist zwar eine einfache Programmierung. Der Nachteil ist aber, daß man 1320*4 Bytes nicht in einem ARRAY verwalten kann und daß man ständig die Liste nach einer bestimmten Stellung DURCHSUCHEN müßte. Geschickter wäre es, ein sogenanntes Hashing zu verwenden. Bei diesem Verfahren weiß man genau, an welcher Stelle im Speicher es vermekt steht, ob eine bestimmte Stellung verboten ist oder nicht. Dazu braucht man zuerst eine Formel, die aus einer beliebigen der 1320 möglichen Stellungen eindeutig eine Zahl zwischen 1 und 1320 liefert. Einiges Nachdenken liefert z.B. die folgende Formel: NR = (((-2*S2+30)*S2-6*S1-34)*S2 + 54*S1+6*S3)/6+120*W wobei W die Position des Wolfs-1, S1, S2 und S3 die Positionen des Schafe sind. Dabei ist ebenfalls zunächst 1 abgezogen. Außerdem sind sie der Größe nach geordnet (S1