3 ms·
There is a simpler way to handle loops. If you end up repeating a position, you know the turn player will repeat the same move as before. By iterating over ever
by malisper 2y ago
There is a simpler way to handle loops. If you end up repeating a position, you know the turn player will repeat the same move as before. By iterating over every possible move and every possible response, you can calculate the expected value of a position. Writing out the equations where V(s, i, j) is the expected value of the position when turn player will attempt move i and the opposing player will attempt move j:
V(s) = max i (min j V(s, i, j))
V(s, i, j) = (probability move i or move j changes the state) * V(new state) + (probability state doesn't change) * V(s, i, j)
You can solve the second equation for all i and j and then use that to solve the first equation.
- Labo333 2y agoAuthor here! I'm not sure about the first part V(s) = max i (min j V(s, i, j)) It looks like you suppose that j "precommits" to some move. But I'm not fully awake yet so you could be right.
- orlp 2y agoYour equation fails to take into account what the original article (before I notified the author, who kindly responded and shouted out my blog without even asking for it) also failed to take into account. When the dice rolls ":|" and you pass your turn, the state does change. Namely, whose turn it is changes. V(s, i, j) fails to capture this crucial detail.
- malisper 2y agoThis is accounted for because the second equation looks at sequences of two moves and not just one. After a sequence of two moves there are two possibilities. Either the state has changed or it has not. This is reflected in the left and right side of the second equation.