Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Bitboard
gerd8888 - Fr 22.11.13 19:25
Titel: Bitboard
hallo,
ich will meine brettdarstellung auf bitboards umstellen. (Die sollen schneller sein) Gibt es dazu vielleicht ein kleines Demo-Beispiel wie z.B. Vier gewinnt oder aehnliches, das ich mir mal anschauen koennte?
gerd8888 - Sa 23.11.13 13:06
Im Wesentlichen interessieren mich 2 Sachen:
0 0 0 0 0 1 0 1
Wenn ich die 6. Position auslesen will. Wie macht man das. Ich will wissen ob sich an einer bestimmen Position eine 1 oder eine 0 befindet.
Wie bekommt man schnell an eine Position mit aller 1 en?
Und die 2 Frage, was schneller ist. Ein Bitverschiebung oder wenn man ein zweites Bit miteinander verknuepft.
ub60 - Sa 23.11.13 14:26
 gerd8888 hat folgendes geschrieben  : |
Wenn ich die 6. Position auslesen will. Wie macht man das. |
Wenn DU die Positionen im Byte so zählst: 76543210, dann etwa so:
Delphi-Quelltext
1:
| if (DeinByte AND 01000000)=01000000 then ... |
| gerd8888 hat folgendes geschrieben : |
Wie bekommt man schnell an eine Position mit aller 1 en?
|
Meinst Du 8 Einsen in einem Byte (=255) oder 8 aufeinanderfolgende Einsen in einem Stream?
| gerd8888 hat folgendes geschrieben : |
Und die 2 Frage, was schneller ist. Ein Bitverschiebung oder wenn man ein zweites Bit miteinander verknuepft.
|
Das ist schon die 3. Frage :wink:
Aber konkret: Ein zweites Bit willst Du mit was verknüpfen. Erkläre Dein Problem doch besser mal an einem Beispiel.
gerd8888 - Sa 23.11.13 15:57
Ich glaube ich habe es verstanden. Das mit der Position brauche ich ja auch nicht, da die Leerfelder auch ein Bitboard darstellen.
Ich schreibe jetzt das Programm, und wenn es fertig ist werde ich das hier vorstellen.
Besten Dank.
gerd8888 - Sa 23.11.13 16:38
wenn ich jetzt ein byte var b:byte habe und sage b:=7
aber ich möchte das so machen, dass ich in b:=00000111 (direkt in die speicheradresse reinschreibe)
wie macht man das?
und wie kann ich b:=7 auslesen, dass ich 00000111 bekomme ?
Gerd
WasWeißDennIch - Sa 23.11.13 17:09
Du verwechselst da etwas: 7 = 7, es gibt nur unterschiedliche Darstellungen (binär, oktal, dezimal, hexadezimal, etc.). Wenn Du also der Variablen b die Zahl 7 in dezimaler Schreibweise zuweist, dann enthält sie auch 7. Dasselbe, wenn Du das in hexadezimaler Schreibweise tust ($07).
gerd8888 - Sa 23.11.13 18:17
Ich versuche mein Problem darzustellen.
Ich arbeite mit einem int64 (8 byte) (64 bit) (Schachbrettgroesse)
Bei der Zahl 7 koennte ich die Binaerzahl leicht herausbekommen, indem ich immer durch 2 dividiere.
Bei der int64 habe ich das Problem, das die Zahl in den Minus-Bereich kommt.
Was ich letztendlich will ist folgendes:
Die 64 Bit (int64):
00100000001000 ... (dann folgen bis zur 64. Stelle nur 0 en)
Jetzt habe ich diese Zahl mit 2 "1" von denen ich ahnungslos bin, wo sie sind und wieviele es sind und will das an der 3. Stelle um 2 nach rechts Verschieben also
00001000001000 ...
und die 2 "1" auch um 2 verschieben, so:
00100000000010 ...
Wie will ich suchen, wenn mir die int64 Zahl unbekannt ist?
1000000.... (Dezimalzahl?, die ich fuer die Suche brauche)
0100000....
0010000....
usw
Und dann noch die Frage, wie ich das am schnellsten verschiebe. Mit slr duerfte das mit 2 "1"en nicht gehen??
Ich will also in einem int64 die "1" aufsuchen und um 2 nach rechts verschieben, aber nicht beide gleichzeitig.
Horst_H - Sa 23.11.13 18:57
Hallo,
bei Bitboard geht es um die Moeglichkeit moeglichst schnell Stellungen auf Sieg zu pruefen.
Insbesondere bei Verwendung bei 4 Gewinnt von 64 Bit Zahlen.
Ich stelle das mal dar:
Bei 4 gewinnt wirft man die Steine spaltenweise in ein Gestell/Spielfeld mit 7 Spalten und 6 Zeilen ein.Damit waere es anschaulich, diese auch so zu speichern.
Auf Bitebene waeren also 7 Byte mit belegten Bits fuer die Zeilen 0..5
Ein Spielfeld haette damit 7 Byte, fuer den Computer optimal sind aber 8 Byte = 64 Bit, also laesst man dieses eine Byte immer auf 0.
Jeder Spieler verwaltet so ein Spielfeld fuer sich mit den nur von ihm belegten Feldern und die Vereinigungsmenge beider ergibt das tatsaechliche Spielfeld oder wird zusaetzlich verwaltet.
Man erstellt alle moeglichen Anordnungen von 4 in einer Reihe als Bitmasken
Spalte 0..3/Zeile = 0 waere dann ( 2 hoch 0 = 1 )
0|0|0|0|1|1|1|1| = 16843009dez = 0x0000000001010101 (hex)
Spalte 0..3/Zeile = 5 waere dann ( 2 hoch 5 = 32 )
0|0|0|0|32|32|32|32| = 538976288dez = 0x0000000020202020
das sind 69??? verschiedene ( horizontal = 6*4,vertikal 3*7, links steigende diagonalen 3*4 und rechts steigende Diagonalen 3*4,forum softgames/developia gibt es scheinbar nicht mehr. TGGC und hamsterofdeath aegerten sich wie so oft...)
Ein Test, ob man gewonnen hat waere also ein Vergleich darauf, ob ein logisches UND mit der Maske, die Maske selbst ergibt.
IF Maske[i] AND MeinSpielfeld = Maske[i] then
gewonnen :-)
Man testet aber nicht mit allen Masken, sondern nur mit denen die fuer das Feld, in das man den letzten Stein geworfen hat, gelten.
Grusz Horst
P.S.
BitTest,BitSet und BitClear gibt es sicher in tausend Varianten.Hier mal pascal.
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:
| const
EinsInt64 : Int64 = 1;
function Bittest (TestZahl : int64,Bitnr: integer):boolean;
begin
result := TestZahl AND (EinsInt64 shl BitNr) <> 0;
end;
procedure BitSet(var TestZahl : int64,Bitnr: integer);
begin
TestZahl := TestZahl OR (EinsInt64 shl BitNr);
end;
procedure BitClear(var TestZahl : int64,Bitnr: integer);
begin
TestZahl := TestZahl AND NOT(EinsInt64 shl BitNr);
end; |
Hidden - Sa 23.11.13 19:36
Hallo Gerd,
Bitboards hatte ich mir vor einiger Zeit auch angeschaut (der Wikipedia-Artikel zu dem Thema ist ziemlich gut, da steht eigentlich alles drin was man braucht
*klick* [
http://de.wikipedia.org/wiki/Bitboard]). Letztendlich habe ich
ein anderes Verfahren (0x88 Methode) [
http://en.wikipedia.org/wiki/Board_representation_%28chess%29#0x88_method] genommen, mit dem es sehr leicht wird zu prüfen ob ein Zug das Brett verlassen würde (z.B. für Springer sehr wichtig): Neben dem Spielfeld wird ein zweites, virtuelles, Brett positioniert und die 128 Felder beider Bretter werden nummeriert. Dann läuft ein Zug, der das eine Brett verlässt, automatisch auf das andere. Außerdem ist es möglich, mit elementaren bitweisen Operationen herauszufinden auf welchem Brett ein Feld liegt und was seine Koordinaten sind.
Möglicherweise kann man auch beide Verfahren in einem Programm verwenden und zusätzlich Bitboards für Tabellen-lookups haben?
lg,
Daniel
gerd8888 - Sa 23.11.13 21:04
Hallo Horst,
habe gerade mal die bitset und bitclear getestet und funktioniert einwandfrei.
Ich dachte mir, dass ich mir die (Bitmaske := 1 shl BitNr;) durch konstante Zahlen ersetzten muss.
Wuerde immerhin auch die Bitverschiebung einsparen. Aber ich glaube, dass die so schnell ist, dass das so gut wie keine Zeit kostet.
Das war wirklich sehr hilfreich.
So wie es im Wikipedia-Artikel zu lesen ist, genau so habe ich es mir auch vorgestellt. Ich mache ein brett_w[1..6 (Figurentypen) ] of int64 und
ein brett_s[1..6] of int64 und ein leerfeld: int64. Die 0x88 Methode habe ich nicht ganz verstanden. Aber es hat natürlich einen Vorteil, wenn
man das Brett kopiert, insbesondere wenn man einen Zug zuruecknimmt. Wenn ich das richtig verstanden habe hat man ein brett:array[1..8] of byte ?
Martok - So 24.11.13 01:26
Kann ich so nicht bestätigen. Was hast du für ein Delphi? Das hier funktioniert in D7 akkurat...
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
| var
x: int64;
begin
x:= $A292888868222949; Assert((x and (Int64(1) shl 61)) <> 0);
Assert((x and (Int64(1) shl 29)) <> 0);
x := x and not (Int64(1) shl 61);
Assert((x and (Int64(1) shl 61)) = 0);
Assert((x and (Int64(1) shl 29)) <> 0); |
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!