FEATURE - Negamax for Tic-Tac-Toe #1
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
added 2 commits
May 19, 2019 14:48
added 10 commits
May 19, 2019 19:34
marciovmf
reviewed
May 20, 2019
|
|
||
| for (int x = 0; x < 9; x++) | ||
| { | ||
| if ((board & mask) == 0) |
| { | ||
| if ((board & mask) == 0) | ||
| { | ||
| int score = getMinTreeScore(board | mask, alpha, beta); |
There was a problem hiding this comment.
I suggest make this bitshift operation a constant variable inside the loop so it is easier to debug its value
| int state = getState(board); | ||
| if (state != Playing) return getScore(state); | ||
|
|
||
| int bestScore = INT_MAX; |
There was a problem hiding this comment.
make it const. It can make the compiler use the raw value instead of a pointer to a variable
| if (state != Playing) return getScore(state); | ||
|
|
||
| int bestScore = INT_MAX; | ||
| int mask = 2; |
There was a problem hiding this comment.
We can't make this field constant because we are using it on bitshift operations inside this method.
Closed
andreimesquita
changed the title
andreimesquita
changed the title
Open
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
What is it about?
This PR introduces the adversarial search context by sharing a specific Negamax logic that solves the Tic-Tac-Toe game. The Negamax is a variant of the Minimax algorithm that performatively prunes nodes that are not important for the final result.
More details about this implementation are going to be described at the SoloGameDevBlog in the near future. You could read about the threoretical description of the Minimax algorithm at [Teoría] Adversarial Search: Minmax.
The complete game (Minimax vs Minimax) is taking 2ms total to run; sometimes it takes less than that.