I have this repository.
My main concern this time is my implementation of the Negamax algorithm with alpha-beta pruning:
com.github.coderodde.game.zerosum.impl.ConnectFourNegamaxSearchEngine.java:
package com.github.coderodde.game.zerosum.impl;
import com.github.coderodde.game.connect4.ConnectFourBoard;
import static com.github.coderodde.game.connect4.ConnectFourBoard.COLUMNS;
import com.github.coderodde.game.zerosum.HeuristicFunction;
import com.github.coderodde.game.zerosum.PlayerType;
import com.github.coderodde.game.zerosum.SearchEngine;
/**
* This class implements a Negamax algorithm with alpha-beta pruning for playing
* Connect Four.
*
* @version 1.0.0 (Jun 16, 2024)
* @since 1.0.0 (Jun 16, 2024)
*/
public final class ConnectFourNegamaxSearchEngine implements SearchEngine<ConnectFourBoard> {
private final HeuristicFunction<ConnectFourBoard> heuristicFunction;
public ConnectFourNegamaxSearchEngine(
final HeuristicFunction<ConnectFourBoard> heuristicFunction) {
this.heuristicFunction = heuristicFunction;
}
@Override
public ConnectFourBoard search(final ConnectFourBoard root,
final int depth,
final PlayerType playerType) {
if (playerType == PlayerType.MINIMIZING_PLAYER) {
return negamaxRoot(root,
depth,
Double.NEGATIVE_INFINITY,
Double.POSITIVE_INFINITY,
-1);
} else {
return negamaxRoot(root,
depth,
Double.NEGATIVE_INFINITY,
Double.POSITIVE_INFINITY,
+1);
}
}
private ConnectFourBoard negamaxRoot(final ConnectFourBoard root,
final int depth,
double alpha,
double beta,
final int color) {
double value = Double.NEGATIVE_INFINITY;
ConnectFourBoard bestMoveState = null;
for (int x = 0; x < COLUMNS; x++) {
if (!root.makePly(
x,
color == 1 ?
PlayerType.MAXIMIZING_PLAYER :
PlayerType.MINIMIZING_PLAYER)) {
continue;
}
final double score =
-negamax(root,
depth - 1,
-beta,
-alpha,
-color);
if (color == +1) {
if (value < score) {
value = score;
bestMoveState = new ConnectFourBoard(root);
}
} else {
if (value > score) {
value = score;
bestMoveState = new ConnectFourBoard(root);
}
}
root.unmakePly(x);
alpha = Math.max(alpha, value);
if (alpha >= beta) {
break;
}
}
return bestMoveState;
}
private double negamax(final ConnectFourBoard root,
final int depth,
double alpha,
double beta,
final int color) {
if (depth == 0 || root.isTerminal()) {
return color * heuristicFunction.evaluate(root, depth);
}
double value = Double.NEGATIVE_INFINITY;
for (int x = 0; x < COLUMNS; x++) {
if (!root.makePly(
x,
color == 1 ?
PlayerType.MAXIMIZING_PLAYER :
PlayerType.MINIMIZING_PLAYER)) {
continue;
}
value = Math.max(
value,
-negamax(
root,
depth - 1,
-beta,
-alpha,
-color));
root.unmakePly(x);
alpha = Math.max(alpha, value);
if (alpha >= beta) {
break;
}
}
return value;
}
}
Typical output
AlphaBetaPruningSearchEngine in 5157 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
ConnectFourAlphaBetaPruningSearchEngine in 2935 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
ParallelConnectFourAlphaBetaPruningSearchEngine in 2193 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
ConnectFourNegamaxSearchEngine in 1599 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
<<< ConnnectFourAlphaBetaPruningSearchEngine vs. ConnectFourNegamaxSearchEngine >>>
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
ConnectFourAlphaBetaPruningSearchEngine depth: 9
ConnectFourNegamaxSearchEngine depth: 9
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 1056 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|O|X|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 617 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
|.|.|O|X|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 1585 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|X|.|.|.|
|.|.|O|X|.|.|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 662 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|X|.|.|.|
|.|.|O|X|.|X|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 2060 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|X|.|.|.|
|.|.|O|X|.|X|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 1529 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|X|.|.|.|
|.|.|O|X|X|X|.|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 4107 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|X|.|.|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 3222 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|X|X|.|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 2241 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|X|X|O|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 1363 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|X|.|.|
|.|.|.|X|X|O|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 1002 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|O|.|.|
|.|.|.|O|X|.|.|
|.|.|.|X|X|O|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 570 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|O|.|.|
|.|.|.|O|X|.|.|
|.|.|X|X|X|O|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 481 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|O|.|.|
|.|.|.|O|X|.|.|
|.|.|X|X|X|O|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 477 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|O|.|.|
|.|.|.|O|X|.|.|
|.|.|X|X|X|O|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 339 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|O|.|.|
|.|.|.|O|X|O|.|
|.|.|X|X|X|O|.|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 435 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|O|.|.|
|.|.|.|O|X|O|.|
|.|.|X|X|X|O|X|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 301 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|O|.|.|
|.|.|O|O|X|O|.|
|.|.|X|X|X|O|X|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 161 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|.|.|.|
|.|.|.|O|O|X|.|
|.|.|O|O|X|O|.|
|.|.|X|X|X|O|X|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 222 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|O|.|.|
|.|.|.|O|O|X|.|
|.|.|O|O|X|O|.|
|.|.|X|X|X|O|X|
|.|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 86 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|O|.|.|
|.|.|.|O|O|X|.|
|.|.|O|O|X|O|.|
|.|.|X|X|X|O|X|
|X|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 68 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|O|.|.|
|.|.|O|O|O|X|.|
|.|.|O|O|X|O|.|
|.|.|X|X|X|O|X|
|X|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 13 milliseconds.
|.|.|.|X|.|.|.|
|.|.|.|O|O|.|.|
|.|.|O|O|O|X|.|
|.|.|O|O|X|O|.|
|X|.|X|X|X|O|X|
|X|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 37 milliseconds.
|.|.|.|X|.|.|.|
|.|.|O|O|O|.|.|
|.|.|O|O|O|X|.|
|.|.|O|O|X|O|.|
|X|.|X|X|X|O|X|
|X|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 6 milliseconds.
|.|.|.|X|.|.|.|
|.|.|O|O|O|.|.|
|.|.|O|O|O|X|.|
|X|.|O|O|X|O|.|
|X|.|X|X|X|O|X|
|X|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Alpha-beta pruning engine (X) in 12 milliseconds.
|.|.|O|X|.|.|.|
|.|.|O|O|O|.|.|
|.|.|O|O|O|X|.|
|X|.|O|O|X|O|.|
|X|.|X|X|X|O|X|
|X|.|O|X|X|X|O|
+-+-+-+-+-+-+-+
1 2 3 4 5 6 7
Negamax engine (O) in 1 milliseconds.
RESULT: Negamax engine wins.
Alpha-beta pruning engine in total 13511 milliseconds.
Negamax engine in total 9142 milliseconds.
Critique request
As always, I would love to receive constructive criticism on my work.
