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?










share|cite|improve this question


















  • 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















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?










share|cite|improve this question


















  • 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













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?










share|cite|improve this question













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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Nov 22 at 14:32









Jean-Pierre de Villiers

435




435








  • 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




    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










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.






share|cite|improve this answer





















    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
    });


    }
    });














    draft saved

    draft discarded


















    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.






    share|cite|improve this answer

























      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.






      share|cite|improve this answer























        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.






        share|cite|improve this answer












        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.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Nov 23 at 23:52









        Mark S.

        11.4k22568




        11.4k22568






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            Wiesbaden

            Marschland

            Dieringhausen