3

Essentially I'm just trying to create a somewhat efficient chess ai using an Alpha Beta Pruning approach for a future neural network to train against. I know I could use an existing program but this is a learning experience and I want to write the code for myself. Essentially the entire program is based on this pseudocode for the Alpha Beta algorithm

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if α ≥ β then
                break (* β cut-off *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if α ≥ β then
                break (* α cut-off *)
        return value

The way I've chosen to represent the game state which I found was both somewhat easy to understand and an efficient manner to represent the boards is as an array of bitboards one for each piece type and color. Creating and organizing this system was simple enough but I can't find an as straight forward answer to the question of a decently efficient but both not incredibly complicated way to loop through all the possible moves. And second, a more accurate and efficient way to determine the score of the board. I can think of ways such as storing the opponent's possible attack points to look for checks but even then looking for a check every time seems very inefficient. In addition to this, I can't conceive a good way to add all the possible moves every piece can take because of all the extra cases. For example, a pawn can move forward or if its the first turn move 2 forward or if theirs a piece diagonal to it it can take it. Hard coding all this would be very disorganized so what I guess what I'm looking for is a system that will work generally but also not be widely inefficient. If anyone has suggestions that would be greatly appreciated. This is a version of my code stripped of all the different experiments I tried.

public class Board {
    long[] board = new long[12];

    public Board() {
        /**
         * The board array is a set of 12 bitboards
         * each a different kind of peice and color
         * - Even indexes are white odd indexes are black
         * - The order of peices is order of points 
         *   Pawn, Knight, Bishop, Rook, Queen, King
         * - The board is defined in this order (rook or index 6)
         * 
         *  8 7 6 5 4 3 2 1
         * -----------------
         *  0 0 0 0 0 0 0 0
         *  0 0 0 0 0 0 0 0
         *  0 0 0 0 0 0 0 0
         *  0 0 0 0 0 0 0 0
         *  0 0 0 0 0 0 0 0
         *  0 0 0 0 0 0 0 0
         *  0 0 0 0 0 0 0 0
         *  1 0 0 0 0 0 0 1
         *  
         *  - otherwise described as 
         *  0b0000000100000000000000000000000000000000000000000000000000000001L;
         */


        // Pawns
        // White
        board[0] = 0b00000010_00000010_00000010_00000010_00000010_00000010_00000010_00000010L;
        // Black
        board[1] = 0b01000000_01000000_01000000_01000000_01000000_01000000_01000000_01000000L;

        // Knights
        // White
        board[2] = 0b00000000_00000001_00000000_00000000_00000000_00000000_00000001_00000000L;
        // Black
        board[3] = 0b00000000_10000000_00000000_00000000_00000000_00000000_10000000_00000000L;

        // Bishops
        // White
        board[4] = 0b00000000_00000000_00000001_00000000_00000000_00000001_00000000_00000000L;
        // Black
        board[5] = 0b00000000_00000000_10000000_00000000_00000000_10000000_00000000_00000000L;

        // Rooks
        // White
        board[6] = 0b00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000001L;
        // Black
        board[7] = 0b10000000_00000000_00000000_00000000_00000000_00000000_00000000_10000000L;

        // Queens
        // White
        board[8] = 0b00000000_00000000_00000000_00000000_00000001_00000000_00000000_00000000L;
        // Black
        board[9] = 0b00000000_00000000_00000000_00000000_10000000_00000000_00000000_00000000L;

        // Kings
        // White
        board[10] = 0b00000000_00000000_00000000_00000001_00000000_00000000_00000000_00000000L;
        // Black
        board[11] = 0b00000000_00000000_00000000_10000000_00000000_00000000_00000000_00000000L;
    }

    public void generateMoves() {
    }


    public String getBoard() {
        long fullBoard = 0;
        for(int i = 0; i < board.length; i++) {
            fullBoard |= board[i];
        }
        return Long.toBinaryString(fullBoard);
    }
}
3
  • Are you asking 1. How to generate moves using bitboards or 2. How to loop through the moves in alpha/beta? Commented Feb 22, 2020 at 14:51
  • looping through the moves inherits from generating them so generating Commented Feb 22, 2020 at 23:02
  • Move ordering is extremely important in AB, and is usually done separately. As for actually generating moves: you usually reference from pre-calculated tables (keyword: magic bitboards). I will warn you however that this is a bit of an advanced topic in chess programming. If your goal is to create a stronger/more efficient engine, you should really focus your efforts on improving the search algorithm (this also has the benefit of being easier imo) Commented Feb 22, 2020 at 23:22

1 Answer 1

2

The questions are difficult to understand, and I assume that you are looking for: 1) A way to loop through moves during the AB search (when in bitboard format).

and

2) How to eval the board in the bitboard format.

The simple answer is to look at the code for Crafty Chess. This is a good and heavily commented source code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.