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.
Achso, ich programmiere in C#, konnte aber im System.Security.Cryptography namespace keine geeignete Klasse finden, die eine 64 Bit Hashfunktion hat.
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-function C 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
:
Bearbeitet durch User
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.