chance tree versus game tree Einstein forum
5 replies. Last post: 20120824
Reply to this topic Return to forum
Hjallti at 20120823
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
OOOOOwhere 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 playerquestion 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 playerquestion 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 20120823
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 decisionmaking. 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 20120823
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(XR)] 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 XR, 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 16, in Q1 you can consider the two cases 13 and 46 (and by symmetry you can prune half the tree), and in Q2 you can consider the two cases 15 and 6. In Q3 you must consider three cases 1, 25, 6, and there is a choice to be made if the roll is 25.

Hjallti at 20120824
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 20120824
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 XYplayers 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.