Ytukyg

I have a task to represent game using extensive form. I know how to work with extensive form in general, but I have problem how to represent this type of the game.

Rules: (Player 1 = P1, Player 2 = P2, game is zero sum)

1. S means start position, D means end position.


2. E means dangerous place, where bandit (owned by P2) can be. There is 1 bandit in the game and when met it has P(0.7) to kill P1.


3. We can step on each free space (represented
   by '-') only once.


4. Our task, get to D (utility 10 if successfull)
   and if possible pick up gold on G which provides extra +1 utility.


5. When we step on first E in the game and it happens to be empty, bandit can relocate.


6. '#' is obstacle.

Map representation:

#######

#E---E#

#S#-#D#

#E--EG#

#######

My idea was, P2 will place bandit on either E on [2,2] or [2,4] since P1 has to go through one of those spots first. Then it can happen:

• Bandit gets into conflict and has P(0.7) to kill P1 which will resolve into
  game value of 0.


• Bandit will be on the other E and therefore it will relocate to either [6,2] or [5,4].

Then agent can go either through [6,2] or [5,4] because there is free space in middle through which it can traverse to upper/lower part of the map. P2 is motivated slightly more to defend [5,4] than [6,2].

I calculated that there are basically five outcomes of the whole game:

1. P1 gets caught on the first pair of E's and dies. u=0; P(14/40)


2. P1 gets caught on the first pair of E's and survives, therefore can go for gold and to 'D' without worrying about bandit. u=11; P(6/40)


3. P1 does not get caught on first pair of E's but gets caught on second and dies. u = 0; P(7/40)


4. P1 does not get caught on first pair of E's but gets caught on second and survives. u=10/11 (depends on chosen path); P(3/40)


5. P1 does not get caught on second pair either. u = 10/11; P(10/40)

I also figured value of the game because we know that P2 decision between E tiles in second selection is based on P1 possible utility of the game being either 10 or 11. So we can calculate the utility so we know that P2 will guard E[5,4] with P(0,523...) and E[6,2] with P(0,476...). Therefore we can calculate that value for those cases (u=10/11) which is roughly 10,476... Than we can apply it to probabilites of outcomes and we get final value of game 5.05...

Questions:

1. Is this the right way how to abstract this game?


2. How would the extensive form representation look like?


3. [optionally if anyone would knew] How to formalize this as linear problem/program so we can compute value of the game from either max for P1 or min for P2?

Thanks for any ideas/answers in advance