Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Erst einmal Danke für den Link. Den Wikipedia Aktikel hat er mir erst einmal nicht gebracht, als ich danach gesucht habe. (Und dass ich das durchaus versucht habe, war eigentlich doch verständlich. Diese schnippische Antwort bei jemanden, der es noch nicht einmal schafft, die vermeintlichen Probleme zu beschreiben, die sein Code hat, ist für mich unverständlich.)
Was mir auffällt:
Javascript:
if (hasWon(array, player)) {
return 1;
}
Denn hier wird die Bewertung immer 1 angenommen. Aber die Bewertung ist abhängig vom Spieler. Eigener Sieg ist 1, Gegnerischer Sieg aber -1.
(Dein Wikipedia Artikel: "Eine ideale Bewertungsfunktion ordnet einer Stellung den Wert +1 zu, wenn Spieler A gewinnt, und den Wert −1, wenn Spieler B gewinnt, und 0 bei Unentschieden.")
Also das war etwas voreilig. Wenn man das im Detail betrachtet, dann kommen zwei Fehler auf:
a) Bewertung ist falsch. bewertung(spieler) muss natürlich auch erkennen, wenn der andere Spieler gewonnen hat. Also wenn player dran ist und der Zug zu einem Sieg führen würde, dann wird das nicht richtig erkannt.
b) Die tiefe braucht man nicht als Parameter, aber tiefe==gewünschte tiefe prüft, ob man beim ersten Zug ist. Nur der nächste Zug ist natürlich interessant. Also alles, was in Rekursionen später kommt, soll nicht berücksichtigt werden.
Generell wäre also meine Empfehlung, hier immer erst den original Meta-Code umzusetzen. Der findet sich z.B. unter dem Link, den Du gegeben hast Tobias:
Code:
if (tiefe == 0 or keineZuegeMehr(spieler))
return bewerten(spieler);
int maxWert = -unendlich;
generiereMoeglicheZuege(spieler);
while (noch Zug da) {
fuehreNaechstenZugAus();
int wert = -miniMax(-spieler, tiefe-1);
macheZugRueckgaengig();
if (wert > maxWert) {
maxWert = wert;
if (tiefe == gewuenschteTiefe)
gespeicherterZug = Zug;
}
}
return maxWert;
}
Also geht es darum, dass man benötigt:
a) keineZuegeMehr(spieler) -> Hier kann man Spieler weg lassen, denn keine Züge mehr ist unabhängig davon, wer dran ist.
b) bewerten(spieler) -> Bewertung des Feldes aus Sicht von spieler.
Da das Array übergeben werden soll in Deinem Code, habe ich das auch erst einmal so gelassen. Dann wären diese Funktionen z.B.:
Javascript:
function keineZuegeMehr(array) {
if (hasWon(array, player1)) {
return true;
}
if (hasWon(array, -player1)) {
return true;
}
for (let i = 0; i < array.length; i++) {
if (array[i] == 0) {
return false;
}
}
return true;
}
function bewerte(array, player) {
if (hasWon(array, player)) {
return -1;
}
if (hasWon(array, -player)) {
return 1;
}
return 0;
}
Dann hatte ich gesagt: Tiefe ist wichtig. Im Algorithmus ist die Tiefe aber nur ein Zähler, der herunter gezählt wird. Das Abbruchkriterium ist hier nicht gewünscht, so dass lediglich das erwähnte Kriterium Tiefe == GewünschteTiefe bleibt. Das ist aber einfach die Frage: Bin ich im ersten Aufruf oder in einem rekursiven Aufruf. Also z.B. ein boolean Parameter, der true bzw. false ist.
Damit würde dann minmax so aussehen können:
Javascript:
function minimax(array, player, recursiv) {
if (keineZuegeMehr(array)) {
return bewerte(array, player)
}
let maxScore = -2;
for (let i = 0; i < array.length; i++) {
if (array[i] == 0) {
array[i] = player;
if (hasWon(array, player)) {
array[i] = 0;
return 1;
}
let score = -minimax(array, -player, true);
array[i] = 0;
if (score > maxScore) {
maxScore = score;
if (!recursiv ) {
bestMove = i;
}
}
}
}
return maxScore;
}
Der ganze Code wäre dann (Ich habe noch ein <div id="message"></div> eingefügt:
Javascript:
let array1 = [0, 0, 0, 0, 0, 0, 0, 0, 0];
let player1 = -1;
let bestMove = -1;
function hasWon(array, player) {
for (let i = 0; i < 3; i++) {
let c1 = 0;
let c2 = 0;
for (let j = 0; j < 3; j++) {
const idx = i * 3 + j;
if (array[idx] == player)
c1++;
if (array[j * 3 + i] == player)
c2++;
}
if (c1 == 3 || c2 == 3) {
return true;
}
}
let c1 = 0;
let c2 = 0;
for (let i = 0; i < 3; i++) {
const idx1 = i * 3 + i;
const idx2 = i * 3 + (2 - i);
if (array[idx1] == player)
c1++;
if (array[idx2] == player)
c2++;
}
if (c1 == 3 || c2 == 3) {
return true;
}
return false;
}
function keineZuegeMehr(array) {
if (hasWon(array, player1)) {
return true;
}
if (hasWon(array, -player1)) {
return true;
}
for (let i = 0; i < array.length; i++) {
if (array[i] == 0) {
return false;
}
}
return true;
}
function bewerte(array, player) {
if (hasWon(array, player)) {
return -1;
}
if (hasWon(array, -player)) {
return 1;
}
return 0;
}
function minimax(array, player, recursiv) {
if (keineZuegeMehr(array)) {
return bewerte(array, player)
}
let maxScore = -2;
for (let i = 0; i < array.length; i++) {
if (array[i] == 0) {
array[i] = player;
if (hasWon(array, player)) {
array[i] = 0;
return 1;
}
let score = -minimax(array, -player, true);
array[i] = 0;
if (score > maxScore) {
maxScore = score;
if (!recursiv ) {
bestMove = i;
}
}
}
}
return maxScore;
}
function makeMove() {
let score = minimax(array1, player1, false);
if (bestMove != -1) {
document.getElementById('message').innerHTML += "<br>Next move is: " + bestMove;
array1[bestMove] = player1;
player1 = -player1;
bestMove = -1;
makeTable();
} else {
document.getElementById('message').innerHTML += "<br>No more moves!";
}
}
function clickl(index) {
if (array1[index] == 0) {
array1[index] = player1;
player1 = -player1;
makeTable();
makeMove();
}
}
function makeTable() {
document.getElementById('ta1').innerHTML = '';
for (let i = 0; i < 3; i++) {
let tr = document.createElement('tr');
for (let j = 0; j < 3; j++) {
const idx = i * 3 + j;
let td = document.createElement('td');
let bt = document.createElement('button');
bt.style.width = '50px';
bt.style.height = '25px';
bt.style.border = '1px solid black';
bt.appendChild(document.createTextNode(array1[idx]));
bt.addEventListener('click', function() {
clickl(idx);
});
td.appendChild(bt);
tr.appendChild(td);
}
document.getElementById('ta1').appendChild(tr);
}
}
makeTable();
Ich denke, dass ich damit die beiden prinzipiellen Fehler aufgedeckt habe und ich hoffe, dass die Erklärung auch verständlich war.
Funktioniert leider noch nicht, er spielt "manchmal falsch" und verhindert zum Beispiel nicht obwohl möglich dass Spieler A gewinnt.
Da beide Spieler maximieren, muss die Bewertungsfunktion umso größere Werte liefern, je besser die Brettposition des gerade Ziehenden ist (Funktion bewerten(spieler)). Der Wert wird immer aus dessen Sicht angegeben
Jetzt hatte ich noch einmal kurz Zeit und habe da noch einmal drüber nachgedacht. Was mich an der ganzen Thematik gestört hat, war der fehlende Debugger! Das war ein Zustand, der so für mich nicht akzeptabel war und daher habe ich mich jetzt noch einmal kurz hingesetzt.
Ich habe bisher eigentlich diese ganze JavaScript Entwicklung gescheut aber es ist total einfach und daher einfach einmal kurz der Ablauf ohne eben so Web-Frontends (Die finde ich kontraproduktiv, so schön jsfiddle evtl. am Anfang aussah - eine Debug-Möglichkeit habe ich da zumindest auf Anhieb nicht gefunden....)
Aufbau ist total einfach. Eine einfache html Datei reicht ja schon. Dabei dann einfach einen Rahmen wie folgt nehmen:
HTML:
<html>
<body>
<!-- Hier kommt der HTML Code rein, den man bei jsfiddle in die HTML Box geschrieben hat -->
<table id="ta1"></table>
<div id="message"></div>
<!-- End of insert -->
<!-- Innerhalb des scrript tags kommt dann 1:1 das Script -->
<script>
// Weggelassen ... siehe letzten Post für ganzes Script...
</script>
</body>
</html>
Sowas hat dann den Vorteil, dass es eben eine in sich geschlossene Sache ist, die für jeden relativ einfach zu verwenden ist.
Wenn man das dann z.B. in Chrome öffnet, dann hat man die entsprechende Lösung. Um an den Debugger zu kommen, einfach einmal die Entwicklertools öffnen. Dann kann man auf den Tab Sources clicken, dann sieht man zum einen eine Baumansicht der Sourcen, kann da auf die Datei klicken um da dann Breakpoints zu setzen. Fand ich intuitiv bedienbar. Ansonsten gibt es aber auch Dokumentation z.B. https://developers.google.com/web/tools/chrome-devtools/javascript.
Das habe ich bei der letzten, aktuellen Version so nicht gehabt. Da hat er es immer verhindert. Wenn der Computer gewinnen kann, dann zeigt er den letzten Zug nicht mehr an sondern sagt direkt "No more moves!", das ich dafür noch eingebaut hatte ... Dem könnte man noch einmal nachgehen ...
Kannst Du einmal schreiben, bei welcher Kombination diese Problematik von Dir festgestellt wurde?
Damit hatte ich mich noch nicht im Detail beschäftigt. Ich hatte mir jetzt nur den Negamax Algorithmus etwas angesehen - bisher kannte ich nur den reinen MinMax ohne diese "Erweiterung". Und ich habe beim Tic Tac Toe auch bisher keine Gedanken darauf verschwendet, wie welcher Zug zu bewerten ist. Aus meiner Sicht ist da evtl. eine Verbesserung über flexible Werte denkbar, so dass nicht nur -1, 0 und 1 als Bewertungen erlaubt sind. Dann kann man deutlich dynamischer etwas bewerten. Da wir hier nur ein Gewinnt / Verliert bewertet, wäre da evtl. eine Bewertung a.la. "Sieg in 1 Zug" ist besser als "Sieg in 3 Zügen"....
Daher weiß ich nicht, ob sowas gemeint ist oder nicht.
Als Parallelen aus der Schach-Programmierung wären noch Anregungen:
Wenn der Computer an der Reihe ist und die Mitte ich noch nicht belegt, dann nimmt er die Mitte. (Das könnte eine Parallele sein zu den Eröffnungsbibliotheken.) Aber das könnte auch eine Folge sein von einer Bewertung der Felder. Mitte ist am wertvollsten, dann würde ich gefühlsmäßig die Ecken nehmen und dann erst die mittleren Randfelder.
Ansonsten möchte ich nur kurz anmerken:
Diese JavaScript Entwicklung ist nichts, was ich als mein "Fachgebiet" bezeichnen würde. Die HTML/CSS/JS Grundlagen sind wirklich reine Grundlagen und ich pfusche da den Kollegen da normalerweise nicht in ihr Handwerk
Ach je - ich hatte da absolut nicht aufgepasst bei meinem Code. Sorry:
a) Ich habe in der Methode minimax noch einen Check drin gehabt, ob ein Zug zum Sieg führen würde - der ist natürlich absoluter Quatsch! (Das war am Anfang nur ein Versuch um zu schauen, ob so irgendwie die erste Thematik gelöst werden könnte und ist natürlich Müll.
b) Auf Grund von a) gar nicht gesehen: Ich gebe genau die falschen Werte zurück beim bewerten. Wenn der Spieler, der übergeben wird, gewinnt, dann ist 1 zurück zu geben und nicht -1! (Das ist mir nicht aufgefallen, da er durch a) noch auf richtige Züge gekommen ist. ==> Das mit dem Debugger hätte ich sofort machen sollen - da sieht man sowas schnell...
Javascript:
let array1 = [0, 0, 0, 0, 0, 0, 0, 0, 0];
let player1 = -1;
let bestMove = -1;
function hasWon(array, player) {
for (let i = 0; i < 3; i++) {
let c1 = 0;
let c2 = 0;
for (let j = 0; j < 3; j++) {
const idx = i * 3 + j;
if (array[idx] == player)
c1++;
if (array[j * 3 + i] == player)
c2++;
}
if (c1 == 3 || c2 == 3) {
return true;
}
}
let c1 = 0;
let c2 = 0;
for (let i = 0; i < 3; i++) {
const idx1 = i * 3 + i;
const idx2 = i * 3 + (2 - i);
if (array[idx1] == player)
c1++;
if (array[idx2] == player)
c2++;
}
if (c1 == 3 || c2 == 3) {
return true;
}
return false;
}
function keineZuegeMehr(array) {
if (hasWon(array, player1)) {
return true;
}
if (hasWon(array, -player1)) {
return true;
}
for (let i = 0; i < array.length; i++) {
if (array[i] == 0) {
return false;
}
}
return true;
}
function bewerte(array, player) {
if (hasWon(array, player)) {
return 1;
}
if (hasWon(array, -player)) {
return -1;
}
return 0;
}
function minimax(array, player, recursiv) {
if (keineZuegeMehr(array)) {
return bewerte(array, player)
}
let maxScore = -2;
for (let i = 0; i < array.length; i++) {
if (array[i] == 0) {
array[i] = player;
let score = -minimax(array, -player, true);
array[i] = 0;
if (score > maxScore) {
maxScore = score;
if (!recursiv ) {
bestMove = i;
}
}
}
}
return maxScore;
}
function makeMove() {
let score = minimax(array1, player1, false);
if (bestMove != -1) {
document.getElementById('message').innerHTML += "<br>Next move is: " + bestMove;
array1[bestMove] = player1;
player1 = -player1;
bestMove = -1;
makeTable();
} else {
document.getElementById('message').innerHTML += "<br>No more moves!";
}
}
function clickl(index) {
if (array1[index] == 0) {
array1[index] = player1;
player1 = -player1;
makeTable();
makeMove();
}
}
function makeTable() {
document.getElementById('ta1').innerHTML = '';
for (let i = 0; i < 3; i++) {
let tr = document.createElement('tr');
for (let j = 0; j < 3; j++) {
const idx = i * 3 + j;
let td = document.createElement('td');
let bt = document.createElement('button');
bt.style.width = '50px';
bt.style.height = '25px';
bt.style.border = '1px solid black';
bt.appendChild(document.createTextNode(array1[idx]));
bt.addEventListener('click', function() {
clickl(idx);
});
td.appendChild(bt);
tr.appendChild(td);
}
document.getElementById('ta1').appendChild(tr);
}
}
makeTable();
Damit funktioniert es nun hoffentlich. Die ersten Tests waren erfolgversprechend. Was man noch machen könnte, wäre nach jedem Zug prüfen, ob noch Züge möglich sind. Jetzt gewinnt er aber ohne das Spiel direkt als beendet zu erklären. Also z.B. im click1() prüfen:
- direkt am Anfang: Wenn keine Züge mehr möglich, dann direkt return (=> User clickt obwohl Spiel beendet)
- nach dem setzen: prüfen: Hat der Spieler gewonnen? Wenn ja: Spiel beenden sonst makeMove aufrufen.
- nach makeMove prüfen, ob Computer gewonnen hat und entsprechend reagieren.
