Difference between revisions of "Connect Four"

From CSE231 Wiki
Jump to navigation Jump to search
Line 5: Line 5:
 
[https://en.wikipedia.org/wiki/Negamax Negamax] is a variant which relies on <math>\max(a, b) = -\min(-a, -b)</math>
 
[https://en.wikipedia.org/wiki/Negamax Negamax] is a variant which relies on <math>\max(a, b) = -\min(-a, -b)</math>
  
While this technique is applicable to [https://en.wikipedia.org/wiki/Chess Chess] (as [https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer) Deep Blue] [https://en.wikipedia.org/wiki/Deep_Blue_versus_Garry_Kasparov employed to defeat Kasparov], we choose [https://en.wikipedia.org/wiki/Connect_Four Connect Four] as our context since it has a simpler game mechanic.
+
While this technique is applicable to [https://en.wikipedia.org/wiki/Chess Chess] (as [https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer) Deep Blue] [https://en.wikipedia.org/wiki/Deep_Blue_versus_Garry_Kasparov employed to defeat Kasparov]), we choose [https://en.wikipedia.org/wiki/Connect_Four 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.
 
While the core part of searches like Minimax may be easy to parallelize, critical aspects such as alpha-beta pruning are more challenging.

Revision as of 14:41, 1 May 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.

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