NegaMax-Algorithmus... Kopf raucht!

Übersicht

BlitzBasic

Allgemein

Gehe zu Seite 1, 2 Weiter

	Kernel32 Betreff: NegaMax-Algorithmus... Kopf raucht!	Mi, März 09, 2011 18:34 Antworten mit Zitat
Also, mir raucht der Kopf und ich bräuchte ein wenig Hilfe... ich möchte ein einfaches Vier-Gewinnt programmieren und weiss inzwischen, das die KI am besten mittels NegaMax-Algo umgesetzt wird. Zu diesem Algorithmus gibt es auch massenhaft Beispiele. Den habe ich auch so einigermassen verstanden. Das Problem ist nur: in KEINEM der Beispiele wird erklärt - Wie man den "Game Tree" bildet (ist das jeweils eine ganze Kopie des Spielfeldes? Oder nur das jeweils erfolgreichste Feld, in das man ziehen kann?) - Was die ominöse Funktion evaluateMove() genau macht. Nach welchem Punktesystem vergleicht man, welche Züge besser sind? Wie viele Punkte vergibt man pro Feld und wie speichert man das alles ab, damit dann die NegaMax-Funktion überhaupt ihre Arbeit machen kann? Sorry, wenn ich verwirrt klinge, ich BIN es inzwischen auch...
------------- 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

Betreff: NegaMax-Algorithmus... Kopf raucht!

Mi, März 09, 2011 18:34
Antworten mit Zitat

Also, mir raucht der Kopf und ich bräuchte ein wenig Hilfe... ich möchte ein einfaches Vier-Gewinnt programmieren und weiss inzwischen, das die KI am besten mittels NegaMax-Algo umgesetzt wird.

Zu diesem Algorithmus gibt es auch massenhaft Beispiele. Den habe ich auch so einigermassen verstanden. Das Problem ist nur: in KEINEM der Beispiele wird erklärt

- Wie man den "Game Tree" bildet (ist das jeweils eine ganze Kopie des Spielfeldes? Oder nur das jeweils erfolgreichste Feld, in das man ziehen kann?)

- Was die ominöse Funktion evaluateMove() genau macht. Nach welchem Punktesystem vergleicht man, welche Züge besser sind? Wie viele Punkte vergibt man pro Feld und wie speichert man das alles ab, damit dann die NegaMax-Funktion überhaupt ihre Arbeit machen kann?

Sorry, wenn ich verwirrt klinge, ich BIN es inzwischen auch... Sad

-------------
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

	Midimaster	Mi, März 09, 2011 19:30 Antworten mit Zitat
Eine Frage vorneweg... Hast Du schon das Spielfeld soweit und kontrolliert der Computer schon das Einhalten der Regeln beim Ziehen beider Spieler (Mensch und Computer)?

Midimaster

Mi, März 09, 2011 19:30
Antworten mit Zitat

Eine Frage vorneweg...

Hast Du schon das Spielfeld soweit und kontrolliert der Computer schon das Einhalten der Regeln beim Ziehen beider Spieler (Mensch und Computer)?

	Kernel32	Mi, März 09, 2011 19:46 Antworten mit Zitat
Hallo Midimaster, nein, ich möchte das erst einmal theoretisch verstehen. Der Rest ist überhaupt kein Problem -nur habe ich bisher eben noch nie mit einem Game Tree gearbeitet. Was ich momentan nicht kapiere ist, wie ich diesen Game Tree erstelle und vor allem, wie ich dann bei jedem (theoretischen) Zug analysiere, welcher Zug am besten ist -und welche Wertung bzw. wie viele "Punkte" man dann vergibt, um die schlechten von den guten Zügen unterscheiden zu können. Um das mal zu verdeutlich, hier mal eines der Beispiele, die ich gefunden habe, um die Liste aller getesteten Züge nach dem besten Zug zu durchsuchen (Pseudo-Code): Code: [AUSKLAPPEN] [EINKLAPPEN] int AlphaBeta ( Position p, int depth , int alpha , int beta ) { if( endPosition (p) \|\| depth <=0) return evaluate (p); Move [] moves = generateMoves (p); sort (moves , p); for ( int i =0; i< moves . length ; i ++) { makeMove (p, moves [i ]); int value = - AlphaBeta (p, depth -1, -beta , -alpha ); undoMove (p, moves [i ]); if( value >= beta ) return beta ; if( value > alpha ) alpha = value ; } return alpha ; } Das ist soweit klar -aber was bitte machen generateMoves () makeMove () Klar, generateMoves () erstellt wahrscheinlich einen Game Tree, also eine Liste aller möglichen Züge und deren jeweilige Wertung -aber WIE genau? Wir speichert man das am besten ab, ist diese Liste hierarchisch oder sequentiell? Das verwirrt mich total...
------------- 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

Mi, März 09, 2011 19:46
Antworten mit Zitat

Hallo Midimaster,
nein, ich möchte das erst einmal theoretisch verstehen. Der Rest ist überhaupt kein Problem -nur habe ich bisher eben noch nie mit einem Game Tree gearbeitet.

Was ich momentan nicht kapiere ist, wie ich diesen Game Tree erstelle und vor allem, wie ich dann bei jedem (theoretischen) Zug analysiere, welcher Zug am besten ist -und welche Wertung bzw. wie viele "Punkte" man dann vergibt, um die schlechten von den guten Zügen unterscheiden zu können.

Um das mal zu verdeutlich, hier mal eines der Beispiele, die ich gefunden habe, um die Liste aller getesteten Züge nach dem besten Zug zu durchsuchen (Pseudo-Code):

Code: [AUSKLAPPEN]

int AlphaBeta ( Position p, int depth , int alpha , int beta )
{
if( endPosition (p) || depth <=0) return evaluate (p);

Move [] moves = generateMoves (p);
sort (moves , p);
for ( int i =0; i< moves . length ; i ++)
   {
   makeMove (p, moves [i ]);
   int value = - AlphaBeta (p, depth -1, -beta , -alpha );
   undoMove (p, moves [i ]);
   if( value >= beta ) return beta ;
   if( value > alpha ) alpha = value ;
   }
return alpha ;
}

Das ist soweit klar -aber was bitte machen

generateMoves ()
makeMove ()

Klar, generateMoves () erstellt wahrscheinlich einen Game Tree, also eine Liste aller möglichen Züge und deren jeweilige Wertung -aber WIE genau? Wir speichert man das am besten ab, ist diese Liste hierarchisch oder sequentiell?

Das verwirrt mich total...

	D2006 Administrator	Mi, März 09, 2011 20:02 Antworten mit Zitat
Es wird eine Liste der -jetzt- möglichen Spielzüge erstellt. Dann wird jeder der Reihe nach ausprobiert. Der "Baum" entsteht dabei mehr oder minder automatisch, weil sich die Funktion für jeden Spielzug rekursiv selbst aufruft. Wenn es also 10 Zugmöglichkeiten gibt und beim zweiten Zug dann 9, hat er bei ner "Suchtiefe" von zwei Zügen 90 Stellungen ausprobiert. Deswegen ist der Spaß auch so teuer.
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

Mi, März 09, 2011 20:02
Antworten mit Zitat

Es wird eine Liste der -jetzt- möglichen Spielzüge erstellt. Dann wird jeder der Reihe nach ausprobiert. Der "Baum" entsteht dabei mehr oder minder automatisch, weil sich die Funktion für jeden Spielzug rekursiv selbst aufruft. Wenn es also 10 Zugmöglichkeiten gibt und beim zweiten Zug dann 9, hat er bei ner "Suchtiefe" von zwei Zügen 90 Stellungen ausprobiert. Deswegen ist der Spaß auch so teuer.

	Midimaster	Mi, März 09, 2011 20:21 Antworten mit Zitat
so wie ich das sehe, erstellt generateMoves() alle möglichen Spielzüge der akt. Tiefe für den Spieler der gerade dran ist. D.h. bei "4 gewinnt" kommen 7 Züge hinzu. Dann werden alle 7 Züge wirklich gezogen MakeMove und natürlich anschließend wieder zurückgenommen. UndoMove. Während der 7 Versuche wird dann die AlphaBeta wieder rekursiv gerufen. Um die Bewertung dieser Züge brauchst Du Dir keine Gedanken zu machen, da sie ja erst bei Zurückspringen aus einer Rekursion wirklich bewertet werden können. Theoretisch stelltst Du dir das so vor, dass erst einmal ziemlich tief in die Zukunft hinunterrekursiert wird und dann dort ein Ereignis auftritt, das ein messbares Ergebnis hervorbringt. Dies wird dann an die höhere Rekursionsebene gemeldet und damit ist dann einer dieser 7 Züge bewertet. Jetzt kommen die anderen 6 Züge dran, bis auch aus denen durch Zurückkehren aus der Rekursion Ergebnisse vorliegen. Der beste der 7 Züge wird nun an die nächsthöhere Ebene gemeldet, wo er wieder mit seinen 6 Zügen dort verglichen wird, u.s.w bis du ganz oben ankommst. Das Bewerten der Züge kannst Du zunächst einfach unterteilen in: A. Spielende: bei diesem Zug habe ich gewonnen =+100 B. noch hat keiner gewonnen =0 C. Spielende: der Gegner hat gewonnen. = -100 So erhältst Du leider nur 3 Werte und entscheidest so zwar für einen "Siegerweg", aber vielleicht hätte es einen schnelleren Sieg gegeben. Teilst Du das Ergebnis nun z.b. durch die akt. Rekursionstiefe, erhältst Du soetwas wie eine Zeitkomponente: spät gewinnen = 100/20 früh gewinnen = 100/11 ...und damit alle möglichen Werte zwischen -100 und +100

Midimaster

Mi, März 09, 2011 20:21
Antworten mit Zitat

so wie ich das sehe, erstellt generateMoves() alle möglichen Spielzüge der akt. Tiefe für den Spieler der gerade dran ist. D.h. bei "4 gewinnt" kommen 7 Züge hinzu.

Dann werden alle 7 Züge wirklich gezogen MakeMove und natürlich anschließend wieder zurückgenommen. UndoMove. Während der 7 Versuche wird dann die AlphaBeta wieder rekursiv gerufen.

Um die Bewertung dieser Züge brauchst Du Dir keine Gedanken zu machen, da sie ja erst bei Zurückspringen aus einer Rekursion wirklich bewertet werden können. Theoretisch stelltst Du dir das so vor, dass erst einmal ziemlich tief in die Zukunft hinunterrekursiert wird und dann dort ein Ereignis auftritt, das ein messbares Ergebnis hervorbringt. Dies wird dann an die höhere Rekursionsebene gemeldet und damit ist dann einer dieser 7 Züge bewertet. Jetzt kommen die anderen 6 Züge dran, bis auch aus denen durch Zurückkehren aus der Rekursion Ergebnisse vorliegen. Der beste der 7 Züge wird nun an die nächsthöhere Ebene gemeldet, wo er wieder mit seinen 6 Zügen dort verglichen wird, u.s.w bis du ganz oben ankommst.

Das Bewerten der Züge kannst Du zunächst einfach unterteilen in:

A. Spielende: bei diesem Zug habe ich gewonnen =+100

B. noch hat keiner gewonnen =0

C. Spielende: der Gegner hat gewonnen. = -100

So erhältst Du leider nur 3 Werte und entscheidest so zwar für einen "Siegerweg", aber vielleicht hätte es einen schnelleren Sieg gegeben.

Teilst Du das Ergebnis nun z.b. durch die akt. Rekursionstiefe, erhältst Du soetwas wie eine Zeitkomponente:

spät gewinnen = 100/20
früh gewinnen = 100/11

...und damit alle möglichen Werte zwischen -100 und +100

Zuletzt bearbeitet von Midimaster am Mi, März 09, 2011 20:23, insgesamt einmal bearbeitet

	Kernel32	Mi, März 09, 2011 20:22 Antworten mit Zitat
Sorry, das ist mir irgendwie immer noch zu abstrakt -also ich verstehe schon, warum. Aber eben nicht WIE. Gibt es irgendwo ein Beispiel einer Funktion wie generateMoves(), damit ich mir mal ein Bild davon machen kann, was da eigentlich passiert? Oder könnt ihr vielleicht nur mal ganz grob in Peusdo-Code oder Stichworten skizzieren, wie die aussehen müsste? Und wonach wird in obigem Beispiel die Moves-Liste überhaupt sortiert? Nach Wertung? Aber wie bewertet man ein Feld? Fehlt da nicht noch eine Funktion wie evaluatePosition() die jedem Feld einen gut/schlecht Wert verpasst? Ich bin total groggy
------------- 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

Mi, März 09, 2011 20:22
Antworten mit Zitat

Sorry, das ist mir irgendwie immer noch zu abstrakt -also ich verstehe schon, warum. Aber eben nicht WIE.

Gibt es irgendwo ein Beispiel einer Funktion wie generateMoves(), damit ich mir mal ein Bild davon machen kann, was da eigentlich passiert? Oder könnt ihr vielleicht nur mal ganz grob in Peusdo-Code oder Stichworten skizzieren, wie die aussehen müsste?

Und wonach wird in obigem Beispiel die Moves-Liste überhaupt sortiert? Nach Wertung? Aber wie bewertet man ein Feld?

Fehlt da nicht noch eine Funktion wie evaluatePosition() die jedem Feld einen gut/schlecht Wert verpasst?

Ich bin total groggy Shocked

	Midimaster	Mi, März 09, 2011 20:27 Antworten mit Zitat
also GenerateMoves() erstellt eine Liste alle 7 Züge, die rein theoretisch möglich sind: ein Reinwerfen der Chips in eine der 7 Rippen. MakeMove() spielt wirklich das Spiel mit einer dieser 7 aus der Liste. evaluatePosition() stellt fest: verloren, gewonnen oder weitermachen. Deshalb habe ich ja vorhin gefragt, ob Du das schon fertig hast....

Midimaster

Mi, März 09, 2011 20:27
Antworten mit Zitat

also GenerateMoves() erstellt eine Liste alle 7 Züge, die rein theoretisch möglich sind: ein Reinwerfen der Chips in eine der 7 Rippen.

MakeMove() spielt wirklich das Spiel mit einer dieser 7 aus der Liste.

evaluatePosition() stellt fest: verloren, gewonnen oder weitermachen.

Deshalb habe ich ja vorhin gefragt, ob Du das schon fertig hast....

	D2006 Administrator	Mi, März 09, 2011 20:38 Antworten mit Zitat
Rein theoretisch reicht es, die Bewertung nur nach gewonnen oder verloren vorzunehmen. In der Praxis wird dir die exponentiell ansteigende Rechenzeit einen Strich durch die Rechnung machen (ich hab keine praktische Erfahrung bei 4 gewinnt, wohl aber bei GoBang und Hexagon, wobei da auch jeweils das Spielfeld enorm größer ist) Deine Bewertungsfunktion sollte also Zwischenstufen erkennen. Zum Beispiel eine Reihe von drei Steinen der eigenen Farbe als positiv bewerten und sowas. Allerdings darf die Bewertungsfunktion nicht zu komplex sein, da sie ja oft aufgerufen wird (bei ner Suchtiefe von 2 schon 49 mal, bei 3 schon 343 ... hm irgendwie lächerlich wenig. bei Gobang hatte ich bei 2 schon über 50.000) Übrigens musst du abwechselnd den besten und schlechtesten Zug nach oben durchreichen. Jeder zweite Zug wird ja für den Gegner berechnet und da nimmt der Alogrithmus an, dass dieser genau wie er selbst perfekt spielen will.
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

Mi, März 09, 2011 20:38
Antworten mit Zitat

Rein theoretisch reicht es, die Bewertung nur nach gewonnen oder verloren vorzunehmen. In der Praxis wird dir die exponentiell ansteigende Rechenzeit einen Strich durch die Rechnung machen (ich hab keine praktische Erfahrung bei 4 gewinnt, wohl aber bei GoBang und Hexagon, wobei da auch jeweils das Spielfeld enorm größer ist)

Deine Bewertungsfunktion sollte also Zwischenstufen erkennen. Zum Beispiel eine Reihe von drei Steinen der eigenen Farbe als positiv bewerten und sowas. Allerdings darf die Bewertungsfunktion nicht zu komplex sein, da sie ja oft aufgerufen wird (bei ner Suchtiefe von 2 schon 49 mal, bei 3 schon 343 ... hm irgendwie lächerlich wenig. bei Gobang hatte ich bei 2 schon über 50.000)

Übrigens musst du abwechselnd den besten und schlechtesten Zug nach oben durchreichen. Jeder zweite Zug wird ja für den Gegner berechnet und da nimmt der Alogrithmus an, dass dieser genau wie er selbst perfekt spielen will.

	PSY	Mi, März 09, 2011 22:49 Antworten mit Zitat
Hoi, zu Beginn wird erstmal die Suchtiefe festgelegt. Bei einer Tiefe von 6-7 und entsprechender Evaluierung merkt man da schon merklich, wie die CPU anfängt zu qualmen Sagen wir mal die Suchtiefe ist 3, Du bist ROT, und ROT ist am Zug. Der Algorithmus wirft dann nacheinander rot, gelb, rot in das Spielfeld, und zwar in allen möglichen Kombinationen, rekursiv halt. Wenn die Rekursion bei Suchtiefe 0 ankommt, weiss sie, dass sie das Ende des momentanen Astes abgearbeitet hat und springt in die Bewertungsfunktion. Da wird dann das ganze Spielfeld bewertet. Wie das passiert, bleibt Dir überlassen. Das ganze kann zB so aussehn: -Steine die sich eher in der Mitte des Spielfeldes befinden bekommen eine höhere Wertung als welche am Rand. -Liegen mehrere Steine nebeneinander, steigt die Bewertung entsprechend. Sagen wir mal, im Spielfeld liegen 4x 3 rote Steine nebeneinander, dann ist die Bewertung demenstprechend hoch. Das kannste zB exponentiell lösen...lange Reihen verursachen dann dementsprechend hohe Bewertungen -Liegen 4 Steine nebeneinander, gibts nen maximale Bewertung (100000000000 zB) Denk dran, dass Du jeweils ROT und GELB verschieden bewerten musst beim negamax-algo. Und das Vorzeichen der Bewertung (WERT) ist abhängig von der Suchtiefe --->WERT * 1 oder WERT *(-1). Das hängt damit zusammen, dass je nach Suchtiefe (gerade oder ungerade) positive oder negative Werte nach oben gereicht werden. Hab mal ne 4 Gewinnt-KI fürnen Contest hier geschrieben, aber konnte sie aus Zeitgründen nicht abgeben. Müsste mich mal wieder in den Code einarbeiten. Hab sie auch gegen alle anderen KI's der Teilnehmer spielen lassen (jemand hat ein Tool geschrieben mit dem das funzte). Ich glaub die hat die alle plattgemacht Such mal im Forum nach dem 4-Gewinnt Contest...BCC 25 glaub ich wars. L8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Mi, März 09, 2011 22:49
Antworten mit Zitat

Hoi,

zu Beginn wird erstmal die Suchtiefe festgelegt. Bei einer Tiefe von 6-7 und entsprechender Evaluierung merkt man da schon merklich, wie die CPU anfängt zu qualmen Very Happy

Sagen wir mal die Suchtiefe ist 3, Du bist ROT, und ROT ist am Zug.
Der Algorithmus wirft dann nacheinander rot, gelb, rot in das Spielfeld, und zwar in allen möglichen Kombinationen, rekursiv halt. Wenn die Rekursion bei Suchtiefe 0 ankommt, weiss sie, dass sie das Ende des momentanen Astes abgearbeitet hat und springt in die Bewertungsfunktion.
Da wird dann das ganze Spielfeld bewertet. Wie das passiert, bleibt Dir überlassen. Das ganze kann zB so aussehn:
-Steine die sich eher in der Mitte des Spielfeldes befinden bekommen eine höhere Wertung als welche am Rand.
-Liegen mehrere Steine nebeneinander, steigt die Bewertung entsprechend. Sagen wir mal, im Spielfeld liegen 4x 3 rote Steine nebeneinander, dann ist die Bewertung demenstprechend hoch. Das kannste zB exponentiell lösen...lange Reihen verursachen dann dementsprechend hohe Bewertungen
-Liegen 4 Steine nebeneinander, gibts nen maximale Bewertung (100000000000 zB)

Denk dran, dass Du jeweils ROT und GELB verschieden bewerten musst beim negamax-algo.
Und das Vorzeichen der Bewertung (WERT) ist abhängig von der Suchtiefe --->WERT * 1 oder WERT *(-1). Das hängt damit zusammen, dass je nach Suchtiefe (gerade oder ungerade) positive oder negative Werte nach oben gereicht werden.

Hab mal ne 4 Gewinnt-KI fürnen Contest hier geschrieben, aber konnte sie aus Zeitgründen nicht abgeben.
Müsste mich mal wieder in den Code einarbeiten.
Hab sie auch gegen alle anderen KI's der Teilnehmer spielen lassen (jemand hat ein Tool geschrieben mit dem das funzte). Ich glaub die hat die alle plattgemacht Very Happy

Such mal im Forum nach dem 4-Gewinnt Contest...BCC 25 glaub ich wars.

L8er,
PSY

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

	BlitzMoritz	Mi, März 09, 2011 23:03 Antworten mit Zitat
Herrliches Thema, ebenso faszinierend wie vertrackt. Vielleicht findest du beim BCC#25 oder bei meinem Take Five, in dem du selbst eine KI programmieren kannst, die gegen das Programm spielt, ein paar Anregungen. Habe mich jüngst an einer KI für ein dreidimensionales 4-gewinnt-Spiel gemacht. Sobald man die bescheidenen Regeln des ursprünglichen 4-gewinnt-Spiels erweitert, sprengt die Vielzahl der Möglichkeiten jeden Rahmen. Das Gewicht meiner KI's war bisher meist auf die Untersuchung von wenigen strategisch guten Positionen mit möglichst vielen potentiellen Gewinnmöglichkeiten verlagert und kaum in eine vorausschauende iterative Spielzuganalyse, wie D sagt, wächst die potentiell rasend schnell an. Letzten Endes bin ich aber etwas skeptisch geworden, ob solche Spiele wirklich beliebt sind: Der ganze Ehrgeiz des Programmiers gilt dem Ersinnen einer KI, die stärker ist als der menschliche Spieler. Je besser ihm das gelungen ist, desto weniger Spaß wird es dem Spieler machen, weil er ständig verliert. Irgendwie ist da der Wurm im Spielkonzept drin. Vom Abwechslungsfaktor ganz zu schweigen, der noch einmal eine ganz andere Sache ist, denn die "optimale" KI kennt keine "Kompromisse", wer will jedoch immer dieselbe Partie spielen, selbst wenn er eine Lücke gefunden und gewonnen hat? Edit: PSY hat Folgendes geschrieben: Hab mal ne 4 Gewinnt-KI fürnen Contest hier geschrieben, aber konnte sie aus Zeitgründen nicht abgeben... Hab sie auch gegen alle anderen KI's der Teilnehmer spielen lassen. Ich glaub die hat die alle plattgemacht. Wie schaaade, dass wir dieses Erlebnis von dir nicht teilen durften, das wäre bestimmt spannend geworden.

BlitzMoritz

Mi, März 09, 2011 23:03
Antworten mit Zitat

Herrliches Thema, ebenso faszinierend wie vertrackt. Vielleicht findest du beim BCC#25 oder bei meinem Take Five, in dem du selbst eine KI programmieren kannst, die gegen das Programm spielt, ein paar Anregungen. Habe mich jüngst an einer KI für ein dreidimensionales 4-gewinnt-Spiel gemacht. Sobald man die bescheidenen Regeln des ursprünglichen 4-gewinnt-Spiels erweitert, sprengt die Vielzahl der Möglichkeiten jeden Rahmen. Das Gewicht meiner KI's war bisher meist auf die Untersuchung von wenigen strategisch guten Positionen mit möglichst vielen potentiellen Gewinnmöglichkeiten verlagert und kaum in eine vorausschauende iterative Spielzuganalyse, wie D sagt, wächst die potentiell rasend schnell an.

Letzten Endes bin ich aber etwas skeptisch geworden, ob solche Spiele wirklich beliebt sind:
Der ganze Ehrgeiz des Programmiers gilt dem Ersinnen einer KI, die stärker ist als der menschliche Spieler.
Je besser ihm das gelungen ist, desto weniger Spaß wird es dem Spieler machen, weil er ständig verliert. Irgendwie ist da der Wurm im Spielkonzept drin. Vom Abwechslungsfaktor ganz zu schweigen, der noch einmal eine ganz andere Sache ist, denn die "optimale" KI kennt keine "Kompromisse", wer will jedoch immer dieselbe Partie spielen, selbst wenn er eine Lücke gefunden und gewonnen hat?

Edit:
PSY hat Folgendes geschrieben:

Hab mal ne 4 Gewinnt-KI fürnen Contest hier geschrieben, aber konnte sie aus Zeitgründen nicht abgeben... Hab sie auch gegen alle anderen KI's der Teilnehmer spielen lassen. Ich glaub die hat die alle plattgemacht.

Wie schaaade, dass wir dieses Erlebnis von dir nicht teilen durften, das wäre bestimmt spannend geworden. Wink

	PSY	Do, März 10, 2011 7:51 Antworten mit Zitat
@blitzmoritz ich hab die noch hab sie eben mal gegen die andern 4 KI's spielen lassen...sie hat nix verlernt g mal sehn, vllt feil ich noch ein wenig dran rum. wollte mal eine art tournament draus machen, wo man gegen immer stärker werdende gegner (auch mit unterschiedlicher KI) spielt...mal sehn vllt setzt ich mich im frühjahr mal dran ^^ l8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Do, März 10, 2011 7:51
Antworten mit Zitat

@blitzmoritz

ich hab die noch Very Happy

hab sie eben mal gegen die andern 4 KI's spielen lassen...sie hat nix verlernt *g*

mal sehn, vllt feil ich noch ein wenig dran rum. wollte mal eine art tournament draus machen, wo man gegen immer stärker werdende gegner (auch mit unterschiedlicher KI) spielt...mal sehn vllt setzt ich mich im frühjahr mal dran ^^

l8er,
PSY

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

	Midimaster	Do, März 10, 2011 8:55 Antworten mit Zitat
Bei einem Spiel baust Du mehrere KI-Algos ein, damit verschiedene Level erreicht werden können. Sonst hast Du wirklich keinen Spaß mit dem Programm. Ich denke da an diese Level Level 0-: Computer kann gerade mal die Steine richtig reinwerfen. Ist schon zufrieden, wenn er gleich in der ersten Ebene eine Stelle gefunden hat. (wichtiges Level gegen Kinder) Weitere Level entstehen durch weitere Annahmen, z.B.: - "wenn möglich neben einen Gegnerstein plazieren" - "lieber in die Mitte als am Rand" - "gerne neben einen eigenen" Level 10-: Computer versucht nicht zu verlieren. Diese KI ignoriert hartnäckig ihre Gewinnchancen, verwirft aber alles, wo sie verlieren würde. Durch verschiedene Suchtiefen erreichst Du weitere Level. Level 20-: Computer versucht zu gewinnen. Diese KI setzt auf Züge, wo sie gewinnnen könnte. Durch verschiedene Suchtiefen erreichst Du weitere Level. Alle diese Levels unterscheiden sich nur im Bewertungsmaßstab der Felder, der Suchalgo bleibt immer der gleiche.

Midimaster

Do, März 10, 2011 8:55
Antworten mit Zitat

Bei einem Spiel baust Du mehrere KI-Algos ein, damit verschiedene Level erreicht werden können.

Sonst hast Du wirklich keinen Spaß mit dem Programm.

Ich denke da an diese Level

Level 0-:
Computer kann gerade mal die Steine richtig reinwerfen. Ist schon zufrieden, wenn er gleich in der ersten Ebene eine Stelle gefunden hat. (wichtiges Level gegen Kinder) Weitere Level entstehen durch weitere Annahmen, z.B.:
- "wenn möglich neben einen Gegnerstein plazieren"
- "lieber in die Mitte als am Rand"
- "gerne neben einen eigenen"

Level 10-:
Computer versucht nicht zu verlieren. Diese KI ignoriert hartnäckig ihre Gewinnchancen, verwirft aber alles, wo sie verlieren würde. Durch verschiedene Suchtiefen erreichst Du weitere Level.

Level 20-:
Computer versucht zu gewinnen. Diese KI setzt auf Züge, wo sie gewinnnen könnte. Durch verschiedene Suchtiefen erreichst Du weitere Level.

Alle diese Levels unterscheiden sich nur im Bewertungsmaßstab der Felder, der Suchalgo bleibt immer der gleiche.

	BlitzMoritz	Do, März 10, 2011 8:57 Antworten mit Zitat
@PSY: Ich hatte nämlich auch eine KI gemacht. Die war statistisch besser als die anderen, durfte aber nicht teilnehmen, da ich ja der Wettbewerbsausrichter war Den Download habe ich 'runtergenommen, aber ich such's in den nächsten Tage zuhause noch einmal heraus. Dann können wir sie uns gegenseitig schicken und schauen, welche häufiger gewinnt Und wenn deine wirklich alle totschlägt, bist du Zwangs-engagiert für mein 4-gewinnt-3D-Projekt, hehe

BlitzMoritz

Do, März 10, 2011 8:57
Antworten mit Zitat

@PSY: Ich hatte nämlich auch eine KI gemacht. Die war statistisch besser als die anderen, durfte aber nicht teilnehmen, da ich ja der Wettbewerbsausrichter war Confused

Den Download habe ich 'runtergenommen, aber ich such's in den nächsten Tage zuhause noch einmal heraus. Dann können wir sie uns gegenseitig schicken und schauen, welche häufiger gewinnt Smile

Und wenn deine wirklich alle totschlägt, bist du Zwangs-engagiert für mein 4-gewinnt-3D-Projekt, hehe Cool

Zuletzt bearbeitet von BlitzMoritz am Do, März 10, 2011 10:50, insgesamt einmal bearbeitet

	Holzchopf Meisterpacker	Do, März 10, 2011 10:05 Antworten mit Zitat
Die Schwierigkeit, Vier-Gewinnt-KIs (und solche ähnlicher Spiele) zu programmieren, ist ja nicht die "Intelligenz" an sich, sondern die Dummheit, die noch vorhanden sein muss, damit ein menschlicher Spieler auch die Chance hat zu gewinnen, aber dabei das "Blödheits"-Muster der KI nicht erkennen kann. Bei einem Spiel wie vier Gewinnt ist es möglich, eine perfekte KI zu schreiben, die im schlechtesten Falle ein Unentschieden erspielt. Aber man sollte nie vergessen, dass dies u.U. gar nicht erwünscht ist. Man muss dann von Beginn an schon eine Strategie aushecken, wie man die KI elegant dazu bringt, bestimmte Gewinnchancen oder fatale Fehler zu übersehen. Ich hab' mal für ein Java-Projekt in der Schule eine Vier-Gewinnt-KI implementiert. 4 Stufen hatte die. Statistisch zumindest. Denn Stufe 4 gewann in 90% der Fälle gegen Stufe 3, diese zu 90% gegen Stufe 2 und so weiter, aber als Mensch hat man kaum einen Unterschied festgestellt, weil man nach 2/3 Spielen das Muster eh immer durchschaut hat.
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf CC BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018) Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

Holzchopf

Meisterpacker

Do, März 10, 2011 10:05
Antworten mit Zitat

Die Schwierigkeit, Vier-Gewinnt-KIs (und solche ähnlicher Spiele) zu programmieren, ist ja nicht die "Intelligenz" an sich, sondern die Dummheit, die noch vorhanden sein muss, damit ein menschlicher Spieler auch die Chance hat zu gewinnen, aber dabei das "Blödheits"-Muster der KI nicht erkennen kann. Bei einem Spiel wie vier Gewinnt ist es möglich, eine perfekte KI zu schreiben, die im schlechtesten Falle ein Unentschieden erspielt. Aber man sollte nie vergessen, dass dies u.U. gar nicht erwünscht ist. Man muss dann von Beginn an schon eine Strategie aushecken, wie man die KI elegant dazu bringt, bestimmte Gewinnchancen oder fatale Fehler zu übersehen.

Ich hab' mal für ein Java-Projekt in der Schule eine Vier-Gewinnt-KI implementiert. 4 Stufen hatte die. Statistisch zumindest. Denn Stufe 4 gewann in 90% der Fälle gegen Stufe 3, diese zu 90% gegen Stufe 2 und so weiter, aber als Mensch hat man kaum einen Unterschied festgestellt, weil man nach 2/3 Spielen das Muster eh immer durchschaut hat.

Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

	Kernel32	Do, März 10, 2011 17:41 Antworten mit Zitat
Also ich denke, das es in der Tat einfach ist, eine "perfekte" KI "dümmer" zu machen, als andersrum. Deshalb möchte ich mich zuerst mal auf einen möglichst guten Algo konzentrieren und kann dann ja immer noch sehen, wie man "Schwächen" einbauen kann. Ich führe mir gerade mal PSY's Code vom Contest Zeile für Zeile zu Gemüte, was ich mom. nicht ganz verstehe, ist die Aufgabe folgender Arrays bzw. Variablen: 1.) movesLeft(searchDepth) - Ist das die "Tiefe" des Baums? 2.) slot(6, searchDepth) - Sind das die Spalten, in denen pro virtuellem Zug die "Probierwürfe" gespeichert werden? 3.) undoX(searchDepth) undoY(searchDepth) - Die beiden undo's verstehe ich noch nicht ganz... 4.) player2rate und currentPlayer - Ist player2rate der Spieler, dessen Zug beim jeweils aktuellen Aufruf der Funktion simuliert wird? Ich komme da wegen den Bezeichnungen echt durcheinander
------------- 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

Do, März 10, 2011 17:41
Antworten mit Zitat

Also ich denke, das es in der Tat einfach ist, eine "perfekte" KI "dümmer" zu machen, als andersrum. Deshalb möchte ich mich zuerst mal auf einen möglichst guten Algo konzentrieren und kann dann ja immer noch sehen, wie man "Schwächen" einbauen kann.

Ich führe mir gerade mal PSY's Code vom Contest Zeile für Zeile zu Gemüte, was ich mom. nicht ganz verstehe, ist die Aufgabe folgender Arrays bzw. Variablen:

1.) movesLeft(searchDepth)
- Ist das die "Tiefe" des Baums?

2.) slot(6, searchDepth)
- Sind das die Spalten, in denen pro virtuellem Zug die "Probierwürfe" gespeichert werden?

3.)
undoX(searchDepth)
undoY(searchDepth)
- Die beiden undo's verstehe ich noch nicht ganz...

4.) player2rate und currentPlayer
- Ist player2rate der Spieler, dessen Zug beim jeweils aktuellen Aufruf der Funktion simuliert wird? Ich komme da wegen den Bezeichnungen echt durcheinander Sad

	PSY	Do, März 10, 2011 18:38 Antworten mit Zitat
BlitzMoritz hat Folgendes geschrieben: @PSY: Ich hatte nämlich auch eine KI gemacht. Die war statistisch besser als die anderen, durfte aber nicht teilnehmen, da ich ja der Wettbewerbsausrichter war Den Download habe ich 'runtergenommen, aber ich such's in den nächsten Tage zuhause noch einmal heraus. Dann können wir sie uns gegenseitig schicken und schauen, welche häufiger gewinnt Und wenn deine wirklich alle totschlägt, bist du Zwangs-engagiert für mein 4-gewinnt-3D-Projekt, hehe Hey, das wusste ich nicht Ja, wenn Du Zeit hast such sie mal raus, würd mich echt mal interessieren wie stark die ist. Werd mich die Tage auch mal wieder an die Bewertungsfunktion setzten, da müsste noch einiges zu verbessern sein. Es gibt bis jetzt quasi 3 Spielstyles...neutral - agressiv - defensiv, wobei der neutrale am besten spielt, da muss ich noch dran tweaken. 4D 3-gewinnt? Das wär was für Spock Aber der steht ja eher auf Schach: http://cgi.ebay.de/Star-Trek-d...3a63e76337 Schade dass das Brett so teuer ist Oo L8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Do, März 10, 2011 18:38
Antworten mit Zitat

BlitzMoritz hat Folgendes geschrieben:

@PSY: Ich hatte nämlich auch eine KI gemacht. Die war statistisch besser als die anderen, durfte aber nicht teilnehmen, da ich ja der Wettbewerbsausrichter war Confused

Den Download habe ich 'runtergenommen, aber ich such's in den nächsten Tage zuhause noch einmal heraus. Dann können wir sie uns gegenseitig schicken und schauen, welche häufiger gewinnt Smile

Und wenn deine wirklich alle totschlägt, bist du Zwangs-engagiert für mein 4-gewinnt-3D-Projekt, hehe Cool

Hey,

das wusste ich nicht Very Happy

Ja, wenn Du Zeit hast such sie mal raus, würd mich echt mal interessieren wie stark die ist.
Werd mich die Tage auch mal wieder an die Bewertungsfunktion setzten, da müsste noch einiges zu verbessern sein.
Es gibt bis jetzt quasi 3 Spielstyles...neutral - agressiv - defensiv, wobei der neutrale am besten spielt, da muss ich noch dran tweaken.

4D 3-gewinnt? Das wär was für Spock Smile

Aber der steht ja eher auf Schach:

http://cgi.ebay.de/Star-Trek-d...3a63e76337

Schade dass das Brett so teuer ist Oo

L8er,
PSY

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

	PSY	Do, März 10, 2011 19:12 Antworten mit Zitat
Kernel32 hat Folgendes geschrieben: Also ich denke, das es in der Tat einfach ist, eine "perfekte" KI "dümmer" zu machen, als andersrum. Deshalb möchte ich mich zuerst mal auf einen möglichst guten Algo konzentrieren und kann dann ja immer noch sehen, wie man "Schwächen" einbauen kann. Ich führe mir gerade mal PSY's Code vom Contest Zeile für Zeile zu Gemüte, was ich mom. nicht ganz verstehe, ist die Aufgabe folgender Arrays bzw. Variablen: ( Die KI ausm Forum ist veraltet, hab sie nach der Veröffentlichung noch ein wenig weiterentwickelt (Steine in mittigen Positionen wirken sich stärker auf die Wertung aus, Steinketten (mehrere Steine nebeneinander) werden exponentiell bewertet, es gibt verschiedene Styles...). Die "aktuelle" KI spielt auch wesentlich stärker. movesLeft(searchDepth): searchDepth ist die Suchbaumtiefe (absolut), d.h. wie tief geht die KI im Suchbaum movesLeft(depth) Darin ist einfach gespeichert, wieviele Züge auf der aktuellen Tiefe (depth) noch auszuprobieren sind. Die KI überprüft alle Spalten. Kann in jede Spalte noch ein Stein geworfen werden (keine Spalte ist voll) dann ist die aktuelle Anzahl der auszutestenden Züge auf der jeweiligen Stufe 7. Damit weiss die KI, wieviel Züge sie noch ausprobieren muss. slot(6, searchDepth) Wenn TRUE, wird in Spalte 6 der aktuellen Tiefe noch ein (virtueller) Stein reingeworfen. Wenn FALSE, dann wurde schon probiert, oder Spalte ist voll. undoX(searchDepth) undoY(searchDepth) Das ist einfach, alle Probierwürfe müssen ja schliesslich wieder zurückgenommen werden, und zwar jedesmal wenn in der Rekursion wieder zurückgegangen wird, um einen anderen Ast auszuprobieren. 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 L8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Do, März 10, 2011 19:12
Antworten mit Zitat

Kernel32 hat Folgendes geschrieben:

Die KI ausm Forum ist veraltet, hab sie nach der Veröffentlichung noch ein wenig weiterentwickelt (Steine in mittigen Positionen wirken sich stärker auf die Wertung aus, Steinketten (mehrere Steine nebeneinander) werden exponentiell bewertet, es gibt verschiedene Styles...).

Die "aktuelle" KI spielt auch wesentlich stärker.

movesLeft(searchDepth):
searchDepth ist die Suchbaumtiefe (absolut), d.h. wie tief geht die KI im Suchbaum
movesLeft(depth)
Darin ist einfach gespeichert, wieviele Züge auf der aktuellen Tiefe (depth) noch auszuprobieren sind. Die KI überprüft alle Spalten. Kann in jede Spalte noch ein Stein geworfen werden (keine Spalte ist voll) dann ist die aktuelle Anzahl der auszutestenden Züge auf der jeweiligen Stufe 7. Damit weiss die KI, wieviel Züge sie noch ausprobieren muss.

slot(6, searchDepth)
Wenn TRUE, wird in Spalte 6 der aktuellen Tiefe noch ein (virtueller) Stein reingeworfen. Wenn FALSE, dann wurde schon probiert, oder Spalte ist voll.

undoX(searchDepth)
undoY(searchDepth)
Das ist einfach, alle Probierwürfe müssen ja schliesslich wieder zurückgenommen werden, und zwar jedesmal wenn in der Rekursion wieder zurückgegangen wird, um einen anderen Ast auszuprobieren.

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

L8er,
PSY

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

	BlitzMoritz	Do, März 10, 2011 19:42 Antworten mit Zitat
Da die Downloadlinks aus dem BCC-Thread tot waren, habe ich hier noch einmal die Aufgabe inklusive den Netzwerk-Client von Firstdeathmaker zwecks Turnierspiele und alle Ergebnisse inklusive meiner KI hochgeladen. Vielleicht ist in den Quellcodes ja auch für Kernel etwas dabei. @PSY: Du müsstest deine KI mit dem Netwerk-Client kompilieren und im Turnier gegen meine spielen lassen, dann poste mal die Statistik nach 40 Spielen. Ach ja, und das mit meinem 4-gewinnt-3D war keine heiße Luft. Ich habe auch größere Dimensionen, also etwa 6 x 6 x 6 eingebaut, aber das birgt neue Probleme: Derjenige, der anfängt, gewinnt immer. Das ist natürlich indiskutabel und es müssen von Anfang an neutrale Barrieren aufgestellt werden, um es zu verhindern.

BlitzMoritz

Do, März 10, 2011 19:42
Antworten mit Zitat

Da die Downloadlinks aus dem BCC-Thread tot waren, habe ich hier noch einmal die Aufgabe inklusive den Netzwerk-Client von Firstdeathmaker zwecks Turnierspiele und alle Ergebnisse inklusive meiner KI hochgeladen.
Vielleicht ist in den Quellcodes ja auch für Kernel etwas dabei.

@PSY: Du müsstest deine KI mit dem Netwerk-Client kompilieren und im Turnier gegen meine spielen lassen, dann poste mal die Statistik nach 40 Spielen. Cool

Ach ja, und das mit meinem 4-gewinnt-3D war keine heiße Luft. Ich habe auch größere Dimensionen, also etwa 6 x 6 x 6 eingebaut, aber das birgt neue Probleme: Derjenige, der anfängt, gewinnt immer. Sad

Das ist natürlich indiskutabel und es müssen von Anfang an neutrale Barrieren aufgestellt werden, um es zu verhindern.

Zuletzt bearbeitet von BlitzMoritz am Di, Mai 31, 2011 20:03, insgesamt einmal bearbeitet

	PSY	Do, März 10, 2011 21:06 Antworten mit Zitat
Hey, ui das 3D 4-Gewinnt sieht ja echt nett aus Hm iwie kommts mir so vor als ob der Netzwerkcode für die KIs fehlerhaft ist. Ich spiel zb ne Runde geben Comnic, da dauerts in den ersten 10 Runden relativ lang pro Runde, und ich führ 10:0. Dann gehts auf einmal rasend schnell, und Comnic macht einen Punkt nach dem nächsten...das geht gegen andere KI's ähnlich. Solang die Runden am Anfang länger dauern, ist meine KI meist besser, danach gehts auf einmal schneller und sie geht den Bach runter. Irgendwas stimmt da nich... L8er, PSY EDIT: Oder liegts an der KI? Nach ein paar Zügen sinkt die Rechenzeit pro Zug laut Netzwerkcode drastisch...hat fast den Eindruck als würde die Suchtiefe automatisch sinken....echt seltsam. Wenn ich morgen Zeit hab schau ich mir's mal genauer an.
PSY LABS Games Coders don't die, they just gosub without return

PSY

Do, März 10, 2011 21:06
Antworten mit Zitat

Hey,

ui das 3D 4-Gewinnt sieht ja echt nett aus Very Happy

Hm iwie kommts mir so vor als ob der Netzwerkcode für die KIs fehlerhaft ist. Ich spiel zb ne Runde geben Comnic, da dauerts in den ersten 10 Runden relativ lang pro Runde, und ich führ 10:0. Dann gehts auf einmal rasend schnell, und Comnic macht einen Punkt nach dem nächsten...das geht gegen andere KI's ähnlich.
Solang die Runden am Anfang länger dauern, ist meine KI meist besser, danach gehts auf einmal schneller und sie geht den Bach runter.

Irgendwas stimmt da nich...

L8er,
PSY

EDIT: Oder liegts an der KI? Nach ein paar Zügen sinkt die Rechenzeit pro Zug laut Netzwerkcode drastisch...hat fast den Eindruck als würde die Suchtiefe automatisch sinken....echt seltsam. Wenn ich morgen Zeit hab schau ich mir's mal genauer an.

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

	PSY	Fr, März 11, 2011 8:49 Antworten mit Zitat
@BLITZMORITZ So, 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 Hab vergessen die Variable zurückzusetzen Oo Naja hier mal die Ergebnisse mit der momentanen KI, Werte in Klammern = REMIS 36-03 (1) PSY - AnniXa 16-16 (8) PSY - BlitzMoritz 32-07 (1) PSY - ComNik 27-06 (7) PSY - FirstDeathMaker 38-02 (0) PSY - Rallimen 29-11 (0) PSY - TimBo Elite 23-17 (0) PSY - TimBo Assassine Wobei meine KI auch ziemlich lahm ist, kein Vergleich zu Deiner. Allerdings ist die Bewertungsfunktion extrem unausgereift, da gibt es noch sehr viel Verbesserungspotential. Mal sehn ob ich die Tage Zeit finde, dann werd ich mal dran tweaken L8er, PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Fr, März 11, 2011 8:49
Antworten mit Zitat

@BLITZMORITZ

So,

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 Very Happy

Hab vergessen die Variable zurückzusetzen Oo

Naja hier mal die Ergebnisse mit der momentanen KI, Werte in Klammern = REMIS

36-03 (1) PSY - AnniXa
16-16 (8) PSY - BlitzMoritz
32-07 (1) PSY - ComNik
27-06 (7) PSY - FirstDeathMaker
38-02 (0) PSY - Rallimen
29-11 (0) PSY - TimBo Elite
23-17 (0) PSY - TimBo Assassine

Wobei meine KI auch ziemlich lahm ist, kein Vergleich zu Deiner. Allerdings ist die Bewertungsfunktion extrem unausgereift, da gibt es noch sehr viel Verbesserungspotential. Mal sehn ob ich die Tage Zeit finde, dann werd ich mal dran tweaken Very Happy

L8er,
PSY

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

Gehe zu Seite 1, 2 Weiter

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

NegaMax-Algorithmus... Kopf raucht!

Betreff: NegaMax-Algorithmus... Kopf raucht!