I decided to embark on implementing my own chess engine. The first (and perhaps most demanding) part of that endeavour is generating child states out of a given chess board state. Below, you can see my attempt to generate (only) movements of white pawns. The code also mentions a little bit of logic for moving black pawns, yet I don't want that part reviewed since it will eventually become sort of symmetric to moving the white pawns. Finally, the entire GitHub repo is here.
Code
com.github.coderodde.game.chess.ChessBoardState.java:
package com.github.coderodde.game.chess;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* This class implements a chess board state.
*
* @version 1.0.0 (Jun 22, 2024)
* @since 1.0.0 (Jun 22, 2024)
*/
public final class ChessBoardState {
private static final int N = 8;
public static final int EMPTY = 0;
public static final int WHITE_PAWN = 1;
public static final int WHITE_BISHOP = 2;
public static final int WHITE_KNIGHT = 3;
public static final int WHITE_ROOK = 4;
public static final int WHITE_QUEEN = 5;
public static final int WHITE_KING = 6;
public static final int BLACK_PAWN = 9;
public static final int BLACK_BISHOP = 10;
public static final int BLACK_KNIGHT = 11;
public static final int BLACK_ROOK = 12;
public static final int BLACK_QUEEN = 13;
public static final int BLACK_KING = 14;
private static final int CELL_COLOR_NONE = 0;
private static final int CELL_COLOR_WHITE = +1;
private static final int CELL_COLOR_BLACK = -1;
private int[][] state = new int[N][N];
private boolean[] whiteIsPreviouslyDoubleMoved = new boolean[N];
private boolean[] blackIsPreviouslyDoubleMoved = new boolean[N];
public ChessBoardState() {
// Black pieces:
state[0][0] =
state[0][7] = BLACK_ROOK;
state[0][1] =
state[0][6] = BLACK_KNIGHT;
state[0][2] =
state[0][5] = BLACK_BISHOP;
state[0][3] = BLACK_QUEEN;
state[0][4] = BLACK_KING;
for (int x = 0; x < N; x++) {
state[1][x] = BLACK_PAWN;
}
// White pieces:
state[7][0] =
state[7][7] = WHITE_ROOK;
state[7][1] =
state[7][6] = WHITE_KNIGHT;
state[7][2] =
state[7][5] = WHITE_BISHOP;
state[7][3] = WHITE_QUEEN;
state[7][4] = WHITE_KING;
for (int x = 0; x < N; x++) {
state[6][x] = WHITE_PAWN;
}
}
public ChessBoardState(final ChessBoardState copy) {
this.state = new int[N][N];
for (int y = 0; y < N; y++) {
System.arraycopy(copy.state[y], 0, this.state[y], 0, N);
}
this.whiteIsPreviouslyDoubleMoved = copy.whiteIsPreviouslyDoubleMoved;
this.blackIsPreviouslyDoubleMoved = copy.blackIsPreviouslyDoubleMoved;
}
@Override
public boolean equals(final Object o) {
if (o == this) {
return true;
}
if (o == null) {
return false;
}
if (!getClass().equals(o.getClass())) {
return false;
}
final ChessBoardState other = (ChessBoardState) o;
return Arrays.deepEquals(state, other.state);
}
@Override
public int hashCode() {
return Arrays.deepHashCode(state);
}
/**
* Clears the entire board. Used in unit testing.
*/
public void clear() {
this.state = new int[N][N];
}
/**
* Returns the piece value at rank {@code y}, file {@code x}. Used in unit
* testing.
*
* @param x the file of the requested piece.
* @param y the rank of the requested piece.
*
* @return the piece value.
*/
public int get(final int x, final int y) {
return state[y][x];
}
/**
* Sets the piece {@code piece} at rank {@code y}, file {@code x}. Used in
* unit testing.
*
* @param x the file of the requested piece.
* @param y the rank of the requested piece.
*
* @param piece the value of the desired piece.
*/
public void set(final int x, final int y, final int piece) {
state[y][x] = piece;
}
/**
* Clears the position at rank {@code y} and file {@code x}. Used in unit
* testing.
*
* @param x the file of the requested piece.
* @param y the rank of the requested piece.
*/
public void clear(final int x, final int y) {
state[y][x] = EMPTY;
}
/**
* Returns a simple textual representation of this state. Not very readable.
*
* @return a textual representation of this state.
*/
@Override
public String toString() {
final StringBuilder stringBuilder =
new StringBuilder((N + 3) * (N + 2));
int rankNumber = 8;
for (int y = 0; y < N; y++) {
for (int x = -1; x < N; x++) {
if (x == -1) {
stringBuilder.append(rankNumber--).append(' ');
} else {
stringBuilder.append(
convertPieceCodeToUnicodeCharacter(x, y));
}
}
stringBuilder.append('\n');
}
stringBuilder.append("\n abcdefgh");
return stringBuilder.toString();
}
public List<ChessBoardState> expand(final PlayerTurn playerTurn) {
final List<ChessBoardState> children = new ArrayList<>();
if (playerTurn == PlayerTurn.WHITE) {
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
final int cellColor = getCellColor(x, y);
if (cellColor != CELL_COLOR_WHITE) {
continue;
}
expandWhiteMovesImpl(children, x, y);
}
}
} else { // playerTurn == PlayerTurn.BLACK
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
final int cellColor = getCellColor(x, y);
if (cellColor != CELL_COLOR_BLACK) {
continue;
}
expandBlackMovesImpl(children, x, y);
}
}
}
return children;
}
/**
* Marks that the white pawn at file {@code x} made an initial double move.
* Used for unit testing.
*
* @param x the file number of the target white pawn.
*/
public void markWhitePawnInitialDoubleMove(final int x) {
this.whiteIsPreviouslyDoubleMoved[x] = true;
}
/**
* Marks that the black pawn at file {@code x} made an initial double move.
* Used for unit testing.
*
* @param x the file number of the target white pawn.
*/
public void markBlackPawnInitialDoubleMove(final int x) {
this.blackIsPreviouslyDoubleMoved[x] = true;
}
private void expandWhiteMovesImpl(final List<ChessBoardState> children,
final int x,
final int y) {
unmarkAllInitialWhiteDoubleMoveFlags();
final int cell = state[y][x];
switch (cell) {
case WHITE_PAWN:
expandImplWhitePawn(children, x, y);
break;
case WHITE_ROOK:
break;
case WHITE_BISHOP:
break;
case WHITE_KNIGHT:
break;
case WHITE_QUEEN:
break;
case WHITE_KING:
break;
default:
throw new IllegalStateException("Should not get here.");
}
}
private void expandBlackMovesImpl(final List<ChessBoardState> children,
final int x,
final int y) {
throw new UnsupportedOperationException();
}
private void expandImplWhitePawn(final List<ChessBoardState> children,
final int x,
final int y) {
if (y == 6 && state[5][x] == EMPTY
&& state[4][x] == EMPTY) {
// Once here, can move the white pawn two moves forward:
final ChessBoardState child = new ChessBoardState(this);
child.markWhitePawnInitialDoubleMove(x);
child.state[6][x] = EMPTY;
child.state[4][x] = WHITE_PAWN;
children.add(child);
this.markWhitePawnInitialDoubleMove(x);
}
if (y == 3) {
// Try en passant, white pawn can capture a black onen?
if (x > 0) {
// Try en passant to the left:
enPassantWhitePawnToLeft(x, children);
}
if (x < N - 1) {
// Try en passant to the right:
enPassantWhitePawnToRight(x, children);
}
}
if (state[y - 1][x] == EMPTY && y == 1) {
// Once here, can do promotion:
addWhitePromotion(children,
this,
x);
return;
}
// Move forward:
if (y > 0 && getCellColor(x, y - 1) == CELL_COLOR_NONE) {
// Once here, can move forward:
ChessBoardState child = new ChessBoardState(this);
child.state[y][x] = EMPTY;
child.state[y - 1][x] = WHITE_PAWN;
children.add(child);
}
if (x > 0 && y > 0 && getCellColor(x - 1, y - 1) == CELL_COLOR_BLACK) {
// Once here, can capture to the left:
final ChessBoardState child = new ChessBoardState(this);
child.state[y][x] = EMPTY;
child.state[y - 1][x - 1] = WHITE_PAWN;
children.add(child);
}
if (x < N - 1 && y > 0
&& getCellColor(x + 1, y - 1) == CELL_COLOR_BLACK) {
// Once here, can capture to the right:
final ChessBoardState child = new ChessBoardState(this);
child.state[y][x] = EMPTY;
child.state[y - 1][x + 1] = WHITE_PAWN;
children.add(child);
}
}
/**
* Tries to perform an en passant by the white pawn at the file {@code x}
* to a black pawn at the file {@code x - 1}.
*
* @param x the file of the capturing white pawn.
* @param children the list of child n
*/
private void enPassantWhitePawnToLeft(
final int x,
final List<ChessBoardState> children) {
if (!blackIsPreviouslyDoubleMoved[x - 1]) {
return;
}
final ChessBoardState child = new ChessBoardState(this);
child.clear(x, 3);
child.clear(x - 1, 3);
child.set(x - 1, 2, WHITE_PAWN);
children.add(child);
}
private void enPassantWhitePawnToRight(
final int x,
final List<ChessBoardState> children) {
if (!blackIsPreviouslyDoubleMoved[x + 1]) {
return;
}
final ChessBoardState child = new ChessBoardState(this);
child.clear(x, 3);
child.clear(x + 1, 3);
child.set(x + 1, 2, WHITE_PAWN);
children.add(child);
}
private void unmarkAllInitialWhiteDoubleMoveFlags() {
for (int i = 0; i < N; i++) {
this.whiteIsPreviouslyDoubleMoved[i] = false;
}
}
private void expandImplBlackPawn(final List<ChessBoardState> children,
final int x,
final int y) {
if (y == 6 && state[2][x] == EMPTY
&& state[3][x] == EMPTY) {
// Once here, can move the black pawn two moves forward:
final ChessBoardState child = new ChessBoardState(this);
//
// child.unsetBlackInitialMovePawn(x);
child.state[2][x] = EMPTY;
child.state[4][x] = BLACK_PAWN;
}
}
private void addWhitePromotion(
final List<ChessBoardState> children,
final ChessBoardState state,
final int x) {
ChessBoardState child = new ChessBoardState(state);
child.state[0][x] = WHITE_QUEEN;
child.state[1][x] = EMPTY;
children.add(child);
if (x > 0 && getCellColor(x - 1, 0) == CELL_COLOR_BLACK) {
// Can capture/promote to the left:
child = new ChessBoardState(state);
child.state[0][x - 1] = WHITE_QUEEN;
child.state[1][x] = EMPTY;
children.add(child);
}
if (x < N - 1 && getCellColor(x + 1, 0) == CELL_COLOR_BLACK) {
// Can capture/promote to the right:
child = new ChessBoardState(state);
child.state[0][x + 1] = WHITE_QUEEN;
child.state[1][x] = EMPTY;
children.add(child);
}
}
private void addBlackPromotion(final List<ChessBoardState> children,
final ChessBoardState state,
final int x) {
final ChessBoardState child = new ChessBoardState(state);
child.state[7][x] = BLACK_QUEEN;
children.add(child);
}
/**
* Returns the color of the cell at file {@code (x + 1)} and rank
* {@code 8 - y}.
*
* @param x the file index.
* @param y the rank index.
*
* @return {@link #CELL_COLOR_NONE} if the requested cell is empty,
* {@link #CELL_COLOR_WHITE} if the requested cell is white, and,
* {@link #CELL_COLOR_BLACK} if the requested cell is black.
*/
private int getCellColor(final int x, final int y) {
final int cell = state[y][x];
if (cell == EMPTY) {
return CELL_COLOR_NONE;
}
return 0 < cell && cell < 7 ? CELL_COLOR_WHITE :
CELL_COLOR_BLACK;
}
private char convertPieceCodeToUnicodeCharacter(final int x, final int y) {
final int pieceCode = state[y][x];
switch (pieceCode) {
case EMPTY -> {
return (x + y) % 2 == 0 ? '.' : '#';
}
case WHITE_PAWN -> {
return 'P';
}
case WHITE_KNIGHT -> {
return 'K';
}
case WHITE_BISHOP -> {
return 'B';
}
case WHITE_ROOK -> {
return 'R';
}
case WHITE_QUEEN -> {
return 'Q';
}
case WHITE_KING -> {
return 'X';
}
case BLACK_PAWN -> {
return 'p';
}
case BLACK_KNIGHT -> {
return 'k';
}
case BLACK_BISHOP -> {
return 'b';
}
case BLACK_ROOK -> {
return 'r';
}
case BLACK_QUEEN -> {
return 'q';
}
case BLACK_KING -> {
return 'x';
}
default -> throw new IllegalStateException("Should not get here.");
}
}
}
The unit test class follows.
com.github.coderodde.game.chess.ChessBoardStateTest.java:
package com.github.coderodde.game.chess;
import static com.github.coderodde.game.chess.ChessBoardState.BLACK_BISHOP;
import static com.github.coderodde.game.chess.ChessBoardState.BLACK_KNIGHT;
import static com.github.coderodde.game.chess.ChessBoardState.BLACK_PAWN;
import static com.github.coderodde.game.chess.ChessBoardState.BLACK_ROOK;
import static com.github.coderodde.game.chess.ChessBoardState.WHITE_BISHOP;
import static com.github.coderodde.game.chess.ChessBoardState.WHITE_PAWN;
import static com.github.coderodde.game.chess.ChessBoardState.WHITE_QUEEN;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.*;
public final class ChessBoardStateTest {
private ChessBoardState state;
@Before
public void before() {
state = new ChessBoardState();
state.clear();
}
@Test
public void moveWhitePawnInitialDoubleMove() {
state.set(0, 6, WHITE_PAWN);
final List<ChessBoardState> children = state.expand(PlayerTurn.WHITE);
assertEquals(2, children.size());
final ChessBoardState child1 = children.get(0);
final ChessBoardState child2 = children.get(1);
assertTrue(children.contains(child1));
assertTrue(children.contains(child2));
final Set<Integer> indexSet = new HashSet<>();
indexSet.add(children.indexOf(child1));
indexSet.add(children.indexOf(child2));
assertEquals(2, indexSet.size());
final ChessBoardState move1 = new ChessBoardState();
final ChessBoardState move2 = new ChessBoardState();
move1.clear();
move2.clear();
move1.set(0, 5, WHITE_PAWN);
move2.set(0, 4, WHITE_PAWN);
assertTrue(children.contains(move1));
assertTrue(children.contains(move2));
}
@Test
public void whitePawnCannotMoveForward() {
state.set(4, 5, WHITE_PAWN);
state.set(4, 4, BLACK_ROOK);
final List<ChessBoardState> children = state.expand(PlayerTurn.WHITE);
assertTrue(children.isEmpty());
}
@Test
public void whitePawnCanEatBothDirectionsAndMoveForward() {
state.set(5, 4, WHITE_PAWN);
state.set(4, 3, BLACK_KNIGHT);
state.set(6, 3, BLACK_ROOK);
final List<ChessBoardState> children = state.expand(PlayerTurn.WHITE);
assertEquals(3, children.size());
final ChessBoardState move1 = new ChessBoardState();
final ChessBoardState move2 = new ChessBoardState();
final ChessBoardState move3 = new ChessBoardState();
move1.clear();
move2.clear();
move3.clear();
// Eat to the left:
move1.set(4, 3, WHITE_PAWN);
move1.set(6, 3, BLACK_ROOK);
// Move forward:
move2.set(5, 3, WHITE_PAWN);
move2.set(4, 3, BLACK_KNIGHT);
move2.set(6, 3, BLACK_ROOK);
// Eat to the right:
move3.set(6, 3, WHITE_PAWN);
move3.set(4, 3, BLACK_KNIGHT);
assertTrue(children.contains(move1));
assertTrue(children.contains(move2));
assertTrue(children.contains(move3));
}
@Test
public void whitePawnCannotMakeFirstDoubleMoveDueToObstruction() {
state.set(6, 6, WHITE_PAWN);
state.set(6, 5, WHITE_BISHOP);
assertTrue(state.expand(PlayerTurn.WHITE).isEmpty());
state.clear();
state.set(4, 6, WHITE_PAWN);
state.set(4, 5, BLACK_ROOK);
assertTrue(state.expand(PlayerTurn.WHITE).isEmpty());
}
@Test
public void whitePawnPromotion() {
state.set(3, 1, WHITE_PAWN);
final List<ChessBoardState> children = state.expand(PlayerTurn.WHITE);
assertEquals(1, children.size());
final ChessBoardState move = new ChessBoardState();
move.clear();
move.set(3, 0, WHITE_QUEEN);
assertEquals(move, children.get(0));
}
@Test
public void whitePawnPromotionCaptureBoth() {
state.set(5, 1, WHITE_PAWN);
state.set(4, 0, BLACK_BISHOP);
state.set(6, 0, BLACK_PAWN);
final List<ChessBoardState> children = state.expand(PlayerTurn.WHITE);
assertEquals(3, children.size());
final ChessBoardState move1 = new ChessBoardState();
final ChessBoardState move2 = new ChessBoardState();
final ChessBoardState move3 = new ChessBoardState();
move1.clear();
move2.clear();
move3.clear();
// Queen forward:
move1.set(4, 0, BLACK_BISHOP);
move1.set(5, 0, WHITE_QUEEN);
move1.set(6, 0, BLACK_PAWN);
// Queen left:
move2.set(4, 0, WHITE_QUEEN);
move2.set(6, 0, BLACK_PAWN);
// Queen right:
move3.set(6, 0, WHITE_QUEEN);
move3.set(4, 0, BLACK_BISHOP);
assertTrue(children.contains(move1));
assertTrue(children.contains(move2));
assertTrue(children.contains(move3));
final Set<Integer> indexSet = new HashSet<>();
indexSet.add(children.indexOf(move1));
indexSet.add(children.indexOf(move2));
indexSet.add(children.indexOf(move3));
assertEquals(3, indexSet.size());
}
@Test
public void whitePawnEnPassantToLeft() {
state.set(0, 3, BLACK_PAWN);
state.set(1, 2, BLACK_ROOK);
state.set(1, 3, WHITE_PAWN);
state.markBlackPawnInitialDoubleMove(0);
final List<ChessBoardState> children = state.expand(PlayerTurn.WHITE);
assertEquals(1, children.size());
final ChessBoardState move = new ChessBoardState();
move.clear();
move.set(1, 2, BLACK_ROOK);
move.set(0, 2, WHITE_PAWN);
assertTrue(children.contains(move));
}
@Test
public void whitePawnEnPassantToRight() {
state.set(7, 3, BLACK_PAWN);
state.set(6, 2, BLACK_ROOK);
state.set(6, 3, WHITE_PAWN);
state.markBlackPawnInitialDoubleMove(7);
final List<ChessBoardState> children = state.expand(PlayerTurn.WHITE);
assertEquals(1, children.size());
final ChessBoardState move = new ChessBoardState();
move.clear();
move.set(6, 2, BLACK_ROOK);
move.set(7, 2, WHITE_PAWN);
assertTrue(children.contains(move));
}
}
Critique request
First of all, do I break the rules? Also, I would like whatever comes to mind.