Difference between revisions of "Connect Four"

From CSE231 Wiki
Jump to navigation Jump to search
Line 44: Line 44:
 
=Code To Implement=
 
=Code To Implement=
 
==Negamax==
 
==Negamax==
{{CodeToImplement|ConnectFour|select<br>negamaxKernel<br>selectNextColumn|connectfour.studio}}
+
{{CodeToImplement|ConnectFour|negamaxKernel<br>selectNextColumn|connectfour.studio}}
  
 
{{Parallel|static double negamaxKernel(Board board, ToDoubleFunction<Board> heuristic, IntPredicate searchAtDepth,
 
{{Parallel|static double negamaxKernel(Board board, ToDoubleFunction<Board> heuristic, IntPredicate searchAtDepth,
Line 52: Line 52:
  
 
==Win or Lose Heuristic==
 
==Win or Lose Heuristic==
{{CodeToImplement|WinOrLoseHeuristic|evaluate|connectfour.studio}}
+
{{CodeToImplement|WinOrLoseHeuristic|applyAsDouble|connectfour.studio}}
  
{{Sequential|public double evaluate(Board board)}}
+
{{Sequential|public double applyAsDouble(Board board)}}
  
 
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.
 
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.
  
 
==OpenEndedHeuristic (Optional)==
 
==OpenEndedHeuristic (Optional)==
{{CodeToImplement|OpenEndedHeuristic|evaluate|connectfour.challenge}}
+
{{CodeToImplement|OpenEndedHeuristic|applyAsDouble|connectfour.challenge}}
  
{{Sequential|public double evaluate(Board board)}}
+
{{Sequential|public double applyAsDouble(Board board)}}
  
 
=Testing Your Solution=
 
=Testing Your Solution=

Revision as of 07:14, 13 February 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>

Code To Implement

Negamax

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

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

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.

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

Visualization

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

ConnectFourViz.png