4
$\begingroup$

I have a task on my class to find all the nodes, calculate their values and choose the best way for the player on the given game graph:

enter image description here

Everything is fine, but I have no idea what these dots are. Is this a third player, or just a 'split' for player1 move? Some kind of heuristics?

$\endgroup$
4
$\begingroup$

The triangles pointing up are Max' nodes. We assume it starts. Then follows a random choice of moves at the circles, for instance, with a die. The triangles pointing down are from Min. This variant is called Expectiminimax, see https://en.wikipedia.org/wiki/Expectiminimax_tree.

At that circles you have to multiply the possibilities on the edges below that nodes to your current value and sum all products up. The circles in your picture mean that Min dices.

| improve this answer | |
$\endgroup$
  • $\begingroup$ If that is the case, it seems like a trivial question. Why bother to calculate the probabilities when the left branch has every possible positive outcome for the Max player? The right branch is at best a zero for the Max player. $\endgroup$ – Jnani Jenny Hale Feb 1 '17 at 7:37
  • $\begingroup$ I improved my answer a little bit. In the right chance node you would get 0*0.5+-1*0.5 which is -0.5 for Min here. $\endgroup$ – marli Feb 1 '17 at 7:53
  • $\begingroup$ You mean, it will be -0.5 on the right node, 1 on the second from the right and then we choose a MIN from them both, right? $\endgroup$ – Jacob Feb 1 '17 at 9:07
  • $\begingroup$ No, I mean that on the right of the tree Min chooses 0 instead of 2 left and right it chooses -1 instead of 0. Then we multiply both with 0.5 and get the sum of -0.5. Which is the value what Min delivers to Max. This models that Min chooses the minimal values (the leafs) and then has a chance of 50 % to choose between the two possible moves with the value 0 and -1 respectively. $\endgroup$ – marli Feb 1 '17 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.