Chess programming algorithm minimax to Alpha Beta

Question

I have written some code for alpha beta for Chess programming and not sure completely if that is the correct way to do it. Can someone please tell me if I implemented the alpha_beta properly?

public class Minimax{
    private boolean side;
    public static int depth;

    public Minimax(boolean inputSide, int inputDepth) {
        side = inputSide;
        depth = inputDepth;
    }

    public int[] getMoves(Board board, boolean white, int inputDepth, boolean check) {
        ArrayList<int[]> values = new ArrayList<int[]>();
        int initScore = board.getScore();
        boolean multipleMoves = false;
        ArrayList<int[]> multiple = new ArrayList<int[]>();
        if (white) {
            values.add(new int[]{-2000, 0, 0, 0, 0});
        }
        else {
            values.add(new int[]{2000, 0, 0, 0, 0});
        }
        int position = 0;
        if (inputDepth == depth) {
            int[] ret = {board.getScore(), 0, 0, 0, 0};
            return ret;
        }
        for (Pieces[] subPiece : board.getArray()) {
            for (Pieces piece : subPiece) {
                if (piece != null && piece.white() == white) {
                    int[][] moves = piece.getMoves(board, false);
                    if (moves != null) {
                        for (int[] move : moves) {
                            Board newBoard = board.newBoard(move[0], move[1], move[2], move[3]);
                            if (newBoard != null) {
                                int score = getMoves(newBoard, !white, inputDepth + 1, newBoard.check(white))[0];
                                values.add(new int[]{score, move[0], move[1], move[2], move[3]});
                                if ((white && score > values.get(position)[0]) || (!white && score < values.get(position)[0])) {
                                    position = values.size() - 1;
                                    multipleMoves = false;
                                    multiple.clear();
                                }
                                else if (score == values.get(position)[0]) {
                                    multipleMoves = true;
                                    multiple.add(values.get(values.size() - 1));
                                    multiple.add(values.get(position));
                                }
                            }
                        }
                    }
                }
            }
        }
        if (values.size() == 1) {
            if (depth == 0) {
                return null;
            }
            else {
                if (white) {
                    return new int[]{-3000, 0, 0, 0, 0};
                }
                else {
                    return new int[]{3000, 0, 0, 0, 0};
                }
            }
        }
        if (multipleMoves && multiple != null) {
            position = (int)((multiple.size() - 1) * Math.random() + 1);
            return multiple.get(position);
        }

        return values.get(position);
    }

    public int getDepth() {
            System.out.println(depth);
            return depth;

    }
}

Answer 1

A couple of things on top of what @tim already covered.

Use Random.nextInt instead of Math.random

Instead of this:

position = (int)((multiple.size() - 1) * Math.random() + 1);

you can write much simpler like this:

position = 1 + random.nextInt(multiple.size() - 1);

where random is an instance of Random, created for example in the constructor. Simpler isn't it?

Use interface types instead of implementations

Instead of:

    ArrayList<int[]> values = new ArrayList<int[]>();

This would be better:

    List<int[]> values = new ArrayList<int[]>();

(but not quite good enough, see the next item)

Define Abstract Data Types for your problem domain

An Abstract Data Type (ADT) is essentially a collection of data and operations on that data. In object oriented languages an ADT is usually modeled with a class, where data is represented by member fields and the operations are represented by methods.

When I look at that ArrayList<int[]> in the previous point, I've no idea what it stands for, what kind of logical object it represents, and what the numbers in new int[]{-2000, 0, 0, 0, 0} and the other array initializations scattered in the code mean.

If you have defined an ADT for this, the code would become all the more readable. Instead of new ArrayList<int[]>, there might be new MinimaxValueSet(). Instead of values.add(new int[]{-2000, 0, 0, 0, 0}), there might be valueSet.addNewSetWithScore(-2000), where this helper method would fill in the repetitive zeros.

Don't print to the console

I suppose the println here was added for debugging:

public int getDepth() {
        System.out.println(depth);
        return depth;

It doesn't belong there and should be removed. (I suggest to remove debugging code before pasting for code review, it's just noise for reviewers.)

Answer 2

Null checks

You have quite a lot of null checks, which leads to deeply nested statements and thus hard to read code.

The first thing you should do is return an empty collection instead of null in piece.getMoves. That way, you don't need if (moves != null) because if the result is empty, the for loop will just not execute.

It's not that clear what board.newBoard returns, but I would guess that you could also change it so that if (newBoard != null) is not needed.

The Minimax::getMoves method should also return an empty array instead of null, otherwise you will have the same problem in the calling code (although it's unclear if it returns multiple moves as the method name suggest, or a single move, which the return type suggests).

Misc

• I would use an enum for the color of pieces instead of a boolean, because a boolean results in code like if (piece.white() == white) which just doesn't look that good.
• getMoves probably shouldn't be a method of Pieces, but of board.
• Why Pieces (plural)? It seems to only represent a single piece.
• I would introduce a Move class instead of using an array for it, because it would be clearer. I would also do this for Value, because it's also not clear how that array is build.
• your variable names are often quite generic. values? What values? check? What's being checked? multipleMoves? Like castling? multiple? multiple what?
• you don't need temporary variables if you only use them in one place and they don't have a clarifying name. Eg int[] ret = [...]; return ret; is not necessary, return the thing directly.