NegaMax-Algorithmus... Kopf raucht!

Übersicht

BlitzBasic

Allgemein

Gehe zu Seite Zurück 1, 2

	Kernel32	Fr, März 11, 2011 10:58 Antworten mit Zitat
PSY hat Folgendes geschrieben: player2rate und currentPlayer ja, vllt bischen unglücklich gewählt die Bezeichnungen currentPlayer ist der der grad dran ist auf der aktuellen Tiefe (ROT oder GELB) player2rate ist quasi die KI selbst, der Player der nach der besten Bewertung sucht Also, so wie ich das aus dem Code lese, ist player2rate also der Spieler, der in der momentanen Runde dran ist -und das ändert sich ja nicht, bis alle Durchläufe der Evaluierung beendet sind und der Zug abgeschlossen ist. Aber hättest du dann nicht gleich die globale "farbe" benutzen können? Das verwirrt mich ein wenig. Und currentPlayer ist dann der Spieler, aus dessen Sicht beim aktuellen Aufruf der Evaluierungsfunktion bewertet wird? Also das, was pro Durchlauf der Funktion dann immer wieder hin- und her wechselt? Also: player2rate = Der Spieler des aktuellen Zuges im Spiel (änder sich erst wieder beim nächsten Spielzug) currentPlayer = Aus welcher Sicht gerade die Evaluierungsfunktion durchlaufen wird. Ändert sich pro Aufruf der Evaluierungsfunktion . Stimmt das so? Zitat: hab mal reingeschaut und den Fehler gefunden. Sobald soviele Steine im Spielfeld waren, dass die Suchtiefe von der KI reduziert werden musste, wurde beim nächsten Spiel mit der reduzierten Suchtiefe weitergesucht lol Genau das ist mir grad beim Durchgucken deines Codes auch aufgefallen, das wollt ich grad reinschreiben =) Aber wenn searchDepth eigentlich immer gleich bleibt, wozu dient dann die Zeile Code: [AUSKLAPPEN] [EINKLAPPEN] If (searchDepth Mod 2) = 0 Then EM=1 Else EM=-1 Da ändert sich ja eigentlich nichts -nur wenn das Board eben fast volll ist. Warum wird gerade dann der Modifikator gewechselt?
------------- Wollte neulich Herrn Brot anrufen, aber da war belegt. Dann hab ich bei Wheight Watcher's angerufen, aber niemand hat abgenommen. Schliesslich hab ich im Irak angerufen, aber dort war besetzt o.O

Kernel32

Fr, März 11, 2011 10:58
Antworten mit Zitat

PSY hat Folgendes geschrieben:

player2rate und currentPlayer
ja, vllt bischen unglücklich gewählt die Bezeichnungen Very Happy

currentPlayer ist der der grad dran ist auf der aktuellen Tiefe (ROT oder GELB)
player2rate ist quasi die KI selbst, der Player der nach der besten Bewertung sucht

Also, so wie ich das aus dem Code lese, ist player2rate also der Spieler, der in der momentanen Runde dran ist -und das ändert sich ja nicht, bis alle Durchläufe der Evaluierung beendet sind und der Zug abgeschlossen ist. Aber hättest du dann nicht gleich die globale "farbe" benutzen können? Das verwirrt mich ein wenig.

Und currentPlayer ist dann der Spieler, aus dessen Sicht beim aktuellen Aufruf der Evaluierungsfunktion bewertet wird? Also das, was pro Durchlauf der Funktion dann immer wieder hin- und her wechselt?

Also:
player2rate = Der Spieler des aktuellen Zuges im Spiel (änder sich erst wieder beim nächsten Spielzug)
currentPlayer = Aus welcher Sicht gerade die Evaluierungsfunktion durchlaufen wird. Ändert sich pro Aufruf der Evaluierungsfunktion .

Stimmt das so?

Zitat:

hab mal reingeschaut und den Fehler gefunden. Sobald soviele Steine im Spielfeld waren, dass die Suchtiefe von der KI reduziert werden musste, wurde beim nächsten Spiel mit der reduzierten Suchtiefe weitergesucht

lol Genau das ist mir grad beim Durchgucken deines Codes auch aufgefallen, das wollt ich grad reinschreiben =)

Aber wenn searchDepth eigentlich immer gleich bleibt, wozu dient dann die Zeile

Code: [AUSKLAPPEN]

If (searchDepth Mod 2) = 0 Then EM=1 Else EM=-1

Da ändert sich ja eigentlich nichts -nur wenn das Board eben fast volll ist. Warum wird gerade dann der Modifikator gewechselt? Shocked

-------------
Wollte neulich Herrn Brot anrufen, aber da war belegt.
Dann hab ich bei Wheight Watcher's angerufen, aber niemand hat abgenommen.
Schliesslich hab ich im Irak angerufen, aber dort war besetzt o.O

	PSY	Fr, März 11, 2011 17:54 Antworten mit Zitat
Kernel32 hat Folgendes geschrieben: Aber hättest du dann nicht gleich die globale "farbe" benutzen können? Das verwirrt mich ein wenig. Hätte ich. Das hat aber diverse Gründe. Erstens hatte ich das Hauptprogramm zwecks diverser Tests derart modifiziert, dass ich eine eigenständige Variable brauchte. Zweitens gab es Phasen während der Entwicklung des Algos, in denen ich den Wert geändert habe Wenn Du das Hauptprogramm beibehälst und player2rate durch farbe ersetzt, funzt das natürlich Kernel32 hat Folgendes geschrieben: Und currentPlayer ist dann der Spieler, aus dessen Sicht beim aktuellen Aufruf der Evaluierungsfunktion bewertet wird? Also das, was pro Durchlauf der Funktion dann immer wieder hin- und her wechselt? Ja, der Spieler der gerade dran ist, je nachdem wie tief man im Suchbaum ist. Geht man 1 Schritt tiefer oder zurück, muss die Farbe ja wechseln. Hat nicht unbedingt was mit der Evaluierungsfunktion zu tun. Kernel32 hat Folgendes geschrieben: Aber wenn searchDepth eigentlich immer gleich bleibt, wozu dient dann die Zeile Code: [AUSKLAPPEN] [EINKLAPPEN] If (searchDepth Mod 2) = 0 Then EM=1 Else EM=-1 Naja, erstmal wird man später searchDepth ändern können, je nachdem gegen welchen KI-Gegner man spielt. Zweitens läuft gerade ohne diese Zeile der Code komplett aus dem Ruder Die Zeile überprüft ja, ob die Evaluierungsfunktion im Moment bei einer GERADEN oder UNGERADEN Suchtiefe durchgeführt wird. Wenn die Evaluierungsfunktion eine Suchtiefe bewertet, die GERADE (Minimierungsknoten)ist, muss ein POSITIVER Wert zurückgegeben werden, bei einer UNGERADEN (Madimierungsknoten) Suchtiefe ein NEGATIVER. So funzt ja der Algorithmus. L8er,PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Fr, März 11, 2011 17:54
Antworten mit Zitat

Kernel32 hat Folgendes geschrieben:

Aber hättest du dann nicht gleich die globale "farbe" benutzen können? Das verwirrt mich ein wenig.

Hätte ich. Das hat aber diverse Gründe. Erstens hatte ich das Hauptprogramm zwecks diverser Tests derart modifiziert, dass ich eine eigenständige Variable brauchte. Zweitens gab es Phasen während der Entwicklung des Algos, in denen ich den Wert geändert habe Very Happy

Wenn Du das Hauptprogramm beibehälst und player2rate durch farbe ersetzt, funzt das natürlich Very Happy

Kernel32 hat Folgendes geschrieben:

Und currentPlayer ist dann der Spieler, aus dessen Sicht beim aktuellen Aufruf der Evaluierungsfunktion bewertet wird? Also das, was pro Durchlauf der Funktion dann immer wieder hin- und her wechselt?

Ja, der Spieler der gerade dran ist, je nachdem wie tief man im Suchbaum ist. Geht man 1 Schritt tiefer oder zurück, muss die Farbe ja wechseln. Hat nicht unbedingt was mit der Evaluierungsfunktion zu tun.

Kernel32 hat Folgendes geschrieben:

Aber wenn searchDepth eigentlich immer gleich bleibt, wozu dient dann die Zeile

Code: [AUSKLAPPEN]

If (searchDepth Mod 2) = 0 Then EM=1 Else EM=-1

Naja, erstmal wird man später searchDepth ändern können, je nachdem gegen welchen KI-Gegner man spielt.
Zweitens läuft gerade ohne diese Zeile der Code komplett aus dem Ruder Very Happy

Die Zeile überprüft ja, ob die Evaluierungsfunktion im Moment bei einer GERADEN oder UNGERADEN Suchtiefe durchgeführt wird.
Wenn die Evaluierungsfunktion eine Suchtiefe bewertet, die GERADE (Minimierungsknoten)ist, muss ein POSITIVER Wert zurückgegeben werden, bei einer UNGERADEN (Madimierungsknoten) Suchtiefe ein NEGATIVER.
So funzt ja der Algorithmus.

L8er,PSY

PSY LABS Games
Coders don't die, they just gosub without return

	Kernel32	So, März 13, 2011 9:27 Antworten mit Zitat
Ah, ok, das mit dem Modifikator habe ich verstanden -man wechselt quasi das Vorzeichen, je nachdem, wer gerade dran ist. Aber ich tue mir immer noch sehr schwer damit, zu verstehen, wie der Game Tree angelegt ist. 1.) Soweit ich verstanden habe, wird pro Wurf ein neues Array Slot(Spalte, Suchtiefe) angelegt, wobei jedes der 7 Felder dort TRUE ist, wenn man dort werfen kann oder FALSE, wenn das nicht möglich ist, oder? Dort, wo es TRUE ist, wird dann als nächstes weitergesucht. 2.) Jede Suche wird nur ganz am Schluss bewertet, also wenn das Ende der Suchtiefe erreicht ist (Leaf) stimmt das? Dann wird mit den anderen Ergebnissen verglichen, oder? 3.) Und es wird dann nur bewertet, ob jemand gewonen hat, oder nicht. Es werden keine Punkte für bestimmte Konstellationen vergeben (Dreierkombo, Steine in der Mitte etc.), ebenso keine Punkte VOR dem Erreichen eines Leafs. Erst am Ende der Suchtiefe wird dann geguckt, ob jemand gewonnen hat, oder?
------------- Wollte neulich Herrn Brot anrufen, aber da war belegt. Dann hab ich bei Wheight Watcher's angerufen, aber niemand hat abgenommen. Schliesslich hab ich im Irak angerufen, aber dort war besetzt o.O

Kernel32

So, März 13, 2011 9:27
Antworten mit Zitat

Ah, ok, das mit dem Modifikator habe ich verstanden -man wechselt quasi das Vorzeichen, je nachdem, wer gerade dran ist.

Aber ich tue mir immer noch sehr schwer damit, zu verstehen, wie der Game Tree angelegt ist.

1.) Soweit ich verstanden habe, wird pro Wurf ein neues Array Slot(Spalte, Suchtiefe) angelegt, wobei jedes der 7 Felder dort TRUE ist, wenn man dort werfen kann oder FALSE, wenn das nicht möglich ist, oder? Dort, wo es TRUE ist, wird dann als nächstes weitergesucht.

2.) Jede Suche wird nur ganz am Schluss bewertet, also wenn das Ende der Suchtiefe erreicht ist (Leaf) stimmt das? Dann wird mit den anderen Ergebnissen verglichen, oder?

3.) Und es wird dann nur bewertet, ob jemand gewonen hat, oder nicht. Es werden keine Punkte für bestimmte Konstellationen vergeben (Dreierkombo, Steine in der Mitte etc.), ebenso keine Punkte VOR dem Erreichen eines Leafs. Erst am Ende der Suchtiefe wird dann geguckt, ob jemand gewonnen hat, oder?

	D2006 Administrator	So, März 13, 2011 15:35 Antworten mit Zitat
Nee, mach mal lieber ein Array und reiche das in der Funktion immer weiter. Deswegen machst du den Zug ja rückgängig, damit du mit einem Array arbeiten kannst. Sonst würde auch der Speicherverbrauch explodieren. (Gut, bei dem langweiligen 4gewinnt sicher nich, aber bei komplexeren Nullsummenspielen)
Intel Core i5 2500 \| 16 GB DDR3 RAM dualchannel \| ATI Radeon HD6870 (1024 MB RAM) \| Windows 7 Home Premium Intel Core 2 Duo 2.4 GHz \| 2 GB DDR3 RAM dualchannel \| Nvidia GeForce 9400M (256 MB shared RAM) \| Mac OS X Snow Leopard Intel Pentium Dual-Core 2.4 GHz \| 3 GB DDR2 RAM dualchannel \| ATI Radeon HD3850 (1024 MB RAM) \| Windows 7 Home Premium Chaos Interactive :: GoBang :: BB-Poker :: ChaosBreaker :: Hexagon :: ChaosRacer 2

D2006

Administrator

So, März 13, 2011 15:35
Antworten mit Zitat

Nee, mach mal lieber ein Array und reiche das in der Funktion immer weiter. Deswegen machst du den Zug ja rückgängig, damit du mit einem Array arbeiten kannst. Sonst würde auch der Speicherverbrauch explodieren. (Gut, bei dem langweiligen 4gewinnt sicher nich, aber bei komplexeren Nullsummenspielen)

	PSY	So, März 13, 2011 19:04 Antworten mit Zitat
Kernel32 hat Folgendes geschrieben: Ah, ok, das mit dem Modifikator habe ich verstanden -man wechselt quasi das Vorzeichen, je nachdem, wer gerade dran ist. Aber ich tue mir immer noch sehr schwer damit, zu verstehen, wie der Game Tree angelegt ist. 1.) Soweit ich verstanden habe, wird pro Wurf ein neues Array Slot(Spalte, Suchtiefe) angelegt, wobei jedes der 7 Felder dort TRUE ist, wenn man dort werfen kann oder FALSE, wenn das nicht möglich ist, oder? Dort, wo es TRUE ist, wird dann als nächstes weitergesucht. Das Array wird nur 1x angelegt. Beim Aufrufen der KI-Funktion wird es erstmal komplett leergemacht. Der Zweck des Arrays ist einfach, bei jeder Suchtiefe festzuhalten, ob in einen bestimmten Slot noch Chips eingeworfen werden können, oder ob es schon voll ist. Bei TRUE kann noch eingeworfen werden, bei FALSE ist die Spalte voll. Kernel32 hat Folgendes geschrieben: 2.) Jede Suche wird nur ganz am Schluss bewertet, also wenn das Ende der Suchtiefe erreicht ist (Leaf) stimmt das? Dann wird mit den anderen Ergebnissen verglichen, oder? Stimmt fast. Bewertungen finden nur am Ende jedes Zweiges statt. Jedoch suche ich bei jeder geraden Suchtiefe (was bedeutet, dass jeder Player 1 Chip eingeworfen hat) nach einer Gewinnsituation. Das verkürzt das ganze. Falls Du noch Verständnisprobleme mit dem Negamax hast, hier ein Link (die untere Grafik auf der rechten Seite), der das Ganze genau erklärt. Ist ein animated GIF, dauert ca. 20 Minuten. http://en.wikipedia.org/wiki/Negamax Falls zu kompliziert oder Du kein Englisch kannst, hab ich Dir hier mal eine super verständliche Darstellung von der Uni Hannover hochgeladen (step for step explanation): http://pheryllt.de/_misc/Blitzforum/minimax.html Kernel32 hat Folgendes geschrieben: 3.) Und es wird dann nur bewertet, ob jemand gewonen hat, oder nicht. Es werden keine Punkte für bestimmte Konstellationen vergeben (Dreierkombo, Steine in der Mitte etc.), ebenso keine Punkte VOR dem Erreichen eines Leafs. Erst am Ende der Suchtiefe wird dann geguckt, ob jemand gewonnen hat, oder? Falsch. Am Ende nehm ich überhaupt keine Gewinnbewertung vor. Je mehr Steine einer Farbe in einer Reihe, desto mehr Punkte gibts für diese Stellung. Punkte VOR Erreichen eines Leafs werden überhaupt nicht vergeben, das würde das alphabeta Prinzip ad absurdum führen. Ich checke nur jede 2. Stellung auf Gewinn/Verlust, um zu Beschleunigen. Dreierkombos erhalten automatisch mehr Punkte. Wie gesagt, die Version vom Contest war quasi pre-alpha ^^ Es ging mir primär nur um die korrekte Umsetzung des alpha beta algos mit beta cutoff. Bei der neuen Version gibt es diverse kleine Bugfixes, zudem ist sie spürbar schneller. Steine die in der Mitte liegen erhalten eine höhere Bewertung, es gibt diverse KI-Systeme, usw. Was ich noch einbauen werde sind diverse Checks, wie zB ob es auf 2 übereinanderliegenden Positionen eine Siegposition gibt usw.. L8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

So, März 13, 2011 19:04
Antworten mit Zitat

Kernel32 hat Folgendes geschrieben:

Das Array wird nur 1x angelegt. Beim Aufrufen der KI-Funktion wird es erstmal komplett leergemacht. Der Zweck des Arrays ist einfach, bei jeder Suchtiefe festzuhalten, ob in einen bestimmten Slot noch Chips eingeworfen werden können, oder ob es schon voll ist. Bei TRUE kann noch eingeworfen werden, bei FALSE ist die Spalte voll.

Kernel32 hat Folgendes geschrieben:

2.) Jede Suche wird nur ganz am Schluss bewertet, also wenn das Ende der Suchtiefe erreicht ist (Leaf) stimmt das? Dann wird mit den anderen Ergebnissen verglichen, oder?

Stimmt fast. Bewertungen finden nur am Ende jedes Zweiges statt. Jedoch suche ich bei jeder geraden Suchtiefe (was bedeutet, dass jeder Player 1 Chip eingeworfen hat) nach einer Gewinnsituation. Das verkürzt das ganze.
Falls Du noch Verständnisprobleme mit dem Negamax hast, hier ein Link (die untere Grafik auf der rechten Seite), der das Ganze genau erklärt. Ist ein animated GIF, dauert ca. 20 Minuten.
http://en.wikipedia.org/wiki/Negamax

Falls zu kompliziert oder Du kein Englisch kannst, hab ich Dir hier mal eine super verständliche Darstellung von der Uni Hannover hochgeladen (step for step explanation):
http://pheryllt.de/_misc/Blitzforum/minimax.html

Kernel32 hat Folgendes geschrieben:

3.) Und es wird dann nur bewertet, ob jemand gewonen hat, oder nicht. Es werden keine Punkte für bestimmte Konstellationen vergeben (Dreierkombo, Steine in der Mitte etc.), ebenso keine Punkte VOR dem Erreichen eines Leafs. Erst am Ende der Suchtiefe wird dann geguckt, ob jemand gewonnen hat, oder?

Falsch. Am Ende nehm ich überhaupt keine Gewinnbewertung vor. Je mehr Steine einer Farbe in einer Reihe, desto mehr Punkte gibts für diese Stellung.
Punkte VOR Erreichen eines Leafs werden überhaupt nicht vergeben, das würde das alphabeta Prinzip ad absurdum führen. Ich checke nur jede 2. Stellung auf Gewinn/Verlust, um zu Beschleunigen.
Dreierkombos erhalten automatisch mehr Punkte.

Wie gesagt, die Version vom Contest war quasi pre-alpha ^^ Es ging mir primär nur um die korrekte Umsetzung des alpha beta algos mit beta cutoff.
Bei der neuen Version gibt es diverse kleine Bugfixes, zudem ist sie spürbar schneller.
Steine die in der Mitte liegen erhalten eine höhere Bewertung, es gibt diverse KI-Systeme, usw.
Was ich noch einbauen werde sind diverse Checks, wie zB ob es auf 2 übereinanderliegenden Positionen eine Siegposition gibt usw..

L8er,
PSY

PSY LABS Games
Coders don't die, they just gosub without return

Zuletzt bearbeitet von PSY am Di, Dez 04, 2018 21:41, insgesamt einmal bearbeitet

	Kernel32	So, März 20, 2011 10:32 Antworten mit Zitat
Also, ich bin nun ein grosses Stück weiter gekommen. Auf Suchtiefe 6 ist meine KI inzwischen so gut, das ich es nicht mehr schaffe, sie zu schlagen und benötigt im Schnitt zwischen 0.7 und 2 Sekunden pro Zug . Pro Zug werden im Schnitt "nur" 15.000 - 30.000 Nodes evaluiert, bis der Computer weiss, welcher Zug wohl der beste ist. Vorher waren es 150.000, aber durch eine bessere Evaluierung habe ich die Anzahl enorm senken können. Einen enormen Geschwindigkeitszuwachs habe ich erzielt, indem ich die Liste der erlaubten Züge vorsortiere (die Züge, die auf strategisch wertvolleren Position auf dem Spielbrett landen, erhalten eine höhere Wertung und werden daher zuerst durchsucht). Ich teste hauptsächlich, ob die Spieler sog. odd oder even threats haben -denn anhand der geraden und ungeraden threats steht schon früh im Spiel fest, ob ein Spieler gewinnen kann. Hierfür gibt es sogar feste Gewinnformeln. Sind noch keine threats vorhanden, werden die Einer- und Zweiercombos anhand ihrer Position auf dem Spielfeld bewertet (mittlere Positionen geben mehr Punkte). All das allerdings nur, wenn der Gegner keine Steine in der jeweiligen Gewinngruppe hat (davon gibt es 69), ansonsten gilt die Position als wertlos. Das benutzen von "Winning Groups" ist hier sehr komfortabel, da man so ohne viele For...Next Schleifen bequem und schnell prüfen kann, wie viele einer, zweier, dreier und vierer ein Spieler hat -und ob der Gegner in dieser Combo einen Stein gesetzt hat, was sie ja dann wertlos macht. Ach ja, und bei der Bewertung der threats beziehe ich die Anzahl der bis dahin gespielten Züge ein (je mehr, desto weniger Punkte), so versucht die KI möglichst früh zu gewinnen und bevozugt Züge, die schneller ein Ergebnis bringen. Das funktioniert sehr gut bisher. Jetzt suche ich nur noch einen Weg, die Rechenzeit evtl. weiter zu senken. Dazu kommen mir Transposition Tables oder iterative Deepening in den Sinn, ich werde das mal ausprobieren. Ich muss das ganze mal gegen ein anderes Programm testen, bisher habe ich nur selbst gegen die KI gespielt, es aber nicht mehr geschafft sie zu schlagen. Ich würde das Proggie gerne gegen eure antreten lassen, aber ich habe das mom. mal in LUA geschrieben und müsste das erst nach BB konvertieren
------------- Wollte neulich Herrn Brot anrufen, aber da war belegt. Dann hab ich bei Wheight Watcher's angerufen, aber niemand hat abgenommen. Schliesslich hab ich im Irak angerufen, aber dort war besetzt o.O

Kernel32

So, März 20, 2011 10:32
Antworten mit Zitat

Also, ich bin nun ein grosses Stück weiter gekommen. Auf Suchtiefe 6 ist meine KI inzwischen so gut, das ich es nicht mehr schaffe, sie zu schlagen und benötigt im Schnitt zwischen 0.7 und 2 Sekunden pro Zug . Pro Zug werden im Schnitt "nur" 15.000 - 30.000 Nodes evaluiert, bis der Computer weiss, welcher Zug wohl der beste ist. Vorher waren es 150.000, aber durch eine bessere Evaluierung habe ich die Anzahl enorm senken können.

Einen enormen Geschwindigkeitszuwachs habe ich erzielt, indem ich die Liste der erlaubten Züge vorsortiere (die Züge, die auf strategisch wertvolleren Position auf dem Spielbrett landen, erhalten eine höhere Wertung und werden daher zuerst durchsucht).

Ich teste hauptsächlich, ob die Spieler sog. odd oder even threats haben -denn anhand der geraden und ungeraden threats steht schon früh im Spiel fest, ob ein Spieler gewinnen kann. Hierfür gibt es sogar feste Gewinnformeln. Sind noch keine threats vorhanden, werden die Einer- und Zweiercombos anhand ihrer Position auf dem Spielfeld bewertet (mittlere Positionen geben mehr Punkte). All das allerdings nur, wenn der Gegner keine Steine in der jeweiligen Gewinngruppe hat (davon gibt es 69), ansonsten gilt die Position als wertlos.

Das benutzen von "Winning Groups" ist hier sehr komfortabel, da man so ohne viele For...Next Schleifen bequem und schnell prüfen kann, wie viele einer, zweier, dreier und vierer ein Spieler hat -und ob der Gegner in dieser Combo einen Stein gesetzt hat, was sie ja dann wertlos macht.

Ach ja, und bei der Bewertung der threats beziehe ich die Anzahl der bis dahin gespielten Züge ein (je mehr, desto weniger Punkte), so versucht die KI möglichst früh zu gewinnen und bevozugt Züge, die schneller ein Ergebnis bringen.

Das funktioniert sehr gut bisher. Jetzt suche ich nur noch einen Weg, die Rechenzeit evtl. weiter zu senken.

Dazu kommen mir Transposition Tables oder iterative Deepening in den Sinn, ich werde das mal ausprobieren.

Ich muss das ganze mal gegen ein anderes Programm testen, bisher habe ich nur selbst gegen die KI gespielt, es aber nicht mehr geschafft sie zu schlagen. Ich würde das Proggie gerne gegen eure antreten lassen, aber ich habe das mom. mal in LUA geschrieben und müsste das erst nach BB konvertieren Sad

	PSY	Di, März 22, 2011 0:42 Antworten mit Zitat
Ui, das hört sich ja wirklich schon sehr gut an Nicht schlecht! Hast Du für die Winning Tables dims, types oder einfach nur Abfragen benutzt? Mich würd mal der Geschwindigkeitsunterschied interessieren wenn ich for...next komplett ersetze... Werd ich vllt mal austesten. Hab im Moment mal wieder super viel RL, wird wohl nächste oder ünächste Woche werden L8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Di, März 22, 2011 0:42
Antworten mit Zitat

Ui,

das hört sich ja wirklich schon sehr gut an Very Happy

Nicht schlecht!

Hast Du für die Winning Tables dims, types oder einfach nur Abfragen benutzt? Mich würd mal der Geschwindigkeitsunterschied interessieren wenn ich for...next komplett ersetze...

Werd ich vllt mal austesten. Hab im Moment mal wieder super viel RL, wird wohl nächste oder ünächste Woche werden Very Happy

L8er,
PSY

PSY LABS Games
Coders don't die, they just gosub without return

	Kernel32	Di, März 22, 2011 9:18 Antworten mit Zitat
Da ich das bisher ja nur mit LUA umgesetzt habe, habe ich Arrays und Hashtables benutzt. Für die Wingroups habe ich ein Array in folgender Art angelegt: WinGroups[col][row] = [gruppeNummer, gruppenNummer, gruppenNumer...] Also für jedes Square gespeichert, zu welchen Gewinngruppen es gehört. Wenn dann ein Stein gesetzt wird, kann man die Kombos eines Spielers (einer, zweier, dreier etc.) ganz einfach updaten, indem man durch die WinGroup[col][row] des gesetzten Steins loopt und SpielerKombos[spielernummer][gruppeNummer] + 1 zählt. Ist dann z.B. SpielerKombos[spielernummer][gruppeNummer] == 4, hat ein Spieler gewonnen. Allerdings habe ich die feststellung gemacht, das dies zwar eine viel bessere Evaluierung erlaubt (die KI ist intelligenter, da man so ganz genau auf odd und even threats eingehen kann), aber eine reine Feldbewertung mit festen Punkten pro Feld ist dennoch schneller. Am meisten hat bisher die Zugvorsortierung gebracht. Da ging die Anzahl der evaluierten Nodes rasant runter von 145.000 auf ca. 14.000 - 25.000
------------- Wollte neulich Herrn Brot anrufen, aber da war belegt. Dann hab ich bei Wheight Watcher's angerufen, aber niemand hat abgenommen. Schliesslich hab ich im Irak angerufen, aber dort war besetzt o.O

Kernel32

Di, März 22, 2011 9:18
Antworten mit Zitat

Da ich das bisher ja nur mit LUA umgesetzt habe, habe ich Arrays und Hashtables benutzt.

Für die Wingroups habe ich ein Array in folgender Art angelegt:

WinGroups[col][row] = [gruppeNummer, gruppenNummer, gruppenNumer...]

Also für jedes Square gespeichert, zu welchen Gewinngruppen es gehört.

Wenn dann ein Stein gesetzt wird, kann man die Kombos eines Spielers (einer, zweier, dreier etc.) ganz einfach updaten, indem man durch die WinGroup[col][row] des gesetzten Steins loopt und

SpielerKombos[spielernummer][gruppeNummer] + 1

zählt.

Ist dann z.B. SpielerKombos[spielernummer][gruppeNummer] == 4, hat ein Spieler gewonnen.

Allerdings habe ich die feststellung gemacht, das dies zwar eine viel bessere Evaluierung erlaubt (die KI ist intelligenter, da man so ganz genau auf odd und even threats eingehen kann), aber eine reine Feldbewertung mit festen Punkten pro Feld ist dennoch schneller.

Am meisten hat bisher die Zugvorsortierung gebracht. Da ging die Anzahl der evaluierten Nodes rasant runter von 145.000 auf ca. 14.000 - 25.000 Shocked

	PSY	Di, März 22, 2011 15:50 Antworten mit Zitat
Kernel32 hat Folgendes geschrieben: Allerdings habe ich die feststellung gemacht, das dies zwar eine viel bessere Evaluierung erlaubt (die KI ist intelligenter, da man so ganz genau auf odd und even threats eingehen kann), aber eine reine Feldbewertung mit festen Punkten pro Feld ist dennoch schneller. jo deshalb frag ich, hab mir sowas gedacht. sind ja doch jede menge abfragen die zu überprüfen sind....hmmmm Kernel32 hat Folgendes geschrieben: Am meisten hat bisher die Zugvorsortierung gebracht. Da ging die Anzahl der evaluierten Nodes rasant runter von 145.000 auf ca. 14.000 - 25.000 das is ziemlich drastisch ^^ . allerdings hab ich mir darüber noch überhaupt keine gedanken gemacht. naja, sobald ich was brauchbares hab meld ich mich mal..hab noch 1-2 ideen aber keine ahnung ob ich die überhaupt so implementieren kann. l8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Di, März 22, 2011 15:50
Antworten mit Zitat

Kernel32 hat Folgendes geschrieben:

Allerdings habe ich die feststellung gemacht, das dies zwar eine viel bessere Evaluierung erlaubt (die KI ist intelligenter, da man so ganz genau auf odd und even threats eingehen kann), aber eine reine Feldbewertung mit festen Punkten pro Feld ist dennoch schneller.

jo deshalb frag ich, hab mir sowas gedacht. sind ja doch jede menge abfragen die zu überprüfen sind....hmmmm

Kernel32 hat Folgendes geschrieben:

Am meisten hat bisher die Zugvorsortierung gebracht. Da ging die Anzahl der evaluierten Nodes rasant runter von 145.000 auf ca. 14.000 - 25.000 Shocked

das is ziemlich drastisch ^^ . allerdings hab ich mir darüber noch überhaupt keine gedanken gemacht. naja, sobald ich was brauchbares hab meld ich mich mal..hab noch 1-2 ideen aber keine ahnung ob ich die überhaupt so implementieren kann.

l8er,
PSY

PSY LABS Games
Coders don't die, they just gosub without return

	PSY	Di, Apr 05, 2011 5:52 Antworten mit Zitat
Moin, so ich hab mal wieder ein wenig an der KI rumgebastelt. Sie basiert jetzt quasi nur noch auf winning groups und funzt folgendermassen: 1. TYPES Es gibt ja 69 winning groups, deshalb hab ich einfach 69 types angelegt. Jedes Type besitzt startx und starty Koordinate der winninggroup, den Wert der winninggroup (mittlere groups haben natürlich bessere Werte), die Richtung der group von der startx/starty Position aus (nach rechts, nach oben, nach rechts oben, nach rechts unten) und die Anzahl der Steine in der winning group. 2. SUCHALGO Negamax mit beta-cutoff 3. BEWERTUNG WINNING GROUPS Am Ende des jeweiligen Astes wird die Evaluierungsfunktion aufgerufen. Dabei wird jede winning group durchlaufen. Es wird gecheckt, wieviel eigene Steine in der group sind. Stein in Feld1 gibt 2^0 Punkte, in Feld2 2^1 Punkte, in Feld3 2^2 Punkte und in Feld4 2^3 Punkte. Somit lässt sich für spätere Analysen (Threats)ganz einfach bestimmten, wieviel Steine in der jeweiligen winning group sind, und welche es sind, und die Punkte sind auch schon automatisch vergeben (Pro Steinn in der group wird der groupscore addiert). Hat ne winninggroup zb einen Wert von 6, weiss die KI dass in Feld1 nix, in Feld2 ein Stein, in Feld3 ein Stein und in Feld4 nix ist (0x2^0 + 1x2^1 + 1x2^2 + 0x2^3 = 6) 15 bedeutet somit, dass 4 Steine drin sind, 3 dass die 2 ersten drin sind, 9 der erste und der vierte uswusw) Ist ein gegnerischer Stein in der winning group, gibts 0 Punkte. 4. BEWERTUNG THREATS Nachdem alle 69 groups durchlaufen sind, kommt die Bewertung der Threats. Ich frag einfach ab, ob eine Group den Wert 13,14,7 oder 11 hat, was automatisch bedeutet dass 3 Steine drin sind. Anhand der starty-Position der group und der Richtung bestimm ich dann ganz easy, ob ein ungerader oder gerader Threat vorliegt, und vergebe dann jeweils Bonuspunkte dafür, im Moment für ODD 300 und EVEN 50, aber da hab ich noch nicht mit den Werten rumgespielt, die sind noch rein ausm Gefühl raus. D.h. ODD Threats sind besser wenn die KI angefangen hat, EVEN Threats sind besser wenn die KI zweiter ist. 5. EARLY WIN / LOSS Alle 2 Chips überprüf ich, ob ein 4er vorliegt, wenn ja geb ich 500000 points * Tiefe zurück, dh. je mehr Punkte, desto früher der 4er eintritt (verwirrt hier ein wenig, bei mir wird evaluiert wenn die Suchtiefe 0 ist, ich zähl quasi rückwärts). Oder halt -500000 points * Tiefe wenn Gegner nen 4er hat. Da ich das alle 2 Chips mach, muss ich natürlich bei ungeraden Suchtiefen noch einmal extra Punkte geben, wenn ein 4er vorliegt, da nach dem letzten early win/loss check ja noch 1 chip dazugekommen ist. Die Überprüfung ist superschnell und spart jede Menge Zeit bei den Ästen ein. 6. BEWERTUNG AI - GEGNER Diese ganze Bewertung gibts 1x für die AI und einmal für den Gegner. Beide Werte werden subtrahiert. Das verhindert, dass die KI nur ihr Augenmerk auf eigene, gute Positionen richtet und dabei den Gegner vergisst. Das Ganze ist jetzt natürlich nicht wahnsinnig schnell (bei Suchtiefe 7 und 2 Steinen im Brett 1.2 secs, aber sobald 2-3 Steine mehr drin sind fällt sie schon auf .2 - .6 secs). Die andern KI's werden zu 0 oder zu 1 geschlagen, ausser Blitzmoritz, die macht ein paar mehr Punkte. Was interessant ist, ist der Sprung von Tiefe 7 auf 8, da geht sie dann auch gnadenlos unter Wobei sie natürlich WESENTLICH schneller ist als meine ^^ Was ich noch einbauen werde ist eine flexible Suchtiefe, die sich ständig erweitert je mehr Steine im Brett sind, schätze die kann dann auch mal auf 15 hochgehn...muss ich mal austesten. Und diverse Tweaks mit den Punktwertungen, ich nehm an da kann ich noch weiter verbessern. Werde vllt später dann ein komplettes Game drausmachen, wo man sich quasi durch verschieden Länder mit verschiedenen Gegnern kämpfen muss (Depp, Grossmeister, Besoffener, Aggressiv, 4er Zerstörer usw....). Mal sehn, wie ich Zeit und Lust hab. Im Moment geh ich lieber anderen Hobbies nach L8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Di, Apr 05, 2011 5:52
Antworten mit Zitat

Moin,

so ich hab mal wieder ein wenig an der KI rumgebastelt.

Sie basiert jetzt quasi nur noch auf winning groups und funzt folgendermassen:

1. TYPES
Es gibt ja 69 winning groups, deshalb hab ich einfach 69 types angelegt. Jedes Type besitzt startx und starty Koordinate der winninggroup, den Wert der winninggroup (mittlere groups haben natürlich bessere Werte), die Richtung der group von der startx/starty Position aus (nach rechts, nach oben, nach rechts oben, nach rechts unten) und die Anzahl der Steine in der winning group.

2. SUCHALGO
Negamax mit beta-cutoff

3. BEWERTUNG WINNING GROUPS
Am Ende des jeweiligen Astes wird die Evaluierungsfunktion aufgerufen. Dabei wird jede winning group durchlaufen. Es wird gecheckt, wieviel eigene Steine in der group sind. Stein in Feld1 gibt 2^0 Punkte, in Feld2 2^1 Punkte, in Feld3 2^2 Punkte und in Feld4 2^3 Punkte. Somit lässt sich für spätere Analysen (Threats)ganz einfach bestimmten, wieviel Steine in der jeweiligen winning group sind, und welche es sind, und die Punkte sind auch schon automatisch vergeben (Pro Steinn in der group wird der groupscore addiert).
Hat ne winninggroup zb einen Wert von 6, weiss die KI dass in Feld1 nix, in Feld2 ein Stein, in Feld3 ein Stein und in Feld4 nix ist (0x2^0 + 1x2^1 + 1x2^2 + 0x2^3 = 6)

15 bedeutet somit, dass 4 Steine drin sind, 3 dass die 2 ersten drin sind, 9 der erste und der vierte uswusw)
Ist ein gegnerischer Stein in der winning group, gibts 0 Punkte.

4. BEWERTUNG THREATS
Nachdem alle 69 groups durchlaufen sind, kommt die Bewertung der Threats. Ich frag einfach ab, ob eine Group den Wert 13,14,7 oder 11 hat, was automatisch bedeutet dass 3 Steine drin sind. Anhand der starty-Position der group und der Richtung bestimm ich dann ganz easy, ob ein ungerader oder gerader Threat vorliegt, und vergebe dann jeweils Bonuspunkte dafür, im Moment für ODD 300 und EVEN 50, aber da hab ich noch nicht mit den Werten rumgespielt, die sind noch rein ausm Gefühl raus. D.h. ODD Threats sind besser wenn die KI angefangen hat, EVEN Threats sind besser wenn die KI zweiter ist.

5. EARLY WIN / LOSS
Alle 2 Chips überprüf ich, ob ein 4er vorliegt, wenn ja geb ich 500000 points * Tiefe zurück, dh. je mehr Punkte, desto früher der 4er eintritt (verwirrt hier ein wenig, bei mir wird evaluiert wenn die Suchtiefe 0 ist, ich zähl quasi rückwärts).
Oder halt -500000 points * Tiefe wenn Gegner nen 4er hat.

Da ich das alle 2 Chips mach, muss ich natürlich bei ungeraden Suchtiefen noch einmal extra Punkte geben, wenn ein 4er vorliegt, da nach dem letzten early win/loss check ja noch 1 chip dazugekommen ist.
Die Überprüfung ist superschnell und spart jede Menge Zeit bei den Ästen ein.

6. BEWERTUNG AI - GEGNER
Diese ganze Bewertung gibts 1x für die AI und einmal für den Gegner. Beide Werte werden subtrahiert. Das verhindert, dass die KI nur ihr Augenmerk auf eigene, gute Positionen richtet und dabei den Gegner vergisst.

Das Ganze ist jetzt natürlich nicht wahnsinnig schnell (bei Suchtiefe 7 und 2 Steinen im Brett 1.2 secs, aber sobald 2-3 Steine mehr drin sind fällt sie schon auf .2 - .6 secs).

Die andern KI's werden zu 0 oder zu 1 geschlagen, ausser Blitzmoritz, die macht ein paar mehr Punkte. Was interessant ist, ist der Sprung von Tiefe 7 auf 8, da geht sie dann auch gnadenlos unter Very Happy

Wobei sie natürlich WESENTLICH schneller ist als meine ^^

Was ich noch einbauen werde ist eine flexible Suchtiefe, die sich ständig erweitert je mehr Steine im Brett sind, schätze die kann dann auch mal auf 15 hochgehn...muss ich mal austesten.
Und diverse Tweaks mit den Punktwertungen, ich nehm an da kann ich noch weiter verbessern.
Werde vllt später dann ein komplettes Game drausmachen, wo man sich quasi durch verschieden Länder mit verschiedenen Gegnern kämpfen muss (Depp, Grossmeister, Besoffener, Aggressiv, 4er Zerstörer usw....).
Mal sehn, wie ich Zeit und Lust hab. Im Moment geh ich lieber anderen Hobbies nach Very Happy

L8er,
PSY

PSY LABS Games
Coders don't die, they just gosub without return

Gehe zu Seite Zurück 1, 2

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

NegaMax-Algorithmus... Kopf raucht!