Connect Four

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 $\max(a,b)=-\min(-a,-b)$

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

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)

class EvaluationColumnPair

double getEvaluation()

Optional<Integer> getColumn()

java.util

class Optional<T>

Code To Implement

Negamax

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

method: private static ColumnEvaluationPair select(ColumnEvaluationPair[] array) (sequential implementation only)

method: static ColumnEvaluationPair negamaxKernel(Board board, Heuristic heuristic, IntPredicate parallelPredicate, IntPredicate evaluatePredicate, int currentDepth) (parallel implementation required)

method: public static int selectNextColumn(Board board, Heuristic heuristic, IntPredicate parallelPredicate, IntPredicate evaluatePredicate) (sequential implementation only)

Win or Lose Heuristic

class:	WinOrLoseHeuristic.java
methods:	evaluate
package:	connectfour.studio
source folder:	student/src/main/java

method: public double evaluate(Board board) (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
methods:	evaluate
package:	connectfour.challenge
source folder:	student/src/main/java

method: public double evaluate(Board board) (sequential implementation only)

Testing Your Solution

Correctness

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

Visualization

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