Hallo zusammen,
ich bin grade mit der Implementierung von Minimax-Algorithmus beschäftigt.
Als Grundlage für die Implementierung habe ich dieses Video
angeschaut.
Ich habe mir handlich einen Spielbaum zeichnen lassen, um zu überprüfen, ob der Algorithmus tut, was er tun soll, allerdings macht er das nicht.
Hier ist der Code:
Hier ist ein Ausschnitt aus dem Spielbaum und zwar ist X dran und dann soll X gewinnen, also nimmt X den rechten Weg mit dem Wert 2,
allerdings gibt die Methode 1 zurück und nicht 2.
Ich hoffe, dass ihr mir helfen könnt, um den Fehler herauszufinden
ich bin grade mit der Implementierung von Minimax-Algorithmus beschäftigt.
Als Grundlage für die Implementierung habe ich dieses Video
Ich habe mir handlich einen Spielbaum zeichnen lassen, um zu überprüfen, ob der Algorithmus tut, was er tun soll, allerdings macht er das nicht.
Hier ist der Code:
Java:
import java.util.*;
public class Board implements VierGewinntGame {
private int[] grid = { 9,9,9,9,9,9,9,9,9,
9,0,0,0,0,0,0,0,9,
9,0,0,0,0,0,0,0,9,
9,0,0,0,0,0,0,0,9,
9,0,0,0,0,0,0,0,9,
9,0,0,0,0,0,0,0,9,
9,0,0,0,0,0,0,0,9,
9,9,9,9,9,9,9,9,9
}; // Nullen sind die sichbaren Felder
public int[] setGrid(int[] grid) {
this.grid = grid;
return grid;
}
private int idx;
private int[] memory = {55,56,57,58,59,60,61};
private final int[] direction = {9,1,10,8};
public int counter = 0;
private int currentPlayer = 2;
private int pos;
private List<Integer> moves = new ArrayList<>();
public Board() {
}
int max(int restTiefe){
if(fourInArow() != 0) return fourInArow();
if(restTiefe == 0) return 1;
int maximalwert = -99;
for(int i = 0; i < grid.length; i++) {
if (i % 9 == 8) {
continue;
}
if (grid[i] == 0) {
grid[i] = currentPlayer;
int wert = min(restTiefe - 1);
if(wert > maximalwert) maximalwert = wert;
grid[i] = 0;
}
}
return maximalwert;
}
int min(int restTiefe){
if(fourInArow() != 0) return fourInArow();
if(restTiefe == 0) return 1;
int minimalwert = 99;
for(int i = 0; i < grid.length; i++) {
if (i % 9 == 8) {
continue;
}
if (grid[i] == 0) {
grid[i] = -currentPlayer;
int wert = max(restTiefe - 1);
if(wert < minimalwert) minimalwert = wert;
grid[i] = 0;
}
}
return minimalwert;
}
int minmumPos;
int maximaleTiefe = 4;
int minWo(){
if(fourInArow() != 0) return fourInArow();
int minimalwert = 99;
for(int i = 0; i < grid.length; i++) {
if (i % 9 == 8) {
continue;
}
if (grid[i] == 0) {
grid[i] = -currentPlayer;
int wert = max(maximaleTiefe);
if(wert < minimalwert){
minimalwert = wert;
minmumPos = i;
}
grid[i] = 0;
}
}
return minmumPos;
}
public int[] getGrid() {
return grid;
}
public int move(int columnNumber) {
assert columnNumber >= 1 && columnNumber <= 7;
pos = columnNumber;
if(fourInArow() == 0) {
if (memory[columnNumber - 1] >= 10) {
grid[memory[columnNumber - 1]] = currentPlayer;
idx = memory[columnNumber - 1];
moves.add(idx);
memory[columnNumber - 1] -= 9;
//grid[minWo()] = -currentPlayer;
currentPlayer = -currentPlayer;
counter++;
if(currentPlayer == -2){
System.out.println("O ist dran");
}
else if(currentPlayer == 2){
System.out.println("X ist dran");
}
}
}
return idx;
}
public void undoMove(){
assert moves.size() != 0;
grid[idx] = 0;
memory[pos - 1] += 9;
moves.remove(moves.size() - 1);
currentPlayer = -currentPlayer;
}
/*
fourInArow
liefert 2, wenn X gewonnen hat
liefert -2, wenn O gewonnen hat
liefert 1, wenn unentschieden ist
liefert 0, wenn es noch nicht klar ist
*/
public int fourInArow() {
if(counter >= 4 && grid[idx] != 0){
for(int d : direction){
int s = 1;
int i = idx + d;
while (grid[i] == -currentPlayer){
s += 1;
i += d;
}
i = idx - d;
while (grid[i] == -currentPlayer){
s += 1;
i -= d;
}
if(s >= 4) return -currentPlayer;
}
}
for(int i = 0; i < grid.length; i++) {
if(grid[i] == 0) {
return 0;
}
}
return 1;
}
public String toString() {
String s = "";
for(int i = 0; i < grid.length; i++) {
if (i % 9 == 8) {
s += "\n\n";
}
if (grid[i] == 0) {
s += "| " + "_" + " | ";
}
else if(grid[i] == 2) {
s += "| " + "X" + " | ";
}
else if(grid[i] == -2) {
s += "| " + "O" + " | ";
}
}
return s;
}
}Hier ist ein Ausschnitt aus dem Spielbaum und zwar ist X dran und dann soll X gewinnen, also nimmt X den rechten Weg mit dem Wert 2,
allerdings gibt die Methode 1 zurück und nicht 2.
Code:
z ==>
| _ | | _ | | O | | X | | X | | O | | O |
| X | | _ | | O | | O | | O | | X | | X |
| X | | _ | | X | | X | | X | | O | | O |
| O | | O | | X | | O | | X | | X | | X |
| O | | O | | O | | X | | O | | O | | O |
| X | | X | | O | | X | | O | | X | | X |
jshell> z.min(5)
$29 ==> 1
jshell> z.max(5)
$30 ==> 1Ich hoffe, dass ihr mir helfen könnt, um den Fehler herauszufinden
