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