Hallo,
ich suche für mein Schachprogramm eine Hashfunktion und denke, dass für
diese 64 Bit einigermaßen auseichen sollte.
Um eine eindeutige Bitfolge aus einer Schachstellung zu erhalten gibts
denke ich erstmal 2 Möglichkeiten: Entweder man schreibt alle 64 Felder
hintereinander, und in jedem Feld steht, falls und wenn ja welche Figur
dort steht. Oder man speichert alle möglichen Figuren hintereinander und
zu jeder Figur natürlich noch die jeweilige Position.
Ich denke, dass die erste Wahl nicht so gut ist, da immer auf mindestens
32 Feldern keine Figur steht und die Bitfolge wohl aus unnötig vielen
Nullen bestehen würde.
Bei der zweiten Wahl bräuchte man pro Figur 6 Bit für die Position (64
Felder), ein Bit ob die Figur überhaupt noch auf dem Brett steht und ein
weiteres Bit welches besondere Züge ermöglicht (Rochaderecht bei Turm
und König und die Ermöglichung des En Passant Schlags bei einem Bauern).
Damit wären wir bei 8 Bit pro Figur. Ich denke nicht, dass es viel Sinn
macht dieses Bit für Springer, Läufer und Dame einzusparen, weil 1 Byte
eine undkomplizierte Programmierung und eine schnelle Berechnung zur
Folge haben sollte.
Für jeden Bauern braucht man allerdings noch weitere Bits, da sich
dieser in Springer, Läufer, Turm oder Dame umgewandelt haben kann (das
besondere Zugrechtsbit wird hier nicht mehr gebraucht, allerdings ein
weiteres Bit ob er sich überhaupt umgewandelt wurde. Somit braucht jeder
Bauer nochmal 3 weitere Bit. Um es nicht zu kompliziert zu machen,
könnte man jedem Bauern insgesamt 12 Bit geben, womit sich 2 Bauern 3
Byte teilen.
Somit komme ich auf eine Bitfolge von 16*8+16*12=320 Bit = 40 Byte. Aus
dieser Bitfolge müsste man mit einer geeigneten und schnellen
Hashfunktion den 64 Bit Hashcode erzeugen.
Habt ihr Ideen wie man die primäre Bitfolge besser berechnen könnte? Und
welche Hashfunktion wäre geeignet um aus den 40 Byte einen 64 Bit
Hashcode zu erzeugen? Die Hashfunktion sollte eine geringe
Kollisonswahrscheinlichkeit haben und schnell zu berechnen sein. Gängige
Hasfunktionen geben mindestens 128 Bit zurück.
Hallo,
C Programmierer schrieb:> Für jeden Bauern braucht man allerdings noch weitere Bits, da sich> dieser in Springer, Läufer, Turm oder Dame umgewandelt haben kann (das> besondere Zugrechtsbit wird hier nicht mehr gebraucht, allerdings ein> weiteres Bit ob er sich überhaupt umgewandelt wurde. Somit braucht jeder> Bauer nochmal 3 weitere Bit. Um es nicht zu kompliziert zu machen,> könnte man jedem Bauern insgesamt 12 Bit geben, womit sich 2 Bauern 3> Byte teilen.
muss man, nachdem ein Bauer in eine z. B. Dame umgewandelt wurde,
wirklich noch wissen, dass die Dame früher einmal ein Bauer war? Das war
mir beim Schach spielen eigentlich immer egal.
Mit freundlichen Grüßen
Guido
Guido C. schrieb:> muss man, nachdem ein Bauer in eine z. B. Dame umgewandelt wurde,> wirklich noch wissen, dass die Dame früher einmal ein Bauer war? Das war> mir beim Schach spielen eigentlich immer egal.
Hallo Guido, vielen Dank für deine Hilfe!
Nein, das braucht man nicht zu wissen. Trotzdem werde ich natürlich den
Speicherplatz des alten Bauern verwenden, in dem bereits die
Positionsbits und das Lebensbit vorhanden sind. Somit bekomm ich die
Information, dass es mal ein Bauer war ja quasi geschenkt.
1 Bit gibt an, ob es überhaupt noch ein Bauer ist, zwei weitere Bits
geben an, in welche Figur er sich verwandelt hat. Sollte das "IstBauer"
Bit gesetzt sein werden die "WelcheFigur" Bits einfach ignoriert. Was
man vielleicht noch machen könnte, ist das "BesonderesZugrecht" Bit als
eines der "WelcheFigur" Bits verwenden, sofern der Bauer sich bereits
umgewandelt hat.
Somit könnte man dann noch 1 Bit sparen und käme auf 10 Bit pro Bauer,
womit sich je 4 Bauern auf 5 Byte aufteilen können und sich somit die 40
Byte auf 36 Byte reduzieren. Ich bezweifle aber, dass dieses
Zusammenquetschen noch so viel Sinn ergibt, da es ja auch mit einiger
Rechenzeit verbunden sein dürfte. Diese 36 bzw 40 Byte werden danach ja
sowieso zu 64 Bit zusammengehasht, werden also nur temporär gebraucht.
Ich bin sogar am überlegen in die andere Richtung zu gehen und einfach
jedem Bauern 2 Byte zu spendieren womit die primäre Bytefolge 48 Byte
groß wäre. Ich denke, dass es in der Mitte, also mit 40 Byte die beste
Lösung sein sollte.
Verschwender :-) Es gibt nur 2 x 10^43 legale Stellungen. Bzw. 2^141 --
Du kommst mit 18 Byte aus.
Das Git benutzt einfach 7 bis 8 Zeichen eines SHA als eindeutigen
Hashwert. Falls du 64Bit benutzt, da mit es mit ausreichender
Wahrscheinlichkeit Eindeutig wird -- In der Diskussion zum Git
nachschauen. Die haben bestimmt ausdiskutiert, ob man wirklich 160 Bit
berechnen muss, wenn man nur 50 verwendet.
Noch einer schrieb:> In der Diskussion zum Git> nachschauen. Die haben bestimmt ausdiskutiert, ob man wirklich 160 Bit> berechnen muss, wenn man nur 50 verwendet.
Hallo Noch einer,
welche Diskussion zum Git meinst du? Unter Git habe ich einerseits die
Software zur verteilten Versionsverwaltung von Dateien gefunden,
andererseits eine nicht so vielversprechende Seite namens
http://gitchess.com/.
Verteilte Versionsverwaltung.
Deren Problem: Es gibt keine zentrale Stelle für die Vergabe von Namen
für die Patches. Die verlassen sich darauf, dass die dezentral erzeugten
Hashwerte eindeutig sind. Aus irgendwelchen Gründen berechnen die zuerst
160 Bit, obwohl die der Meinung sind 50-60 Bit ergeben einen eindeutigen
Schlüssel.
C Programmierer schrieb:> und die Ermöglichung des En Passant Schlags bei einem Bauern
Das En-Passant-Schlagen benötigt zwei Bit (außer bei Randbauern), da in
einer gegebenen Stellung, ohne den bisherigen Spielverlauf zu
betrachten,
das Schlagen nach der einen oder der anderen Seite möglich sein könnte
(wenn also jeweils links und rechts neben dem fraglichen Bauern ein
gegnerischer Bauer steht). Bei Bauern könnte man aber auch einige Bits
für die Position zweckentfremden, da er ja nicht auf einer der
Grundreihen stehen kann.
Gruß, Freibauer
C Programmierer schrieb:> Um eine eindeutige Bitfolge aus einer Schachstellung zu erhalten gibts> denke ich erstmal 2 Möglichkeiten: Entweder man schreibt alle 64 Felder> hintereinander, und in jedem Feld steht, falls und wenn ja welche Figur> dort steht. Oder man speichert alle möglichen Figuren hintereinander und> zu jeder Figur natürlich noch die jeweilige Position.
Die zweite Methode hat den Nachteil, dass zwei gleiche Stellungen zu
unterschiedlichen Bitfolgen führen können, so dass die Vorteile der
Verwendung von Hash-Tables nicht ganz voll zum Tragen kommen.
> Ich denke, dass die erste Wahl nicht so gut ist, da immer auf mindestens> 32 Feldern keine Figur steht und die Bitfolge wohl aus unnötig vielen> Nullen bestehen würde.
Das macht doch nichts:
Dur kodierst jeden der 12 verschiedenen Steine als 4-Bit-Zahl. Die 4
verbleibenden Codes repräsentieren leere Felder. Somit trägt jedes der
Leerfelder sogar noch 2 Bit Extrainformation. Da es mindestends 32
Leerfelder gibt, hast du 64 Bit übrig, von denen du (1+1+8)·2=20 Bits
für die Rechte zur großen und kleinen Rochade und En-Passant, jeweils
für Weiß und Schwarz, brauchst. Die ungenutzten 44 Bits setzt du auf 0.
Damit brauchst du 32 Byte zur Speicherung einer Stellung, das sind
deutlich weniger als bei deiner Lösung.
Wenn die die Kodierung von Rochade und En-Passant in den Leerfeldern zu
kompliziert ist, kannst du die En-Passants auch direkt in die Felder mit
den Bauern mit hineinpacken, indem du zwei verschiedene Typen von Bauern
definierst (mit oder ohne En-Passant-Recht), so dass es dann 14 statt 12
verschiedene Steine gibt, die sich zusammen mit dem Leerfeld immer noch
in 4 Bit kodieren lassen. Für die 4 möglichen Rochaden brauchst du dann
allerdings 4 zusätzliche Bits bzw. 1 zusätzliches Byte, insgesamt also
33 Bytes.
Eine geeignete Hash-Funktion, die die 32, 33 bzw. 40 Bytes in einen 32-
oder 64-Bit-Wert überführt, findest du bspw. im Quellcode der Hashmap-
Klasse von C++, C# oder Java. Auch in Python-Quellcode wirst du fündig
werden, da dort jeder Zugriff auf Objektelemente per Hash geschieht.
Diese Hashes sind im Gegensatz zu kryptographischen Hashes nicht auf
Sicherheit, sondern auf Geschwindigkeit getrimmt, was dir bei deinem
Schachprogramm entgegenkommen wird.
Hier hat übrigens jemand den Quellcode der string_hash-Funktion von
Python gepostet:
http://stackoverflow.com/questions/2070276/where-can-i-find-source-or-algorithm-of-pythons-hash-functionC Programmierer schrieb:> C Programmierer
Wieso schreibst du als C-Programmierer das Schachprogramm in C#? Bei
einem Schachprogramm kommt es doch fast auf jeden Taktzyklus an, dachte
ich ;-)
Bietet dir C# Features, die die Programmierung so sehr vereinfachen,
dass du mit den Effizienzeinbußen (auch wenn sie nicht allzu heftig sein
werden) leben kannst?
Freibauer schrieb:> Das En-Passant-Schlagen benötigt zwei Bit (außer bei Randbauern), da in> einer gegebenen Stellung, ohne den bisherigen Spielverlauf zu> betrachten,
Ich würde die En-Passant-Information nicht auf den schlagenden, sondern
den zu schlagenden Bauern beziehen. Dann braucht man nur 1 Bit/Bauer.
Dass En-Passant-Bit für einen Bauern wird also immer dann und nur dann
gesetzt, wenn der letzte Zug ein Doppelschritt dieses Bauern war.
Freibauer schrieb:> Bei Bauern könnte man aber auch einige Bits> für die Position zweckentfremden, da er ja nicht auf einer der> Grundreihen stehen kann.
Das war offensichtlich etwas zu optimistisch gedacht, mehr als ein
halbes Bit dürfte das wohl nicht bringen.
Gruß, Freibauer
Noch einer schrieb:> Aus irgendwelchen Gründen berechnen die zuerst> 160 Bit, obwohl die der Meinung sind 50-60 Bit ergeben einen eindeutigen> Schlüssel.
Danke! Ich denke der Grund dafür könnte sein, dass Speicherplatz einfach
nichts kostet und der Hashcode nur sehr selten berechnet wird.
Freibauer schrieb:> Das En-Passant-Schlagen benötigt zwei Bit (außer bei Randbauern), da in> einer gegebenen Stellung, ohne den bisherigen Spielverlauf zu> betrachten,> das Schlagen nach der einen oder der anderen Seite möglich sein könnte> (wenn also jeweils links und rechts neben dem fraglichen Bauern ein> gegnerischer Bauer steht).
Wie Yalu nach dir schreibt, wird das En Passant Bit bei dem zu
schlagenden Bauern gespeichert. Und es lässt sich auch kein halbes und
auch kein viertel Bit einsparen, da ich spätestens nach der Umwandlung
alle Positionsbits brauche. Ein Bauer braucht leider auf jeden Fall mehr
als ein Byte, somit hab ich für ihn sowieso noch genug Bits zur
Verfügung.
Yalu X. schrieb:> Die zweite Methode hat den Nachteil, dass zwei gleiche Stellungen zu> unterschiedlichen Bitfolgen führen können, so dass die Vorteile der> Verwendung von Hash-Tables nicht ganz voll zum Tragen kommen.
Das stimmt.
Allerdings habe ich alle meine Figuren sowieso schon in einem Array
drin. Eine unterschiedliche Bitfolge würde vorkommen, wenn zwar die
gleichen Figuren auf dem Brett stehen jedoch nicht dieselben. Also wenn
z.B Turm_1 auf Feld A steht, Turm_2 auf Feld B oder eben Turm_1 auf B
und Turm_2 auf A. Dies würde aber im Vergleich zu den sonstigen selben
Stellung sehr, sehr selten zutreffen. Ein Beispiel: Um alle 4 Springer
nach 2 Zügen von der Startposition in die Mitte zu setzen gibt es schon
4 Möglichkeiten, wenn man jetzt noch 2 Züge dazu nimmt könnte jeder
Springer auf ein Feld und wieder zurückspringen, die beiden Türme
könnten auch schon das gleiche machen, sodass ich auf die schnelle nicht
mehr ausrechnen kann, wie oft ich in diesem kleinen Beispiel schon die
gleiche Stellung immer wieder neu bewerten müsste. Bis hierhin dürfte es
sogut wie noch nie möglich gewesen sein, dass sich 2 gleiche, aber nicht
2 selbe Stellungen ergeben.
Dennoch sollte ich naürlich versuchen, auch diese wiederholende
Stellungsbewertung zu vermeiden.
Yalu X. schrieb:> Dur kodierst jeden der 12 verschiedenen Steine als 4-Bit-Zahl. Die 4> verbleibenden Codes repräsentieren leere Felder. Somit trägt jedes der> Leerfelder sogar noch 2 Bit Extrainformation. Da es mindestends 32> Leerfelder gibt, hast du 64 Bit übrig, von denen du (1+1+8)·2=20 Bits> für die Rechte zur großen und kleinen Rochade und En-Passant, jeweils> für Weiß und Schwarz, brauchst. Die ungenutzten 44 Bits setzt du auf 0.
Entweder kann ich dir nicht ganz folgen, oder du hast dich vertan. Aber
ich verstehe natürlich worauf du hinaus willst. Es gibt erstmal 13
verschiedene "Figuren". Deine 12 genannten plus die "leeres Feld"-Figur.
Das heißt man hätte theoretisch noch 64*3 freie Möglichkeiten in den 32
Byte, also 192 Möglichkeiten was theoretisch etwa 7,58 Bit sind. Nun
kann man sich zunutze machen, dass eine Rochaderechtsbit nur auf der
Grundreihe sein kann, während Bauern nie auf einer Grundreihe stehen
können. Ein Rochaderecht auf der A und H Reihe ist immer ein Turm, auf
der E Reihe immer ein König.
Somit brauche ich nur 2 der 3 verbliebenen Codes:
Code 1: Weiße Figur mit besonderem Zugrecht (je nach Position kann auf
die Figur zurückgeschlossen werden)
Code 2: Code 1, dasselbe in schwarz.
Damit käme man auf 32 Byte und müsste noch irgendwo verstecken, wer dran
ist. Da könnte ich zum Beispiel sagen, wenn freie Felder den Code 0x00
haben, dann ist weiß dran, wenn freie Felder den Code 0x01 haben, dann
ist schwarz dran.
Und obwohl sich diese Lösung so toll anhört weiß ich nicht, ob es
wirklich die bessere ist. Einen Vorteil durch eine kurze primäre
Bitfolge gibt es meines Erachtes sogut wie garnicht, auch da sich ein
Hashcode idR sehr schnell berechnen lässt. Der einzige wirkliche Vorteil
liegt darin, dass 2 gleiche Stellungen nicht unterschiedliche Bitfolgen
haben können. Ich werde denke ich beide Optionen mal ausprobieren um zu
sehen, welche davon die schnellere ist.
Yalu X. schrieb:> Wieso schreibst du als C-Programmierer das Schachprogramm in C#? Bei> einem Schachprogramm kommt es doch fast auf jeden Taktzyklus an, dachte> ich ;-)>> Bietet dir C# Features, die die Programmierung so sehr vereinfachen,> dass du mit den Effizienzeinbußen (auch wenn sie nicht allzu heftig sein> werden) leben kannst?
Ich habe das Spiel in 2011 programmiert um objektorientierte
Programmierung richtig zu verstehen und C# zu lernen (die Beispiel aus
der Literatur mit "Eine Kuh gibts Milch" (falls du sie kennst) waren mir
einfach zu praxisfern). Und auch entgegen meiner Erwartung ist C#
komischerweise teilweise schneller als C++.
Ein enormer Vorteil von C# ist natürlch auch, dass man sich eine
Beenutzeroberfläche mit ein paar geklauten Bildern von google mal eben
zusammenklicken kann. Und das Konzept der objektorientierten
Programmierung hilft mir hier auch weiter, als dieses alles per Hand in
C zu programmieren.
Vielen Dank an alle für die Hilfe!
C Programmierer schrieb:> Und das Konzept der objektorientierten> Programmierung hilft mir hier auch weiter, als dieses alles per Hand in> C zu programmieren.
Wobei der aktuelle Trend ja wohl dahin geht, Objektorientierte
Programmierung nur noch als ein Paradigma unter Vielen anzusehen und es
wenn möglich eher zu vermeiden. Und für Schach wird man OOP nicht
wirklich benötigen. Ihr könnt ja mal
http://spf13.com/post/is-go-object-oriented/
lesen, das fand ich ganz interessant.
Stefan Salewski schrieb:> Wobei der aktuelle Trend ja wohl dahin geht, Objektorientierte> Programmierung nur noch als ein Paradigma unter Vielen anzusehen und es> wenn möglich eher zu vermeiden. Und für Schach wird man OOP nicht> wirklich benötigen.
Der Trend ist wohl an mir vorbeigegangen, wobei ich beruflich auch kein
PC-Programmierer bin.
Aber sofern es sich nicht um Kleinstprogramme handelt würde ich immer
die objektorientierte der funktonsorientierten Programmierung vorziehen.
Und natürlich benötigt man die OOP nicht für Schach, aber ich denke
schon, dass es das ganze einfacher macht.
C Programmierer schrieb:> Entweder kann ich dir nicht ganz folgen, oder du hast dich vertan. Aber> ich verstehe natürlich worauf du hinaus willst. Es gibt erstmal 13> verschiedene "Figuren". Deine 12 genannten plus die "leeres Feld"-Figur.> Das heißt man hätte theoretisch noch 64*3 freie Möglichkeiten in den 32> Byte, also 192 Möglichkeiten was theoretisch etwa 7,58 Bit sind.
Es gibt 12 "echte" und 4 verschiedene "Leerfiguren". Bei 32 Leerfeldern
gibt es also 4**32=2**64 verschiedene Möglichkeiten, sie mit Leerfiguren
zu belegen. Das entspricht einem Informationsgehalt von 64 Bit.
> Und obwohl sich diese Lösung so toll anhört weiß ich nicht, ob es> wirklich die bessere ist. Einen Vorteil durch eine kurze primäre> Bitfolge gibt es meines Erachtes sogut wie garnicht, auch da sich ein> Hashcode idR sehr schnell berechnen lässt.
Sehe ich das richtig, dass in deiner Hash-Table die Keys nicht die
Bitfolgen der Stellungen, sondern die 64-Bit-Hashes sind? Die Hashes für
die Adressierung der Buckets wären dann jeweils ein Teil der
64-Bit-Hashes (bspw. deren niederwertige 24 Bit)?
Da die Bitfolgen in diesem Fall nicht in der Tabelle gespeichert werden,
spielt deren Größe tatsächlich keine große Rolle. Ich hatte dich erst so
verstanden, dass du die Länge der Bitfolgen optimieren möchtest, um
Speicher zusparen.
Yalu X. schrieb:> Es gibt 12 "echte" und 4 verschiedene "Leerfiguren". Bei 32 Leerfeldern> gibt es also 4**32=2**64 verschiedene Möglichkeiten, sie mit Leerfiguren> zu belegen. Das entspricht einem Informationsgehalt von 64 Bit.
Stimmt.
Yalu X. schrieb:> Sehe ich das richtig, dass in deiner Hash-Table die Keys nicht die> Bitfolgen der Stellungen, sondern die 64-Bit-Hashes sind?
So war mein Plan.
Yalu X. schrieb:> Die Hashes für> die Adressierung der Buckets wären dann jeweils ein Teil der> 64-Bit-Hashes (bspw. deren niederwertige 24 Bit)?
Ich hab noch nie mit Hashtabellen gearbeitet, Ich wusste garnicht, dass
es überhaupt einen Unterschied zwischen Keys und Buckets gibt. Wieder
was dazugelernt.
Yalu X. schrieb:> Da die Bitfolgen in diesem Fall nicht in der Tabelle gespeichert werden,> spielt deren Größe tatsächlich keine große Rolle. Ich hatte dich erst so> verstanden, dass du die Länge der Bitfolgen optimieren möchtest, um> Speicher zusparen.
Richtig. Ich möchte einen 64 Bit Key haben, um nicht zu viel Speicher zu
verbauchen. Das gute ist, dass .NET bereits eine Hashtable-Klasse zur
Verfügung stellt und ein Objekt als Key erwartet. Somit kann ich beide
Optionen mit wenigen Quellcodeänderungen testen.
Nochmals danke an alle für die Hilfe!
Freibauer schrieb:> Das En-Passant-Schlagen benötigt zwei Bit (außer bei Randbauern), da in> einer gegebenen Stellung, ohne den bisherigen Spielverlauf zu> betrachten,Yalu X. schrieb:> Ich würde die En-Passant-Information nicht auf den schlagenden, sondern> den zu schlagenden Bauern beziehen.
ich würde entweder ein separates Leerfeld definieren, was einen gültigen
en-Passant-Zielfeld darstellt (darduch werden automatisch der zu
schlagende bauer (nämlich der hinter diesem feld), als auch die
potentiellen Schläger (alle NAchbarbauern, die auf dieses Feld schlagen
dürften) eindeutig beschrieben.
Die Rochade würde ich durch einen eigenen Turm-Typ definieren.
damit hätte man 16 verschiedene figuren. Im einfachsten Fall braucht man
also 32 Byte.
man könnte diesen Figuren aber noch eine zur Häufigkeit umgekehrt
propotional lange bitfolge zuordnen, zb:
typ cnt bits initialer verbrauch
---------------------------------------------
felder 64 1 32
w_bauern 8 010 24
s_bauern 8 001 24
w_läufer 2 01110 10
s_läufer 2 00011 10
w_spring 2 00001 10
s_spring 2 00010 10
w_turm 2 01101 10
s_turm 2 01111 10
w_könig 1 000001 6
s_könig 1 011000 6
w_dame 1+ 000000 6
s_dame 1+ 0110011 7
felder_e 1 0110010 0
initial ergibt sich eine summe von 165 bits + je 2 bits pro spieler um
festzulegen mit welchem Turm noch eine Rochade möglich ist.
En-Passant-Felder kann es maximal eins pro zug geben, so dass 6
zusätzliche Bits reserviert werden müssen.
Möglicherweise gibt es moch klevere Verteilungen. Was ich auch versucht
hatte, war ein Rochade-Turm-Symbol einzuführen, aber das hat in Summe
mehr gekostet, weil ein (eins reicht, weil es nur 4 gültige postionen
gibt, die eindeutig zuzuordnen sind) zusätzliches symbol hätte kodiert
werden müssen,
Reichen also 22Byte für das komplette spielfeld. Es sei denn durch sehr
ungünstige Konstellationen kann das spiel so laufen, das viele Bauern
durch Damen ersetzt werden, ohne dass andere Figuren genug Platz
freimachen ;-)
Um aus so einem Bitstrom einen Hash zu machen, würde ich das aber noch
irgendwie verwursten und nicht einfach die ersten n-Bits benutzen, sonst
gibt es ziemlich viele Kollisionen
