Difference between revisions of "Connect Four"

From CSE231 Wiki
Jump to navigation Jump to search
Line 43: Line 43:
  
 
{{Parallel|public ColumnEvaluationPair compute()}}
 
{{Parallel|public ColumnEvaluationPair compute()}}
 +
 +
==OpenEndedHeuristic==
 +
{{CodeToImplement|OpenEndedHeuristic|evaluate|connectfour.challenge}}
 +
 +
{{Sequential|public double evaluate(Board board, Player color, Config config, int currentDepth)}}
  
 
==(Optional) Utility==
 
==(Optional) Utility==
Line 50: Line 55:
  
 
{{Sequential|public static <T> ColumnEvaluationPair select(T[] array, Function<T, ColumnEvaluationPair> f)}}
 
{{Sequential|public static <T> ColumnEvaluationPair select(T[] array, Function<T, ColumnEvaluationPair> f)}}
 
==Challenge OpenEndedHeuristic==
 
{{CodeToImplement|OpenEndedHeuristic|evaluate|connectfour.challenge}}
 
 
{{Sequential|public double evaluate(Board board, Player color, Config config, int currentDepth)}}
 
  
 
=Testing Your Solution=
 
=Testing Your Solution=

Revision as of 14:24, 30 April 2018

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

Solving Connect Four

Code To Implement

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, Player color, Config config, int currentDepth) Sequential.svg (sequential implementation only)

Sequential Negamax

class: SequentialConnectFour.java Java.png
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.svg (sequential implementation only)

Parallel Choose Your Own Adventure

Choose one of the following paths:

path a) forall

class: ParallelForallConnectFour.java Java.png
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.svg (parallel implementation required)

path b) futures

class: ParallelFuturesConnectFour.java Java.png
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.svg (parallel implementation required)

path c) recursive tasks

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

method: public ColumnEvaluationPair compute() Parallel.svg (parallel implementation required)

OpenEndedHeuristic

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

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

(Optional) Utility

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

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

method: public static <T> ColumnEvaluationPair select(T[] array, Function<T, ColumnEvaluationPair> f) 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