MinMax Algorithm for Tic Tac Toe
I'm trying to do the MinMax for the tic tac toe (Always computer win) but I can't get it to work. All the successors simply return 0 (draw) as score and so the computer always chooses to move in the natural direction of the matrix.
PS: Matrix (class) is the board where they play, that contains an array of 9 positions.
| X | O | X | O | ... | like this.
Global Variable that handles the Tic Tac Toe board is called Main and is an instance of Matrix.
public void minMax(Matrix p) {
Matrix bestvalue = maxValue(p);
print(bestvalue);
System.out.println(bestvalue.getScore());
main = searchSucessorWithScore(p, bestvalue.getScore());
}
public Matrix maxValue(Matrix p) {
if(endState(p)) { p.setScore(utility(p)); return p; } //always sets score to 0 but the method utility is correct...
Matrix bestmove = new Matrix();
bestmove.setScore(Integer.MIN_VALUE);
LinkedList<Matrix> list = addSucessors(p, plays.PLAY_X);
for(Matrix s : list) {
Matrix move = minValue(s);
if(move.getScore() > bestmove.getScore()) {
bestmove = move;
}
}
return bestmove;
}
public Matrix minValue(Matrix p) {
if(endState(p)) { p.setScore(utility(p)); return p;}
Matrix bestmove = new Matrix();
bestmove.setScore(Integer.MAX_VALUE);
LinkedList<Matrix> list = addSucessors(p, plays.PLAY_O);
for(Matrix s : list) {
Matrix move = maxValue(s);
if(move.getScore() < bestmove.getScore()) { // <
bestmove = move;
}
}
return bestmove;
}
Auxiliar methods:
public LinkedList<Matrix> addSucessors(Matrix k, plays l) {
LinkedList<Matrix> list = new LinkedList<Matrix>();
for(int i=0; i<9; i++) {
if(k.getRow(i).equals(plays.BLANK)) {
Matrix p = k.clone();
p.setRow(i, l);
list.add(p);
}
}
return list;
}
/* RETURNS 0 FOR DRAW, 1 FOR PC WIN, -1 FOR USER WIN */
public int utility(Matrix p) {
for(int i=0; i<9; i=i+3) {
if(main.getRow(i).equals(plays.PLAY_X) && main.getRow(i+1).equals(plays.PLAY_X) && main.getRow(i+2).equals(plays.PLAY_X)) return 1;
if(main.getRow(i).equals(plays.PLAY_O) && main.getRow(i+1).equals(plays.PLAY_O) && main.getRow(i+2).equals(plays.PLAY_O)) return -1;
}
for(int i=0; i<3; i++) {
if(main.getRow(i).equals(plays.PLAY_X) && main.getRow(i+3).equals(plays.PLAY_X) && main.getRow(i+6).equals(plays.PLAY_X)) return 1;
if(main.getRow(i).equals(plays.PLAY_O) && main.getRow(i+3).equals(plays.PLAY_O) && main.getRow(i+6).equals(plays.PLAY_O)) return -1;
}
if(main.getRow(0).equals(plays.PLAY_X) && main.getRow(4).equals(plays.PLAY_X) && main.getRow(8).equals(plays.PLAY_X)) return 1;
if(main.getRow(2).equals(plays.PLAY_X) && main.getRow(4).equals(plays.PLAY_X) && main.getRow(6).equals(plays.PLAY_X)) return 1;
if(main.getRow(0).equals(plays.PLAY_O) && main.getRow(4).equals(plays.PLAY_O) && main.getRow(8).equals(plays.PLAY_O)) return -1;
if(main.getRow(2).equals(plays.PLAY_O) && main.getRow(4).equals(plays.PLAY_O) && main.getRow(6).equals(plays.PLAY_O)) return -1;
return 0;
}
public Matrix searchSucessorWithScore(Matrix p, Integer v) {
for(Matrix s : addSucessors(p, plays.PLAY_X) {
if(s.getScore() == v) return s;
}
return null;
}
The method utility is correct, but inside recursion only returns 0 even for matrix's where there's a winner.
Help :D
There is not enough code posted to correctly assess, but this almost never works.
Integer v s.getScore() == v
You should be using Integer.intValue()
上一篇: MinMax算法不按预期工作
下一篇: Tic Tac Toe的MinMax算法