Hallo zusammen,
ich bin gerade dabei, mich in dem Bereich Algorithmik etwas weiterzubilden und stoße dabei auf folgenden Fehler:
Mein Negamax Algorithmus liefert immer -1 zurück.
Hat jemand von euch eine Idee, woran es liegt?
Hier seht ihr noch meinen entsprechenden Code ausschnitt.
ich bin gerade dabei, mich in dem Bereich Algorithmik etwas weiterzubilden und stoße dabei auf folgenden Fehler:
Mein Negamax Algorithmus liefert immer -1 zurück.
Hat jemand von euch eine Idee, woran es liegt?
Hier seht ihr noch meinen entsprechenden Code ausschnitt.
Java:
package Game_ai;
import java.util.ArrayList;
import java.util.List;
import GUI.GUI;
import static GUI.GUI.*;
import GUI.Winner;
import org.jetbrains.annotations.NotNull;
import static java.lang.Thread.*;
public class Game {
public static void main(String[] args) throws InterruptedException {
new Game();
}
GUI frame;
final int NUM_ACTIONS = 9;
final int[] board = new int[NUM_ACTIONS];
int movesRemaining = NUM_ACTIONS;
int AIMOVE;
boolean gameEnded = false;
int move;
Game() throws InterruptedException {
frame = new GUI();
while (!gameEnded) {
sleep(10);
if (frame.newButtonClicked) {
phaseint2darrayzuarray(spiel);
frame.newButtonClicked = false;
ausgeben(board);
switch (whowon(board)){
case 'X':
xgewonnen = true;
System.out.println("X Gewonnen \n Herzlichen Glückwunsch");
winner = "Winner: X \n Herzlichen Glückwunsch";
new Winner();
break;
case 'O':
ogewonnen = true;
System.out.println("O Gewonnen \n Herzlichen Glückwunsch");
winner = "Winner: O \n Herzlichen Glückwunsch";
new Winner();
break;
case 'D':
}
phaseint2darrayzuarray(spiel);
try {
sleep(100);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
aimove(board,2);
try {
sleep(100);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
if (whowon(board) == 'O'){
ogewonnen = true;
System.out.println("O Gewonnen \n Herzlichen Glückwunsch");
winner = "Winner: O \n Herzlichen Glückwunsch";
new Winner();
}
movesRemaining--;
}
}
}
public void aimove(int[]board, int player){
AIMOVE = negamax(board, player)[1];
if (AIMOVE == -1) {
//throw new RuntimeException("T");
System.err.println("Random Move");
dorandomComputerMove();
} else {
board[AIMOVE] = 2;
}
phasearrayzu2darray(board);
frame.doupdate();
}
public int[] negamax(int @NotNull [] board, int player) {
move = -1;
//List of all valid moves
List<Integer> validMoves = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
if (board[i] == 0)
validMoves.add(i);
}
//Abbruchbedingung
int winner = eval(board);
if (winner != -10 || validMoves.size() < 1)
return (new int[]{winner, move});
int bestmovepoints;
// for Computer
if (player == 1) {
bestmovepoints = Integer.MIN_VALUE;
for (int i = 0; i < validMoves.size(); i++) {
int[] tmpState = new int[9];
System.arraycopy(board, 0, tmpState, 0, board.length);
tmpState[validMoves.get(i)] = 2;
int val = negamax(tmpState, 2)[0];
if (val > bestmovepoints) {
bestmovepoints = val;
move = validMoves.get(i);
}
}
}//Human
else {
bestmovepoints = Integer.MAX_VALUE;
for(int i = 0; i < validMoves.size(); i++) {
int[] tmpState = new int[9];
System.arraycopy(board, 0, tmpState, 0, board.length);
tmpState[validMoves.get(i)] = player;
int val = negamax(tmpState, 1)[0];
if(val < bestmovepoints) {
bestmovepoints = val;
move = validMoves.get(i);
}
}
}
return (new int[] { bestmovepoints, move });
}
private boolean isWinner(int @NotNull [] state, int player)
{
return (state[0] == state[1] && state[1] == state[2] && state[0] == player) // horizontal
|| (state[3] == state[4] && state[4] == state[5] && state[3] == player)
|| (state[6] == state[7] && state[7] == state[8] && state[6] == player)
|| (state[0] == state[3] && state[3] == state[6] && state[0] == player) // vertical
|| (state[1] == state[4] && state[4] == state[7] && state[1] == player)
|| (state[2] == state[5] && state[5] == state[8] && state[2] == player)
|| (state[0] == state[4] && state[4] == state[8] && state[0] == player) // diagonal
|| (state[2] == state[4] && state[4] == state[6] && state[2] == player);
}
private int eval(int[] state)
{
if(isWinner(state, 1))
return 1;
else if(isWinner(state, 2))
return -1;
else if (movesRemaining <1)
return 0;
else
return -10;
}
public void ausgeben(int @NotNull [] daten) {
for (int j = 0; j < daten.length; j++) {
System.out.println(daten[j] + "\t");
}
System.out.println();
System.out.println();
System.out.println();
}
private char whowon(int[] board){
int winner = eval(board);
return switch (winner) {
case 1 -> 'X';
case -1 -> 'O';
case 0 -> 'D';
default -> 'f';
};
}
private void phaseint2darrayzuarray(int [] @NotNull [] arr){
int lauf = 0;
for (int[] ints : arr) {
for (int j = 0; j < arr.length; j++) {
this.board[lauf] = ints[j];
lauf++;
}
}
}
private void phasearrayzu2darray(int @NotNull [] arr){
spiel[0][0] = arr[0];
spiel[0][1] = arr[1];
spiel[0][2] = arr[2];
spiel[1][0] = arr[3];
spiel[1][1] = arr[4];
spiel[1][2] = arr[5];
spiel[2][0] = arr[6];
spiel[2][1] = arr[7];
spiel[2][2] = arr[8];
}
private void dorandomComputerMove() {
try {
int zufallszahl1 = (int) (Math.random() * 9);
if (ismovelegit(zufallszahl1)) {
board[zufallszahl1] = 2;
}else {
dorandomComputerMove();
}
phasearrayzu2darray(board);
frame.doupdate();
} catch (StackOverflowError ignored) {
}
}
private boolean ismovelegit(int zahl1){
return board[zahl1] != 1 && board[zahl1] != 2;
}
}