Entwickler-Ecke
Algorithmen, Optimierung und Assembler - const wege schach
gerd8888 - So 04.09.16 15:24
Titel: const wege schach
Hallo,
ich will die dazwischenliegenden Felder eines Schachbretts in einer const Variablen unterbringen.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| x array[0..63] of byte= (0,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); |
Ich will von der Verbindungsline 0 und 7 dazwischen liegen die Zahlen 1, 2, 3, 4, 5, 6 usw.
oder 8 und 11 dazwischen liegen die Zahlen 9,10
oder 39 und 63 dazwischen liegen 47, 55
in einer const variable speichern
Man koennte schon ein
Delphi-Quelltext
1: 2: 3: 4: 5: 6:
| type Tt=record z:array[1..6]; end;
const zwischenwerte=array of array of Tt |
da ich aber die Verbindungslinie z.B. 0 und 7 vertauschen kann, waere viel Speicher vergoldet.
Gibt es eine bessere Loesung?
Gerd
Moderiert von Th69: Delphi-Tags hinzugefügt
Delphi-Laie - So 04.09.16 16:06
gerd8888 hat folgendes geschrieben : |
const Variablen |
Ist das nicht ein Oxymoron?
gerd8888 - So 04.09.16 16:41
Delphi-Quelltext
1: 2: 3: 4:
| type Tt=record z:array[1..6] of byte; end; |
Oxymoron? Warum?
Delphi-Laie - So 04.09.16 16:43
Weil eine Konstante nicht variabel sein kann bzw. eine Variable nicht konstant sein muß. In Pascal gibt es dafür zwei unterschiedliche Schlüsselwörter.
Christian S. - So 04.09.16 16:47
gerd8888 hat durch seinen Quelltext ja klar gemacht, was er meint. Daher bitte zurück zum Thema ;)
gerd8888 - So 04.09.16 16:50
Delphi-Quelltext
1:
| const zwischenwerte=array[0..63] of array[0..63] of Tt |
so muss es ganz korrekt sein.
Aber vielleicht geht es wirgendwie besser?
Delphi-Laie - So 04.09.16 16:55
Ich muß es leider so deutlich schreiben, aber die Beschreibung ist wirr.
gerd8888 hat folgendes geschrieben : |
Ich will von der Verbindungsline 0 und 7 dazwischen liegen die Zahlen 1, 2, 3, 4, 5, 6 usw.
oder 8 und 11 dazwischen liegen die Zahlen 9,10
oder 39 und 63 dazwischen liegen 47, 55
in einer const variable speichern |
"Ich will von der Verbindungslinie 0 und 7 [, dazwischen liegen.....] in einer const variable speichern."
Tut mir leid, aber das ist kein Satz!
Auch geht m.E. die Systematik nicht hervor - welche horizontalen und welche vertikalen Linien (Zwischenwerte) werden gespeichert?
gerd8888 hat folgendes geschrieben : |
da ich aber die Verbindungslinie z.B. 0 und 7 vertauschen kann, waere viel Speicher vergoldet. |
Eine Verbindungslinie läßt sich nicht vertauschen, sondern immer nur (mindestens) zwei Objekte lassen sich vertauschen. Sind 0 und 7 gemeint?
FinnO - So 04.09.16 17:01
Moin,
deine Fragestellung wird mir zwar nicht über die Maßen klar, aber ich glaube raten zu können, was du möchtest.
Zunächst: Unter normalen Bedingungen dürfte der Speicherplatz deines Arrays
64 * 64 * 6Byte = 24KB nicht zu einer übertriebenen Belastung deines Rechners führen. Demzufolge muss an dieser Stelle gesagt werden, dass alle folgenden Optimierung effektiv keinen Nutzen haben und nur die Lesbarkeit des Codes verschlechtern werden (siehe hierzu
When is optimization not premature and therefore not evil? [
http://programmers.stackexchange.com/questions/33020/when-is-optimization-not-premature-and-therefore-not-evil]).
Natürlich kannst du dein Start- und Zielfeld immer aufsteigend sortieren. Dann kannst du eine Dreiecksmatrix aufbauen, die nur die Zwischenfelder von Feld X zu allen davor indizierten Feldern aufbaut. Du guckst dann in deiner Dreiecksmatrix die Zwischenfelder für das höher indizierte Feld nach und musst (falls die Reihenfolge der Felder relevant ist), den Weg ggf. reversieren. Dabei hast du dann zahlreiche teure Aktionen gemacht, mächtige 12KB RAM gespart, aber keinerlei Performance gewonnen.
In deinen Beispielen hast du nur Pfade genannt, die in Spalten oder Zeilenrichtung verlaufen. Sollen grundsätzlich auch diagonale oder sonstwie schräge Wege möglich sein?
Bis dann
Finn
Übrigens:
Delphi-Laie hat folgendes geschrieben : |
Ist das nicht ein Oxymoron? |
Immerhin ist es nicht off-topic.
JoelH - Mo 05.09.16 08:38
gerd8888 hat folgendes geschrieben : |
Delphi-Quelltext 1:
| const zwischenwerte=array[0..63] of array[0..63] of Tt |
so muss es ganz korrekt sein.
Aber vielleicht geht es wirgendwie besser? |
Ich würde sagen, die Antwort ist JA. So ist es korrekt, wenn du ganz ohne Berechnungen auskommen möchtest. Ich vermute du möchtest z.B. die Zugmöglichkeiten eines Turms aus diesem Array ermitteln.
Ich bin mir allerdings nicht sicher ob dein Code effektiv schneller ist als wenn du die Möglichkeiten jeweils in der Ausleseschleife via Addition jedes Mal neu errechnest.
gerd8888 - Mo 05.09.16 09:38
Der Turm oder (die Dame) in der oberen linken Ecke soll zur rechten oberen Ecke 0 und 7 und zur unteren linken Ecke 0 und 56.
Da der Turm nicht über Steine fliegen kann (wie der Springer) muss ich die Zwischenfelder, die jeweils auf dieser Geraden liegen prüfen.
Wenn da ein weisser oder schwarzer Stein dazwischen ist, kann der T nicht ziehen.
Wenn ich nun eine Berechnung machen würde, muesste ich so vorgehen:
1) ich muss erst von den 2 Punkten das kleinere und das groessere ermitteln
2) Ich ziehe von der groesseren Zahl die kleinere Zahl ab
3) Das Ergebnis z.B. ich habe die Punkte 0 und 7 dann 7-0=7 dann muss ich 7 mod 8 machen. Ist es ungleich 0 addiere ich jeweils von 0 immer 1 bis ich
zur 7 komme
4) z.B. bei 0 und 56 56-0=58 56 mod 8 =0 dann muss ich jeweils 8 addieren.
Wieviel das rechnen ausmacht weiss ich nicht. Aber ich muss dass dann auch für den Läufer und für die Dame machen.
Die Abfrage findet wiederholt staendig im Zugbaum statt.
Ausserdem bei der Abfrage ob der König im Schach steht, verfolge ich den T-Weg des K und brauche das wieder.
Ich könnte mir also schon vorstellen, dass sich das lohnen könnte.
JoelH - Mo 05.09.16 09:52
Ich empfehle dir, aus programmtechnischen Gründen von einem 8x8 Board Abstand zu nehmen und ein 10x12 Feld als Board zu nehmen. Dadurch entfallen bei der Zugerzeugung nämlich die aufwendigen Ränderprüfungen.
Zum Thema gibt es gute Wiki, ist zwar englichsprachig aber ich habe dort sehr viele Informationen erhalten bei meinem Schachprogrammprojekt.
http://chessprogramming.wikispaces.com/ und dort zunächst mal
http://chessprogramming.wikispaces.com/Board+Representation
Warum das Rad neu erfinden?
gerd8888 - Mo 05.09.16 13:48
JoelH, die Brettdarstellung ist mir nicht unbekannt. Man kann auch bei dem Springer ausserhalb dem Rand huepfen.
Andererseits, schreibe ich alles in einer Tabelle, wo der Springer hinzieht (er hüpft gar nicht erst über den Rand hinaus) und alle anderen Figuren auch, somit sehe ich darin keinen so grossen Sinn.
Und das einzige Problem mit T und L Zwischenfelder habe ich jetzt so geloest:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| Ttl_zwischen = record zwischen:array of byte; end;
y_zahl = record y:array[0..63] of Ttl_zwischen; end; zw_felder:array[0..63] of y_zahl; |
Ich lege das doch nicht in eine const ab, sondern erzeuge sie vor dem eigentlichen Lösevorgang.
Hat auch den Vorteil, dass ich mit dynamischen arrays nur die tatsaechlichen werte habe und evt. Blindgänger z.B. j=0 und x=0 gar kein Speicherplatz belegt.
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:
| for j:=0 to 63 do begin for x:=0 to 63 do begin if x<>j then begin if x>j then begin g:=x; n:=j; end else begin n:=x; g:=j; end; if (g-n)<>1 then begin if (g-n)<>8 then begin if (g-n) mod 8 <> 0 then begin m:=1; repeat setlength(zw_felder[x].y[j].zwischen,m); zw_felder[x].y[j].zwischen[m-1]:=(n+m); inc(m); if (n+m)=g then m:=101; until m>100; end else begin m:=1; repeat setlength(zw_felder[x].y[j].zwischen,m); zw_felder[x].y[j].zwischen[m-1]:=(n+(m*8)); inc(m); if (n+(m*8))=g then m:=101; until m>100; end; end; end; end; end; end;
if high(zw_felder[0].y[8].zwischen)<>-1 then for n:=0 to high(zw_felder[0].y[8].zwischen) do begin st1:=st1+' '; st1:=st1+inttostr(zw_felder[0].y[8].zwischen[n]); end; label1.Caption:=st1; |
Warum das Rad neu erfinden? Meine Nachbarin sagt mir auch, dass es schon so viele Schachprogramme gibt, warum ich eigentlich programmiere.
Tatsächlich habe ich mir auch schon überlegt es bleiben zu lassen, weil es eh schon alles gibt.
Andererseits macht es immer wieder Spass. Den Rekord werde ich bestimmt nicht brechen... oder doch?
Gerd
JoelH - Mo 05.09.16 14:15
In der Tat, das dachte ich mir damals auch ;-)
Allerdings, was Boardrepräsentation/Zuggeneration angeht, da hab ich das Rad nicht wirklich neu erfunden. Ich habe lieber "unter der Haube" rum geschraubt und meine Stellungsbewertungen "optimiert".
Aber davon mal ab. Bei langschrittigen Figuren musst du sowieso testen ob es in Zuglinie eine andere Figur gibt. Und da Frage ich mich ob auslesen aus einem Array wirklich der einfachen Addition zur Laufzeit signifikant/überhaupt überlegen ist. Bei Ersterm muss das Programm eine dynamisch abgelegte Information aus dem Speicher raus suchen und laden. Bei Zweiterem werden lediglich zwei ShortInts addiert. Ich würde fast daruaf tippen, das zweiteres schneller geht.
JoelH - Mo 05.09.16 14:59
Habe mal schnell was gebastelt, welches das Problem jeweils abbildet.
Bei mir ist die Addition (~300 ms) dem Auslesen aus dem Array (~400 ms) überlegen.
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:
| procedure TForm1.cmd_1Click(Sender: TObject); var i, n, x, t: ShortInt; p: Integer; freq: Int64; startTime: Int64; endTime: Int64; begin QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime);
n := 1; for p := 1 to 100000000 do begin
x := 0;
while (x < 8) do begin t := x; inc(x, n); end; end;
QueryPerformanceCounter(endTime);
mem_1.Lines.Add('Die Routine benötigte etwa ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');
end;
procedure TForm1.cmd_2Click(Sender: TObject); var i, n, x, t : ShortInt; p: Integer; freq: Int64; startTime: Int64; endTime: Int64; a : Array[0..63, 0..63] of Array of Shortint; begin
t := 8; SetLength(a[0,7],t); for i := 0 to 7 do a[0,7][i] := i;
QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime);
x := 0; n := 7;
for p := 1 to 100000000 do begin for i := 0 to Length(a[x,n])-1 do begin t := a[x,n][i]; end; end;
QueryPerformanceCounter(endTime);
mem_1.Lines.Add('Die Routine benötigte etwa ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');
end; |
gerd8888 - Mo 05.09.16 16:17
JoelH, ich habe den Test gerade durchgefuehrt.
Auf meinem Computer ist das Ergebnis auch um ca. 100 ms unterschiedlich
Variante A: ca. 500 ms
Variante B: ca. 630 ms
(Ich habe zudem noch einen langsameren Rechner)
Ich weiss auch, was der Grund für die etwas schlechteren Werte sind:
setlength ist der Übeltäter. Wenn man naemlich kein dynamisches array hernimmt, dann kommt man zu folgendem Ergebnis.
Hier der Code von Button2
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:
| procedure TForm1.Button2Click(Sender: TObject); var i, n, x, t : ShortInt; p: Integer; freq: Int64; startTime: Int64; endTime: Int64; a : Array[0..63, 0..63] of Array of Shortint; b: array[0..63, 0..63,0..7] of shortint; begin
t := 8; for i := 0 to 7 do b[0,7][i]:=i;
QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime);
x := 0; n := 7;
for p := 1 to 100000000 do begin for i := 0 to Length(a[x,n])-1 do begin t := a[x,n][i]; end; end;
QueryPerformanceCounter(endTime);
memo1.Lines.Add('Die Routine benötigte etwa ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');
end; |
Variante A: 500 ms
Variante B: (obiger code) 166 ms
Sogar deutlich langsamer. Das dürfte auch der Fall sein, wenn ich es doch noch mal in const umschreibe. Das Ergebnis duerfte aehnlich sein.
Aber trotzdem will ich nochmal erwaehnen, dass wir hier von 100 Mio. Zuegen sprechen und da ist eine Abweichung von ein paar ms glaube ich wirklich nicht so schlimm.
gerd8888 - Mo 05.09.16 16:27
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:
| procedure TForm1.Button2Click(Sender: TObject); var i, n, x, t : ShortInt; p: Integer; freq: Int64; startTime: Int64; endTime: Int64; a : Array[0..63, 0..63] of Array of Shortint; b: array[0..63, 0..63,0..7] of shortint; begin
t := 8; for i := 0 to 7 do b[0,7][i]:=i;
QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime);
x := 0; n := 7;
for p := 1 to 100000000 do begin for i := 0 to Length(b[x,n])-1 do begin t := b[x,n][i]; end; end;
QueryPerformanceCounter(endTime);
memo1.Lines.Add('Die Routine benötigte etwa ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');
end; |
so ist es richtig, vorher hatte ich t:=a[x,n][i] hergenommen.
ausserdem Length(b[x,n])-1
Dann ist es ca. gleich schnell.
gerd8888 - Di 06.09.16 11:40
Noch eine kleine Schlussbemerkung:
Die Zwischenwerte brauche ich gar nicht, da ich den T in allen Himmelsrichtungen (also eigene 4 Schachblonen habe) und wenn eine Figur da ist, breche ich die Schablone ab. Das ist mir erst im Nachhinein gekommen.
acadam71 - Di 06.09.16 17:18
@gerd8888: Soll Dein Schachprogramm die Protokolle Winboard bzw. UCI unterstützen oder willst Du eine eigene UI entwickeln? Zur Info: Ich bastle auch gerade an einer Schach-Engine. Den Zuggenerator habe ich bereits fertig und arbeite zurzeit an der Bewertungsfunktion und der Winboard-Anbindung.
gerd8888 - Di 13.09.16 11:14
Ich will erst mal das Programm schreiben und danach mal sehen, ob sich eine UCi lohnt.
acadam71: Wie schnell ist Dein Zuggenerator. Wieviele Zuege in 1 sek schafft dein Programm.
Ich habe nun bei meinen Programm festgestellt, dass die Bitboards sogar langsamer sind:
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:
| unit Unit1;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, math;
type TForm1 = class(TForm) Button1: TButton; Button2: TButton; Label1: TLabel; Label2: TLabel; Memo1: TMemo; procedure Button1Click(Sender: TObject); procedure Button2Click(Sender: TObject); private public end;
var Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject); var p:cardinal; maske,wk:int64; freq: Int64; startTime: Int64; endTime: Int64;
procedure BitSet(var TestZahl : int64;Bitnr: byte); var bitmaske:int64; begin bitmaske := Int64(1) shl bitnr; testzahl:= bitmaske or testzahl; end;
begin wK:=0; QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime); for p:=1 to 10000000 do begin maske:=0; bitset(maske,0); bitset(maske,3); wK:=wK xor maske; wk:=wK xor maske; end;
QueryPerformanceCounter(endTime);
memo1.Lines.Add('Die Routine benötigte etwa ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');
end;
procedure TForm1.Button2Click(Sender: TObject); var a:array[1..64] of byte; p:cardinal; freq: Int64; startTime: Int64; endTime: Int64; begin QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime); for p:=1 to 10000000 do begin a[1]:=10; a[2]:=0; a[2]:=0; a[1]:=10; end;
QueryPerformanceCounter(endTime);
memo1.Lines.Add('Die Routine benötigte etwa ' + IntToStr((endTime - startTime) * 1000 div freq) + 'ms');
end;
end. |
mit Bitboard 145 ms
auf einem array 14 ms
Was mache ich falsch?
JoelH - Di 13.09.16 14:52
Na ja, das ist schon ein wenig unfair. Bei der Bitgeschichte setzt du jeweils die Maske neu, das muss nicht sein. Einmal setzen sollte reichen. Des Weiteren setzt du in der Bitvariante variabel, während du in der Arrayvariante Konstanten verwendest, das der Compiler sicher weiter optimiert.
Was die Knotenzahlen angeht. Ich kann für mein Programm ca. 1 Mio. Knoten in der Sekunde einwerfen. Dabei muss aber berücksichtigt werden, dass davon im Regelfall nur gut 50% legal (Allerdings spielt das Programm die Variante Atomic, kein reguläres Schach) sind, davon werden dann nochmal gut 50% aus sortiert durch Alpha/Beta, Hashtabellen usw.
Der Zuggenerator ist alleine sicher schneller (Hab es nie ausprobiert, wie schnell genau) , die BEwertungsfunktion ist die Bremse, so oder so.
Zusatz: Okay, hab mal die Bewertung abgekoppelt und aus der Grundstellung 10.000.000 Züge erzeugen lassen. Das hat 2925 ms gedauert. Also ca. 3418 Züge pro ms.
gerd8888 - Mi 14.09.16 20:00
Jetzt habe ich die Masken in einem array gespeichert und greife direkt zu. Ist etwas schneller.
Ich habe schon mal ein Schachprogramm geschrieben mit einer brett[1..64] of shortint.
Ich habe die beiden Schachprogramme verglichen (nur mit Königen) und da ist immer noch mein altes Programm schneller.
Wahrscheinlich benoetigt die Schachabfrage viel Zeit. Hier mal die procedure
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:
| function Bittest (TestZahl : int64;Bitnr: byte):boolean; begin Result := (testzahl and (Int64(1) shl bitnr)) <> 0; end;
function sK_im_schach:boolean; var a,b,c,d:byte; h,schach:boolean; begin schach:=false; for a:=0 to 63 do begin if schach=false then if bittest(sk,a) then begin for b:=1 to 4 do begin if schach=false then if t_anz[b,a]<>0 then begin for c:=1 to t_anz[b,a] do begin h:=true; if bittest(st,t_wege[b,a].zahlen[c]) then begin h:=false; end; if h then begin if bittest(wk,t_wege[b,a].zahlen[c]) then begin h:=false; end; if h then begin if bittest(wt,t_wege[b,a].zahlen[c]) then begin schach:=true; h:=false; end; end; end; if h=false then break; end; end; end; end; end; if schach then result:=true else result:=false; end; |
Ich gehe vom König weg und schaue ob da eine Figur steht. Hier sogar nur die T-Züge. Das braucht ziemlich viel Zeit...
JoelH - Do 15.09.16 10:14
Hilfreich sind Variablen die auch etwas aussagen. In deiner Varianten ist der Code mühsam zu entziffern.
Sehe ich das richtig, dass du jedes mal über das gesamte Brett gehst um den König zu suchen? Das ist ja mal der absoluten Speedkiller. Wenn es ungünstig läuft benötigst du bei 10.000.000 Stellungen 640.000.000 Iterationen, von denen 630.000.000 überflüssig sind wenn du einfach eine Figurenliste mit führst, die dir zur jeweiligen Stellung die Position des Königs zurück gibt.
gerd8888 - Do 15.09.16 12:04
Das stimmt. Das habe ich übrigens noch selbst herausgefunden, dass es besser ist den weissen König und den schwarzen König einfach in ein byte abzuspeichern. Dann habe ich festgestellt, dass ich das auf das bitboard bei königen ganz verzichten kann. Nur bei Königen speichere ich das anders ab, wegen der Schachabfrage.
(Normalerweise habe ich aussagekraeftige Variablen gewaehlt. Nur bei der Schachabfrage waren es alles Schleifen und da habe ich keinen Sinn gesehen)
gerd8888 - Do 15.09.16 19:11
Habe mir heute mal das sog. magic-bitboard angesehen.
Die Grundidee ist einfach. Z.B. beim Turm in der Mitte, wird eine Maske (die schon erzeugt wurde und nur noch aufgerufen werden muss) mit der
bitboard_gesamte_steine xor maske (siehe unten)
00010000
00010000
00010000
00010000
11101111
00010000
00010000
00010000
Somit spart man sich, wenn man vom König alle Richtungen durchsucht, die Leerfeldabfrage.
Hast Du das in Deinem Atomschach auch eingebaut?
JoelH - Fr 16.09.16 08:20
Nein, habe ich nicht. Ich arbeite ganz oldschool mit Figurentabelle und 10*12 Board. Wie ich schon weiter oben schrieb, mein Hauptaugenmerk legte ich ganz traditionell (ganz vom eigenen Ego getrieben) auf die Stellungsbewertung und nicht auf den Zuggenerator, Oldschool eben.
Heute geht es ja fast nur noch um schnelle Zuggeneration und nur noch rudimentäre Stellungsbewertung mit Hauptaugenmerk auf die perfekte Zugsortierung um sehr gute Alpha/Beta Cuts zu bekommen. Das war aber nicht meine Motivation hinter dem Projekt. Mein Ziel war es zunächst einfach nur ein Programm zu schreiben welches mich schlagen kann. Das ging allerdings recht einfach, obwohl ich jetzt gar kein so schlechter Atomicschachler bin. Danach hab ich es eine Weile auf einem Schachserver spielen lassen, mit überraschend guten Ergebnissen. Ich schätze das Programm auf etwa 1800 Schachserver-ELO aber es hat einen Wert von knapp 2500 erreicht. Im weiteren Verlauf habe ich dann immer mehr Ideen zur Stellungsbewertung eingefügt um zu schauen ob meine Ideen auch so funktionieren wie ich mir es vorstelle oder ob ich total daneben liege.
Einige Anekdoten dazu findest du in meinem Blog zum Projekt. Da siehst du aber auch, dass ich seit mehr als einem Jahr nichts mehr daran gemacht haben.
http://joelh.de/atomystica/?lang=de
gerd8888 - Fr 16.09.16 17:35
JoelH, habe mir Deine Seite angesehen. Mit welchen Spielregeln spielst Du Dein Atomschach. Darf der König direkt geschlagen werden. Oder wird er nur mattgesetzt, wenn er durch eine Explosion vom Brett verschwindet. Da ich an Kunstschach interessiert bin, würde mich interessieren, ob es auch einfache Mattprobleme, wie Matt in 3 Zügen gibt.
Jetzt habe ich mich nochmal mit den magic Bitboards beschaeftigt.
00001000
00001000
00001000
11110111
00001000
00001000
00001000
00001000
(1 Maske, auf e5 steht ein wT )
00000000
00000000
00000000
00101000
00000000
00000000
00000000
00000000
(2 Ausgangsstellung)
Maske xor Ausgangstellung
00001000
00001000
00001000
11010111
00001000
00001000
00001000
00000000
(3 Attakierten Felder des Turms)
Die Felder a5 und b5 sind auch attakiert. Aber auf dem Feld c5 ist ein
Block.
Es soll nun als Ergebnis das hier herauskommen:
00001000
00001000
00001000
00010111
00001000
00001000
00001000
00000000
(4 wirklich attakierten Felder des Turms)
Jetzt ist a5 und b5 nicht blockiert.
Nun koennte man ein Lookup von Dia 3 und vielen weiteren Stellungen
erstellen. Das Problem ist nun, dass es hier sehr viele Moeglichkeiten
gibt. Verringert soll das durch ein "magic bitboard" Maske werden.
Kann mir das einer erklären, wie das funktionieren soll?
gerd8888 - Fr 16.09.16 22:06
Das Prinzip habe ich verstanden. Die magic Maske soll praktisch die untenere Maske mit Buchstaben in einer Reihenfolge bringen
00000000
0000B000
0000A000
0EDC1FG0
0000H000
0000I000
0000J000
00000000
Dann hat man wieder eine Zahl
BADECIJH
Dann wandelt es die Zahlen in einem Lookup um
Danach macht man alles rueckgaenig und hat das fertige Ergebnis.
Nur ueber eine Kleinigkeit raetsel ich noch.
Warum sind die ganz aeusseren Felder der Maske nicht besetzt.
Ich kann doch nicht automatisch einen Rückschluss machen, dass wenn e7 attackiert ist auch e8 attackiert ist, denn wenn auf e7 eine schwarze Figur steht und geschlagen wird, dann ist eben e8 nicht attackiert.
Wer hilft mir jetzt die magischen Zahlen herauszufinden. Wie funktioniert diese Art der Bitmanipulation eigentlich?
JoelH - So 18.09.16 12:32
gerd8888 hat folgendes geschrieben : |
JoelH, habe mir Deine Seite angesehen. Mit welchen Spielregeln spielst Du Dein Atomschach. Darf der König direkt geschlagen werden. Oder wird er nur mattgesetzt, wenn er durch eine Explosion vom Brett verschwindet. Da ich an Kunstschach interessiert bin, würde mich interessieren, ob es auch einfache Mattprobleme, wie Matt in 3 Zügen gibt.
|
Es wird nach den Regeln gespielt die hier hinterlegt sind.
https://www.unix-ag.uni-kl.de/~chess/atomic/
Der König wird nicht geschlagen sondern geht ganz normal Matt oder er wird indirekt gesprengt, wenn eine eigenen Figur direkt daneben geschlagen wird. Das normale Matt ist dabei von einer einzelnen Dame herbeiführbar in der Ecke. wDb2 sKa1 ist Matt da ein König im Atomic nicht schlagen darf.
Alle anderen Regeln des normalen Schachs gelten weiterhin. Also es ist auch Patt möglich.
Hier gibt es eine tolle Seite über Atomic
http://www.nicklong.net/chess/atomic/ da gibt es auch eine Mattaufgaben zu finden
http://www.nicklong.net/chess/atomic/puzzles.htm
gerd8888 - Mo 19.09.16 23:51
Ich habe mir die Atomschachrätsel angesehen. Konnte nur das letzte Problem lösen. Schade, dass es keine Lösungsbesprechung gibt.
Zurueck zu den Magic Bitboards.
Ich will jetzt die magischen Masken herausfinden:
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:
| procedure TForm1.magische_zahlen; var testz,t,magic,erg,i:int64;
begin testz:=0; bitset(testz,50); bitset(testz,43); bitset(testz,36); bitset(testz,29); bitset(testz,22); bitboard(testz); label1.Caption:=inttostr(low(testz))+' '+inttostr(high(testz)); update; t:=testz; for i:= low(testz) to high(testz) do begin} if t*i >= low(testz) then if t*i <= high(testz) then begin erg:=t*i; if bittest(erg,59) then if bittest(erg,60) then if bittest(erg,61) then if bittest(erg,62) then if bittest(erg,63) then begin bitclear(t,50); if not bittest(erg,59) then if bittest(erg,60) then if bittest(erg,61) then if bittest(erg,62) then if bittest(erg,63) then begin bitset(t,50); bitclear(t,43); if bittest(erg,59) then if not bittest(erg,60) then if bittest(erg,61) then if bittest(erg,62) then if bittest(erg,63) then begin bitset(t,43); bitclear(t,36); if bittest(erg,59) then if bittest(erg,60) then if not bittest(erg,61) then if bittest(erg,62) then if bittest(erg,63) then begin bitset(t,36); bitclear(t,29); if bittest(erg,59) then if bittest(erg,60) then if bittest(erg,61) then if not bittest(erg,62) then if bittest(erg,63) then begin bitset(t,29); bitclear(t,22); if bittest(erg,59) then if bittest(erg,60) then if bittest(erg,61) then if bittest(erg,62) then if not bittest(erg,63) then begin magic:=i; beep; break; end; end; end; end; end;
end; end; end; beep;
label1.caption:=inttostr(magic);
end; |
Nach 2 Stunden habe ich abgebrochen. Ich habe herausgefunden, dass es an der Multiplikation liegt:
Delphi-Quelltext
1: 2: 3:
| for i:= low(testz) to high(testz) do begin} if t*i >= low(testz) then if t*i <= high(testz) then begin erg:=t*i; |
Was nun?
Gerd
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 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!