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