Connect Four

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

Solving Connect Four

Code To Implement

Win or Lose Heuristic

class:	WinOrLoseHeuristic.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)

Sequential Negamax

class:	SequentialConnectFour.java
methods:	negamax
package:	connectfour.challenge
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

Choose one of the following paths:

path a) forall

class:	ParallelForallConnectFour.java
methods:	negamax
package:	connectfour.challenge.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.challenge.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.challenge.chooseyourownadventure.recursivetasks
source folder:	student/src/main/java

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

(Optional) Utility

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

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)

Challenge 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)

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