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:
1
#define FIELD_W 7
2
#define FIELD_H 6
3
4
#define FAKTOR ((int)pow(2,FIELD_H))
5
//[...]
6
unsignedint_4Gewinnt::GetHashCode()
7
{
8
unsignedinthash=0;
9
for(intx=0,multi=1;x<FIELD_W;x++,multi*=FAKTOR)
10
{
11
for(inty=0,z=1;y<FIELD_H;y++,z*=2)
12
hash+=((field[x][y]+1)/2)*z*multi;
13
}
14
returnhash;
15
}
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.
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.)
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...
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)
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?)
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.
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.
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.
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.
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?
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.
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'
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.
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.
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.
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).
Thread beobachten
Seitenaufteilung abschalten