Difference between revisions of "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

The Core Questions

• What is the data?
• Is the data mutable?
• If so, how is it shared?

Code To Use

connectfour.core

isDone()
getWinner()
getCurrentPlayer()
getTurnsPlayed()
createNextBoard(int column)

java.util.function

applyAsDouble(value)
test(value)

Mistakes To Avoid

 Warning:Do NOT be lured in be Double.MIN_VALUE. Use Double.NEGATIVE_INFINITY instead.
 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

 class: ConnectFour.java methods: negamaxKernelselectNextColumn package: connectfour.studio source folder: src/main/java

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

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

Win or Lose Heuristic

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

method: `public double applyAsDouble(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: applyAsDouble package: connectfour.challenge source folder: src/main/java

method: `public double applyAsDouble(Board board)` (sequential implementation only)