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
Silas 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
Narses 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
alzaimar 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
galagher 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
Horst_H hat folgendes geschrieben: |
was sagt denn der TAskmanager über die CPU Zeiten in %. |
Zwischen 89 und 97, so in etwa.
Horst_H hat folgendes geschrieben: |
Was bringt denn 1% bei 50 min, gerade mal 30 Sekunden. |
Ist ein Argument, ja...
BenBE 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.
Gausi 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
galagher 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
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
Christian S. hat folgendes geschrieben: |
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
hathor 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.
Gausi 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
galagher hat folgendes geschrieben: |
ich denke, der Code ist optimal. |
galagher 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
delfiphan 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
delfiphan 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);
if (c[i] < 0) and (Random(2) = 1) then c[i] := Abs(c[i]) else if (c[i] > 0) and (Random(2) = 1) then c[i] := -c[i];
while c[i]>9999 do c[i] := c[i] - 1000;
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;
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 if AskEndCurrentGame then exit;
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;
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 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 if mod500 then c2 := c1; 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:
| if (c[i] < 0) and (Random(2) = 1) then c[i] := Abs(c[i]) else if (c[i] > 0) and (Random(2) = 1) then c[i] := -c[i]; |
das hier???
Delphi-Quelltext
1: 2:
| if (Random(2) = 1) then 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
GTA-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!
BenBE 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.
BenBE 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.
BenBE 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!
BenBE 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.
BenBE 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.
BenBE 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
GTA-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
galagher hat folgendes geschrieben: |
BenBE 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
BenBE 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
galagher hat folgendes geschrieben: |
GTA-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
alzaimar 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!
alzaimar 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!
alzaimar 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.
alzaimar 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
alzaimar:
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;
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..7] of Boolean; BlockedCols: array[0..8] of Boolean;
begin 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; p := 0; m := 0; s := 0; d := 0; w := 0; o := 0; a := 0; v := 0; l := 0; c := 0; y := 0; t := 0; no := 0; np := 0; ne := 0; f := 0; g := 0;
_f := 0; _g := 0; _y := 0;
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; if not (opponentRow[j - 1] or 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);
if (aBoard[r1-1, j + 1] = aPlayer) or (aBoard[r1-1, j - 1] = aOpponent) and (aBoard[r, j] = aPlayer) and (aBoard[r1, j] = plEmpty) then inc(o);
if (aBoard[r1-1, j + 1] = aOpponent) or (aBoard[r1-1, j - 1] = aPlayer) and (aBoard[r, j] = aOpponent) and (aBoard[r1, j] = plEmpty) then inc(o);
if (aBoard[r1-1, j + 1] = aPlayer) or (aBoard[r1-1, j - 1] = aPlayer) and (aBoard[r, j] = aPlayer) and (aBoard[r1, j] = plEmpty) then inc(a);
if (aBoard[r1-1, j + 1] = aOpponent) or (aBoard[r1-1, j - 1] = aPlayer) and (aBoard[r, j] = aOpponent) and (aBoard[r1, j] = plEmpty) then inc(o);
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);
if not (aBoard[r, j] = plEmpty) and not (aBoard[r1, j] = plEmpty) then inc(l);
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);
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);
for z := 0 to 7 do begin if (aBoard[z, j] = aPlayer) then inc(_y);
if (aBoard[z, j] = plEmpty) then inc(_f);
if (aBoard[r, z] = plEmpty) then inc(_g); end;
if _y > 1 then inc(y);
if _f = 6 then inc(f);
if _g = 7 then inc(g);
if (aBoard[r-2, j] = aPlayer) and (aBoard[r-2, j+1] = aplayer) and
(aBoard[r-1, j] = plEmpty) and (aBoard[r-1, j+1] = aOpponent) and (aBoard[r-1, j+2] = plEmpty) and
(aBoard[r, j-1] = aOpponent) then inc(t);
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
(aBoard[r, j] = aPlayer) then inc(t);
if (aBoard[r, j+1] = aOpponent) or (aBoard[r, j-1] = aOpponent) then inc(no);
if (aBoard[r, j+1] = aPlayer) or (aBoard[r, j-1] = aPlayer) then inc(np);
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 + 1] then 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:
| ...
if (aBoard[r-2, j] = aPlayer) and (aBoard[r-2, j+1] = aplayer) and |
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
alzaimar 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!
alzaimar 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...
alzaimar 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!
alzaimar 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.
alzaimar 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.
alzaimar hat folgendes geschrieben: |
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9:
| ...
if (aBoard[r-2, j] = aPlayer) and (aBoard[r-2, j+1] = aplayer) and | |
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).
alzaimar 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!
BenBE 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
BenBE 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
alzaimar 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
BenBE 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 = ( 405, 27, -858, 7, -3070, 13, -144, 85, -48, -39, -10, 918, -78, -214, -20, 22, 20, -1730, 188, -58, 7649, 1, 52, 25, 6, -9637, -964 ); |
Was fehlt? Was kann man besser machen?
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!