Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An pseudocode AI demonstrating the Minimax algorithm. Note that the algorithm has two helper functions: min and max.
class AdversarialSearchAI {
private PieceType piece;
public AdversarialSearchAI(PieceType piece) {
this.piece = piece;
}
/**
* Returns the best move given the state of the game
*/
public Move minimax(State state) {
int highestScore = INTEGER.MIN_VALUE;
Move bestMove = null;
ArrayList<Move> moves = state.getMoves();
int score = 0;
for (Move move : moves) {
State clone = state.clone();
score = min(clone);
if (score > highestScore) {
highestScore = score;
bestMove = move;
}
}
return move;
}
/**
* Returns the lowest score received by the min player
*/
private int min(State state) {
if (state.isEnd())
return eval(state);
int lowestScore = INTEGER.MAX_VALUE;
ArrayList<Move> moves = state.getMoves();
int score = 0;
for (Move move : moves) {
State clone = state.clone();
score = max(clone);
if (score < lowestScore)
highestScore = score;
}
return move;
}
/**
* Returns the highest score received by the max player
*/
private int max(State state) {
if (state.isEnd())
return eval(state);
int highestScore = INTEGER.MIN_VALUE;
ArrayList<Move> moves = state.getMoves();
int score = 0;
for (Move move : moves) {
State clone = state.clone();
score = min(clone);
if (score > highestScore)
highestScore = score;
}
return move;
}
/**
* Returns 1 if the AI is the winner
*/
private int eval(State state) {
PieceType piece = state.winner();
if (piece == this.piece)
return 1;
else
return -1;
}
public static enum PieceType {
X, O
}
/**
* Represents the state of the game board
*/
public static State {
private static final WIDTH = 3;
private static final HEIGHT = 3;
public int board[WIDTH][HEIGHT];
public ArrayList<Move> getMoves() {
// TODO: Retrieve available moves
}
public boolean isEnd() {
// TODO: Implement end-game check
}
public PieceType winner() {
// TODO: Implement winner
}
}
public static Move {
private int x;
private int y;
public Move(int x, int y) {
this.x = x;
this.y = y;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment