Hallo zusammen,
ich wollte den besten Zug für meinen Spiel implementieren und zwar mit Hilfe von Minimax-Algorithmus.
Um ein besseres Verständnis von meinem Problem zu empfinden, poste ich meinen ganzen Code.
Der Algorithmus, den ich implementiert habe, gibt eine Fehlermeldung zurück.
ich wollte den besten Zug für meinen Spiel implementieren und zwar mit Hilfe von Minimax-Algorithmus.
Um ein besseres Verständnis von meinem Problem zu empfinden, poste ich meinen ganzen Code.
Java:
import java.util.*;
public class Board implements VierGewinntGame {
private int[] grid = { 2,2,2,2,2,2,2,2,2,
2,0,0,0,0,0,0,0,2,
2,0,0,0,0,0,0,0,2,
2,0,0,0,0,0,0,0,2,
2,0,0,0,0,0,0,0,2,
2,0,0,0,0,0,0,0,2,
2,0,0,0,0,0,0,0,2,
2,2,2,2,2,2,2,2,2
}; // Nullen sind die sichbaren Felder
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 = 1;
private int pos;
private List<Integer> moves = new ArrayList<>();
public Board() {
}
public Board(Board different) {
this.grid = different.grid; //copy constructor
this.idx = different.idx;
this.memory = different.memory;
this.counter = different.counter;
this.currentPlayer = different.currentPlayer;
this.pos = different.pos;
this.moves = different.moves;
}
public int[] getGrid() {
return grid;
}
public int move(int columnNumber) {
assert columnNumber >= 1 && columnNumber <= 7;
assert fourInArow() == 0: "GAME OVER! Player "+-currentPlayer+" is won";
//assert counter < 42 : "grid is full, DRWA!";
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;
currentPlayer = -currentPlayer;
counter++;
}
}
return idx;
}
public void undoMove(){
assert moves.size() != 0;
grid[idx] = 0;
memory[pos - 1] += 9;
moves.remove(moves.size() - 1);
currentPlayer = -currentPlayer;
}
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;
}
}
return 0;
}
List<Integer> generatePossibleMoves(){
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 7; i++){
if(grid[i+9] != 0) continue;
list.add(i);
}
return list;
}
int randomlyMove(Board b){
int value = b.fourInArow();
while (value == 0){
List<Integer> moves = b.generatePossibleMoves();
if(moves.size() == 0) return 0;
Random random = new Random();
int randomMove = moves.get(random.nextInt(moves.size()));
b.move(randomMove);
value = b.fourInArow();
}
return value;
}
int[] simulateMoves(Board b, int number) {
assert number >= 1;
int[] count = {0,0,0}; // Verluste, unntschieden, Gewinnne
while (number > 0){
Board a = new Board();
b = new Board(a);
count[randomlyMove(a) + 1] += 1;
number -= 1;
}
return count;
}
List<List<Integer>> evaluateMoves(Board b, int number) {
assert number >= 1;
List<Integer> moves = b.generatePossibleMoves();
List<List<Integer>> values = new ArrayList<>();
for(int move : moves) {
b.move(move);
values.add(Arrays.stream(simulateMoves(b,number)).boxed().toList());
b.undoMove();
}
return values;
}
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] == 1) {
s += "| " + "X" + " | ";
}
else if(grid[i] == -1) {
s += "| " + "O" + " | ";
}
}
return s;
}
}
Der Algorithmus, den ich implementiert habe, gibt eine Fehlermeldung zurück.
Code:
int max(Board b, int currentPlayer, int depth) {
if(depth == 0 || b.fourInArow() != 0) {
return evaluation(b);
}
int maxValue = -10;
for (int i : generatePossibleMoves()){
b.move(i);
}
while (b.fourInArow() == 0) {
b.move(pos);
int value = min(b,-currentPlayer,depth - 1);
b.undoMove();
if(value > maxValue) {
maxValue = value;
if(depth == desiredDepth){
savedMove = move(pos);
}
}
}
return maxValue;
}
int min(Board b, int currentPlayer, int depth) {
if(depth == 0 || b.fourInArow() != 0) {
return evaluation(b);
}
int maxValue = 10;
for (int i : generatePossibleMoves()){
b.move(i);
}
while (b.fourInArow() == 0) {
b.move(pos);
int value = max(b,-currentPlayer,depth - 1);
b.undoMove();
if(value > maxValue) {
maxValue = value;
if(depth == desiredDepth){
savedMove = move(pos);
}
}
}
return maxValue;
}