Autor Beitrag
der organist
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 467
Erhaltene Danke: 17

WIN 7
NQC, Basic, Delphi 2010
BeitragVerfasst: Sa 14.05.11 21:30 
Liebe Leserin, lieber Leser, liebes Leses,

heute habe ich ein Tutorial geschrieben mit dem es dir leichter fallen soll einen Bot für das, zugegeben schon vergangenen April-Gewinnspiel zu schreiben. Gib aber die Lebenshoffnung nicht auf, vielleicht schaffst du es ja dich dadurch zu kämpfen, einen eigenen Bot zu schreiben und ein eeLigist zu werden.

Die Notwendigkeit dieses Tutorials existiert und lässt sich damit anschaulich zeigen, dass z.B. nur wenige Menschen teilgenommen haben. Danke an euch, meine Heuristik war bestimmt nicht stark, aber Danke euch habe ich es trotzdem an die (Achtung - Ironie) hart-umkämpfte Spitze geschafft.

Begin of Tutorial:


Jetzt gibt es keinen Schritt mehr zurück. Ihr seid im Tutorial des Bösen angekommen. Für ein erfolgreiches Spiel müsst ihr folgendes machen (erfolgreich = Regeln befolgt, ich übernehme keine Gewinngarantie).

Zu allerallerallererst musst du in die Unit UClient deinen eigenen Namen und Passwort eintragen:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
class function TUIClient.ClientName: String;
begin
  Result:= 'dein Name';
end;

class function TUIClient.ClientSecret: String;
begin
  Result:= 'dein geheimes Passwort';
end;


Name und Passwort bekommst du, wenn du das Team, das alleingelassen daheim vor den Rechnern sitzt, mit einer Kiste Wein samt Verpackung für das nächste Gewinnspiel oder einfach mit einer PN beglückst.

Nun erstellen wir einen Bot, der zufällige Züge spielt. Dazu brauchen wir eine Klasse, die folgendes macht: Herausfinden von gültigen Zügen und Auswählen eines von denselben.

1. Eine Klasse von TUIClient ableiten, die dann als Bot arbeitet:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
unit UZufallsKI;

interface

type
  TForceUser = class(TUIClient)


2. Außerdem kannst du einige Methoden übernehmen. Hier GameStart, NextMove und AfterMove, wozu erkläre ich gleich. Übernehmen geht folgendermaßen:

- in die Deklaration des Bots die Methoden mit override schreiben:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
type
  TBot=class(TUIClient)
    procedure GameStart; override;
    procedure NextMove; override;
    procedure AfterMove(FieldFrom,FieldTo: TFieldCoord; MovingPlayer: TField); override;
  end;


- in die Implementation gehören die Methoden natürlich auch aufgelistet: Damit alles bisherige vom TUIClient ausgeführt wird fügen wir am Anfang jeder Methode ein inherited ein. Jede dieser Methoden sollte so aussehen wie z.B. Gamestart:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
procedure TBot.GameStart;
begin
  inherited;
end;


3. Die Züge sollen wirklich zufällig werden, also ein Randomize, das am Anfang vom jedem Spiel aufgerufen wird; also in der Methode GameStart:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
procedure TBot.GameStart;
begin
  inherited;
  Randomize;
end;


4. Damit der Bot immer auf dem aktuellen Stand ist, müssen wir das die gespielten Züge speichern. Netterweise wird nach jedem Zug, sei es unser oder einer vom Gegner in der Methode AfterMove mitgeteilt. Die wiederum wird, wie es ihr Name schon sagt, nach jedem Zug automatisch aufgerufen, was uns einige Arbeit erspart. Wir machen uns außerdem ein wenig Mehrarbeit indem wir nicht das Feldvariable Board benutzen (Board ist von TNetGame über TUIClient in unseren Bot immer übernommen). Wir machen uns ein Array für das Brett:

ausblenden Delphi-Quelltext
1:
TBrett = Array [1..9of Array [1..9of TField;					


Es ist fast selbsterklärend: Nachher müssen die Felder im Format eines Strings abgesendet werden, z.B.: 'd3'. 'd' ist der vierte Buchstabe, also wäre das Feld 'd3' auf unserm Brett das Feld [4,3]. Eben eine Erklärung für TField. Wer das nachschlägt findet in der Unit UProtocol folgendes:

ausblenden Delphi-Quelltext
1:
TField = (Empty, Blocked, ThisPlayer, OtherPlayer);					


Praktisch ist es eine Variable, die die Werte Empty bis OtherPlayer annehmen kann und dementsprechend über den Status eines Feldes Information gibt.
Diese Informationen müssen wir aktualisieren, in dem wir z.B. eine Feldvariable einführen FVersuchsBrett und dieses nach jedem Zug auf den neuesten Stand bringen:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
procedure TForceUser.AbgleichVersuchsBrett;
var
  k,l:Integer;
begin
  for k := 1 to 9 do
    for l := 1 to 9 do
                 FVersuchsbrett[l,k]:=Board[BreToCol(Point(l,k)),BreToRow(Point(l,k))];
end;


4.1. Was ist BreToCol und BreToRow? Nun, wir haben ja schon festgestellt, dass die Informationen als String kommen, wir sie aber in ein doppeltes Array einfügen. Deshalb brauchen wir Funktionen, die den String in Zahlen und andersherum umwandelt, Bre steht dabei für Brett, Col für TColIndex und Row für TRowIndex. Sind TColIndex und TRowIndex als ein String zusammengefasst nenne ich sie Boa für Board. Für die beiden Datentypen einfach mal in die Unit UProtocol schauen, da stehts erklärt ;).

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
function BoaToBre(ACol:TColIndex;ARow:TRowIndex):TPoint;
begin
  Result.X:=Ord(ACol)-Ord('a')+1;
  Result.Y:=ARow;
end;

function BreToRow(AFeld: TPoint):TRowIndex;
begin
  Result:=AFeld.Y;
end;

function BreToCol(AFeld: TPoint):TColIndex;
begin
  Result:=Char(AFeld.X+Ord('a')-1);
end;


Die sind auch nicht als Funktionen vom Bot implementiert sondern direkt in der Unit:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
type

  TBrett = Array [1..9of Array [1..9of TField;

function BoaToBre(ACol:TColIndex;ARow:TRowIndex):TPoint;
function BreToRow(AFeld:TPoint):TRowIndex;
function BreToCol(AFeld:TPoint):TColIndex;


Aufrufe sehen dann z.B. so aus:

meinString:=BreToCol(meinFeld.X)+BretoRow(meinFeld.Y);

Ist meinFeld (5,9) dann wird meinString zu 'e9'. Das Vorbild dafür waren natürlich IntToStr und Konsorten.

Die Methode AbgleichVersuchsBrett wird dann in Aftermove aufgerufen.

5. Als nächstes müssen wir eine Liste erstellen, die alle möglichen Züge beinhaltet aus der dann ein Zug ausgewählt wird. Dazu erstelle ich ein Record, TZug, die nichts anderes ist als eine Sammlung von zwei TPoint, einem Von und Nach. Allem was einen durchschnittlichen Zug eben so ausmacht. Dann suchen wir nach möglichen Zügen. Achtung - Pseudocode:

Zitat:
Für jedes Zielfeld:
Wenn es noch nicht besetzt oder blockiert ist
Wenn es ein Startfeld gibt (also das Startfeld von dir selbst besetzt ist)
Trag es in eine Liste ein


Als Liste machen wir ein globales Array, FMoglicheZuge und setzen die Länge des Arrays auf Null.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
SetLength(FMoglicheZuge,0);
for k := 1 to 9 do
    for l := 1 to 9 do begin
      if FVersuchsBrett[l,k]=Empty then
        if StartFeldFur(Point(l,k),ASpieler).X>0 then begin
          SetLength(FMoglicheZuge,Length(FMoglicheZuge)+1);
    FMoglicheZuge[High(FMoglicheZuge)].Von:= 
StartFeldFur(Point(l,k),ASpieler);
          FMoglicheZuge[High(FMoglicheZuge)].Nach:=Point(l,k);
        end;
    end;


5.1. Bis auf die Funktion StartFeldFur ist schon alles erklärt. Selbsterklärend, wie die meisten der Methoden, gibt diese ein Startfeld zurück, sonst das Feld (0,0). Dem aufmerksamen Leser (ob du wohl dazugehörst?) fällt hier auf: Dieses existiert nicht und zeigt, dass es einfach kein legales Startfeld gibt.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
function TForceUser.StartFeldFur(AZielFeld: TPoint;ASpieler:TField):TPoint;
begin
  if StartFeldEinzelFur(AZielfeld,ASpieler).X>0 then
    Result:=StartFeldEinzelFur(AZielFeld,ASpieler)
  else if StartFeldDoppelFur(AZielFeld,ASpieler).X>0 then
    Result:=StartfeldDoppelFur(AZielFeld,ASpieler)
  else
    Result:=Point(0,0);
end;


Diese Funktion verbindet die Funktionen um einen Einzelzug und einen Doppelzug zu suchen. Beispiel für die Einzelzug-Funktion gibt es jetzt. Anfangs habe ich ein konstantes Array of TPoint deklariert, das die Operationen bei einem Einzelzug beschreibt:

ausblenden Delphi-Quelltext
1:
2:
3:
Einzel: Array[1..8of TPoint=((X:-1;Y:-1),(X:0;Y:-1),(X:1;Y:-1),
  (X:-1;Y:0),(X:1;Y:0),(X:1;Y:1),    
  (X:0;Y:1),(X:1;Y:1));


So z.B. ist Einzel[3] gleichbedeutend mit (1,-1). Dieses beschreibt einen Zug nach oben (1) links (-1). Außerdem wird in der Einzelzug-Funktion noch zwei weitere, FeldAufBrett und PunktSumme benutzt. Ich hoffe sie sind selbsterklärend:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
function TForceUser.FeldAufBrett(AFeld: TPoint):Boolean;
begin
  Result:=False;
  if (AFeld.X>0)AND(AFeld.X<10then
    if (AFeld.Y>0)AND(AFeld.Y<10then
      Result:=True;
end;

function TForceUser.PunktSumme(AFeld1, AFeld2: TPoint):TPoint;
begin
  Result.X:=AFeld1.X+AFeld2.X;
  Result.Y:=AFeld1.Y+AFeld2.Y;
end;


Nun bist du bereit die Macht der Einzelzug-Funktion zu erleben:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
function TForceUser.StartFeldEinzelFur(AZielFeld:TPoint;ASpieler:TField):TPoint;
var k:Integer;
begin
  Result:=Point(0,0);
  for k := 1 to 8 do
    if FeldAufBrett(PunktSumme(AZielFeld,Einzel[k])) then
      if FVersuchsbrett[PunktSumme(AZielFeld,Einzel[k]).X,
                        PunktSumme(AZielFeld,Einzel[k]).Y]=ASpieler then
        Result:=PunktSumme(AZielFeld,Einzel[k]);
end;


Ihr Aufruf ist bei einem Zufalls-Bot immer mit ThisPlayer für ASpieler, da ich nur meine eigenen möglichen Züge suche.

6. Das Zwischenergebnis ist nun eine Liste von möglichen Zügen. Alles was jetzt noch passieren muss ist eine zufällige Auswahl und das „Abschicken“. Jetzt also nicht mehr schlapp machen, sonst hättet ihr wertvolle Lebenszeit umsonst (und nebenbei auch noch sehr sehr ungeschickt) vergeudet. Da hättet ihr auch eine Kuh auf einer Wiese in Bayern beobachten können. Oder Volksliederfeiersendungen auf einem Regionalsender schauen können.
Wir gehen zurück zu der „vorgegeben“ Methode NextMove. Diese wird automatisch aufgerufen, wenn ihr euren Zug machen sollt.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
procedure TForceUser.NextMove;
var LZug:TZug;
begin
  inherited;
  
  AbgleichVersuchsBrett;
  ListeMoglicheZuge(ThisPlayer);

  LZug:=FMoglicheZuge[Random(High(FMoglicheZuge))];
  FStatusWindow.edMvFrom.Text := BreToFCd(LZug.Von);
  FStatusWindow.edMvTo.Text := BreToFCd(LZug.Nach);
  FStatusWindow.Button1.Click;

end;


Alles zwischen den drei Leerzeilen ist neu in der Methode, alles nach der Zweiten bedarf noch etwas Erklärung. Zunächst weise ich der Variable LZug einen zufälligen Zug zu. In den nächsten beiden Zeilen wird dieser in die beiden Editfelder eingetragen, erst das Startfeld, dann das Zielfeld. Zuletzt wird durch einen simulierten Klick auf den Button das Ergebnis abgeschickt.

Fertig ist der Zufalls-Bot. Was machst du nun? Ein zufälliger Zug ist natürlich nicht sehr erfolgversprechend. Das ist ja wie eine Partnersuche bei der z.B. für einen 20-Jährigen nicht nur eine gleichaltrige Frau herauskommen kann, sondern auch supermegaalte Omas, verheiratete Menschen und Männer. Für die Fortpflanzung denkbar ungeeignet bzw. nachteilig.

Deshalb folgende Hinweise und Anregungen, die nach Schwierigkeit und Fortgeschrittenheit ansteigen (so ca.), aber nicht sehr weit gehen:

- Bewertet die einzelnen Züge, die ihr in das Array FMoglicheZuge eingetragen habt.
- Wählt den besten davon aus >> Das nennt man dann Heuristik.

- Stichwort Monte-Carlo-Algorithmus

-Stichwort Alpha-Beta-Suche

Viel Erfolg beim Ausprobieren. Ich hoffe ich habe dabei geholfen den Einstieg in die Units zu schaffen. Wie du wahrscheinlich schon bemerkt hast, hast du nicht viel von den Units kennengelernt. Das könnte daran liegen, dass man auch nicht viel als User braucht, sondern nur wissen muss, wo man anknüpft. Hoffentlich sehe ich dich demnächst in der eeBot-Liga wieder.

Gruss, Lukas

_________________
»Gedanken sind mächtiger als Waffen. Wir erlauben es unseren Bürgern nicht, Waffen zu führen - warum sollten wir es ihnen erlauben, selbständig zu denken?« Josef Stalin