This site requires JavaScript, please enable it in your browser!
Greenfoot back
Tucky50
Tucky50 wrote ...

2018/7/18

TicTacToe Minimax Algorithm - NullPointer

Tucky50 Tucky50

2018/7/18

#
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;
    }
}
Super_Hippo Super_Hippo

2018/7/19

#
You use "children_boards", but "children_boards" is null. You never set it to anything.
You need to login to post a reply.