I'm trying to implement an AI for the game of TicTacToe, using a minimax algorithm. The code should work but for some reason i'm running into a java.lang.NullPointerException (AI.java:35 - children_boards = new Tree<String>(board);) If anyone knows how to fix this, it would be much appreciated!
import greenfoot.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
public class Main extends World {
public static MovePossession move;
public static boolean gameOver;
public static String[] Board = new String[9];
private static List<Integer> xFields = new ArrayList<Integer>();
private static List<Integer> oFields = new ArrayList<Integer>();
public static final Integer[][] lines = new Integer[][] {
{0, 1, 2},
{0, 3, 6},
{0, 4, 8},
{1, 4, 7},
{2, 4, 6},
{2, 5, 8},
{3, 4, 5},
{6, 7, 8}};
public Main(MovePossession playerAlliance) {
super(790, 790, 1);
init(playerAlliance);
}
public void act() {
checkGameStatus();
if(move == AI.alliance && !gameOver) {
AI.executeMove(AI.minimaxcalc());
}
}
public static void handOver() {
if(move == MovePossession.X) {
move = MovePossession.O;
}
else if(move == MovePossession.O) {
move = MovePossession.X;
}
for(int i = 0; i < Board.length; i++) {
if(!containsNumbers(Board[i])) {
if(Board[i].equals("x")) {
xFields.add(i);
}
else if(Board[i].equals("o")) {
oFields.add(i);
}
}
}
}
private static void checkGameStatus() {
String str = "";
for(int i = 0; i < Board.length; i++) {
str += Board[i];
}
for(int i = 0; i < Main.lines.length; i++) {
if(intersecting(xFields, lines[i]) || intersecting(oFields, lines[i])) {
gameOver = true;
for(int j = 0; j < lines[i].length; j++) {
Board[lines[i][j]] += "w";
}
}
else {
continue;
}
}
if(!Main.containsNumbers(str) && !gameOver) {
gameOver = true;
}
}
public static boolean intersecting(List<Integer> list, Integer[] array) {
return list.containsAll(Arrays.asList(array));
}
public static boolean containsNumbers(String input) {
final String numericSpectrum = "1234567890";
for(int i = 0; i < input.length(); i++) {
if(numericSpectrum.contains(Character.valueOf(input.charAt(i)).toString())) {
return true;
}
else {
continue;
}
}
return false;
}
private void init(MovePossession playerAlliance) {
setBackground("background.png");
gameOver = false;
xFields.clear();
oFields.clear();
for(int i = 0; i < 9; i++) {
this.Board[i] = "" + i;
}
move = MovePossession.X;
Player.setAlliance(playerAlliance);
if(Player.alliance == MovePossession.X) {
AI.init(MovePossession.O);
}
else if(Player.alliance == MovePossession.O) {
AI.init(MovePossession.X);
}
int number = 0;
int x = 135;
int y = 135;
for(int tile = 0; tile < 3; tile++) {
while(x < 750) {
addObject(new Tile(number), x, y);
x += 260;
number++;
}
y += 260;
x = 135;
}
}
}
import java.util.ArrayList;
import java.util.List;
public abstract class AI {
public static MovePossession alliance;
private static Tree<String[]> root_boards;
private static Tree<Integer> root_ratings;
private static Tree<String[]>[] children_boards, grandchildren_boards;
private static Tree<Integer>[] children_ratings;
public static void init(MovePossession pAlliance) {
alliance = pAlliance;
}
public static void executeMove(int tileNumber) {
Main.Board[tileNumber] = (alliance.toString()).toLowerCase();
Main.handOver();
}
public static int minimaxcalc() {
int max = 0;
constructTree(Main.Board);
rateTree();
for(int i = 0; i < children_ratings.length; i++) {
if(children_ratings[i].getData() > max) {
max = children_ratings[i].getData();
}
}
return alteredField(Main.Board, children_boards[max].getData());
}
private static void constructTree(String[] givenBoard) {
root_boards = new Tree<String[]>(givenBoard);
int iterator = 0;
for(int i = 0; i < possibleFields(givenBoard).size(); i++) {
if(possibleFields(givenBoard).get(i) != null) {
String[] board = givenBoard;
board[possibleFields(givenBoard).get(i)] = (alliance.toString()).toLowerCase();
children_boards[iterator] = new Tree<String[]>(board);
root_boards.addChild(children_boards[iterator]);
iterator++;
}
}
iterator = 0;
for(int x = 0; x < root_boards.getChildren().size(); x++) {
Tree<String[]> child = root_boards.getChildren().get(x);
String[] board = child.getData();
if(possibleFields(board) != null) {
for(int y = 0; y < possibleFields(board).size(); y++) {
if(possibleFields(board).get(y) != null) {
board[possibleFields(board).get(y)] = (Player.alliance.toString()).toLowerCase();
grandchildren_boards[iterator] = new Tree<String[]>(board);
children_boards[x].addChild(grandchildren_boards[iterator]);
iterator++;
}
}
}
}
}
private static void rateTree() {
root_ratings = new Tree<Integer>(new Integer(0));
for(int i = 0; i < children_boards.length; i++) {
children_ratings[i] = new Tree<Integer>(rateResult(getResult(children_boards[i].getData())));
root_ratings.addChild(children_ratings[i]);
if(children_boards[i].getChildren() != null) {
for(int j = 0; j < children_boards[i].getChildren().size(); j++) {
Tree<String[]> grandchild = children_boards[i].getChildren().get(j);
Integer rating = new Integer(rateResult(getResult(grandchild.getData())));
children_ratings[i] = new Tree<Integer>(children_ratings[i].getData() + rating);
}
}
}
}
public static List<Integer> possibleFields(String[] currentBoard) {
List<Integer> result = new ArrayList<Integer>();
for(int i = 0; i < currentBoard.length; i++) {
if(Main.containsNumbers(currentBoard[i])) {
result.add(Integer.parseInt(currentBoard[i]));
}
else {
continue;
}
}
if(getResult(currentBoard) != Result.incomplete) {
result = null;
}
return result;
}
private static Result getResult(String[] board) {
List<Integer> xFields = new ArrayList<Integer>();
List<Integer> oFields = new ArrayList<Integer>();
for(int i = 0; i < board.length; i++) {
if(!Main.containsNumbers(board[i])) {
if(board[i].equals("x")) {
xFields.add(i);
}
else if(board[i].equals("o")) {
oFields.add(i);
}
}
}
String str = "";
for(int j = 0; j < board.length; j++) {
str += board[j];
}
boolean gameOver = false;
for(int i = 0; i < Main.lines.length; i++) {
if(Main.intersecting(xFields, Main.lines[i])) {
gameOver = true;
return Result.Xwon;
}
else if(Main.intersecting(oFields, Main.lines[i])) {
gameOver = true;
return Result.Owon;
}
else {
continue;
}
}
if(!Main.containsNumbers(str) && !gameOver) {
gameOver = true;
return Result.tie;
}
return Result.incomplete;
}
private static int rateResult(Result result) {
int rating = 0;
if(result == Result.incomplete) {
rating = 0;
}
else if(result == Result.tie) {
rating = 0;
}
else {
String winner = (Character.valueOf(result.toString().charAt(0)).toString());
if(winner.equals(alliance.toString())) {
rating = 10;
}
else if(winner.equals(Player.alliance.toString())) {
rating = -10;
}
}
return rating;
}
private static int alteredField(String[] prevBoard, String[] newBoard) {
int field = 0;
for(int i = 0; i < prevBoard.length; i++) {
if(!newBoard[i].equals(prevBoard[i])) {
field = i;
}
else {
continue;
}
}
return field;
}
}
import java.util.ArrayList;
import java.util.List;
public class Tree<T> {
private T data = null;
private Tree parent = null;
private List<Tree> children = new ArrayList<>();
public Tree(T data) {
this.data = data;
}
public void addChild(Tree child) {
child.setParent(this);
this.children.add(child);
}
public void addChild(T data) {
Tree<T> newChild = new Tree<>(data);
newChild.setParent(this);
children.add(newChild);
}
public void addChildren(List<Tree> children) {
for(Tree t : children) {
t.setParent(this);
}
this.children.addAll(children);
}
public List<Tree> getChildren() {
return children;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
private void setParent(Tree parent) {
this.parent = parent;
}
public Tree getParent() {
return parent;
}
public void clear() {
this.data = null;
this.parent = null;
for(int i = 0; i < this.children.size(); i++) {
children.get(i).clear();
}
this.children = null;
}
}