### chance tree versus game tree Einstein forum

5 replies. Last post: 2012-08-24

chance tree versus game tree
• Hjallti at 2012-08-23

For my exam last year I used EWN.
My main question here in the forum is "what is the (most) correct way to formulate the answer to question 5?"
You may wander which student had to answer this. Take a guess.

The exam question was (boring) situation with the next board

OOXOO
OOOOO
YOOOA
OOOOO
OOOOO

where X and Y are stones that move to the upper left and A to be the single stone to lower right (O are empty spaces)

X,Y player has the next turn

question 1: suppose X=3 and Y=4 and A=5, give the chance tree for this game
question 2: calculate the win chance for the XY player

question 3: suppose X=5 and Y=6 and A=3 give the chance tree for this game
question 4: calculate the win chance for the XY player

question 5: suppose X=1 and Y=6 and A=2. I can’t ask for the chance tree for this game. Why?
question 6: calculate the win chance for the XY player (if he tries his best to win)

• MarleysGhost at 2012-08-23

s/wander/wonder/

While of course question 5 is impossible to answer without a definition of the term “chance tree”, a term I have not run across before, I will hazard that in the definition you gave the students a chance tree has to depend only on chance, not on human decision-making. If so, then since the XY player can decide on an arbitrary basis which stone to move on a roll of 2, 3, 4 or 5, the outcome of the game does not depend on just chance.

Q. 2: 1/2
Q. 4: 13/18
Q. 6: 5/6 for perfect play (or any probability in the range 1/6..5/6 if the player makes arbitrary decisions)

• Tommah at 2012-08-23

Question 5 must have an answer. These questions are like the problem of calculating the equity of a position in backgammon. IIUC the equations are like this. (Hjallti must know this already, so this is more of a public service announcement.) Let X be a position, and let R be a roll of the dice. Then we can define the conditional equity of X based on dice roll R as

equity(X | R) = 1 – min {equity(Y1), equity(Y2), ..., equity(Yn)}

where Y1 ... Yn are the positions that can be obtained from using the roll R in position X. IOW you leave your opponent with the position that gives him the lowest equity (from his perspective). Then the equity of X is given by the expected value:

equity(X) = E[equity(X|R)] where the roll R is the running variable.

So in the tree, some nodes will be negamax nodes (just as ALL the nodes are in deterministic games), and some nodes will be averaging nodes. The node for position X is an averaging node. But once you roll the dice and get roll R, you are at the node for X|R, and this is a negamax node. Each negamax node obtains its value from one of its children (the value is then negated), and this tells you the best move.

Is this what you meant by chance tree? Your examples are really simple (they would have to be, to be drawable by hand on an exam) since each stone only has one possible move, and player A has no die roll. In your first two cases you can cheat a little; instead of considering all the rolls 1-6, in Q1 you can consider the two cases 1-3 and 4-6 (and by symmetry you can prune half the tree), and in Q2 you can consider the two cases 1-5 and 6. In Q3 you must consider three cases 1, 2-5, 6, and there is a choice to be made if the roll is 2-5.

• Hjallti at 2012-08-24

The last sentence I am not sure. it seems to depend on the word “must”. For a player/analyst in that particular situation it is enough only to consider two situations given by the next positions. If he moves the 1 it doesn’t matter what the roll was. But of course for the tree it does matter.

• Hjallti at 2012-08-24

By the way I suppose a game tree to have from each nodes branches that have numbers that are between 0 and 1 (including 0 and 1) and have sum 1.

equities for XY-players second move from here are 5/6 (in both cases), so 1/6 for the other player a move earlier and so again 5/6 for the first moves... giving a tree with a node of 10/6.

I actually hoped the students that understood 5 would solve 6 with common sense but half of them did try to use the chance tree after all.