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);
}
}