Non-terminating combinatorial games
up vote
1
down vote
favorite
The games I've come across thus far all have the property that their principal ideals are finite i.e the game terminates after finitely many moves so that the last position has the form {A|B} with (at least one of) A or B being empty.
How would one define "winning" in a game whose game tree has either an infinite principal ideal or, more generally, an infinite chain?
combinatorial-game-theory
asked Nov 22 at 14:32
Jean-Pierre de Villiers
415
|
show 2 more comments
up vote
1
down vote
favorite
The games I've come across thus far all have the property that their principal ideals are finite i.e the game terminates after finitely many moves so that the last position has the form {A|B} with (at least one of) A or B being empty.
How would one define "winning" in a game whose game tree has either an infinite principal ideal or, more generally, an infinite chain?
combinatorial-game-theory
asked Nov 22 at 14:32
Jean-Pierre de Villiers
415
1
Same way as for finite games. The only adjustment needed is that a game that never terminates is a tie.
– saulspatz
Nov 22 at 14:38
@saulspatz how would this then affect the theory? For example the result in Conway that states that each game G is exactly one of: positive, negative, zero or fuzzy.
– Jean-Pierre de Villiers
Nov 22 at 15:13
1
I don't really know. If I remember correctly, in "On Numbers and Games," Conway gives at least one example of a game that can last forever, but one of the players can force a win, so the infinite branch doesn't enter into the analysis in any essential way. The game is called "traffic Jams" or something similar, I believe.
– saulspatz
Nov 22 at 17:08
@saulspatz I see. Thanks I'll definitely have a look. The specific game I had in mind is the so-called infinite Ehrenfeucht-Fraïssé/Back-and-forth game (see Basic Model Theory pp. 44 ff.) used in the model theory of the infinitary logic $L_{inftyomega}$ (first-order logic enriched with conjunctions/disjunctions over arbitrarily many formulas) in which one of the two players is known to have a winning strategy.
– Jean-Pierre de Villiers
Nov 22 at 18:50
1
Your question is closely related to Is there a term to describe combinatorial games that don't necessarily end?, but it's a little different since you're not asking about terminology, but about win conditions.
– Mark S.
Nov 23 at 23:41
|
show 2 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
The games I've come across thus far all have the property that their principal ideals are finite i.e the game terminates after finitely many moves so that the last position has the form {A|B} with (at least one of) A or B being empty.
How would one define "winning" in a game whose game tree has either an infinite principal ideal or, more generally, an infinite chain?
combinatorial-game-theory
asked Nov 22 at 14:32
Jean-Pierre de Villiers
415
The games I've come across thus far all have the property that their principal ideals are finite i.e the game terminates after finitely many moves so that the last position has the form {A|B} with (at least one of) A or B being empty.
How would one define "winning" in a game whose game tree has either an infinite principal ideal or, more generally, an infinite chain?
combinatorial-game-theory
combinatorial-game-theory
asked Nov 22 at 14:32
Jean-Pierre de Villiers
415
asked Nov 22 at 14:32
Jean-Pierre de Villiers
415
asked Nov 22 at 14:32
Jean-Pierre de Villiers
415
asked Nov 22 at 14:32
Jean-Pierre de Villiers
415
asked Nov 22 at 14:32
Jean-Pierre de Villiers
415
415
1
Same way as for finite games. The only adjustment needed is that a game that never terminates is a tie.
– saulspatz
Nov 22 at 14:38
@saulspatz how would this then affect the theory? For example the result in Conway that states that each game G is exactly one of: positive, negative, zero or fuzzy.
– Jean-Pierre de Villiers
Nov 22 at 15:13
1
I don't really know. If I remember correctly, in "On Numbers and Games," Conway gives at least one example of a game that can last forever, but one of the players can force a win, so the infinite branch doesn't enter into the analysis in any essential way. The game is called "traffic Jams" or something similar, I believe.
– saulspatz
Nov 22 at 17:08
@saulspatz I see. Thanks I'll definitely have a look. The specific game I had in mind is the so-called infinite Ehrenfeucht-Fraïssé/Back-and-forth game (see Basic Model Theory pp. 44 ff.) used in the model theory of the infinitary logic $L_{inftyomega}$ (first-order logic enriched with conjunctions/disjunctions over arbitrarily many formulas) in which one of the two players is known to have a winning strategy.
– Jean-Pierre de Villiers
Nov 22 at 18:50
1
Your question is closely related to Is there a term to describe combinatorial games that don't necessarily end?, but it's a little different since you're not asking about terminology, but about win conditions.
– Mark S.
Nov 23 at 23:41
|
show 2 more comments
1
Same way as for finite games. The only adjustment needed is that a game that never terminates is a tie.
– saulspatz
Nov 22 at 14:38
@saulspatz how would this then affect the theory? For example the result in Conway that states that each game G is exactly one of: positive, negative, zero or fuzzy.
– Jean-Pierre de Villiers
Nov 22 at 15:13
1
I don't really know. If I remember correctly, in "On Numbers and Games," Conway gives at least one example of a game that can last forever, but one of the players can force a win, so the infinite branch doesn't enter into the analysis in any essential way. The game is called "traffic Jams" or something similar, I believe.
– saulspatz
Nov 22 at 17:08
@saulspatz I see. Thanks I'll definitely have a look. The specific game I had in mind is the so-called infinite Ehrenfeucht-Fraïssé/Back-and-forth game (see Basic Model Theory pp. 44 ff.) used in the model theory of the infinitary logic $L_{inftyomega}$ (first-order logic enriched with conjunctions/disjunctions over arbitrarily many formulas) in which one of the two players is known to have a winning strategy.
– Jean-Pierre de Villiers
Nov 22 at 18:50
1
Your question is closely related to Is there a term to describe combinatorial games that don't necessarily end?, but it's a little different since you're not asking about terminology, but about win conditions.
– Mark S.
Nov 23 at 23:41
1
1
Same way as for finite games. The only adjustment needed is that a game that never terminates is a tie.
– saulspatz
Nov 22 at 14:38
Same way as for finite games. The only adjustment needed is that a game that never terminates is a tie.
– saulspatz
Nov 22 at 14:38
@saulspatz how would this then affect the theory? For example the result in Conway that states that each game G is exactly one of: positive, negative, zero or fuzzy.
– Jean-Pierre de Villiers
Nov 22 at 15:13
@saulspatz how would this then affect the theory? For example the result in Conway that states that each game G is exactly one of: positive, negative, zero or fuzzy.
– Jean-Pierre de Villiers
Nov 22 at 15:13
1
1
I don't really know. If I remember correctly, in "On Numbers and Games," Conway gives at least one example of a game that can last forever, but one of the players can force a win, so the infinite branch doesn't enter into the analysis in any essential way. The game is called "traffic Jams" or something similar, I believe.
– saulspatz
Nov 22 at 17:08
I don't really know. If I remember correctly, in "On Numbers and Games," Conway gives at least one example of a game that can last forever, but one of the players can force a win, so the infinite branch doesn't enter into the analysis in any essential way. The game is called "traffic Jams" or something similar, I believe.
– saulspatz
Nov 22 at 17:08
@saulspatz I see. Thanks I'll definitely have a look. The specific game I had in mind is the so-called infinite Ehrenfeucht-Fraïssé/Back-and-forth game (see Basic Model Theory pp. 44 ff.) used in the model theory of the infinitary logic $L_{inftyomega}$ (first-order logic enriched with conjunctions/disjunctions over arbitrarily many formulas) in which one of the two players is known to have a winning strategy.
– Jean-Pierre de Villiers
Nov 22 at 18:50
@saulspatz I see. Thanks I'll definitely have a look. The specific game I had in mind is the so-called infinite Ehrenfeucht-Fraïssé/Back-and-forth game (see Basic Model Theory pp. 44 ff.) used in the model theory of the infinitary logic $L_{inftyomega}$ (first-order logic enriched with conjunctions/disjunctions over arbitrarily many formulas) in which one of the two players is known to have a winning strategy.
– Jean-Pierre de Villiers
Nov 22 at 18:50
1
1
Your question is closely related to Is there a term to describe combinatorial games that don't necessarily end?, but it's a little different since you're not asking about terminology, but about win conditions.
– Mark S.
Nov 23 at 23:41
Your question is closely related to Is there a term to describe combinatorial games that don't necessarily end?, but it's a little different since you're not asking about terminology, but about win conditions.
– Mark S.
Nov 23 at 23:41
|
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
There are two common approaches in the sphere of Combinatorial Game Theory.
One approach is to declare that if a game goes on forever, it is a draw. Instead of four outcomes like "positive, negative, zero, or fuzzy", there are now nine: If Left goes first, they can either guarantee a win in finite time, or Right can, or both can at best guarantee a draw. Similarly if Right moves first, for a total of $3*3=9$ outcomes. An online resource discussing the main points in this theory of "loopy" games is Coping with cycles by Aaron N. Siegel. Most (all?) of that material and more can be found in Chapter VI of Siegel's Combinatorial Game Theory.
Another approach is to grant infinite play as a win to one player. This is done in John H. Conway's Angel Problem, and it appears this (or something very similar) is also the convention in the "infinite Ehrenfeucht-Fraïssé/Back-and-forth game" you mentioned in a comment.
answered Nov 23 at 23:52
Mark S.
11.4k22568
add a comment |
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',
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%2f3009208%2fnon-terminating-combinatorial-games%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
There are two common approaches in the sphere of Combinatorial Game Theory.
One approach is to declare that if a game goes on forever, it is a draw. Instead of four outcomes like "positive, negative, zero, or fuzzy", there are now nine: If Left goes first, they can either guarantee a win in finite time, or Right can, or both can at best guarantee a draw. Similarly if Right moves first, for a total of $3*3=9$ outcomes. An online resource discussing the main points in this theory of "loopy" games is Coping with cycles by Aaron N. Siegel. Most (all?) of that material and more can be found in Chapter VI of Siegel's Combinatorial Game Theory.
Another approach is to grant infinite play as a win to one player. This is done in John H. Conway's Angel Problem, and it appears this (or something very similar) is also the convention in the "infinite Ehrenfeucht-Fraïssé/Back-and-forth game" you mentioned in a comment.
answered Nov 23 at 23:52
Mark S.
11.4k22568
add a comment |
up vote
1
down vote
accepted
There are two common approaches in the sphere of Combinatorial Game Theory.
One approach is to declare that if a game goes on forever, it is a draw. Instead of four outcomes like "positive, negative, zero, or fuzzy", there are now nine: If Left goes first, they can either guarantee a win in finite time, or Right can, or both can at best guarantee a draw. Similarly if Right moves first, for a total of $3*3=9$ outcomes. An online resource discussing the main points in this theory of "loopy" games is Coping with cycles by Aaron N. Siegel. Most (all?) of that material and more can be found in Chapter VI of Siegel's Combinatorial Game Theory.
Another approach is to grant infinite play as a win to one player. This is done in John H. Conway's Angel Problem, and it appears this (or something very similar) is also the convention in the "infinite Ehrenfeucht-Fraïssé/Back-and-forth game" you mentioned in a comment.
answered Nov 23 at 23:52
Mark S.
11.4k22568
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
There are two common approaches in the sphere of Combinatorial Game Theory.
One approach is to declare that if a game goes on forever, it is a draw. Instead of four outcomes like "positive, negative, zero, or fuzzy", there are now nine: If Left goes first, they can either guarantee a win in finite time, or Right can, or both can at best guarantee a draw. Similarly if Right moves first, for a total of $3*3=9$ outcomes. An online resource discussing the main points in this theory of "loopy" games is Coping with cycles by Aaron N. Siegel. Most (all?) of that material and more can be found in Chapter VI of Siegel's Combinatorial Game Theory.
Another approach is to grant infinite play as a win to one player. This is done in John H. Conway's Angel Problem, and it appears this (or something very similar) is also the convention in the "infinite Ehrenfeucht-Fraïssé/Back-and-forth game" you mentioned in a comment.
answered Nov 23 at 23:52
Mark S.
11.4k22568
There are two common approaches in the sphere of Combinatorial Game Theory.
One approach is to declare that if a game goes on forever, it is a draw. Instead of four outcomes like "positive, negative, zero, or fuzzy", there are now nine: If Left goes first, they can either guarantee a win in finite time, or Right can, or both can at best guarantee a draw. Similarly if Right moves first, for a total of $3*3=9$ outcomes. An online resource discussing the main points in this theory of "loopy" games is Coping with cycles by Aaron N. Siegel. Most (all?) of that material and more can be found in Chapter VI of Siegel's Combinatorial Game Theory.
Another approach is to grant infinite play as a win to one player. This is done in John H. Conway's Angel Problem, and it appears this (or something very similar) is also the convention in the "infinite Ehrenfeucht-Fraïssé/Back-and-forth game" you mentioned in a comment.
answered Nov 23 at 23:52
Mark S.
11.4k22568
answered Nov 23 at 23:52
Mark S.
11.4k22568
answered Nov 23 at 23:52
Mark S.
11.4k22568
answered Nov 23 at 23:52
Mark S.
11.4k22568
11.4k22568
add a comment |
add a comment |
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%2f3009208%2fnon-terminating-combinatorial-games%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
1
Same way as for finite games. The only adjustment needed is that a game that never terminates is a tie.
– saulspatz
Nov 22 at 14:38
@saulspatz how would this then affect the theory? For example the result in Conway that states that each game G is exactly one of: positive, negative, zero or fuzzy.
– Jean-Pierre de Villiers
Nov 22 at 15:13
1
I don't really know. If I remember correctly, in "On Numbers and Games," Conway gives at least one example of a game that can last forever, but one of the players can force a win, so the infinite branch doesn't enter into the analysis in any essential way. The game is called "traffic Jams" or something similar, I believe.
– saulspatz
Nov 22 at 17:08
@saulspatz I see. Thanks I'll definitely have a look. The specific game I had in mind is the so-called infinite Ehrenfeucht-Fraïssé/Back-and-forth game (see Basic Model Theory pp. 44 ff.) used in the model theory of the infinitary logic $L_{inftyomega}$ (first-order logic enriched with conjunctions/disjunctions over arbitrarily many formulas) in which one of the two players is known to have a winning strategy.
– Jean-Pierre de Villiers
Nov 22 at 18:50
1
Your question is closely related to Is there a term to describe combinatorial games that don't necessarily end?, but it's a little different since you're not asking about terminology, but about win conditions.
– Mark S.
Nov 23 at 23:41