StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It seems like you're trying to implement some form of the <a href="http://en.wikipedia.org/wiki/Minimax" rel="nofollow">Minimax</a> algorithm. This finds the best possible score for a player, assuming that both players make the best moves for themselves.</p> <p>But there are some strange things in your code: too many score variables, unconditionally assigning to <code>maxScore</code> in the middle of the function (and thus losing its old value), and I don't see how the scores could ever receive a nonzero value.</p> <p>Here's I'd implement this in pseudocode. The function <code>getScore(graph)</code> will return the best possible score for the player whose turn it is (assuming both players play to maximize their own score), where "score" means that player's points minus the other player's points. I'm using the <a href="http://en.wikipedia.org/wiki/Negamax" rel="nofollow">Negamax</a> variant of minimax. This uses the fact that a score of +x for one player is the same as a score of -x for another to avoid having to write things twice. There's not even a need to keep track of whose turn it is because both players can make exactly the same moves.</p> <pre><code>int getScore(graph): if no possible moves: return 0 maxScore = -infinity for each possible move: make the move score = the score directly obtained by this move if the player gets another turn: score += getScore(graph) else: //opponent turn - subtract opponent's best score from player score score -= getScore(graph) maxScore = max(maxScore, score) undo the move return maxScore </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload