3
$\begingroup$

In combinatorial game theory: The birthday of a game is defined recursively as 1 plus the maximal birthday of its options, with the zero game having birthday 0.

Suppose we define the quasi-birthday of a game to be 1 + the minimal birthday of its options, with the zero game having birthday 0. Is anything known about this concept with respect to impartial combinatorial games? Are there any references available?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Any game is "equivalent" to a game with quasi-birthday 2, just by modifying the rules to allow either player to resign on their moves. (Of course, this depends on what we mean by "equivalent," but I think this is an obstacle to quasi-birthdays being very useful.) $\endgroup$
    – Noah Schweber
    Commented Oct 2, 2015 at 2:42

1 Answer 1

Reset to default
3
$\begingroup$

Since your definition of birthday just said "1+…", I assume you're not talking about transfinite games. In this context, the birthday is the longest a game could go on (in number of moves), and the quasi-birthday is the shortest a game could go on.

It's notationally convenient to treat a short impartial game as the set of its options. Here are some basic facts: The quasi-birthday is $1$ exactly when there's a move to {}. The quasi-birthday of any game with {{}} or {{},{{}}} as an option but not {} is $2$. The quasi-birthday of {{{{}}}} is $3$, and the only games with birthday equal to quasi-birthday must look like that.

The concept of birthday is useful for giving bounds on things in a variety of theorems and proofs. One example is the theorem that if a short partizan game $G$ has finite order and birthday $n$, then $2^n\cdot G=0$. Another example is Mesdal and Ottaway's original proof that in the partizan misère context, $0$ is not equal to any other game. If $H$ is a game, then their witness to the fact that $H\ne0$ is a game $G$ where $G^{RR}$ is $n$ consecutive moves for Left, where $n$ is one more than the birthday of $H$. That way they can use the fact that $H$ will be exhausted of moves before Left can be done moving in $G$. (See "Simplification of Partizan Games in Misère Play" at http://www.integers-ejcnt.org/vol7.html )

I do not recall seeing any argument that used the shortest line of play, as in your quasi-birthday idea, and suspect that it is not very helpful when considering disjunctive sums. As Noah Schweber seemed to be getting at, a consequence of the Sprague-Grundy theory is that every impartial game is equal under normal play to a game of quasi-birthday $0$ or $1$. But perhaps with one of the other, more rarely considered, combinations other than disjunctive sum, it could be helpful.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .