Difference between revisions of "Connect Four"

From CSE231 Wiki
Jump to navigation Jump to search
 
(29 intermediate revisions by 2 users not shown)
Line 8: Line 8:
  
 
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.
 
+
<!--
 
Parallelism can be added in a number of different ways.  We can choose at our preference between: <code>forall</code>, <code>futures</code>, and [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/RecursiveTask.html RecursiveTask].
 
Parallelism can be added in a number of different ways.  We can choose at our preference between: <code>forall</code>, <code>futures</code>, and [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/RecursiveTask.html RecursiveTask].
 +
-->
  
 
=Background=
 
=Background=
Line 22: Line 23:
  
 
[https://en.wikipedia.org/wiki/Negamax Negamax]
 
[https://en.wikipedia.org/wiki/Negamax 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==
 
==Code To Use==
 
===connectfour.core===
 
===connectfour.core===
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/connectfour/core/Config.html class Config]
+
[https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/connectfour/core/Board.html interface Board]
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/connectfour/core/Config.html#getHeuristic-- getHeuristic()]
+
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/connectfour/core/Board.html#isDone()-- isDone()]
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/connectfour/core/Config.html#getMaxDepth-- getMaxDepth()]
+
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/connectfour/core/Board.html#getWinner()-- getWinner()]
:[https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/connectfour/core/Config.html#getMaxParallelDepth-- getMaxParallelDepth()]
+
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/connectfour/core/Board.html#getCurrentPlayer()-- getCurrentPlayer()]
 +
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/connectfour/core/Board.html#getTurnsPlayed()-- getTurnsPlayed()]
 +
: [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/s18/apidocs/connectfour/core/Board.html interface Board]
+
===java.util===
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/connectfour/core/Board.html#isDone-- isDone()]
+
[https://docs.oracle.com/javase/8/docs/api/java/util/Optional.html class Optional<T>]
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/connectfour/core/Board.html#getValidPlays-- getValidPlays()]
 
: [https://www.cse.wustl.edu/~cosgroved/courses/cse231/s18/apidocs/connectfour/core/Board.html#createNextBoard-int- createNextBoard(int column)]
 
  
===java.util.concurrent===
+
===java.util.function===
[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/function/ToDoubleFunction.html interface ToDoubleFunction<T>]
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/RecursiveTask.html#compute-- compute()]
+
: [https://docs.oracle.com/javase/8/docs/api/java/util/function/ToDoubleFunction.html#applyAsDouble-T- applyAsDouble(value)]
  
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinTask.html class ForkJoinTask]
+
[https://docs.oracle.com/javase/8/docs/api/java/util/function/IntPredicate.html interface IntPredicate]
:[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/function/IntPredicate.html#test-int- test(value)]
:[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ForkJoinTask.html#join-- join()]
 
  
=Code To Implement=
+
=Mistakes To Avoid=
==Win or Lose Heuristic==
+
{{Warning|Do NOT be lured in be [https://docs.oracle.com/javase/8/docs/api/java/lang/Double.html#MIN_VALUE Double.MIN_VALUE].  Use [https://docs.oracle.com/javase/8/docs/api/java/lang/Double.html#NEGATIVE_INFINITY Double.NEGATIVE_INFINITY] instead.}}
{{CodeToImplement|WinOrLoseHeuristic|evaluate|connectfour.studio}}
 
  
{{Sequential|public double evaluate(Board board, Player color, Config config, int currentDepth)}}
+
{{Warning|<br>If you are going to use [https://docs.oracle.com/javase/8/docs/api/java/lang/Double.html#NaN Double.NaN] to indicate an invalid/unsearched column (which as an implementation detail, is not the worst choice) [https://www.baeldung.com/java-not-a-number be sure you know what you are doing].<br>Double.NaN's semantics can absolutely be leveraged, but it can be tricky.}}
  
==Sequential Negamax==
+
=Code To Implement=
{{CodeToImplement|SequentialConnectFour|negamax|connectfour.studio}}
+
NOTE: While you should defer to the IntPredicate searchAtDepth for when to continue to search (test returns true) or when to return an evaluation (test returns false), it is up to you to decide when to search in parallel and when to fall back to sequential search.
 +
==Negamax==
 +
===negamaxKernel===
 +
This private method will do the lion's share of the search.  At each invocation either evaluating the board (if appropriate) selecting the evaluation which is worst for the opponent.
  
{{Sequential|public static ColumnEvaluationPair negamax(Board board, Player playerWhoseTurnItIs, Config config, int currentDepth)}}
+
For this assignment, there are two conditions when is appropriate to evaluation the board via the specified <code>heuristic</code>:
 +
# the <code>board</code> state indicates that the game is over.
 +
# the <code>searchAtDepth</code> predicate test fails for the current depth.
  
==Parallel Choose Your Own Adventure==
+
{{CodeToImplement|ConnectFour|negamaxKernel<br>selectNextColumn|connectfour.studio}}
The approach for each of the parallel paths is fundamentally the same.  Create tasks for each branch until you reach the specified depth at which you transition to sequential.
 
  
The forall and futures paths use our X10 inspired features.  The NegamaxTask path is more well suited to those interested in standard Java parallel constructs.
+
{{Parallel|private static double negamaxKernel(Board board, ToDoubleFunction<Board> heuristic, IntPredicate searchAtDepth,
 +
int currentDepth)}}
  
Choose one of the following paths:
 
===path a) forall===
 
{{CodeToImplement|ParallelForallConnectFour|negamax|connectfour.studio.chooseyourownadventure.forall}}
 
  
{{Parallel|public static ColumnEvaluationPair negamax(Board board, Player playerWhoseTurnItIs, Config config, int currentDepth)}}
+
===selectNextColumn===
 +
This public method will leverage <code>negamaxKernel</code> to search, but returns the (optional) column index of the chosen best move rather than the evaluation.  If there is no move to make, the method should return [https://docs.oracle.com/javase/8/docs/api/java/util/Optional.html#empty-- Optional.empty()].
  
===path b) futures===
+
{{Parallel|public static Optional<Integer> selectNextColumn(Board board, ToDoubleFunction<Board> heuristic, IntPredicate searchAtDepth)}}
{{CodeToImplement|ParallelFuturesConnectFour|negamax|connectfour.studio.chooseyourownadventure.futures}}
 
  
{{Parallel|public static ColumnEvaluationPair negamax(Board board, Player playerWhoseTurnItIs, Config config, int currentDepth)}}
+
==Win or Lose Heuristic==
 +
{{CodeToImplement|WinOrLoseHeuristic|applyAsDouble|connectfour.studio}}
  
===path c) recursive tasks===
+
{{Sequential|public double applyAsDouble(Board board)}}
{{CodeToImplement|NegamaxTask|compute|connectfour.studio.chooseyourownadventure.recursivetasks}}
 
  
{{Parallel|public ColumnEvaluationPair compute()}}
+
Evaluate the current state of the [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/connectfour/core/Board.html Board].  You should return a negative number if you have lost.  You should return less negative numbers for losses that occur later.  Put another way, draws should return 0.  Losses on the final turn should return -1.  Losses on the third to last turn should return -3.  Wins should return the analogous positive numbers.
  
==OpenEndedHeuristic==
+
Interestingly (at least to the Professor), if you build your algorithm in an expected way, you will only need to handle draws as well as (wins or losses). Which one is it?  Wins?  Or losses?
{{CodeToImplement|OpenEndedHeuristic|evaluate|connectfour.challenge}}
 
  
{{Sequential|public double evaluate(Board board, Player color, Config config, int currentDepth)}}
+
==OpenEndedHeuristic (Optional)==
 +
{{CodeToImplement|OpenEndedHeuristic|applyAsDouble|connectfour.challenge}}
  
==(Optional) Utility==
+
{{Sequential|public double applyAsDouble(Board board)}}
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:
+
=Testing Your Solution=
 
+
==Correctness==
<nowiki>return NegamaxUtils.select(futures, (future) -> chainedGet(future));</nowiki>
+
{{TestSuite|ConnectFourTestSuite|connnectfour.studio}}
  
{{CodeToImplement|NegamaxUtils|select|connectfour.challenge}}
+
Some preliminary tests use a simple end game board, destined for a draw, where the last three searches will end in Optional.of(6).
  
{{Sequential|public static <T> ColumnEvaluationPair select(T[] array, Function<T, ColumnEvaluationPair> f)}}
+
[[File:Simple end game test board.png|300px]]
  
=Testing Your Solution=
 
 
==Visualization==
 
==Visualization==
{{Viz|ConnectFourViz|connnectfour.challenge}}
+
{{Viz|ConnectFourViz|connnectfour.viz.game}}
  
 
[[File:ConnectFourViz.png|400px]]
 
[[File:ConnectFourViz.png|400px]]
 
==Correctness==
 
{{TestSuite|ConnectFourTestSuite|connnectfour.challenge}}
 

Latest revision as of 05:22, 15 March 2020

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.

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()
getWinner()
getCurrentPlayer()
getTurnsPlayed()
createNextBoard(int column)

java.util

class Optional<T>

java.util.function

interface ToDoubleFunction<T>

applyAsDouble(value)

interface IntPredicate

test(value)

Mistakes To Avoid

Attention niels epting.svg Warning:Do NOT be lured in be Double.MIN_VALUE. Use Double.NEGATIVE_INFINITY instead.
Attention niels epting.svg Warning:
If you are going to use Double.NaN to indicate an invalid/unsearched column (which as an implementation detail, is not the worst choice) be sure you know what you are doing.
Double.NaN's semantics can absolutely be leveraged, but it can be tricky.

Code To Implement

NOTE: While you should defer to the IntPredicate searchAtDepth for when to continue to search (test returns true) or when to return an evaluation (test returns false), it is up to you to decide when to search in parallel and when to fall back to sequential search.

Negamax

negamaxKernel

This private method will do the lion's share of the search. At each invocation either evaluating the board (if appropriate) selecting the evaluation which is worst for the opponent.

For this assignment, there are two conditions when is appropriate to evaluation the board via the specified heuristic:

  1. the board state indicates that the game is over.
  2. the searchAtDepth predicate test fails for the current depth.
class: ConnectFour.java Java.png
methods: negamaxKernel
selectNextColumn
package: connectfour.studio
source folder: student/src/main/java

method: private static double negamaxKernel(Board board, ToDoubleFunction<Board> heuristic, IntPredicate searchAtDepth, int currentDepth) Parallel.svg (parallel implementation required)


selectNextColumn

This public method will leverage negamaxKernel to search, but returns the (optional) column index of the chosen best move rather than the evaluation. If there is no move to make, the method should return Optional.empty().

method: public static Optional<Integer> selectNextColumn(Board board, ToDoubleFunction<Board> heuristic, IntPredicate searchAtDepth) Parallel.svg (parallel implementation required)

Win or Lose Heuristic

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

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

Evaluate the current state of the Board. You should return a negative number if you have lost. You should return less negative numbers for losses that occur later. Put another way, draws should return 0. Losses on the final turn should return -1. Losses on the third to last turn should return -3. Wins should return the analogous positive numbers.

Interestingly (at least to the Professor), if you build your algorithm in an expected way, you will only need to handle draws as well as (wins or losses). Which one is it? Wins? Or losses?

OpenEndedHeuristic (Optional)

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

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

Testing Your Solution

Correctness

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

Some preliminary tests use a simple end game board, destined for a draw, where the last three searches will end in Optional.of(6).

Simple end game test board.png

Visualization

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

ConnectFourViz.png