Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Programmcode schneller machen?


galagher - Fr 31.08.07 20:00
Titel: Programmcode schneller machen?
Hallo!

Kann man Programmcode schneller machen, inden man ihm (oder dem gesamten Programm) mehr "CPU-Priorität" gibt? Und Windows das Programm / die Prozedur / die Funktion dann schneller ausführt?


Silas - Fr 31.08.07 20:16

Jop, das geht, und zwar mit dem Task-Manager. Prozesse -> Rechtsklick auf dein Programm (es gibt da auch eine API-Funktion, den Namen weiß ich grad net).
Grundsätzlich ist das aber keine so gute Idee, wenn du viele Berechnungen machen musst, würd ich dir eher Assembler empfehlen.


galagher - Fr 31.08.07 20:42

user profile iconSilas hat folgendes geschrieben:
(es gibt da auch eine API-Funktion, den Namen weiß ich grad net).

Ich suche eine Funktion, die ich in mein Programm einbauen kann. Es soll dann nur unter bestimmten Umständen eine höhere Priorität haben, der User bestimmt dann, ob oder ob nicht.

Assembler - wer's kann... Nein, es ist Delphi-Code und das soll auch so bleiben!


Narses - Fr 31.08.07 20:45

Moin!

Die beste Methode, ein Programm schneller zu machen, ist einfach immer noch: effizienter Code! :P

(du kannst noch so viele Spoiler an deinen Code schrauben, wenn der nicht leistungsfähig ist, wird er auch mit mehr CPU-Zeit nicht besser...)

cu
Narses


galagher - Fr 31.08.07 21:05

user profile iconNarses hat folgendes geschrieben:
Moin!

Die beste Methode, ein Programm schneller zu machen, ist einfach immer noch: effizienter Code! :P

(du kannst noch so viele Spoiler an deinen Code schrauben, wenn der nicht leistungsfähig ist, wird er auch mit mehr CPU-Zeit nicht besser...)

cu
Narses


Na schön, ich denke, der Code ist optimal. Kann man aber nicht noch auf Systemebene, auch auf Kosten anderen laufender Programme, noch was rausholen?

Wie sieht's aus denn mit:

Delphi-Quelltext
1:
SetPriorityClass(Application.Handle, REALTIME_PRIORITY_CLASS);                    

Bringt das etwas?

Das Problem ist, der Code wird Stunden oder Tage brauchen - es ist die selbstlernende KI, die user profile iconalzaimar für mein Bauernspiel programmiert hat. Die braucht im höchsten Level mit höchster Rechentiefe pro Zug schon mal 50 Minuten oder mehr, und da will ich alles rausholen, was geht!
Und ich versuche nun, das Programm ein wenig zu verbessern.


Horst_H - Fr 31.08.07 21:30

Hallo,

was sagt denn der TAskmanager über die CPU Zeiten in %.
Wenn meine Delphi Programme viel zu rechnen haben, dann sind diese bei 98% CPU-Zeit und mehr, da ich nebenher auch nichts anderes rechnen lasse.
Was bringt denn 1% bei 50 min, gerade mal 30 Sekunden.

Das lohnt nicht den Aufwand für diesen Effekt, der andere Anwendungen auch extrem schlechter ansprechen lässt.

Gruß Horst


BenBE - Fr 31.08.07 21:44

Je nach Rechner lassen sich damit schon einige Sekunden erzielen ...

Auf meinem System hab ich eine Webanwendung (komplett mit Apache und PHP) am Laufen. Diese brauch auf Normal-Prio 48%, auf High-Prio 50% ;-) Die Arbeitszeiten sind 26s vs. 22s.

Aber wie gesagt: Wo man optimieren kann hängt hauptsächlich vom Source ab. Kannst ja gern mal deine Aufwändigsten Routinen zeigen (auch ohne ASM lässt sich noch sehr viel erreichen) (ich erinner nur an die Primzahl-Ermittlungsschlacht hier in der Sparte).


Gausi - Fr 31.08.07 21:45

user profile icongalagher hat folgendes geschrieben:
Wie sieht's aus denn mit:

Delphi-Quelltext
1:
SetPriorityClass(Application.Handle, REALTIME_PRIORITY_CLASS);                    

Bringt das etwas?
Ja, das bringt was. Dein System reagiert zum Beispiel nicht mehr vernünftig auf Nutzereingaben.

Prinzipiell sollte man nicht an den Prioritäten rumspielen. Bei einigen wenigen Anwendungen macht das Sinn, die Priorität hochzusetzen. Aber das nur deswegen zu tun, damit das eigene Programm etwas schneller fertig ist, ist definitiv der falsche Weg.

Einige Autos fahren ja auch mit Blaulicht und Martinshorn durch die Gegend, und das ist sinnvoll so. Aber wenn das jeder machen würde, um schneller zur Arbeit zu kommen, bricht das System zusammen.


galagher - Fr 31.08.07 22:04

user profile iconHorst_H hat folgendes geschrieben:
was sagt denn der TAskmanager über die CPU Zeiten in %.

Zwischen 89 und 97, so in etwa.

user profile iconHorst_H hat folgendes geschrieben:
Was bringt denn 1% bei 50 min, gerade mal 30 Sekunden.

Ist ein Argument, ja...

user profile iconBenBE hat folgendes geschrieben:
Kannst ja gern mal deine Aufwändigsten Routinen zeigen (auch ohne ASM lässt sich noch sehr viel erreichen) (ich erinner nur an die Primzahl-Ermittlungsschlacht hier in der Sparte).

Mal sehen, ich denke, dass Application.ProcessMessages das Programm schon bremst, aber ohne liesse sich das Berechnen der Züge nicht beenden, das Programm scheint zu "hängen" - das kennt sicher jeder hier. Vielleicht gibt's aber was schnelleres als ProcessMessages.

user profile iconGausi hat folgendes geschrieben:
Einige Autos fahren ja auch mit Blaulicht und Martinshorn durch die Gegend, und das ist sinnvoll so. Aber wenn das jeder machen würde, um schneller zur Arbeit zu kommen, bricht das System zusammen.

Tja, das Programm wäre dann eben nur zeitweilig, wenn es lernt, mit Blaulicht unterwegs. Aber es muss schon merklich etwas nützen, ich meine, ob es nun 5 Stunden und 40 Minuten oder 5 Sunden und 35 Minuten rechnet, ist mir letzlich egal.


Delete - Fr 31.08.07 22:09

Was hast Du für eine Grafikkarte?
Für manche gibt es Programme, um die GPU für bestimmte Funktionen zu nutzen.


Gausi - Fr 31.08.07 22:21

Na, dann hau das APM einfach raus und pack die Berechnung in einen eigenen Thread. Das dürfte wesentlich mehr bringen, als die Priorität hochzuschrauben.


GTA-Place - Fr 31.08.07 22:24

user profile icongalagher hat folgendes geschrieben:
Vielleicht gibt's aber was schnelleres als ProcessMessages.

Lager die Berechnung in einen Thread aus.

EDIT: gausi - bitte nicht so schnell :mrgreen:


Bernhard Geyer - Fr 31.08.07 23:21

Ich empfehle Tools wie AQTime (http://www.automatedqa.com/products/aqtime/index.asp).
Damit habe ich in den letzten Tagen ein Funktionalität locker mal auf das 5-10fach beschleunigt (Bisher war die Funktion nicht zeitkritisch).

Im meinem Fall hat folgendes was gebracht:

- Zusätzliche Cache-Felder die Zwischenergebnis auch über mehrer Funktionsaufrufe gespeichert hatten
- Lokale Funktion ohne Parameter statt Methoden/Funktionsaufruf mit mehreren Parametern.


In anderen Fällen waren folgende Bremsen vorhanden

- Zu häufige aktualisierung der GUI
- Verwendung von ineffizienten Strukturen (Stringlist statt BTree)
- Fehlende const-Parameter
- Abbruchkritieren wurden vergessen.


Christian S. - Sa 01.09.07 00:33

user profile iconBernhard Geyer hat folgendes geschrieben:
Ich empfehle Tools wie AQTime (http://www.automatedqa.com/products/aqtime/index.asp).
Wollte mir gerade die Trial-Version angucken und hab dann den Preis für die Vollversion gesehen. $600 :shock: Ich wollte nicht die ganze Firma kaufen ...


Bernhard Geyer - Sa 01.09.07 08:40

user profile iconChristian S. hat folgendes geschrieben:
user profile iconBernhard Geyer hat folgendes geschrieben:
Ich empfehle Tools wie AQTime (http://www.automatedqa.com/products/aqtime/index.asp).
Wollte mir gerade die Trial-Version angucken und hab dann den Preis für die Vollversion gesehen. $600 :shock: Ich wollte nicht die ganze Firma kaufen ...

Für Privatanwender ist das schon happig. Bei uns in der Firma sind die Einsparungen um Welten größer (ok, hier ist es vor allem der Kundenfrust wenn das Programm irgendwo zu langsam wäre).


galagher - Sa 01.09.07 09:59

user profile iconhathor hat folgendes geschrieben:
Was hast Du für eine Grafikkarte?
OnBoard, spielt aber keine Rolle, da das Programm die Züge, die es "lernt", nicht anzeigt.

user profile iconGausi hat folgendes geschrieben:
Na, dann hau das APM einfach raus und pack die Berechnung in einen eigenen Thread.
Muss ich mich erst einarbeiten, wüsste nicht, was ich da ändern muss!


delfiphan - Sa 01.09.07 10:27

user profile icongalagher hat folgendes geschrieben:
ich denke, der Code ist optimal.

user profile icongalagher hat folgendes geschrieben:
(...) pro Zug schon mal 50 Minuten oder mehr

Häufig kann man eine 50-Minütige Berechnung auf 5 Minuten reduzieren. Du sprichst von Rekursionen. Hört sich für mich wie Brute-Force an. Hast du schon mal ein Spiel der Konkurrenz angeschaut? Dort wartest du wohl kaum so lange. AQTime kann dir bei der Auswahl des Algorithmus leider auch nicht helfen.
Vielleicht postest du mal ein wenig Code. Ansonsten empfehle ich dir, etwas in der Literatur über Lösungsstrategien über das Spiel und ähnliche Spiele zu stöbern. Es lohnt sich nicht, sich über etwas etwas den Kopf zu zerbrechen, wenn darüber geforscht wird/wurde.


galagher - Sa 01.09.07 10:50

user profile icondelfiphan hat folgendes geschrieben:
Häufig kann man eine 50-Minütige Berechnung auf 5 Minuten reduzieren. Du sprichst von Rekursionen. Hört sich für mich wie Brute-Force an.

Naja, das Programm verändert per Random einen Koeffizienten und wenn feststeht, dass die neue Konstellation besser ist als die alte und die originale, dann werden die neuen Werte gespeichert und in Zukunft verwendet.
Ich gebe zu, dass ich bei alzaimar's Code selbst nur teilweise durchsteige, aber er ist gut und das Programm spielt sinnvoll! Das ganze spielt sich in einer repeat-until Schleife ab und wird entweder durch Benutzerabbruch oder durch das Erreichen der maximalen Anzahl an Durchgängen (=MAXINT) beendet.

http://www.delphi-forum.de/viewtopic.php?t=59658&highlight=bauernspiel

user profile icondelfiphan hat folgendes geschrieben:
Vielleicht postest du mal ein wenig Code.

Hier ist er:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
procedure TForm1.IAeverButton2Click(Sender: TObject);
Var
  c00, c0, C1, c2: tcoeffArray;
  iLevel, cnt, w1, w2, i, b: Integer;
  mod500: Boolean;

  Procedure Mutant (Var c : TCoeffArray);
  Var
    i, v : Integer;

  Begin
    i := Random(Length(c));
    v := Abs(c[i]);

    If v < 10 Then v := 100;

    c[i] := c[i] + Random(v) - Random(v);

    {Negative Zahlen bleiben sonst immer negativ}
    if (c[i] < 0and
       (Random(2) = 1then c[i] := Abs(c[i])
    else
    {Positive Zahlen bleiben sonst immer positiv}
    if (c[i] > 0and
       (Random(2) = 1then c[i] := -c[i];

    while c[i]>9999 do
      c[i] := c[i] - 1000;

    {Wenn die "Zufalls"zahl gleich dem alten Wert ist, nochmal}
    {eine "Zufalls"zahl ermitteln; hat ja sonst keinen Sinn}
    if c[i] = StrToInt(TLabel(FindComponent('L'+IntToStr(i))).Caption) then
    begin
     Mutant(c);
     exit;
    end;

    Shape1.SetBounds(TLabel(FindComponent('L'+IntToStr(i))).Left+1,
     TLabel(FindComponent('L'+IntToStr(i))).Top-2, Shape1.Width, Shape1.Height);

    Label1.Caption := 'Teste '+IntToStr(i+1)+'. Koeffinient, Wert = '+IntToStr(c[i]);
  End;

  Function xMakeMove(aPlayer, aOpponent: TPlayer; Const C: TCoeffArray):
      Boolean;
  Var
    m: TMove;

  Begin
    Coeffs := C;

    {Wenn iLevel=2, dann läuft es in noch akzeptabler}
    {Geschwindingkeit, ab 3 wird's langsam!}
    FindBestMove(iLevel, aPlayer, aOpponent, Board, M, False);
    If m.mPlayer = plEmpty Then
      Result := False
    Else Begin
      Result := True;
      MakeMove(Board, m);
    End;
  End;

  Function Wins (a,b : TPlayer) : Boolean;
  Begin
    Result := Score(Board,a,b) >= sWinScore;
  End;

  Procedure PlayGame(Const c1, c2: TCoeffArray; Var w1, w2: Integer);
  Var
    p: Integer;

  Begin
    InitBoard(board);
    p := 0;
    Repeat
      If Not xMakeMove(plHuman, plComputer, C1) Then
        inc(p)
      Else Begin
        p := 0;
        If Wins(plHuman, plComputer) Then Begin
          inc(w1);
          Exit;
        End
      End;
      If Not xMakeMove(plComputer, plHuman, C2) Then
        inc(p)
      Else Begin
        p := 0;
        If Wins(plComputer, plHuman) Then Begin
          inc(w2);
          Exit;
        End
      End;
      If p > 1 Then Exit;
    Until false;
  End;

Begin
  if IAEverButton2.Tag = 1 then
  begin
   if RealTimePriority then
    SetPriorityClass(Windows.GetCurrentProcess, NORMAL_PRIORITY_CLASS);

   SetApplicationTitle('');
   Blinker.Tag := 0;
   Blinker.Enabled := False;
   IAeverButton2.Caption := 'L&ernen per Evolution!';
   IAeverButton2.Tag := 0;
   Panel5.Show;
   Memo1.Show;
   IAeverButton1Click(Sender);

   IAEverButton1.Enabled := True;
   IAEverButton4.Enabled := True;
   IAEverButton7.Enabled := True;
   IAEverButton8.Enabled := True;
   IAEverButton9.Enabled := True;
   IAEverButton10.Enabled := True;
   IAEverButton11.Enabled := True;
   IAEverButton15.Enabled := False;
   IAeverButton16.Enabled := True;
   IAeverButton18.Enabled := True;
   ColorTrackBar1.Enabled := True;
   CheckBox1.Font.Color := clWhite;
   CheckBox1.Enabled := True;

   SpielEnde := True;

   exit;
  end;

  if RealTimePriority then
  begin
   SetPriorityClass(Windows.GetCurrentProcess, REALTIME_PRIORITY_CLASS);
   Label2.Font.Color := clRed;
  end
  else
   Label2.Font.Color := clWhite;

  if IAeverButton3.Enabled then  {Wenn ein Spiel gerade läuft}
   if AskEndCurrentGame then exit;

  {Einstellung, ob das aktuelle Level verwendet wird, s. in Unit3}
  if UseCurrentLevel then iLevel := Level
  else                    iLevel := 1;

  CheckBox1.Checked := False;
  IAeverButton1Click(Sender);

  SpielEnde := False;

  Label2.Caption := '';
  Blinker.Tag := 2;
  Blinker.Enabled := True;

  mod500 := False;

  IAEverButton1.Enabled := False;
  IAEverButton3.Enabled := False;
  IAEverButton4.Enabled := False;
  IAEverButton7.Enabled := False;
  IAEverButton8.Enabled := False;
  IAEverButton9.Enabled := False;
  IAEverButton10.Enabled := False;
  IAEverButton11.Enabled := False;
  IAEverButton12.Enabled := False;
  IAeverButton16.Enabled := False;
  IAeverButton18.Enabled := False;
  ColorTrackBar1.Enabled := False;
  CheckBox1.Font.Color := clSilver;
  CheckBox1.Enabled := False;
  Label10.Caption := '';

  IAeverButton2.Caption := 'Stop l&ernen';
  IAeverButton2.Tag := 1;
  Image1.Enabled := False;

  SetApplicationTitle('Lernen per Evolution');

  cnt := 0;
  c00 := Coeffs;
  c0 := Coeffs;

  if Zerovalues then
   for w1 := 0 to high (Coeffs) do coeffs[w1] := 0;

  {Anzeigen der aktuellen Koeffizienten}
  for b := 0 to High(Coeffs) do
   TLabel(FindComponent('L'+IntToStr(b))).Caption := IntToStr(coeffs[b]);

  Panel5.Hide;
  Memo1.Hide;

  ColorProgressBar1.Position := 0;
  ColorProgressBar2.Position := 0;

  repeat
   {Abbrechen bei Erreichen der max. möglichen Anzahl an Durchgängen oder bei Spielende}
   if (cnt >= MaxInt) or (cnt >= EvolutionCount) or SpielEnde then
   begin
    IAeverButton2Click(Sender);
    break;
   end;

    if ColorProgressBar2.Position =  ColorProgressBar2.Max then
       ColorProgressBar2.Position := ColorProgressBar2.Min;
    if ColorProgressBar1.Position =  ColorProgressBar1.Max then
       ColorProgressBar1.Position := ColorProgressBar1.Min;

    c1 := Coeffs;
    c2 := c1;
    inc (cnt);

    Label7.Caption := IntToStr(cnt)+'. Durchgang, Level '+IntToStr(iLevel);

    if cnt mod 500 = 0 then
     begin
      mod500 := True;
      c2 := c00;
      Label5.Caption := 'Vergleiche mit Original-Koeffizienten';
      Label1.Caption := '';
     end
    else
    if cnt mod 50 = 0 then
    begin
     c2 := c0;
     c0 := coeffs;
     Label5.Caption := 'Vergleiche mit alten Koeffizienten';
     Label1.Caption := '';
     end
    else
    begin
     mutant (c2);
     Label5.Caption := '';
    end;

    w1 := 0;
    w2 := 0;
    for i := 1 to 50 do
    begin
     PlayGame(c1, c2, w1, w2);
     PlayGame(c2, c1, w2, w1);
    end;

    if (w2+1)/(w1+1) > 1.3 Then
    begin  {Wenn nach dem 500. Durchgang, bei dem gegen die Original-Koeffizienten}
        {gespielt wurde, feststeht, dass die geänderten Koeffizienten besser sind,}
     if mod500 then c2 := c1;     {dann diese übernehmen. Sonst werden immer diese}
                     {anstelle der geänderten übernommen! c1 wird innerhalb dieser}
                 {repeat-until - Schleife laufend aktualisiert, es werden also die}
                 {jeweils aktuellen Koeffizienten genommen. Ansonsten, wenn dieser}
            {Block nicht erreicht wird, werden die Originale in c00 verwendet - s.}
                       {im Anweisungsblock "if cnt mod 500 = 0 then" -> c2 := c00;}
     BetterCoeffs := True;
     Label6.Caption := 'Neue verbesserte Koeffizienten';
     Label10.Caption := Format('Siege alt = %d, neu = %d', [w1,w2]);
     coeffs := c2;

     for b := 0 to High(Coeffs) do
     begin
      TLabel(FindComponent('L'+IntToStr(b))).Caption := IntToStr(coeffs[b]);
      if not (TLabel(FindComponent('L'+IntToStr(b))).Caption = IntToStr(c00[b])) then
       TLabel(FindComponent('L'+IntToStr(b))).Font.Color := clLime
      else
       if (TLabel(FindComponent('L'+IntToStr(b))).Caption = IntToStr(c00[b])) then
        TLabel(FindComponent('L'+IntToStr(b))).Font.Color := clWhite;
     end;
    end
    else
     coeffs := c1;

    mod500 := False;

    if IAeverButton2.Tag = 0 then
    begin
     IAeverButton1Click(Sender);
     exit;
    end;

    ColorProgressBar1.StepIt;
    ColorProgressBar2.StepIt;

  until IAeverButton2.Tag = 0;
end;

... und jetzt sagt bitte keiner: "Auslagern/aufteilen/..." !


GTA-Place - Sa 01.09.07 11:43

Das mit FindComponent ist ganz ganz schlecht. Speicher die Werte in einer Variable, aber bitte nicht StrToInt(FindComponent()) verwenden. Das kostet enorm Zeit.


BenBE - Sa 01.09.07 11:51

Dein Source greift zu häufig auf die VCL in einer Hauptschleife zurück.

Ferner solltest Du vermeiden, Progressbars in jedem Schleifendurchlauf neu zu setzen, da dann ein Neuzeichnen dieser erzwungen wird, was unnötig Zeit frisst.

Bau deinen Source mal so um, dass z.B. nur noch alle 1000 Durchläufe (hier fragt man am Besten auf If Count and $3FF = 0 Then ab) die Progressbars neuzeichnet. Ähnliches gilt für die anderen VCL-Zugriffe. Alles, was über die VCL geleitet wird (und sei's das Setzen einer Caption) verschwendet Zeit.

Ferner:
Warum nicht einfach anstatt:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
    {Negative Zahlen bleiben sonst immer negativ}
    if (c[i] < 0and
       (Random(2) = 1then c[i] := Abs(c[i])
    else
    {Positive Zahlen bleiben sonst immer positiv}
    if (c[i] > 0and
       (Random(2) = 1then c[i] := -c[i];

das hier???

Delphi-Quelltext
1:
2:
    //Vorzeichen drehen ...
    if (Random(2) = 1then c[i] := -c[i];

Ist schon mal eine Abfrage in jedem Durchlauf gespart.

Ferner fehlt hier die untere Grenze???

Delphi-Quelltext
1:
2:
    while c[i]>9999 do
      c[i] := c[i] - 1000;

Geht so hier:

Delphi-Quelltext
1:
2:
3:
4:
    if c[i]>9999 then
      c[i] := 9000 + c[i] mod 1000
    else if c[i]<-9999 then
      c[i] := -9000 + c[i] mod 1000;


VCL in nem zeitkritischen Abschnitt, speziell FindComponent geht mal gar nicht!!!

Delphi-Quelltext
1:
    if c[i] = StrToInt(TLabel(FindComponent('L'+IntToStr(i))).Caption) then                    

Mal abgesehen davon, dass hier jegliche Fehlerprüfung fehlt!

Das gleiche hier:

Delphi-Quelltext
1:
2:
3:
4:
    Shape1.SetBounds(TLabel(FindComponent('L'+IntToStr(i))).Left+1,
     TLabel(FindComponent('L'+IntToStr(i))).Top-2, Shape1.Width, Shape1.Height);

    Label1.Caption := 'Teste '+IntToStr(i+1)+'. Koeffinient, Wert = '+IntToStr(c[i]);

GUI-Interaktion ohne Ende ...

Das seh ich mal so auf'n ersten Blick; mal sehen, was die anderen noch finden.


GTA-Place - Sa 01.09.07 11:56


Delphi-Quelltext
1:
2:
3:
4:
    if c[i]>9999 then  
      c[i] := 9000 + c[i] mod 1000  
    else if c[i]<-9999 then  
      c[i] := -9000 + c[i] mod 1000;

@BenBe: Die while-Schleife ist schneller als Mod.

10.000 Durchgänge (c[i] = High(Integer)):
while: 0 ms
mod: 33266 ms


galagher - Sa 01.09.07 16:14

user profile iconGTA-Place hat folgendes geschrieben:
aber bitte nicht StrToInt(FindComponent()) verwenden. Das kostet enorm Zeit.
StrToInt(TLabel(FindComponent('L'+IntToStr(i))).Caption) wird am Beginn jedes neuen Spiels aufgerufen und nicht ständig! Wie viele Millisekunden könnte ich da gleich sparen? 3 oder mehr? :mrgreen: Das bringt doch nichts! Anders wäre es natürlich, wenn der Aufruf ständig hintereinander erfolgt, ok, das ist ein Punkt, den man dann verbessern könnte. Aber wenn das alle 60 Sekunden bei niedrigen Levels oder, was weiss ich, alle 5 Stunden bei hohen Levels geschieht - bringt doch nix!

user profile iconBenBE hat folgendes geschrieben:
Dein Source greift zu häufig auf die VCL in einer Hauptschleife zurück.
Ja, eben wieder nur am Beginn jedes neuen Spiels! Shape1 setzt einfach einen Rahmen um ein label mit einer Zahl, damit man sieht, welche Zahl gerade dran ist.

user profile iconBenBE hat folgendes geschrieben:
Ferner solltest Du vermeiden, Progressbars in jedem Schleifendurchlauf neu zu setzen, da dann ein Neuzeichnen dieser erzwungen wird, was unnötig Zeit frisst.
Und wieder nur am Beginn jedes neuen Spiels, nicht dauernd. Ist zwar nur eine optische Spielerei, aber man sieht dadurch, dass das Programm etwas tut.

user profile iconBenBE hat folgendes geschrieben:
Bau deinen Source mal so um, dass z.B. nur noch alle 1000 Durchläufe (hier fragt man am Besten auf If Count and $3FF = 0 Then ab) die Progressbars neuzeichnet. Ähnliches gilt für die anderen VCL-Zugriffe. Alles, was über die VCL geleitet wird (und sei's das Setzen einer Caption) verschwendet Zeit.
Und wieder: alle VCL-Zugriffe erfolgen jeweils am Anfang eines neuen Spiels. Klar, bei niedrigen Levels erfolgen die Zugriffe schneller hintereinander, 30-60 Sekunden oder so, bei hohen Levels werden die Abstände schon länger.

Positive/Negative Zahlen: Sieht besser aus, so wie du das machst, ok, danke!

user profile iconBenBE hat folgendes geschrieben:
Ferner fehlt hier die untere Grenze???

Delphi-Quelltext
1:
2:
    while c[i]>9999 do
      c[i] := c[i] - 1000;

Geht so hier:

Delphi-Quelltext
1:
2:
3:
4:
    if c[i]>9999 then
      c[i] := 9000 + c[i] mod 1000
    else if c[i]<-9999 then
      c[i] := -9000 + c[i] mod 1000;
Fehlt doch gar nicht:
Solange c[i] grösser als 9999 ist, ziehe 1000 von c[i] ab. Sobald c[i] kleiner als 9999 ist, bricht die Schleife doch ab, oder habe ich da einen Denkfehler drin? Und wenn c[i] < 9999, dann wird die Schleife gar nicht ausgeführt.

user profile iconBenBE hat folgendes geschrieben:
VCL in nem zeitkritischen Abschnitt, speziell FindComponent geht mal gar nicht!!!

Delphi-Quelltext
1:
    if c[i] = StrToInt(TLabel(FindComponent('L'+IntToStr(i))).Caption) then                    

Mal abgesehen davon, dass hier jegliche Fehlerprüfung fehlt!
Zum zeitkritischen Abschnitt: Eben nur am Beginn eines neuen Spiels. Zur Fehlerprüfung: Hat bisher immer funktoniert, muss ich mir mal ansehen! i war bisher immer 0 - 19.

user profile iconBenBE hat folgendes geschrieben:
GUI-Interaktion ohne Ende ...
... immer am Beginn eines neuen Spiels.

Mit "schneller" meinte ich soetwas wie "aus 4 Stunden mach 3" oder so.


GTA-Place - Sa 01.09.07 16:23

Da mod ja so ewig langsam ist, könnte das hier helfen:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
X := cnt;

while X > 500 do
  X := X - 500;

if X = 500 then

statt

Delphi-Quelltext
1:
if cnt mod 500 = 0 then                    


galagher - Sa 01.09.07 16:27

user profile iconGTA-Place hat folgendes geschrieben:
Da mod ja so ewig langsam ist, könnte das hier helfen:
Das passiert alle 500 Spiele! Da bringen mir ein paar ms nichts! Jedes 500. Mal wird mit den alten Werten, jedes 50. Mal mit den Originalwerten verglichen, das bedeutet, 49x bzw. 499x wird der Code nicht ausgeführt.


BenBE - Sa 01.09.07 16:43

user profile icongalagher hat folgendes geschrieben:
user profile iconBenBE hat folgendes geschrieben:
Ferner fehlt hier die untere Grenze???

Delphi-Quelltext
1:
2:
    while c[i]>9999 do
      c[i] := c[i] - 1000;

Geht so hier:

Delphi-Quelltext
1:
2:
3:
4:
    if c[i]>9999 then
      c[i] := 9000 + c[i] mod 1000
    else if c[i]<-9999 then
      c[i] := -9000 + c[i] mod 1000;
Fehlt doch gar nicht:
Solange c[i] grösser als 9999 ist, ziehe 1000 von c[i] ab. Sobald c[i] kleiner als 9999 ist, bricht die Schleife doch ab, oder habe ich da einen Denkfehler drin? Und wenn c[i] < 9999, dann wird die Schleife gar nicht ausgeführt.

Für den Fall, dass deine Variable aber am Anfang <= -10000 wird diese aber nicht in ihrem Wertebereich beschränkt. Ich wollte nur wissen, ob das beabsichtig ist (und hab für den Fall, dass dies nicht der Fall ist) eine mögliche Lösung angegeben.


galagher - Sa 01.09.07 16:57

user profile iconBenBE hat folgendes geschrieben:
Für den Fall, dass deine Variable aber am Anfang <= -10000 wird diese aber nicht in ihrem Wertebereich beschränkt.

Stimmt! Danke für den Tipp! Lieber auf Nummer sicher gehen!


alzaimar - Sa 01.09.07 17:27

Hi galagher,

da der Code von mir ist, werd ich mal meinen Senf dazugeben: Du willst ihn schneller machen, und da hilft nur eins: Du musst an das Herz des Spielealgorithmus ran: Ich habe einen Minimax/Negmax-Algorithmus verwendet. Das Bauernspiel, um das es hier vermutlich noch geht, benötigt zum starken Spiel nicht nur eine hohe Zugtiefe, sondern auch eine ausgefeilte Bewertungsfunktion. Ich hatte Dir bereits vorgeschlagen, mit Mustererkennung zu arbeiten und ggf den Horizonteffekt zu umgehen. Der Horizonteffekt tritt dann ein, wenn das Programm bei einer festen Zugtiefe die Vorausberechnung abbricht und in diesem Stadium scheinbar im Vorteil ist. Das es im darauffolgenden Zug verliert, wird übersehen (=Horizonteffekt). Wenn man Gewinnstellungen als Muster sucht, kann man diesen Effekt vermeiden.

Der Evolutionsalgorithmus, den Du hier gezeigt hast, ist ja eigentlich nicht Bestandteil des Spiels, sondern nur ein Bonmot, um zu zeigen, wie einfach man einem PC das 'Lernen' beibringen kann.

Also: Es bringt (noch) nichts, an irgendwelchen einzelnen Statements rumzubasteln: Zunächst muss das Verfahren verbessert werden. Negamax ist schon ein sehr guter Algorithmus, hier ist also nicht viel zu holen. Stelle die Bewertungsfunktion auf den Prüfstand und lasse sie hier im Forum verbessern. Diese Funktion wird pro Zug (je nach Tiefe) eben einige Millionen mal aufgerufen und hier bringt eine Optimierung am meisten.


GTA-Place - Sa 01.09.07 17:47

user profile icongalagher hat folgendes geschrieben:
user profile iconGTA-Place hat folgendes geschrieben:
Da mod ja so ewig langsam ist, könnte das hier helfen:
Das passiert alle 500 Spiele! Da bringen mir ein paar ms nichts! Jedes 500. Mal wird mit den alten Werten, jedes 50. Mal mit den Originalwerten verglichen, das bedeutet, 49x bzw. 499x wird der Code nicht ausgeführt.

Das ist doch in einer repeat-Schleife?!


alzaimar - Sa 01.09.07 18:01

Der Evolutionsalgorithmus geht so (vorgegeben ist eine Reihe von Koeffizienten K0, die die Bewertungsfunktion definiert):

Quelltext
1:
2:
3:
4:
5:
K := K0
Repeat
  K1 := ErzeugeZufälligeMutation (K)
  Lass K gegen K1 spielen (Der Gewinner ist K)
Until Weihnachten = Ostern.

Wobei die zufällige Mutation von K eben ab und an entweder K0 oder ein älteres K liefert. Auf diese Weise wird K (also die Bewertungsfunktion) immer besser werden. Natürlich darf man keine Wunder erwarten, es kommt immer noch in erster Linie auf die Funktion selbst an, und nicht auf die Koeffizienten. Sie definieren aber z.B. wie stark geschlagene Steine und bestimmte Konstellationen gewichtet werden.

So, jetzt klinke ich mich aber wieder aus und überlasse galagher das Ruder.


galagher - Sa 01.09.07 18:08

user profile iconalzaimar hat folgendes geschrieben:
da der Code von mir ist, werd ich mal meinen Senf dazugeben: Du willst ihn schneller machen, und da hilft nur eins: Du musst an das Herz des Spielealgorithmus ran:
der Code ist ja deshalb von dir, weil soetwas meine Kenntnisse übersteigt! Am Anfang habe ich mir das viel einfacher vorgestellt. Sagen wir so: Ich habe die Karosserie, die Räder und die Bedienelemente gemacht, der Motor ist von dir. Nun will ich den Motor tunen!

user profile iconalzaimar hat folgendes geschrieben:
Ich hatte Dir bereits vorgeschlagen, mit Mustererkennung zu arbeiten und ggf den Horizonteffekt zu umgehen.
Ich habe aber keinen Ansatz, was eine Mustererkennung sein könnte, nicht, weil ich nicht will, sondern weil ich es nicht kann! Deshalb habe ich auch an mehreren Stellen im Quellcode vermerkt, dass dieser von dir stammt und "alzaimar" scheint auch im Info-Fenster auf. Und deshalb konnte ich den Code, den du mir zur Verfügung gestellt hast, im Wesentlichen nur kopieren und einfügen, dann anpassen und erweitern. Ganz einfach deshalb, weil ich ihn nicht ganz verstehe. Ich steige da wirklich nicht durch!

user profile iconalzaimar hat folgendes geschrieben:
Der Evolutionsalgorithmus, den Du hier gezeigt hast, ist ja eigentlich nicht Bestandteil des Spiels, sondern nur ein Bonmot, um zu zeigen, wie einfach man einem PC das 'Lernen' beibringen kann.
Ja, aber der braucht am Längsten, weil er ja beim "Lernen" beide Spieler ist.

user profile iconalzaimar hat folgendes geschrieben:
Stelle die Bewertungsfunktion auf den Prüfstand und lasse sie hier im Forum verbessern. Diese Funktion wird pro Zug (je nach Tiefe) eben einige Millionen mal aufgerufen und hier bringt eine Optimierung am meisten.
Naja, das ist sie - nochmal: sie stammt (bis auf einige Änderungen und Erweiterungen) von user profile iconalzaimar:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
function Score(const aBoard: TBoard; aPlayer, aOpponent: TPlayer): Integer;
(******************************************************************************
 * Das ist das Herz der KI: Hier wird die Stellung bewertet.                  *
 * >0 bedeutet, gut für aPlayer, <0 bedeutet, schlecht für aPlayer            *
 *                                                                            *
 * Je besser und genauer diese Funktion die Stellung wiederspiegelt, desto    *
 * stärker spielt das Programm.                                               *
 ******************************************************************************)

  function _Score(aPlayer, aOpponent: TPlayer): Integer;
  var
    z, i, j, r, r1: Integer;
    w, b, b2, m, p, s, d, e, o, a, v, l, c, _y, y, t, no, np, ne, _f, _g, f, g: Integer;
    OpponentRow: array[0..7of Boolean;
    BlockedCols: array[0..8of Boolean;

  begin
    {Alten, bisherigen Wert sichern, vergleichen zu können (s. Unit1)}
    iOldBewertung := iBewertung;

    r := iRows[aPlayer, 7];
    for i := 0 to 7 do
      if aBoard[r, i] = aPlayer then begin
        Result := sWinScore;
        Exit;
      end;

    e := 0;  {Leeres Feld}
    p := 0;  {Anzahl der Steine}
    m := 0;  {Anzahl der Zugmöglichkeiten ohne Schlagen}
    s := 0;  {Anzahl der Zugmöglichkeiten mit Schlagen}
    d := 0;  {Anzahl der gedeckten Steine}
    w := 0;  {Abstand eines Gewinnsteins zur Grundlinie}
    o := 0;  {Nächster Zug wird Gegner bedrohen}
    a := 0;  {Nächster Zug wird eigenen Stein decken}
    v := 0;  {2 Felder vor Grundlinie bei freiem, ungefährdetem Zug}
    l := 0;  {blockierte Steine}
    c := 0;  {3 Felder links bzw. rechts sind frei, wenn dann eigener Stein folgt}
    y := 0;  {Feststellen, ob aPlayer mehr als 1 Stein in der Reihe hat}
    t := 0;  {Schlagabtausch}
    no := 0{Nachbarstein(e) ist/sind Gegner}
    np := 0{Nachbarstein(e) ist/sind eigene}
    ne := 0{Nachbarfeld(er) ist/sind leer}
    f := 0;  {Freie Reihe (nur leere Felder)}
    g := 0;  {Freie Zeile (nur leere Felder)}

    _f := 0{Hilfszähler für f}
    _g := 0{Hilfszähler für g}
    _y := 0{Hilfszähler für y}

    Fillchar(BlockedCols, Sizeof(BlockedCols), 0);
    Fillchar(OpponentRow, Sizeof(OpponentRow), 0);

    for i := 6 downto 0 do begin
      r := irows[aPlayer, i];
      r1 := irows[aPlayer, i + 1];

      for j := 0 to 7 do begin
        if aBoard[r1, j] = aOpponent then
          OpponentRow[j] := True;
        if aBoard[r, j] = aPlayer then begin
          BlockedCols[j] := True;
          {Wenn kein Gegner zwischen diesem Stein und irows [aplayer,7] ist,}
          {und zwar in den Spalten j-1, j und j+1, dann haben wir schon gewonnen}
          if not (opponentRow[j - 1or opponentRow[j] or opponentRow[j + 1])
            then
            inc(w, i);
          inc(p);

          if aBoard[r1, j] = plEmpty then inc(m);
          if aBoard[r1, j - 1] = aOpponent then inc(s);
          if aBoard[r1, j + 1] = aOpponent then inc(s);
          if aBoard[r1, j - 1] = aPlayer then inc(d);
          if aBoard[r1, j + 1] = aPlayer then inc(d);
          if aBoard[r1, j - 1] = plEmpty then inc(e);
          if aBoard[r1, j + 1] = plEmpty then inc(e);

{Bei Nicht-funktionieren Coeff[8] - Coeff[19] ändern, oder völlig entfernen}
{und das Coeff-Array von TCoeffArray = array[0..19] of Integer zu}
{TCoeffArray = array[0..7] of Integer zurückstellen - diesfalls aber auch}
{L8, L9, L10, L11, L12, L13, L14, L15, L16, L17, L18, L19 in Form1 entfernen und
{in Bauernspiel.ini den Abschnitt [Coeffs] um die letzen 11 Koeffizienten kürzen}

{oder entfernen. Die Variablen}
{o, a, v, l, c, _y, y, t, no, np, ne, _f, _g, f, g}
{in dieser Funktion sind dann ebenfalls zu entfernen!}
{------------------------------------------------------------------------------}
{Coeff[8]}
          {Nächster Zug wird Gegner bedrohen}
          if (aBoard[r1-1, j + 1] = aPlayer) or    {übernächstes Feld schräg oben}
             (aBoard[r1-1, j - 1] = aOpponent) and {übernächstes Feld schräg oben}
             (aBoard[r, j] = aPlayer) and          {aktuelles Feld}
             (aBoard[r1, j] = plEmpty) then        {Feld gerade voraus}
           inc(o);

          if (aBoard[r1-1, j + 1] = aOpponent) or  {übernächstes Feld schräg unten}
             (aBoard[r1-1, j - 1] = aPlayer) and   {übernächstes Feld schräg unten}
             (aBoard[r, j] = aOpponent) and        {aktuelles Feld}
             (aBoard[r1, j] = plEmpty) then        {Feld gerade voraus}
           inc(o);


{Coeff[9]}
         {Nächster Zug wird eigenen Stein decken bzw. Stein ist gedeckt}
          if (aBoard[r1-1, j + 1] = aPlayer) or    {übernächstes Feld schräg oben}
             (aBoard[r1-1, j - 1] = aPlayer) and   {übernächstes Feld schräg oben}
             (aBoard[r, j] = aPlayer) and          {aktuelles Feld}
             (aBoard[r1, j] = plEmpty) then        {Feld gerade voraus}
           inc(a);

          if (aBoard[r1-1, j + 1] = aOpponent) or  {übernächstes Feld schräg unten}
             (aBoard[r1-1, j - 1] = aPlayer) and   {übernächstes Feld schräg unten}
             (aBoard[r, j] = aOpponent) and        {aktuelles Feld}
             (aBoard[r1, j] = plEmpty) then        {Feld gerade voraus}
           inc(o);


{Coeff[10]}
          {2 Felder vor Grundlinie bei freiem, ungefährdetem Zug}
          if (aBoard[6, j] = plEmpty) and not
             (aBoard[6, j+1] = aOpponent) and not
             (aBoard[6, j-1] = aOpponent) and
             (aBoard[5, j] = aPlayer) then
           inc(v);

          if (aBoard[1, j] = plEmpty) and not
             (aBoard[1, j+1] = aOpponent) and not
             (aBoard[1, j-1] = aOpponent) and
             (aBoard[2, j] = aPlayer) then
           inc(v);


{Coeff[11]}
          {Blockierte Linien}
          if not (aBoard[r, j] = plEmpty) and not
                 (aBoard[r1, j] = plEmpty) then
           inc(l);


{Coeff[12]}
          {Lücken in der Stellung erkennen}

          {Die nächsten 3 Felder links sind frei, dann folgt eine eigener Stein}
          if (aBoard[r, j-4] = aPlayer) then
           if (aBoard[r, j-1] = plEmpty) and
              (aBoard[r, j-2] = plEmpty) and
              (aBoard[r, j-3] = plEmpty) then
           inc(c);

          {Die nächsten 3 Felder rechts sind frei, dann folgt eine eigener Stein}
          if (aBoard[r, j+4] = aPlayer) then
           if (aBoard[r, j+1] = plEmpty) and
              (aBoard[r, j+2] = plEmpty) and
              (aBoard[r, j+3] = plEmpty) then
           inc(c);


{Coeff[13]}
          {Feststellen, ob aPlayer mehr als 1 Stein in der Reihe hat, ...}
          for z := 0 to 7 do
          begin
           if (aBoard[z, j] = aPlayer) then
            inc(_y);

{Coeff[18]}
          {Feststellen, ob die ganze Reihe (senkrecht) frei ist, ...}
           if (aBoard[z, j] = plEmpty) then
            inc(_f);

{Coeff[19]}
           if (aBoard[r, z] = plEmpty) then
            inc(_g);
          end;

          if _y > 1 then inc(y);  {... wenn ja, Zähler y erhöhen -> Coeff[13]}

          {Wenn ganze Reihe frei, f erhöhen -> Coeff[18]}
          if _f = 6 then inc(f);

          {Wenn ganze Zeile frei, g erhöhen -> -> Coeff[19]}
          if _g = 7 then inc(g);


{Coeff[14]}
          {Schlagabtausch - etwa diese Stellung:}
{          X X X
           - O -
           O - O
}

          if (aBoard[r-2, j] = aPlayer) and
             (aBoard[r-2, j+1] = aplayer) and
//           (aBoard[r-2, j+2] = aplayer) and   {Klappt nicht (??)}

             (aBoard[r-1, j] = plEmpty) and
             (aBoard[r-1, j+1] = aOpponent) and
             (aBoard[r-1, j+2] = plEmpty) and

             {Mit weiteren if's klappt's nicht (??)}
             (aBoard[r, j-1] = aOpponent) then
              inc(t);

          {Schlagabtausch - etwa diese Stellung:}
{          O - O
           - X -
           X - X
}

          if (aBoard[r-2, j] = aOpponent) and
             (aBoard[r-2, j+1] = plEmpty) and
             (aBoard[r-2, j+2] = aOpponent) and

             (aBoard[r-1, j] = plEmpty) and
             (aBoard[r-1, j+1] = aPlayer) and
             (aBoard[r-1, j+2] = plEmpty) and

             {Mit weiteren if's klappt's nicht (??)}
             (aBoard[r, j] = aPlayer) then
              inc(t);


{Coeff[15]}
          {Nachbarstein(e) ist/sind Gegner}
          if (aBoard[r, j+1] = aOpponent) or
             (aBoard[r, j-1] = aOpponent) then
              inc(no);


{Coeff[16]}
          {Nachbarstein(e) ist/sind eigene}
          if (aBoard[r, j+1] = aPlayer) or
             (aBoard[r, j-1] = aPlayer) then
              inc(np);


{Coeff[17]}
          {Nachbarfeld(er) ist/sind leer}
          if (aBoard[r, j+1] = plEmpty) or
             (aBoard[r, j-1] = plEmpty) then
              inc(ne);

{------------------------------------------------------------------------------}
        end;
      end;
    end;
    b := 0;
    b2 := 0;
    for i := 0 to 7 do
      if not BlockedCols[i] then begin
        inc(b);
        if not BlockedCols[i + 1then
          inc(b2)
      end;
    Result := p * coeffs[0]
      + m * coeffs[1]
      + s * coeffs[2]
      + d * coeffs[3]
      + e * coeffs[4]
      + b * coeffs[5]
      + b2* coeffs[6]
      + w * coeffs[7]
      + o * coeffs[8]
      + a * coeffs[9]
      + v * coeffs[10]
      + l * coeffs[11]
      + c * coeffs[12]
      + y * coeffs[13]
      + t * coeffs[14]
      + no* coeffs[15]
      + np* coeffs[16]
      + ne* coeffs[17]
      + f * coeffs[18]
      + g * coeffs[19];
  end;

begin
  Result := _Score(aPlayer, aOpponent);
  iBewertung := Result;
  if Result >= sWinScore then Exit;
  Result := Result - _Score(aOpponent, aPlayer);
  iBewertung := Result;
end;


galagher - So 02.09.07 09:23

Das Problem an der ganzen Sache ist, dass das Lernen umso langsamer wird, je genauer ich die Spielsituation darstelle, da, wie alzaimar schon gesagt hat, der Code millionenfach ausgeführt wird. Das summiert sich! Das dauert Stunden, mitunter sogar Tage, bis auch nur ein Koeffizient verbessert (und damit übernommen) wird. Ein Dilemma: Genauere Spielsituation = langsamer, aber besser, weniger genau = schneller, aber schlechter.

Und da das Programm alle 50 Durchgänge gegen die alten und alle 500 Durchgänge gegen die Original-Koeffizienten spielt - bis da auch nur 50 Spiele erreicht sind, kann man inzwischen im Park spazieren gehen, was heisst, das reicht glatt für einen Urlaub!

Wenn eine Mustererkennung oder ein effizienterer Code eine Lösung wäre, und jemand kann das, dann bitte ich ihn, mir zu helfen! :D

Schon jetzt: Danke an alle für euer Interesse!


galagher - Mi 05.09.07 17:40

Hallo!

Sorry, dass ich mich zum 3. Mal in Serie melde, aber die Anzahl der Zugriffe zeigt mir, dass das Interesse ja da ist, aber keiner weiss, wie es nun weitergeht! Und, ja, so weit bin ich auch!

Das Programm braucht im höchsten Level wahrscheinlich Tage, bis auch nur ein Spiel beim "Lernen" zu Ende ist. Es ist aber sinnvoll, zumindest 50 Durchgänge zu machen, denn da spielt es mit den neuen Werten gegen die alten. Wohlgemerkt, ohne wesentliche GUI-Zugriffe.

Also versuche ich jetzt, das Berechnen jedes Zuges nach einer einstellbaren Maximalzeit zu beenden (klappt aber noch nicht). Das ist zwar nicht optimal, aber ich habe leider keinen zweiten Rechner, der so nebenbei mal ein paar Monate läuft und das Programm lernen lässt. Ich habe die Stellungsanalyse nach alzaimar's Vorbild ausgebaut, sodass das Programm jetzt 20 Koeffizienten hat. Aber das macht es langsamer, je genauer, desto lahmer, aber dafür desto besser.

Es spielt ja recht gut, alzaimar's KI ist wirklich ok (hätte ich nie hinbekommen!), aber - konkret:
Wer kann mir einen Ansatz geben, wie im Code eine Mustererkennung, ohne den von alzaimar angesprochenen Horizonteffekt funktionieren könnte, und das in einer akzeptablen Zeit, sodass ein Spiel im "Lernmodus" in, sagen wir mal, maximal 10 Stunden vorbei ist?

Das Bauernspiel ist nicht allein mein Programm, aber es ist mir das wichtigste von allen! :flehan: Bitte Hilfe, jedenfalls aber an dieser Stelle nochmal Dank!


alzaimar - Do 06.09.07 11:11

Hi galagher

nachdem ich den Thread nun schon 197,3 mal gelesen habe, ist mir endlich aufgefallen, was Du willst....

Du bist in dem Glauben, das das Lernprogramm Superkoeffizienten herausbringt, wenn man die 'Spieler' gegeinander im höchsten Level antreten lässt. Das stimmt aber nicht. Es reicht imho, die Spieler mit einem relativ geringen Level gegeneinander antreten zu lassen. Eigentlich müsste Level-0 ausreichen. Du willst ja nur zwei 'DNS-Stränge' (also die Koeffizienten) gegeneinander antreten lassen, und nicht, was irgendwelche Spielealgorithmen daraus machen.

Hier ist es auch so, das die Bewertungsfunktion unabhängig vom Suchalgorithmus agiert, Du kannst also getrost den Level beim Lernen runtersetzen. Probier doch mal, was für unterschiede in den Koeffizienten es gibt, wenn man beide Spieler mit Level 0 und mit 3 gegeneinander spielen lässt.

Die Bewertungsfunktion, die Du optimieren willst, soll den aktuellen Spielstand möglichst genau wiedergeben. Optimalerweise sollte die Funktion in der Lage sein, einen strategischen Vorteil zu erkennen. Dazu kann die Mustererkennung dienen. Die hast Du ja schon implementiert (oder war ich das?)

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
...
 {Schlagabtausch - etwa diese Stellung:}
{          X X X
           - O -
           O - O
}

          if (aBoard[r-2, j] = aPlayer) and
             (aBoard[r-2, j+1] = aplayer) and
//           (aBoard[r-2, j+2] = aplayer) and   {Klappt nicht (??)}

Es kann durchaus sein, das so eine Spielstellung nicht sonderlich von solchen Mustern abhängt. Dann würde ein lernenes Programm das relativ schnell erkennen, indem es den Koeffizienten hierfür gegen 0 tendieren, oder wahllos in der Gegend rumhüpfen lässt.

Vielleicht solltest Du eher schauen, das das Programm im Einzelfall über die maximale Zugtiefe hinaus weitersucht. Das kann z.B. bei einem Schlagabtausch nötig sein. Hier ist es ja eher so, das das Schlagen eines Steines nur einen strategischen Vorteil bringt (man schafft sich vielleicht eine leere Spalte zum durchmarschieren).

Welche Stellungen/Muster sind Winner? Welche sind Loser? Gibt es Stellungsmuster, die auf ein Patt hindeuten? Wie sollten die bewertet werden (ach, dafür ist ja der Lern-O-Mat da)...

In diese Richtung solltest Du weiter forschen.


BenBE - Do 06.09.07 14:57

Mir ist auch noch ne Kleinigkeit aufgefallen: Du solltest versuchen, bei Index-Angaben so wenig wie möglich berechnungen durchzuführen.

Wenn Du also mehrfach auf arr[a-1, b+2] zugreifen musst, dann berechnet Delphi jedes Mal auf's Neue, wo sich diese Variable befindet. Diese BErechnung kannst Du etwas verkürzen, indem Du:
1. die Adressen häufig gebrauchter Zellen über Pointer ansprichst
2. Die Index-Attribute zwischenspeicherst.


galagher - Do 06.09.07 17:27

user profile iconalzaimar hat folgendes geschrieben:
Du bist in dem Glauben, das das Lernprogramm Superkoeffizienten herausbringt, wenn man die 'Spieler' gegeinander im höchsten Level antreten lässt.
Ja, dachte ich! Es lernt nun schon seit gestern seit 21:15 ununterbrochen in Level 4 (von 8 ), hat bis jetzt 1 Koeffizienten verändert und ist erst im 8. Spiel! Mit Level 1 (0 hab ich aus dem Programm genommen) geht das Lernen ja ruck-zuck, im Nu sind da 50 Spiele beisammen. Aha, also dann, wenn ich das recht verstehe, ist es genauso gut, das Programm in Level 1 5000 Spiele spielen zu lassen, auch, wenn dann pro Zug die Rechentiefe sehr gering ist? Muss man ja erst mal wissen, DANKE!

user profile iconalzaimar hat folgendes geschrieben:
Du willst ja nur zwei 'DNS-Stränge' (also die Koeffizienten) gegeneinander antreten lassen, und nicht, was irgendwelche Spielealgorithmen daraus machen.
Ich dachte immer, was sie daraus machen sei entscheidend, weil es ja in höheren Levels (=mehr Rechenzeit pro Zug) besser spielt...

user profile iconalzaimar hat folgendes geschrieben:
Hier ist es auch so, das die Bewertungsfunktion unabhängig vom Suchalgorithmus agiert, Du kannst also getrost den Level beim Lernen runtersetzen.
Dann schmeiss' ich die Level-Einstellmöglichkeit beim Lernen raus und setze gleich Level 1 (oder 0)! Geht ja dann gleich viel schneller!

user profile iconalzaimar hat folgendes geschrieben:
Probier doch mal, was für unterschiede in den Koeffizienten es gibt, wenn man beide Spieler mit Level 0 und mit 3 gegeneinander spielen lässt.
Aber wenn's doch egal ist, wozu? Level 3 ist ja wieder langsamer als 0.

user profile iconalzaimar hat folgendes geschrieben:
Die Bewertungsfunktion, [...] Dazu kann die Mustererkennung dienen. Die hast Du ja schon implementiert (oder war ich das?)
Du warst das, ich habe sie aber auf 20 Koeffizienten ausgebaut. Mal sehen, könnten ja auch mehr sein.

user profile iconalzaimar hat folgendes geschrieben:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
...
 {Schlagabtausch - etwa diese Stellung:}
{          X X X
           - O -
           O - O
}

          if (aBoard[r-2, j] = aPlayer) and
             (aBoard[r-2, j+1] = aplayer) and
//           (aBoard[r-2, j+2] = aplayer) and   {Klappt nicht (??)}
Ja, so in etwa sieht das aus. Ein solcher Code IST also schon die Mustererkennung? Dann ist sie ja schon eingebaut (natürlich mehr davon, für alle 20 Koeffizienten).

user profile iconalzaimar hat folgendes geschrieben:
Vielleicht solltest Du eher schauen, das das Programm im Einzelfall über die maximale Zugtiefe hinaus weitersucht.
Macht es bei Level 7 und 8.

Also, zusammenfassend: Level 0 beim Lernen genügt, aber es sollten so viele Spiele wie möglich sein, oder? Und was die Mustererkennung angeht, das ist obiger Code, der die Stellung analysiert und bewertet, richtig? Und den kann man immer weiter ausbauen, sodass möglichst viele Stellungen berücksichtigt werden, auch korrekt?

Vielen Dank, hast mir sehr weitergeholfen, das ist schon was!

user profile iconBenBE hat folgendes geschrieben:
Mir ist auch noch ne Kleinigkeit aufgefallen: Du solltest versuchen, bei Index-Angaben so wenig wie möglich berechnungen durchzuführen.
Werde ich mir auch ansehen, danke!


galagher - Mo 10.09.07 15:58

Hallo zusammen!

Nun fehlt noch eine wesentliche Sache: Das Spiel soll Züge, die als einzige verhindern können, dass der Spieler gewinnt, sofort ausführen, und nicht auch noch andere, die den Spieler gewinnen lassen würde, berechnen. Letztlich führt es in jedem Level den einzig sinnvollen Zug ja doch aus. Ich möchte einfach, dass es ihn schneller ausführt, habe aber keine Ahnung, wie ich das programmieren soll.

Ich meine so in der Art: "Wenn du erkennst, dass der Spieler gewinnt, wenn du seinen Stein nicht schlägst (oder was auch immer), dann höre auf zu rechnen und schlage den Stein sofort!"

Am Besten seht ihr euch das folgende Beispielbild an. Das Programm spielt blau, der Mensch rot. Das Programm kann jetzt noch nicht gewinnen, und wenn es mit seinem bedrohten blauen Stein nicht schlägt, dann schlägt rot und gewinnt im darauffolgenden Zug:


BenBE - Mo 10.09.07 16:52

Du könntest auch den Ansatz etwas anders wählen:

Bewerte diese.
Führe zuerst alle möglichen Züge 1. Ebene aus.
Bewerte alle Züge 2. Ebene
Entscheide dich für die weiter zu verfolgenden
Stelle alle anderen zurück
Führe die bevorzugten Züge aus (der reihe nach) und verfahre genauso.

Auf diese Weise hast Du eine gewichtete Baum-Traversierung, wodurch stark zu bevorzugende Züge schnell gefunden werden sollten. Nachteil ist allerdings der etwas erhöhte Back-Tracking-Aufwand, da Du erstmal alle Möglichkeiten ausführen musst, bevor Du die Bewertung ermitteln kannst UND sich die Bewertung ggf. nachträglich noch mal ändert.


galagher - Mo 10.09.07 17:17

user profile iconBenBE hat folgendes geschrieben:
Auf diese Weise hast Du eine gewichtete Baum-Traversierung, wodurch stark zu bevorzugende Züge schnell gefunden werden sollten.

Ja, und da ist es wieder, das Problem: theoretisch verstehe ich das ja, aber die Praxis... nicht vergessen, die KI hat user profile iconalzaimar geschrieben, nicht ich! Zur Zeit gibt es keine solche Baum-Traversierung, denn wenn man das Programm "zwingt", sofort zu ziehen (ich hab' einen Button dafür eingebaut!), macht es einfach den aktuell berechneten Zug, auch wenn der geradezu hirnrissig ist.
Solche Züge müsste man irgendwie wegbekommen...

Habe nicht einmal ansatzweise eine Idee, wie ich das realisieren soll. Man müsste die Züge nach besseren und schlechteren sortieren, abhängig von der Spielsituation, ja, gut. Aber wie? Das Programm denkt ja nicht und sieht das Naheliegende nicht wie wir, und seine Berechnungen dauern nun schon teilweise recht lange. Es arbeitet mittlerweile mit 27 Koeffizienten, die ich alle nach alzaimar's Vorbild eingebaut habe, und das kostet eben Zeit.

Ok, das mit dem "Lernen per Evolution" klappt hervorragend mit Level 0 - über 75.000 Spiele in 12 Stunden ist akzeptabel. Aber das Sortieren per "gewichtete Baum-Traversierung" bleibt für mich graue Theorie. Ich apelliere hier an alzaimar: Nur noch diese eine Hilfe, dann ist es fertig!

Ich denke auch an eine einfache Eröffnungsbibliothek, falls sinnvoll. Das werde ich auch hinbekommen, aber was die KI angeht, die ist mir immer noch zu hoch... :(

//Edit: Bei Level 0 macht es den einzig sinnvollen Zug sofort, ab Level 1 rechnet es, um ihn schliesslich doch zu machen, nur eben später. :?


galagher - Mi 12.09.07 07:46

Habe es hinbekommen, dass der einzig sinnvolle Zug gleich ausgeführt wird. Ist zwar eine Abfrage, wo der Spieler und der Computer in den entscheidenden Reihen stehen, und ob der Computer gewinnen kann, aber erfüllt seinen Zweck.

Nun möchte ich, dass sich das Spiel eine Art Eröffnungsbibliothek erspielt. Ich denke mir das so, wenn der Spieler den Zug macht, den das Programm an seiner Stelle auch gemacht hätte, speichert es beide Züge ab. Das macht es so bis zum 6. Zug. Wenn bei einem späteren Spiel genau diese Züge kommen, spielt es aus der Bibliothek und damit schneller. Wird sicher klappen.

Nur das Sortieren der errechenten Züge, sodass der beste an erster Stelle kommt, kriege ich nicht hin. Ich meine das so: Wenn der Spieler die Zugberechnung des Spiels abbricht und es zum Ziehen zwingt, soll es nicht den aktuell berechneten Zug machen, sondern den, den es bis dahin als den besten ermittelt hat. Das mag zwar nicht der beste Zug insgesamt sein, aber so sielt es ja doch ein wenig stärker.

In diesem Zusammenhang könnte man auch gleichwertige Züge ermitteln, das wäre dann wiederum sinnvoll für die Eröffnungsbibliothek, die damit flexibler würde. Ich weiss nur nicht, wie!


galagher - Sa 15.09.07 21:16

* Schieb * :wave:


BenBE - Sa 15.09.07 23:50

hmmm, was hindert dich daran, die ersten 6 Züge eines jeden Spiels in einer Baumstruktur zu speichern und die zugehörigen "Best Moves" entsprechend zu markieren?


galagher - So 16.09.07 12:57

user profile iconBenBE hat folgendes geschrieben:
hmmm, was hindert dich daran, die ersten 6 Züge eines jeden Spiels in einer Baumstruktur zu speichern und die zugehörigen "Best Moves" entsprechend zu markieren?

Ich habe etwas Besseres gefunden: Der 1. Zug wird mit Random ermittelt, die nächsten 4 Züge werden in einem niedrigen Level ausgeführt, erst dann wird das eingestellte Level verwendet.

Was noch wünschenswert wäre:

-> Dass das Programm stärker spielt, so etwas wie einen Plan entwickelt oder "Fallen" stellt. Zur Zeit ist es doch so, dass es bei jedem seiner Züge sozusagen bei 0 zu rechnen beginnt.
Nun gibt es da alzaimar's selbstlernende KI, aber in den letzten 135.000(!) "Lern"-Durchgängen konnte kein einziger der 27 Koeffizienten mehr verbessert werden. Das bedeutet meiner Ansicht nach, dass hier eine gewisse Grenze erreicht ist - die Zusammensetzung der 27 Zahlen ist optimal, oder?
Was also nun? Noch mehr Koeffizienten einbauen, 30? Damit wird das Programm ja noch langsamer.

-> Dass das Programm schneller spielt, auch in hohen Levels. 20 Minuten pro Zug ist nicht mehr lustig. Gut, ein Schachcomputer rechnet noch länger, aber der kann dafür auch mehr! :D

Hier mal die Koeffizienten und ihr Sinn:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
  icoeffs: TCoeffArray = (
{0}  405,     {Multiplikator für Anzahl der Steine}
{1}  27,      {für Stein, der ziehen kann}
{2}  -858,    {für Stein, der schlagen kann}
{3}  7,       {für Stein, der gedeckt ist}
{4}  -3070,   {für angegriffenes, freies Feld}
{5}  13,      {für nicht besetzte Spalte}
{6}  -144,    {für 2 nebeinander nicht besetzte Spalten}
{7}  85,      {Abstand eines Gewinnsteins zur Grundlinie}
{8}  -48,     {für nächster Zug deckt Stein und Stein ist gedeckt}
{9}  -39,     {für nächster Zug greift gegnerischen Stein an}
{10} -10,     {für 2 vor Grundlinie bei freiem Zug}
{11}  918,    {für blockierten Stein}
{12}  -78,    {3 Felder links und/oder rechts sind frei}
{13}  -214,   {feststellen, ob aPlayer mehr als 1 Stein in der Reihe hat}
{14}  -20,    {Schlagabtausch}
{15}  22,     {Nachbarstein(e) ist/sind Gegner}
{16}  20,     {Nachbarstein(e) ist/sind eigene}
{17}  -1730,  {Nachbarfeld(er) ist/sind leer}
{18}  188,    {freie Spalte (senkr. nur leere Felder)}
{19}  -58,    {freie Reihe (waagr. nur leere Felder)}
{20}  7649,   {Reihe waagr. lückenlos eigene Steine}
{21}  1,      {Reihe waagr. lückenlos gegnerische Steine}
{22}  52,     {Eigener Stein steht völlig frei}
{23}  25,     {Gegnerischer Stein steht völlig frei}
{24}  6,      {Eigener Stein steht am Rand}
{25}  -9637,  {Gegnerischer Stein steht am Rand}
{26}  -964    {Stein kann in 3 Zügen ohne zu Schlagen gewinnen}
);

Was fehlt? Was kann man besser machen?