Difference between revisions of "Connect Four"

From CSE231 Wiki
Jump to navigation Jump to search
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

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

Solving Connect Four

Wikipedia

Minimax

Negamax

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

interface Board

isDone()
getValidPlays()
createNextBoard(int column)


Code To Implement

Negamax

class: ConnectFour.java Java.png
methods: select
negamaxKernel
selectNextColumn
package: connectfour.studio
source folder: student/src/main/java

method: private static ColumnEvaluationPair select(ColumnEvaluationPair[] array) Sequential.svg (sequential implementation only)

method: static ColumnEvaluationPair negamaxKernel(Board board, Heuristic heuristic, IntPredicate parallelPredicate, IntPredicate evaluatePredicate, int currentDepth) Parallel.svg (parallel implementation required)

method: public static int selectNextColumn(Board board, Heuristic heuristic, IntPredicate parallelPredicate, IntPredicate evaluatePredicate) Sequential.svg (sequential implementation only)

Win or Lose Heuristic

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

method: public double evaluate(Board board) Sequential.svg (sequential implementation only)

OpenEndedHeuristic (Optional)

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

method: public double evaluate(Board board) Sequential.svg (sequential implementation only)

Testing Your Solution

Visualization

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

ConnectFourViz.png

Correctness

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