www.mikrocontroller.net

Forum: PC-Programmierung 4 Gewinnt Hashcode kollision


Autor: Sam .. (sam1994)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hi

Ich programmiere gerade ein 4 Gewinnt Spiel. Die KI ist schon recht gut, 
aber mein Ziel wäre es am Ende eine ziemlich unschlagbare KI zu 
programmieren. Bisher rechnet sie mit Minimax + Hashtable. Durch die 
Hashtables anleine konnte das Prog bei schnellem Ziehen 2 Halbzüge 
weiter rechnen. Später kommt noch Alpha-Beta Algo dazu.

Ich merkte vor kurzem folgendes: Wenn ich die Steine immer auf die 6 
Spalte fallen lasse, setzt der Com immer in der Mitte. Und wenn ich drei 
Steine habe, setzt er auch den dritten in der Mitte. Die Bewertung nach 
meinem 4-er-Block ist -6! Das kann nur eine Hashkollision sein. Wenn ich 
den ganze Zeug ausschalte, setzt er schon nach dem 2. Stein seinen 
darauf.

Problem ist: Ich brauche eine bessere GetHashCode Funktion!

Meine sah bisher so auf:
#define FIELD_W 7
#define FIELD_H 6

#define FAKTOR ((int)pow(2,FIELD_H))
//[...]
unsigned int _4Gewinnt::GetHashCode()
{
    unsigned int hash = 0;
    for(int x = 0, multi = 1; x < FIELD_W; x++, multi *= FAKTOR)
    {
        for(int y = 0, z = 1; y < FIELD_H; y++, z *= 2)
            hash += ((field[x][y] + 1) / 2) * z  * multi;
    }
    return hash;
}

Idee ist folgende: Das Feld wird binär in dargestellt. Es gibt aber noch 
einen Überlauf. Ich dachte der macht aber nichts aus, da die 
Unterschiede beim Überlauf recht groß sein müssten. Da habe ich mich 
wohl getäuscht.

Nun habe ich alles durch unsigned long ersetzt nichts.
Habe ich mich nun doch geirrt. Warum funktioniert es aber dann ohne 
Hashtable?

Ich weiß nicht was ich falsch gemacht habe. Vielleicht kann mal jemand 
über meinen Code schauen.

Wenn es jemand allerdings kompilieren möchte braucht er Allegro4. Am 
Einfachsten bekommt man das über die Updatefunktion von DevC++.

Danke für eure Antworten!

PS: Und zum Spielen sollt man lieber den HTabel ausschalten.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hast du mal mit einem Debugger die Werte angesehen, die deine
Hashfunktion produziert?

In der inneren Schleife beginnt z bei 1, und wird
jeweils verdoppelt.
Binär ist es also eine 1 mit einer wachsenden Anzahl
Nullen dran.
D.h. nach ein paar Durchläufen führt das hash += ... zu keinen
neuen Werten mehr.
So ändern ab einem bestimmten y die Feldlemente nicht mehr
die Hashfunktion, nur die ersten gehen in das Ergebnis ein.

Diese Hashfunktion erscheint mir dadurch etwas suboptimal.

(Auch wenn ich das ganze Programm nicht verstanden habe,
und mir auch gar nicht antun will.)

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zumal ich mich auch frage was das bringen soll, ein Hash macht doch nur 
für eine schnelle Suche Sinn, sind die Eingabewerte aber eh Zahlen und 
dürfen Kollisionen nicht auftreten dann kann man doch gleich die Zahlen 
nutzen um einen Index in eine Look-Up Tabelle daraus zu generieren...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:
> Zumal ich mich auch frage was das bringen soll, ein Hash macht doch nur
> für eine schnelle Suche Sinn,

Ich hab mir sein Programm angesehen.
An dieser Stelle macht der Hash schon Sinn.

es geht darum, dass seine Funktion zur Bewertung einer "Stellung" 
aufwändig ist. Die Bewertung an sich will ich nicht weiter kommentieren, 
das wird schon seine Richtigkeit haben und das ist durchaus einiges an 
Aufwand für den Rechner.

Der Hashcode selber ist daher einfach nur eine Zahl, die eine bestimmte 
Stellung codiert. Dasselbe Bild an eingeworfenen Steinen -> dieselbe 
Hashzahl. Und mit dieser Hashzahl kann er dann aus der std::map die 
bereits berechnete Bewertung abrufen anstatt sie erneut auszurechnen.

> sind die Eingabewerte aber eh Zahlen und
> dürfen Kollisionen nicht auftreten dann kann man doch gleich die Zahlen
> nutzen um einen Index in eine Look-Up Tabelle daraus zu generieren...

Das Problem ist, dass es verdammt viele mögliche 'Stellungen' gibt. Auf 
Anhieb ist es mir nicht gelungen eine exakte Formel dafür abzuleiten, 
sondern nur eine Abschätzung. Und ich gestehe: Ich war erstaunt wie hoch 
das ging

Was er braucht ist ein Schema, mit dem er jedes überhaupt mögliche Bild 
an eingeworfenen Steinen in einer Zahl abbilden kann.

Ich hab mir da schon was überlegt, aber es erscheint mir sehr aufwändig 
zu sein. Das Problem: Pro Position bräuchte man ein ternäres Bit für: 
Spieler A, Spieler B, leeres Feld.
Allerdings gibt es ja noch einen Zusatz: leere Felder können nicht 
einfach irgendwo auftreten.
Mann kann daher jede Spalte so in einer einzigen "Zahl" 
charakterisieren:
* Anzahl von Steinen belegten Feldern
* Genau diese Anzahl an Bits, 0 bedeutet Spieler A, 1 bedeutet Spieler B

Da es pro Spalte 7 Positionen gibt, reichen für die Anzahl 3 Bits. Für 
eine vollständige Spalte könnte man daher 10 Bits benutzen (wenn man 
eine konstante Bitanzahl haben will, die restlichen Bits sind 0 für die 
leeren Felder)

  0   1   2     3     4     5     6     7     8     9

  0   1   1     0     1     0     0     0     0     0

  |       | Stein   Stein Stein
   Anzahl     1       2     3
   Spielsteine

das wären also: In dieser Spalte gibt es 3 Spielsteine: 0 1 0,
also Spieler A, B, A  und die darüberliegenden Positionen der Spalte 
sind leer. Das wäre zb eine andere Spaltensituation als

 1   0   0     0     1     0     0     0     0     0

da wären 4 Steine: A, B, A, A


Für 6 komplette Spalten bräuchte man daher 60 Bits, wenn mann alles 
dicht an dicht packt. Das ginge sich in einem 64 Bit long gerade noch 
aus.

(Und deswegen hab ich auch noch nichts gesagt: Die Funktion ist nämlich 
zu komplex als das ich sie aus dem Ärmel schütteln könnte)

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja aber die Informationsdichte ist halt so hoch, wenn man zuwenig Bits 
nimmt kommt es halt zwangsläufig zu Kollisionen.

Ich hätte das auch eher als Baum codiert, da kann er sich dann auch 
seine schon berechneten Züge ablegen.
Aber sinnvoll ist das doch auch nur wenn das statisch hinterlegt ist, da 
jede "Stellung" ja in einer Partie nur einmal auftreten kann.

Karl heinz Buchegger schrieb:
> An dieser Stelle macht der Hash schon Sinn.
Ja ein "Hash" an sich macht schon Sinn, ich meinte eher sich "irgenwie 
durch ein bischen Multiplizieren, addieren und hoffen das es keine 
Kollisionen gibt"-Hashfunktion ;)

BTW: Wenn der PC zu gut ist wirds langweilig, weil immer der Spieler 
welcher anfängt gewinnt oder wenigstens ein Unentschieden erreichen 
kann. (oder war es umgekehrt?)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:

> Aber sinnvoll ist das doch auch nur wenn das statisch hinterlegt ist, da
> jede "Stellung" ja in einer Partie nur einmal auftreten kann.

Jain.
Die Stellung selber kann schon mehrfach vorkommen. Du darfst ja nicht 
vergessen, dass der Rechner vorausrechnet: Was wäre wenn ich hier 
einwerfe und der Benutzer da und ich wieder hier, ....
Da kann dieselbe Spielsituation in einem Spiel dann schon mehrfach 
auftreten. Auch bei einer Einzelbewertung. Ob ich zuerst bei 3, Benutzer 
bei 5 und ich bei 4 einwerfe, mündet in derselben Stellung wie: ich bei 
4, Benutzer bei 5, ich bei 3. Ab dann sind alle weiteren Analysen für 
noch weiter vorausberechnete Spielsituationen in beiden Fällen 
identisch.

Und offenbar bringt das auch was. Wobei ich nicht weiß, wieviel von dem 
Speedup auf die nicht vollständige Verhashung der Spielsituation 
zurückzuführen ist.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:

> Karl heinz Buchegger schrieb:
>> An dieser Stelle macht der Hash schon Sinn.
> Ja ein "Hash" an sich macht schon Sinn, ich meinte eher sich "irgenwie
> durch ein bischen Multiplizieren, addieren und hoffen das es keine
> Kollisionen gibt"-Hashfunktion ;)

Full ACK.
Das wird gerne unterschätzt. Gute Hash-Funktionen sind nicht banal.
Wobei das was er hat, ja eigentlich kein "Hash" ist. Zumindest nicht in 
dem Sinne, in dem ich Hash-Tabellen gelernt habe.

Er möchte im Grunde ja eine Lookup Tabelle und was er braucht ist eine 
eindeutige Zahl, mit der er exakt eine Spielsituation beschreiben kann. 
Die muss bijektiv sein. Eine Hash-Funktion, wie sie bei Hash-Coding 
eingesetzt wird, ist nicht bijektiv. Sonst gäbe es ja keine Kollisionen 
und man bräuchte keine Kollisionsstrategien :-)

Ich hab auch schon überlegt, ob man nicht eine einfachere Zahl bilden 
könnte und dann an diese Zahl eine Liste der Stellungen anhängen. Beim 
Abfragen, ob man diese Stellung schon bewertet hat, muss man dann eben 
Aufwand treiben und vergleichen, ob nicht nur die Kennzahl 
übereinstimmt, sondern auch noch die dabei gespeicherten Stellungen 
durchgehen, ob es eine davon ist. So wie man es ja auch bei 
Hash-Tabellen macht: Mit der Hashfunktion hat man erst mal nur einen 
(oder mehrere) Kandidaten. Ob das der gesuchte ist, muss seperat geprüft 
werden.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hier nochmal die Idee mit dem "Baum" als 4x4 Beispiel, und nicht alle 
Zweige fortgeführt, aber das Prinzip sollte klar sein.
Ist ein Zug am Ende noch "null" muß er berechnet werden, sonst kann der 
gespeicherte genutzt werden.

Führt nach konstanten 42 Schritten zum gesuchtem Zug, und wer Bäume 
nicht mag, kann den auch vorausberechnen und daraus den benötigten 
Bitvektor bestimmen z.B. mit 00 = leer, 01 = rot, 10 = blau.

Autor: Sam .. (sam1994)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:
> (Auch wenn ich das ganze Programm nicht verstanden habe,
> und mir auch gar nicht antun will.)

Ein 4Gewinnt Spiel. Wenn man die Hash auschaltet und auf 6 Halbzüge 
Rechentiefe stellt ist gewinnen ganz schön schwer. Ich habe erst einmal 
gewonnen, einmal unentschieden gespielt und unzählige Male verloren.

Zum allgemeinen Verständnis:

Das Programm basiert auf der Minimax Methode (wird später durch 
Alpha-Beta ersetzt). Die Bewertungsfunktion ist der schwerste Teil 
(meine Meinung) um einen guten 4Gewinnt Computer zu programmieren. Nun 
möchte ich das ganze noch optimieren. Ziel am Ende wäre es einen 
4Gewinnt-AVR zu entwickeln (ich denke dabei an eine 8*8 dual led 
matrix).

Karl heinz Buchegger schrieb:
> Und offenbar bringt das auch was. Wobei ich nicht weiß, wieviel von dem
> Speedup auf die nicht vollständige Verhashung der Spielsituation
> zurückzuführen ist.

Ja mit der Hashfunktion kann er 2 Halbzüge weiterrechnen, wenn er in 
weniger als 1s ziehen.

Läubi .. schrieb:
> Führt nach konstanten 42 Schritten zum gesuchtem Zug, und wer Bäume
> nicht mag, kann den auch vorausberechnen und daraus den benötigten
> Bitvektor bestimmen z.B. mit 00 = leer, 01 = rot, 10 = blau.

Wenn du mir noch ausrechnest welche Zukunft CPU ich brauche, damit das 
in einer akzeptablen Geschwindigkeit funktioniert, bin ich zufrieden.
4 Gewinnt ist einfach zu komplex um das durchzurechnen. Das geht 
höchstens bei TicTacToe. Ich nutze zurzeit 6 Züge und ich besiege ihn 
fast nicht.

Karl heinz Buchegger schrieb:
> Full ACK.
> Das wird gerne unterschätzt. Gute Hash-Funktionen sind nicht banal.
> Wobei das was er hat, ja eigentlich kein "Hash" ist. Zumindest nicht in
> dem Sinne, in dem ich Hash-Tabellen gelernt habe.
>
> Er möchte im Grunde ja eine Lookup Tabelle und was er braucht ist eine
> eindeutige Zahl, mit der er exakt eine Spielsituation beschreiben kann.

Das stimmt. Das nennt sich aber so. Ich selber habe allerdings noch nie 
damit was gemacht. Minimax und AlphaBeta kannte ich schon.

Mir ist übrigens ein Fehler aufgefallen. Da die Spielsteine als 1, 0 und 
-1 definiert sind richtet (feld+1)/2 Murks an, da -1 und 0 0 ergeben.

Ich muss noch ein bisschen rumprobieren. Eine Hashfunktion für long wäre 
nicht schlecht da passt es noch in den Key rein. Und: Bei 64bit System 
wird es nicht langsamer ausgeführt (hab ich).

Karl heinz Buchegger schrieb:
> Die muss bijektiv sein. Eine Hash-Funktion, wie sie bei Hash-Coding
> eingesetzt wird, ist nicht bijektiv. Sonst gäbe es ja keine Kollisionen
> und man bräuchte keine Kollisionsstrategien :-)

Schau dir mal Schachalgos an. Da gibt es extrem viele. Allerdings sind 
die zu unwahrscheinlich.

Zum Anhang: Ich hab nur ein paar Funktionen hinzugrfügt (Partikel, 
Async-rechnen), aber die Hashfunc ausgeschaltet. Wer mal spielen möchte, 
sollte das hier nehmen.

PS: Das ruckeln am Spielende, liegt an dem vielen Transparenten. Hätte 
ich Allegro5 genommen, wäre das weg. Alleg4 ist im Thema Blending 
einfach langsam.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Samuel K. schrieb:
> Wenn du mir noch ausrechnest welche Zukunft CPU ich brauche, damit das
> in einer akzeptablen Geschwindigkeit funktioniert
Du mußt das doch nicht ausrechnen, trotz allem erhälst du so einen 
kolissionsfreien Hashwert und ich dachte das war dein Ziel?

Autor: Sam .. (sam1994)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:
> Du mußt das doch nicht ausrechnen, trotz allem erhälst du so einen
> kolissionsfreien Hashwert und ich dachte das war dein Ziel?

Ach du meinst eine Art Notation? Das ist leider sehr speicheraufwändig. 
3bit pro Zug * 42 > 15Byte.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Samuel K. schrieb:
> Läubi .. schrieb:
>> Du mußt das doch nicht ausrechnen, trotz allem erhälst du so einen
>> kolissionsfreien Hashwert und ich dachte das war dein Ziel?
>
> Ach du meinst eine Art Notation? Das ist leider sehr speicheraufwändig.
> 3bit pro Zug * 42 > 15Byte.

Genau da liegt das Problem.
Hast du dir das Schema angesehen, das ich weiter oben postuliert habe? 
Das käme mit 8 Bytes pro Stellung aus, ist aber aufwändiger in der 
'Herstellung'

Autor: Sam .. (sam1994)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Genau da liegt das Problem.
> Hast du dir das Schema angesehen, das ich weiter oben postuliert habe?
> Das käme mit 8 Bytes pro Stellung aus, ist aber aufwändiger in der
> 'Herstellung'

Es ist ja nicht das Ram-Problem, sondern das Performance Problem:

Je größer der Map-Key ist, desto länger länger dauert das einordnen (bei 
einem 128bit Prozessor sähe das anders aus).

Deine Methode sieht gut aus - ich habe aber mal gehört, dass 
Bitmanipulation auf dem PC nicht sehr effizient ist. Stimmt das?

Ich werd mal einfach eine Struktur schreiben die das Field Array enthält 
und dann anfangen zu optimieren.

PS: Schachhashcodes werden z.t in < 8Byte gedrückt.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Samuel K. schrieb:
> Es ist ja nicht das Ram-Problem, sondern das Performance Problem
Du hast hoffentlich schon mit einem Profiler geprüft das dies 
tatsächlich der Flaschenhals im Bezug auf die Performance ist...

Samuel K. schrieb:
> PS: Schachhashcodes werden z.t in < 8Byte gedrückt.
Dann musst du dein Problem nur noch auf Schach zurückführen und kannst 
dann die Lösung nehmen...

Samuel K. schrieb:
> ich habe aber mal gehört
... im Vergleich zu was? Zu einem FPGA? Zu der Lösung auf Karopapier? 
Beim Ausdrucken?

Samuel K. schrieb:
> Das ist leider sehr speicheraufwändig.
> 3bit pro Zug * 42 > 15Byte.
Man kann das ganze noch stark optimieren indem man einen Huffman Baum 
aufbaut, Ich verstehe aber ehrlich gesagt immer noch nicht dein Problem 
ursprünglich hast du gesagt du wolltest Kollisionen vermeiden, dann ist 
dir der Hashwert zu lang, hast aber kein Speicherproblem und berechnen 
kann man das ja sowieso nicht... ist mir alles schleierhaft.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
4 gewinnt ist ein vollständig gelöstes Spiel und ich habe hier irgendwo 
noch eine Implementierung rumliegen (nicht von mir) in der dr PC alles 
durchrechnet. Da wird Alpha-Beta-Suche verwendet (was unbedingt 
notwendig ist wenn mans komplett durchrechnen will!), der ist dann auch 
unbesiegbar wenn er anfängt.

Autor: Sam .. (sam1994)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
D. I. schrieb:
> 4 gewinnt ist ein vollständig gelöstes Spiel und ich habe hier irgendwo
> noch eine Implementierung rumliegen (nicht von mir) in der dr PC alles
> durchrechnet. Da wird Alpha-Beta-Suche verwendet (was unbedingt
> notwendig ist wenn mans komplett durchrechnen will!), der ist dann auch
> unbesiegbar wenn er anfängt.

Dann zieht er aber nicht mehr schnell.

PS: Über die Theorie weiß ich bescheid, die meisten Probleme hatte ich 
mit der Bewertungsfunktion. Die würde mich echt mal interessieren (ich 
glaub meine ist auch ganz gut gelungen).

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.