Representing game with map through Extensive Form
up vote
0
down vote
favorite
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)
- S means start position, D means end position.
- 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.
- We can step on each free space (represented
by '-') only once. - Our task, get to D (utility 10 if successfull)
and if possible pick up gold on G which provides extra +1 utility. - When we step on first E in the game and it happens to be empty, bandit can relocate.
- '#' 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:
- P1 gets caught on the first pair of E's and dies. u=0; P(14/40)
- 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)
- P1 does not get caught on first pair of E's but gets caught on second and dies. u = 0; P(7/40)
- 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)
- 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:
- Is this the right way how to abstract this game?
- How would the extensive form representation look like?
- [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
linear-programming game-theory
add a comment |
up vote
0
down vote
favorite
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)
- S means start position, D means end position.
- 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.
- We can step on each free space (represented
by '-') only once. - Our task, get to D (utility 10 if successfull)
and if possible pick up gold on G which provides extra +1 utility. - When we step on first E in the game and it happens to be empty, bandit can relocate.
- '#' 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:
- P1 gets caught on the first pair of E's and dies. u=0; P(14/40)
- 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)
- P1 does not get caught on first pair of E's but gets caught on second and dies. u = 0; P(7/40)
- 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)
- 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:
- Is this the right way how to abstract this game?
- How would the extensive form representation look like?
- [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
linear-programming game-theory
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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)
- S means start position, D means end position.
- 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.
- We can step on each free space (represented
by '-') only once. - Our task, get to D (utility 10 if successfull)
and if possible pick up gold on G which provides extra +1 utility. - When we step on first E in the game and it happens to be empty, bandit can relocate.
- '#' 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:
- P1 gets caught on the first pair of E's and dies. u=0; P(14/40)
- 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)
- P1 does not get caught on first pair of E's but gets caught on second and dies. u = 0; P(7/40)
- 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)
- 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:
- Is this the right way how to abstract this game?
- How would the extensive form representation look like?
- [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
linear-programming game-theory
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)
- S means start position, D means end position.
- 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.
- We can step on each free space (represented
by '-') only once. - Our task, get to D (utility 10 if successfull)
and if possible pick up gold on G which provides extra +1 utility. - When we step on first E in the game and it happens to be empty, bandit can relocate.
- '#' 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:
- P1 gets caught on the first pair of E's and dies. u=0; P(14/40)
- 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)
- P1 does not get caught on first pair of E's but gets caught on second and dies. u = 0; P(7/40)
- 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)
- 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:
- Is this the right way how to abstract this game?
- How would the extensive form representation look like?
- [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
linear-programming game-theory
linear-programming game-theory
edited Nov 23 at 11:48
asked Nov 23 at 11:28
eXPRESS
13
13
add a comment |
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3010251%2frepresenting-game-with-map-through-extensive-form%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3010251%2frepresenting-game-with-map-through-extensive-form%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown