Difference between revisions of "Connect Four"
Line 36: | Line 36: | ||
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/connectfour/core/Board.html#createNextBoard-int- createNextBoard(int column)] | : [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/connectfour/core/Board.html#createNextBoard-int- createNextBoard(int column)] | ||
+ | <!-- | ||
===java.util.concurrent=== | ===java.util.concurrent=== | ||
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/RecursiveTask.html class RecursiveTask] extends ForkJoinTask | [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/RecursiveTask.html class RecursiveTask] extends ForkJoinTask | ||
Line 43: | Line 44: | ||
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinTask.html#fork-- fork()] | :[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinTask.html#fork-- fork()] | ||
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinTask.html#join-- join()] | :[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinTask.html#join-- join()] | ||
+ | --> | ||
=Code To Implement= | =Code To Implement= |
Revision as of 17:50, 13 February 2019
credit for this assignment: Finn Voichick and Dennis Cosgrove
Contents
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
Video
Tutorial
Wikipedia
The Core Questions
- What are the tasks?
- What is the data?
- Is the data mutable?
- If so, how is it shared?
Code To Use
connectfour.core
Code To Implement
Negamax
class: | ConnectFour.java | |
methods: | select negamaxKernel selectNextColumn |
|
package: | connectfour.studio | |
source folder: | student/src/main/java |
method: private static ColumnEvaluationPair select(ColumnEvaluationPair[] array)
(sequential implementation only)
method: static ColumnEvaluationPair negamaxKernel(Board board, Heuristic heuristic, IntPredicate parallelPredicate, IntPredicate evaluatePredicate, int currentDepth)
(parallel implementation required)
method: public static int selectNextColumn(Board board, Heuristic heuristic, IntPredicate parallelPredicate, IntPredicate evaluatePredicate)
(sequential implementation only)
Win or Lose Heuristic
class: | WinOrLoseHeuristic.java | |
methods: | evaluate | |
package: | connectfour.studio | |
source folder: | student/src/main/java |
method: public double evaluate(Board board)
(sequential implementation only)
OpenEndedHeuristic (Optional)
class: | OpenEndedHeuristic.java | |
methods: | evaluate | |
package: | connectfour.challenge | |
source folder: | student/src/main/java |
method: public double evaluate(Board board)
(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 |