credit for this assignment: Finn Voichick and Dennis Cosgrove
- 1 Motivation
- 2 Background
- 3 Mistakes To Avoid
- 4 Code To Implement
- 5 Testing Your Solution
Negamax is a variant which relies on
While the core part of searches like Minimax may be easy to parallelize, critical aspects such as alpha-beta pruning are more challenging.
The Core Questions
- What are the tasks?
- What is the data?
- Is the data mutable?
- If so, how is it shared?
Code To Use
Mistakes To Avoid
|Warning:Do NOT be lured in be Double.MIN_VALUE. Use Double.NEGATIVE_INFINITY instead.|
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.
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
boardstate indicates that the game is over.
searchAtDepthpredicate test fails for the current depth.
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().
Win or Lose Heuristic
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?
Testing Your Solution
Some preliminary tests use a simple end game board, destined for a draw, where the last three searches will end in Optional.of(6).