Connect Four

credit for this assignment: Finn Voichick and Dennis Cosgrove

Motivation

Minimax is an important concept in game theory and search.

Negamax is a variant which relies on $\max(a,b)=-\min(-a,-b)$

While this technique is applicable to Chess (as Deep Blue employed to defeat Kasparov), we choose Connect Four as our context since it has a simpler game mechanic.

While the core part of searches like Minimax may be easy to parallelize, critical aspects such as alpha-beta pruning are more challenging.

Parallelism can be added in a number of different ways. We can choose at our preference between: forall, futures, and RecursiveTask.

Background

Tutorial

Solving Connect Four

Wikipedia

Minimax

Negamax

Code To Use

connectfour.core

class Config

getHeuristic()

getMaxDepth()

getMaxParallelDepth()

interface Board

isDone()

getValidPlays()

createNextBoard(int column)

java.util.concurrent

class RecursiveTask extends ForkJoinTask

compute()

class ForkJoinTask

fork()

join()

Code To Implement

Win or Lose Heuristic

class:	WinOrLoseHeuristic.java
methods:	evaluate
package:	connectfour.studio
source folder:	student/src/main/java

method: public double evaluate(Board board, Player color, Config config, int currentDepth) (sequential implementation only)

Sequential Negamax

class:	SequentialConnectFour.java
methods:	negamax
package:	connectfour.studio
source folder:	student/src/main/java

method: public static ColumnEvaluationPair negamax(Board board, Player playerWhoseTurnItIs, Config config, int currentDepth) (sequential implementation only)

Parallel Choose Your Own Adventure

The approach for each of the parallel paths is fundamentally the same. Create tasks for each branch until you reach the specified depth at which you transition to sequential.

The forall and futures paths use our X10 inspired features. The NegamaxTask path is more well suited to those interested in standard Java parallel constructs.

Choose one of the following paths:

path a) forall

class:	ParallelForallConnectFour.java
methods:	negamax
package:	connectfour.studio.chooseyourownadventure.forall
source folder:	student/src/main/java

method: public static ColumnEvaluationPair negamax(Board board, Player playerWhoseTurnItIs, Config config, int currentDepth) (parallel implementation required)

path b) futures

class:	ParallelFuturesConnectFour.java
methods:	negamax
package:	connectfour.studio.chooseyourownadventure.futures
source folder:	student/src/main/java

method: public static ColumnEvaluationPair negamax(Board board, Player playerWhoseTurnItIs, Config config, int currentDepth) (parallel implementation required)

path c) recursive tasks

class:	NegamaxTask.java
methods:	compute
package:	connectfour.studio.chooseyourownadventure.recursivetasks
source folder:	student/src/main/java

method: public ColumnEvaluationPair compute() (parallel implementation required)

OpenEndedHeuristic

class:	OpenEndedHeuristic.java
methods:	evaluate
package:	connectfour.challenge
source folder:	student/src/main/java

method: public double evaluate(Board board, Player color, Config config, int currentDepth) (sequential implementation only)

(Optional) Utility

You may elect to implement this utility method so that you can reuse the functionality across your negamaxes.

One of the annoying things about parallel programming is that you often have to duplicate code for the initial parallel part often followed by the sequential part when you have created enough tasks already. When building negamax, I found that I wanted to build a common method which would select the best column value pair from both the sequential and parallel algorithms. To allow for all of the different parallel adventures, select takes a function which returns the ColumnEvaluationPair. As an example, for the ParallelFuturesConnectFour adventure I used:

return NegamaxUtils.select(futures, (future) -> chainedGet(future));

class:	NegamaxUtils.java
methods:	select
package:	connectfour.challenge
source folder:	student/src/main/java

method: public static <T> ColumnEvaluationPair select(T[] array, Function<T, ColumnEvaluationPair> f) (sequential implementation only)

Testing Your Solution

Visualization

class:	ConnectFourViz.java	VIZ
package:	connnectfour.challenge
source folder:	student/src//java

Correctness

class:	ConnectFourTestSuite.java
package:	connnectfour.challenge
source folder:	testing/src/test/java