Difference between revisions of "Connect Four"

From CSE231 Wiki
Jump to navigation Jump to search
Line 1: Line 1:
 +
credit for this assignment: Finn Voichick and Dennis Cosgrove
 
=Motivation=
 
=Motivation=
 
[https://en.wikipedia.org/wiki/Minimax Minimax] is an important concept in [https://en.wikipedia.org/wiki/Game_theory game theory] and search.
 
[https://en.wikipedia.org/wiki/Minimax Minimax] is an important concept in [https://en.wikipedia.org/wiki/Game_theory game theory] and search.

Revision as of 04:23, 29 March 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.challenge
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.challenge
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.challenge.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.challenge.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.challenge.chooseyourownadventure.recursivetasks
source folder: student/src/main/java

method: public ColumnEvaluationPair compute() Parallel.svg (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 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)

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

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