Wie entwickle ich einen performanten Othello Zuggenerator?

[beule]

Hallo Foren-Mitglieder,

nach längerer Delphi Abstinenz wollte ich endlich mal ein kleines (großes?) Projekt in Angriff nehmen.
Ich entwickle gerade ein Othello-Programm und habe mich an dem Zuggenerator festgebissen.

Das Brett präsentiere ich intern durch 2 Cardinals (A1 bis H4 und A5 bis H8 ) mal 2 für (Schwarz und Weiss) ..Stichwort: bitboards.
UInt64 soll ja buggy sein?!

Jetzt kommt ein wenig Pseudo-Code. Ich vernachlässige hier mal die oberen Cardinals!

Delphi-Quellcode:

Const A1 = 1;
      B1 = A1 * 2;
      C1 = B1 * 2;
      {usw.}
      A5 = 1;
      B5 = A5 * 2;
      {usw.} 
      Empty = 0;
Var
      wbBoard, {schwarze + weisse Steine}
      wBoard, {weisse Steine}
      bBoard {schwarze Steine}: Cardinal; 

wbBoard = wBoard or bBoard;
if (wbBoard and A1) = Empty then
  if (bBoard and B1) = B1 then
    if (bBoard and C1) = C1 then
      {usw.}
    else
      if (wBoard and C1) = C1 then
        {GEFUNDEN A1 leer, B1 schwarzer Stein, C1 weisser Stein}
      else
        {kein Match}

Also es gibt keine Schleife, hier wird jedes Bit umgedreht.

Jetzt meine Fragen:
1) Geht das hier evtl. eleganter und schneller? Besserer Algorithmus? (BESTIMMT )
2) Meine Assembler (68000-er) Kenntnisse sind schon veraltet. Gibt es
bestimmte Befehle die mein Vorhaben hier beschleunigen können? Also
Assembler in Delphi einbinden (..hier gibt es ja auch ein tolles Tutorial)

Dieser Code hier soll weniger als 200 Taktzyklen brauchen Othello Zuggenerator
..behauptet wird das hier: radagast siehe: Bitboard trickery
Dort steht übrigens auch:
The main trick used by the code is to find all moves that flip discs in a certain direction, e.g. up, in parallel. This can be done in several different ways, this code uses a variation first suggested by Richard Delorme which I have improved somewhat. There are 8 possible flip directions, 6 of these are managed by the MMX ALUs and the remaining 2 by the integer ALUs.

Leider weiss ich nicht ob ein z.B. ein And mit einem Vergleich ein oder 2 Taktzyklen sind, z.B. (bBoard and B1) = B1

Wenn ich nur das Feld A1 untersuche (Wagerecht, Senkrecht, Diagonale) sind das im schlimmsten Fall ca. 22 Vergleiche (jede Richtung 7 und das Ausgangsfeld) und 60 Felder habe ich zu vergleichen (64 - 4 gesetzte Steine).

Ich muss hier mehr parallel machen, aber wie

Ciao beule

[beule]

Hi,

zwei kleine Fragen:

1) Sollte ich auf Free Pascal ausweichen um 64 bit nutzen zu können? Wenn ich es
richtig verstehe, sind Uint64 und QWORD das gleiche, nur das UInt64 in Delphi 2005 nicht funktioniert.

2) Gibt es einen Assembler-Befehl, der mir sehr schnell die Position des höchsten gesetzten
bit liefert?

Beispiel: 0000 0100 0001 0000
........................^
11. Stelle

Wäre SUPER wenn mir jemand helfen würde

Ciao beule

[Medium]

Zu 1: Die 64Bit von Freepascal meinen, dass es Kompilate für 64Bit CPUs erstellen kann. So lange du eine solche nicht hast, bringt es dir auch nix. In wie weit sind QWords denn eigentlich "buggy"? Wäre es für deine Zwecke nicht evtl. sogar sinnvoll sich mal mit dem MMX Befehlssatz zu befassen? Dort hast du auch auf einer 32-bittigen CPU 64Bit Register von Hause aus, und man kann u.U. dank SIMD noch ein wenig tricksen.
SSE(2) kämen evtl. auch in Frage, jedoch weiss ich da nicht, in wie weit diese Möglichkeiten bieten integer-mäßig damit zu arbeiten.

Zu 2: Da würde mir nur einfallen das Register so lange nach rechts zu shiften bis es 0 ist, und die Anzahl der Shifts in einem anderen mitzuzählen.
Edit: Oder die einzelnen Positionen nacheinander rausmaskieren, vom nieder- zum höchstwertigen Bit, und sobald das Register 0 ist hast du das höchst vorkommende erwischt. Dürfte schneller sein als Shifts.

[jfheins]

Ich weis jetzt nicht, wie schnell das ist, aberman könnte es auch so machen:

Ceil(ld(Zahl));

Wobei ld = log zur basis 2 und Ceil() aufrunden (könnte in delphi anderes heißen ...)

Das wäre die mathematische lösung, aber wie schnell das geht ...

[grenzgaenger]

Zitat von beule:

Also es gibt keine Schleife, hier wird jedes Bit umgedreht.

sag mal, was willste eigentlich? die bits umdrehen? also aus 1 'n 0 machen? dann sollte NEG dein freund sein...

[beule]

Hallo Medium,

vielen Dank für Deine Antwort. Ich habe einen Athlon(Venice). Ein wenig habe ich mich auch schon mit dem MMX Befehlssatz beschäftigt. Ich habe nicht gesagt das QWORD buggy ist, sondern uInt64 in Delphi 2005.
Suche mal hier hier nach uInt64

Wenn ich dies in Delphi 2005 ausführe, erhalte ich als Ergebnis -1, in Free Pascal 18446744073709551615
(In Free Pascal ersetze ich uInt64 durch QWORD)

Delphi-Quellcode:

Var test_uint64: uInt64;
test_uint64: = 18446744073709551615; {alle 64 bit auf 1 gesetzt}
ShowMessage(intToStr(test_uint64: ))

Zu 2)
Habe mir schon gedacht, daß es da keinen speziellen Befehl gibt. SCHADE

Hintergrund meiner Frage: Ich dachte da an folgenden Algorithmus:
Ein QWORD für die weissen Steine (wQW), eines für die schwarzen (sQW) und für die leeren Felder -> leerQW:= neg(sQW or wQW)
Interne Darstellung des Spielbrettes Feld A1 = 1 und H8 = 8000000000000000 Hex

Jetzt der Zuggenerator aus der Sicht von Weiss:
1) Zuerst suche ich alle Zugmöglichkeiten von links nach Rechts. Ich entferne (maskiere) alle nicht benötigten Steine von Schwarz die dafür uninteressant sind (A1 bis A8 und H1 bis H8 )
2) Dann schiebe ich das Brett mit den schwarzen Steinen um eine Position nach rechts und mache ein AND mit leerQW. Dadurch habe ich alle leeren Felder gefunden bei denen direkt rechts daneben ein schwarzer Stein ist.
3) Jetzt tue ich so, als ob der abschl. weisse Stein kommt. Hier interessieren mich folgende weisse Steine nicht, von (A1 bis A8 und B1 bis B8 maskieren). Schiebe 2 nach rechts und mach ein AND mit leerQW, was ich in ein neues QWORD rette. In diesem QWORD stehen jetzt alle Zugmöglichkeiten von links nach rechts, wo nur ein schwarzer Stein umgedreht wird.
4) Entferne jetzt diese Treffer aus der Menge zu Punkt 2) => Ergenis aus 2) AND NEG (neues QWORD aus 4) )
usw.

Als Ergebnis habe ich 8 (Richtungen) * 6 (1 bis 6 umgedrehte schwarze Steine) = 48 QWORDS

..und wenn ich jetzt auch noch in den 48 QWORDS suchen muss, dann verliere ich wieder alles, was vorher so schön geklappt hat

..und deswegen habe ich @grenzgaenger geschrieben, hier wird jedes Bit umgedreht. Damit meine ich meinen obigen Pseudocode, wo
ich alles auscodieren wollte!
Also:

Delphi-Quellcode:

if (wbBoard and A1) = Empty then
begin
..
end; 
if (wbBoard and A2) = Empty then 
begin
..
end; 

..bis H8

..auch Danke für Deine Hilfe @jfheins. Sehr trickreich Ich vermute aber wie Du das es nicht besonders performant ist.

Mal sehen ob mir noch was geschicktes einfällt

[Medium]

Ich habe das also richtig verstanden, dass die 48 QWORDS mögliche Züge darstellen, und je höhherwertig das zuletzt gesetzte Bit ist, desto besser wäre der Zug (bzw. dreht er am meisten Gegnersteine um), richtig? Weil dann musst du doch nur noch das QWORD raussuchen, dass am größten ist, also einfach via normlaem arithmetischem Vergleich. Wenn du dann das letzte gefunden hast, kannst du einmalig durch den Logarithmus die Stelle des Bits ermitteln, und musstest dies nicht für alle tun. Der Logarithmus ist zudem nicht allzu wild, da es direkt Opcodes dafür, und auch fürs Runden gibt. Wobei ich grad nicht sicher bin wie viel Aufwand es durch die 64-Bittigkeit mehr ist das zwischen den Registern hin und her zu schieben. Im Zweifel machste einfach ein Case daraus. Der ist zwar erstmal viel Geschreibsel, aber unter Delphi in der Regel sehr schnell:

Delphi-Quellcode:

case zugQW of
  $0: umgedreht := 0;
  $1: umgedreht := 1;
  $2..$3: umgedreht := 2;
  $4..$7: umgedreht := 3;
  $8..$F: umgedreht := 4;
  $10..$1F: umgedreht := 5;
  $20..$3F: umgedreht := 6;
.
.
.
end;

Wobei ich mir HIER wiederum nicht mehr ganz sicher bin, ob ein QWORD als Ordinaltyp gilt, und mangels Delphi an dieser Kiste grad auch nicht schnell nachsehen kann.

Edit: Ich seh mir grad den Wikipedia Artikel an. Die Sache mit dem Case dürfte nach diesen Infos wohl leider an der Beschränkung der Literale scheitern, es sei denn in Hex gehts evtl. doch

[beule]

Hi @Medium,

finde ich ja klasse wie Du Dich da reinhängst.

Der Zuggenerator macht keine Bewertungen. Es kann nicht pauschal gesagt
werden, dass es besser ist mehr oder weniger Steine umzudrehen. Am Anfang
und im Mittelspiel ist es eher so, dass man besser weniger Steine umdreht
und am Ende eher umgekehrt, da der Gewinner derjenige ist, der die meisten
Steine seiner Farbe hat.

Der Zuggenerator liefert mir ein Array von n verschiedenen Brettpositionen,
wobei n auch 0 sein kann. In dem Fall muss man aussetzen.

Mal sehen was mir als Algorithmus noch einfällt und was man noch an speziellen
Befehlen herausholen kann.

In den 48 QWORDS stehen sämtliche Züge einer Brettposition. Ich finde diese
Lösung an dieser Stelle nicht besonders geschickt. Da muss ich noch nachbessern!

Ciao beule

[Medium]

Ahhh, das ganze läuft also letztlich auf einen Spielbaum (Alpha-Beta-Pruning) hinaus? Eine andere Frage noch: Ich habe bis jetzt nicht ganz durchblickt, warum du überhaupt das höchstwertige gesetzte Bit brauchst. Bzw. hab ich wohl generell noch nicht wirklich verstanden wie dieser gesamte Ansatz generell zustande kommt =)

[beule]

Hallo Medium,

genau, die Spielbaumsuche, sowie die Bewertungsfunktion stehen noch aus.

In den Zuggenerator geht eine aktuelle Spielsituation und der Zuggenerator liefert mir ein Array von daraus resultierenden Zügen.

Zum Beispiel geht folgende Brettposition in den Zuggenerator:

00000000
00000000
00000000
00SWWZ00
00WWW000
00W0Z000
00S00000
00000000

unten links ist A1 und oben rechts H8. Es gibt 2 schwarze Steine (c2, c5) und 6 weisse Steine. Annahme schwarz ist am Zug, dann sind Z (e3,f5) die möglichen Züge.
Schwarz legt z.B. einen Stein auf e3 und dreht den weissen Stein auf d4 um oder legt einen auf f5 und dreht e5+d5 um.

Eine Brettsituation stelle ich in einem struct mit 2 OWORD's da. Eines für Weiss, das andere für Schwarz. Da wo ein Feld besetzt ist, wird eine 1 eingetragen.

Das QWORD für Schwarz besteht bis auf die BitPositionen 11 und 35 nur aus 0-en.

Der Zuggenerator liefert mir eine Array mit 2 structs zurück, also 2 möglich Züge aus der Sicht von Schwarz!

Mit meinem obigen Ansatz habe ich sehr schnell die Z-Felder gefunden. Also ich habe ein QWORD das überall 0-en hat bis auf die Bitpositionen 21 und 38. Ich weiss schonmal genau wo ich einen Stein hinsetzen muss, aber jetzt muss ich mich trotzdem von bit 1 bis 64 durchhangeln um diese Positionen (21+38 ) zu finden und habe ich dann eine gefunden, dann muss ich noch alle Richtungen (8 Stück) abklappern um die angrenzenden Weissen Steine zu finden und irgendwie finde ich das nicht effizient!!!

Ich muss wohl erstmal ein wenig grübeln