Multithreaded Alpha-beta pruning for playing Connect Four in Java

Question

Intro

(The entire repository is in GitHub.)

This time, I have parallelized the famous Alpha-beta pruning algorithm. The idea is that the parallel algorithm descends in a game tree (at least) 2 levels down (reaching the seed level), and for each state at the seed level runs in parallel it in a single-threaded Alpha-beta pruning to compute their scores. The rest is a sequential search starting from the root all the way down to the seed layer. Basically, this is the divide-and-conquer approach.

Code

com.github.coderodde.game.zerosum.impl.ParallelConnectFourAlphaBetaPruningSearchEngine.java:

import com.github.coderodde.game.connect4.ConnectFourBoard;
import static com.github.coderodde.game.connect4.ConnectFourBoard.COLUMNS;
import com.github.coderodde.game.connect4.ConnectFourHeuristicFunction;
import com.github.coderodde.game.zerosum.HeuristicFunction;
import com.github.coderodde.game.zerosum.PlayerType;
import com.github.coderodde.game.zerosum.SearchEngine;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
 * This class implements the parallel Alpha-beta pruning for playing Connect 
 * Four.
 * 
 * @version 1.0.0 (Jun 7, 2024) 
 * @since 1.0.0 (Jun 7, 2024)
 */
public final class ParallelConnectFourAlphaBetaPruningSearchEngine 
implements SearchEngine<ConnectFourBoard> {
 private static final int MINIMUM_SEED_DEPTH = 2;
 private static final int DEFAULT_SEED_DEPTH = 2;
 private static final int MINIMUM_DEPTH = 5;
 
 private final HeuristicFunction<ConnectFourBoard> heuristicFunction;
 private int requestedDepth;
 private int seedDepth;
 
 /**
 * Constructs this search engine.
 * 
 * @param heuristicFunction the heuristic function used to score the states.
 * @param seedDepth the depth of the seed states.
 */
 public ParallelConnectFourAlphaBetaPruningSearchEngine(
 final HeuristicFunction<ConnectFourBoard> heuristicFunction,
 final int seedDepth) {
 
 this.heuristicFunction = heuristicFunction;
 this.seedDepth = seedDepth;
 }
 
 /**
 * Constructs this search engine.
 * 
 * @param heuristicFunction the heuristic function used to score the states.
 */
 public ParallelConnectFourAlphaBetaPruningSearchEngine(
 final ConnectFourHeuristicFunction heuristicFunction) {
 
 this(heuristicFunction, DEFAULT_SEED_DEPTH);
 }
 
 /**
 * Performs the actual search for the next move state.
 * 
 * @param root the root state of the search.
 * @param depth the depth of the search.
 * 
 * @return next move state.
 */
 @Override
 public ConnectFourBoard 
 search(final ConnectFourBoard root, 
 final int depth,
 final PlayerType playerType) {
 
 this.requestedDepth = depth;
 
 if (depth < Math.max(MINIMUM_SEED_DEPTH, MINIMUM_DEPTH)) {
 // If too shallow, delegate to single-threaded AI:
 return new ConnectFourAlphaBetaPruningSearchEngine(
 heuristicFunction).search(root,
 depth);
 }
 
 // Obtains the list of seed states. May lower the 'seedDepth':
 final List<ConnectFourBoard> seedStates = getSeedStates(root,
 playerType);
 
 // Randomly shuffle the seed states. This is a trivial load balancing:
 Collections.shuffle(seedStates);
 
 // Get the list of thread workloads:
 final List<List<ConnectFourBoard>> threadLoads = 
 bucketizeSeedStates(seedStates, 
 Runtime.getRuntime().availableProcessors());
 
 // Create the list of search threads:
 final List<SearchThread> searchThreadList = 
 new ArrayList<>(threadLoads.size());
 
 // Populate the search threads:
 for (final List<ConnectFourBoard> threadLoad : threadLoads) {
 final SearchThread searchThread =
 new SearchThread(
 threadLoad,
 heuristicFunction,
 seedDepth % 2 == 0 ? PlayerType.MAXIMIZING_PLAYER :
 PlayerType.MINIMIZING_PLAYER,
 depth - seedDepth);
 
 searchThread.start();
 
 searchThreadList.add(searchThread);
 }
 
 // Wait for all the threads to complete:
 for (final SearchThread searchThread : searchThreadList) {
 try {
 searchThread.join();
 } catch (final InterruptedException ex) {
 
 }
 }
 
 // Compute the global seed state score map:
 final Map<ConnectFourBoard, Double> globalScoreMap = 
 getGlobalScoreMap(searchThreadList);
 
 // Construct the seed state heuristic function:
 final SeedStateHeuristicFunction seedHeuristicFunction = 
 new SeedStateHeuristicFunction(globalScoreMap);
 
 // Just compute above the seed states:
 return alphaBetaImplRoot(root, 
 seedHeuristicFunction,
 requestedDepth,
 playerType);
 }
 
 /**
 * The topmost call to the search routine.
 * 
 * @param root the root state.
 * @param heuristicFunction the heuristic function.
 * @param seedDepth the seed state depth.
 * 
 * @return the next move state.
 */
 private ConnectFourBoard 
 alphaBetaImplRoot(
 final ConnectFourBoard root,
 final SeedStateHeuristicFunction seedHeuristicFunction,
 final int depth,
 final PlayerType playerType) {
 
 ConnectFourBoard bestMoveState = null;
 
 if (playerType == PlayerType.MAXIMIZING_PLAYER) {
 
 double alpha = Double.NEGATIVE_INFINITY;
 double value = Double.NEGATIVE_INFINITY;
 double tentativeValue = Double.NEGATIVE_INFINITY;
 for (int x = 0; x < COLUMNS; x++) {
 // Try to make a ply at column 'x':
 if (!root.makePly(x, PlayerType.MAXIMIZING_PLAYER)) {
 // The entire column at X=x is full. Omit.
 continue;
 }
 value = Math.max(value,
 alphaBetaImplAboveSeedLayer(
 root,
 depth - 1,
 alpha,
 Double.POSITIVE_INFINITY,
 PlayerType.MINIMIZING_PLAYER,
 seedHeuristicFunction));
 
 if (tentativeValue < value) {
 tentativeValue = value;
 bestMoveState = new ConnectFourBoard(root);
 }
 
 // Undo the previously made ply:
 root.unmakePly(x);
 
 // Possibly raise alpha:
 alpha = Math.max(alpha, value);
 }
 
 return bestMoveState;
 } else {
 
 double beta = Double.POSITIVE_INFINITY;
 double value = Double.POSITIVE_INFINITY;
 double tentativeValue = Double.POSITIVE_INFINITY;
 
 for (int x = 0; x < COLUMNS; x++) {
 // Try to make a ply at column 'x':
 if (!root.makePly(x, PlayerType.MINIMIZING_PLAYER)) {
 // The entire column at X=x is full. Omit.
 continue;
 }
 
 value = Math.min(value,
 alphaBetaImplAboveSeedLayer(
 root,
 depth - 1,
 Double.NEGATIVE_INFINITY,
 beta,
 PlayerType.MAXIMIZING_PLAYER,
 seedHeuristicFunction));
 
 if (tentativeValue > value) {
 tentativeValue = value;
 bestMoveState = new ConnectFourBoard(root);
 }
 
 // Undo the previously made ply:
 root.unmakePly(x);
 
 // Possibly lower beta:
 beta = Math.min(beta, value);
 }
 }
 
 // The best known value
 return bestMoveState;
 }
 
 private double alphaBetaImplAboveSeedLayer(
 final ConnectFourBoard root,
 final int depth,
 double alpha,
 double beta,
 final PlayerType rootPlayerType,
 final SeedStateHeuristicFunction seedStateHeuristicFunction) {
 
 if (depth == 0 || root.isTerminal()) {
 // Once here, we have a loss, victory or tie:
 return heuristicFunction.evaluate(root, depth);
 }
 
 if (requestedDepth - depth == seedDepth) {
 // Once here, we have reached the seed level.
 // 0 as the second argument is ignored. Just return the
 // score for 'root' as we have computed its score in a 
 // thread:
 return seedStateHeuristicFunction.evaluate(root, 0);
 }
 
 if (rootPlayerType == PlayerType.MAXIMIZING_PLAYER) {
 double value = Double.NEGATIVE_INFINITY;
 for (int x = 0; x < COLUMNS; x++) {
 if (!root.makePly(x, PlayerType.MAXIMIZING_PLAYER)) {
 continue;
 }
 value = Math.max(value, 
 alphaBetaImplAboveSeedLayer(
 root,
 depth - 1,
 alpha,
 beta,
 PlayerType.MINIMIZING_PLAYER,
 seedStateHeuristicFunction));
 root.unmakePly(x);
 if (value > beta) {
 break;
 }
 alpha = Math.max(alpha, value);
 } 
 return value;
 } else {
 double value = Double.POSITIVE_INFINITY;
 for (int x = 0; x < COLUMNS; x++) {
 if (!root.makePly(x, PlayerType.MINIMIZING_PLAYER)) {
 continue;
 }
 value = Math.min(value,
 alphaBetaImplAboveSeedLayer(
 root,
 depth - 1,
 alpha,
 beta,
 PlayerType.MAXIMIZING_PLAYER,
 seedStateHeuristicFunction));
 root.unmakePly(x);
 if (value < alpha) {
 break;
 }
 beta = Math.min(beta, value);
 }
 return value;
 }
 }
 
 /**
 * Combines all the score maps into one global map for searching above the
 * seed states.
 * 
 * @param searchThreadList the list of search threads.
 * 
 * @return the combined global score map.
 */
 private static Map<ConnectFourBoard, Double>
 getGlobalScoreMap(final List<SearchThread> searchThreadList) {
 
 // Construct the global score map:
 final Map<ConnectFourBoard, Double> globalScoreMap = new HashMap<>();
 
 // Load the global score map from each search thread score map:
 for (final SearchThread searchThread : searchThreadList) {
 globalScoreMap.putAll(searchThread.getScoreMap());
 }
 
 return globalScoreMap;
 }
 
 /**
 * Splits the list of seed states into list of lists of seed states.
 * 
 * @param seedStates the list of all the seed states.
 * @param threadCount the number of threads to assume.
 * 
 * @return list of seed state buckets. One for each thread.
 */
 private static List<List<ConnectFourBoard>> 
 bucketizeSeedStates(final List<ConnectFourBoard> seedStates,
 final int threadCount) {
 
 // Construct a list with capacity sufficient to accommodate all the
 // buckets:
 final List<List<ConnectFourBoard>> threadBuckets = 
 new ArrayList<>(threadCount);
 
 // The basic number of seed states per thread bucket:
 final int basicNumberOfSeedsPerBucket = seedStates.size() / threadCount;
 
 // The seed state index:
 int index = 0;
 
 for (int i = 0; i < threadCount; i++) {
 // Construct the new bucket. +1 in order to add additional possible
 // seed state in case 'threadCount' does not divide
 // 'seedStates.size()':
 final List<ConnectFourBoard> bucket = 
 new ArrayList<>(basicNumberOfSeedsPerBucket + 1);
 
 // Load the current bucket:
 for (int j = 0; j < basicNumberOfSeedsPerBucket; j++, index++) {
 bucket.add(seedStates.get(index));
 }
 
 // Add the bucket to the bucket list:
 threadBuckets.add(bucket);
 }
 
 // How many threads should receive one more additional seed state?
 final int remainingStates = seedStates.size() % threadCount;
 
 for (int i = 0; i < remainingStates; i++, index++) {
 threadBuckets.get(i).add(seedStates.get(index));
 }
 
 return threadBuckets;
 }
 
 /**
 * Computes the list of seed states. The idea is that each search thread 
 * starts its search from a seed state. This method resembles breadth-
 * first search in a tree. This method may update {@link #seedDepth}.
 * 
 * @param root the actual root state of the search.
 * 
 * @return the list of seed states.
 */
 private List<ConnectFourBoard> getSeedStates(final ConnectFourBoard root,
 PlayerType playerType) {
 
 List<ConnectFourBoard> levelA = new ArrayList<>();
 List<ConnectFourBoard> levelB = new ArrayList<>();
 
 // Initialize the expansion:
 levelA.add(root);
 
 int effectiveSeedDepth = 0;
 
 for (int i = 0; i < seedDepth; i++) {
 // Load next state layer:
 for (final ConnectFourBoard cfb : levelA) {
 levelB.addAll(cfb.expand(playerType));
 }
 
 if (levelB.isEmpty() == false) {
 effectiveSeedDepth++;
 } else {
 // Once here, the root state is missing very few plies:
 seedDepth = effectiveSeedDepth;
 return levelA;
 }
 
 levelA.clear();
 levelA.addAll(levelB);
 levelB.clear();
 
 // Assume the opposite player:
 playerType = playerType.flip();
 }
 
 return levelA;
 }
 @Override
 public ConnectFourBoard search(final ConnectFourBoard root,
 final int depth) {
 
 return search(root, depth, PlayerType.MAXIMIZING_PLAYER);
 }
}
/**
 * This class implements the actual search routine starting from seed states.
 */
final class SearchThread extends Thread {
 /**
 * The list of seed states to process.
 */
 private final List<ConnectFourBoard> workload;
 /**
 * This map maps each seed states to its score after computation.
 */
 private final Map<ConnectFourBoard, Double> scoreMap;
 /**
 * The heuristic function for evaluating intermediate states.
 */
 private final HeuristicFunction<ConnectFourBoard> heuristicFunction;
 /**
 * The beginning player type.
 */
 private final PlayerType rootPlayerType;
 /**
 * The (maximal) search depth.
 */
 private final int depth;
 /**
 * Constructs this search thread.
 * 
 * @param workload the workload list of seed states.
 * @param heuristicFunction the heuristic function.
 * @param rootPlayerType the beginning player type.
 * @param depth the maximal search depth.
 */
 SearchThread(final List<ConnectFourBoard> workload,
 final HeuristicFunction<ConnectFourBoard> 
 heuristicFunction,
 final PlayerType rootPlayerType,
 final int depth) {
 this.workload = workload;
 this.scoreMap = new HashMap<>(workload.size());
 this.heuristicFunction = heuristicFunction;
 this.rootPlayerType = rootPlayerType;
 this.depth = depth;
 }
 /**
 * Returns computed score map mapping each seed state to its score.
 * 
 * @return the score map.
 */
 Map<ConnectFourBoard, Double> getScoreMap() {
 return scoreMap;
 }
 /**
 * Runs the search in this thread.
 */
 @Override
 public void run() {
 for (final ConnectFourBoard root : workload) {
 final double score = 
 alphaBetaImpl(
 root,
 depth, 
 Double.NEGATIVE_INFINITY,
 Double.POSITIVE_INFINITY,
 rootPlayerType);
 scoreMap.put(root, score);
 }
 }
 private double alphaBetaImpl(final ConnectFourBoard root,
 final int depth,
 double alpha,
 double beta,
 final PlayerType rootPlayerType) {
 
 if (depth == 0 || root.isTerminal()) {
 return heuristicFunction.evaluate(root, depth);
 }
 if (rootPlayerType == PlayerType.MAXIMIZING_PLAYER) {
 double value = Double.NEGATIVE_INFINITY;
 for (int x = 0; x < COLUMNS; x++) {
 if (!root.makePly(x, PlayerType.MAXIMIZING_PLAYER)) {
 continue;
 }
 value = Math.max(value, 
 alphaBetaImpl(root,
 depth - 1,
 alpha,
 beta,
 PlayerType.MINIMIZING_PLAYER));
 root.unmakePly(x);
 if (value > beta) {
 break;
 }
 alpha = Math.max(alpha, value);
 } 
 return value;
 } else {
 double value = Double.POSITIVE_INFINITY;
 for (int x = 0; x < COLUMNS; x++) {
 if (!root.makePly(x, PlayerType.MINIMIZING_PLAYER)) {
 continue;
 }
 value = Math.min(value,
 alphaBetaImpl(root,
 depth - 1,
 alpha,
 beta,
 PlayerType.MAXIMIZING_PLAYER));
 root.unmakePly(x);
 if (value < alpha) {
 break;
 }
 beta = Math.min(beta, value);
 }
 return value;
 }
 }
}
 
/**
 * This class implements the heuristic function for the seed states.
 */
final class SeedStateHeuristicFunction
 implements HeuristicFunction<ConnectFourBoard> {
 private final Map<ConnectFourBoard, Double> scoreMap;
 SeedStateHeuristicFunction(
 final Map<ConnectFourBoard, Double> scoreMap) {
 this.scoreMap = scoreMap;
 }
 @Override
 public double evaluate(ConnectFourBoard state, int depth) {
 return scoreMap.get(state);
 }
}

Comparison output

The comparison program shows the following results on a octocore CPU (8 physical cores):

AlphaBetaPruningSearchEngine in 4640 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
ConnectFourAlphaBetaPruningSearchEngine in 2764 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
ParallelConnectFourAlphaBetaPruningSearchEngine in 1818 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
<<< AI vs. AI >>>
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial AI depth: 9
Parallel AI depth: 8
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 1027 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|X|O|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 122 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|O|.|.|.|
|.|.|X|O|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 1589 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
|.|.|.|O|.|.|.|
|.|.|X|O|.|.|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 164 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
|.|.|.|O|.|.|.|
|.|.|X|O|.|O|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 2016 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
|.|.|.|O|.|.|.|
|.|.|X|O|X|O|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 225 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
|.|.|.|O|.|O|.|
|.|.|X|O|X|O|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 1787 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
|.|.|.|O|.|O|.|
|X|.|X|O|X|O|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 209 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
|.|.|.|O|O|O|.|
|X|.|X|O|X|O|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 2535 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|.|.|
|.|.|X|O|O|O|.|
|X|.|X|O|X|O|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 63 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|O|.|
|.|.|X|O|O|O|.|
|X|.|X|O|X|O|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 3651 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|X|.|
|.|.|.|X|.|O|.|
|.|.|X|O|O|O|.|
|X|.|X|O|X|O|.|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 105 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|X|.|
|.|.|.|X|.|O|.|
|.|.|X|O|O|O|.|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 2437 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|X|.|
|.|.|.|X|.|O|.|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 164 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|.|.|X|.|
|.|.|.|X|O|O|.|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 2468 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|.|X|.|
|.|.|.|X|O|O|.|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 102 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|
|.|.|.|X|O|X|.|
|.|.|.|X|O|O|.|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 1248 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|X|.|.|
|.|.|.|X|O|X|.|
|.|.|.|X|O|O|.|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 92 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|X|.|.|
|.|.|.|X|O|X|.|
|.|.|.|X|O|O|O|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 1271 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|.|X|.|.|
|.|.|.|X|O|X|X|
|.|.|.|X|O|O|O|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 126 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|O|X|.|.|
|.|.|.|X|O|X|X|
|.|.|.|X|O|O|O|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 257 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|O|X|.|.|
|.|.|.|X|O|X|X|
|.|.|X|X|O|O|O|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 52 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|O|X|.|.|
|.|.|O|X|O|X|X|
|.|.|X|X|O|O|O|
|.|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 47 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|O|X|.|.|
|.|.|O|X|O|X|X|
|.|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 19 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|O|X|.|.|
|.|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 39 milliseconds.
|.|.|.|.|.|.|.|
|.|.|.|O|X|.|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 17 milliseconds.
|.|.|.|.|.|.|.|
|.|.|O|O|X|.|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 48 milliseconds.
|.|.|X|.|.|.|.|
|.|.|O|O|X|.|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 8 milliseconds.
|.|.|X|.|.|.|.|
|O|.|O|O|X|.|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 22 milliseconds.
|.|.|X|.|.|.|.|
|O|.|O|O|X|X|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 6 milliseconds.
|.|.|X|.|.|O|.|
|O|.|O|O|X|X|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 3 milliseconds.
|.|.|X|X|.|O|.|
|O|.|O|O|X|X|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 3 milliseconds.
|O|.|X|X|.|O|.|
|O|.|O|O|X|X|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 0 milliseconds.
|O|.|X|X|X|O|.|
|O|.|O|O|X|X|.|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 2 milliseconds.
|O|.|X|X|X|O|.|
|O|.|O|O|X|X|O|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 0 milliseconds.
|O|.|X|X|X|O|X|
|O|.|O|O|X|X|O|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|.|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 2 milliseconds.
|O|.|X|X|X|O|X|
|O|.|O|O|X|X|O|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|.|X|O|O|O|X|
|X|O|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Serial engine in 0 milliseconds.
|O|.|X|X|X|O|X|
|O|.|O|O|X|X|O|
|X|.|O|X|O|X|X|
|O|.|X|X|O|O|O|
|X|X|X|O|O|O|X|
|X|O|X|O|X|O|O|
+-+-+-+-+-+-+-+
 1 2 3 4 5 6 7
Parallel engine in 3 milliseconds.
RESULT: Parallel engine wins.
Serial engine in total 20445 milliseconds.
Parallel engine in total 1484 milliseconds.

Critique request

Please, tell me whatever comes to mind.

• Toby Speight: A 3x speedup sounds like a reasonable start for 8 cores. Read up on Amdahl's law and consider where your code has serial processing and thread creation/destruction/communication overheads.
• coderodde: @TobySpeight I am well aware about Amdahl's law and its implications. However, I was expecting to see speed up of 6.

Answer 1

You're probably not getting any replies because the subject is not very trivial and there isn't much to complain about your code. I would have written this as a comment as I don't think it really qualifies as a proper review, but I ran out of characters.

Have you evaluated how a ThreadPoolExecutor affects the performance? It would seem like a tool designed for this job, since you're always creating the same number of threads to handle a large amount of workload items.

You probably want to use HashMap.newHashMap(workload.size()) instead of the constructor, as it guarantees that a rehashing won't happen.

Consider splitting alphaBetaImpl into two methods, one for minimizing and one or maximizing, so you don't need a long if-else block.

• coderodde: Fair enough. Your text well qualifies as an answer. I will try your threading advice later.
• coderodde: Took a look at docs.oracle.com/en%2Fjava%2Fjavase%2F11%2Fdocs%2Fapi%2F%2F/… I don't quite get how it is any better than creating two threads for each physical core and run almost equal number of subtasks on each thread.