ConwayLife.com

after posting this, I have a compelling desire to play a "game" of TREE(3) with someone.
symbols:
1: () -- parentheses
2: [] --brackets
3: {} --braces

an example game:
P1: ()
P2: []
P1: {{}}
P2: {}
P1 wins as they have no legal moves.

note that if () and [] have been played but not {{}} or {} you should play {{}}, forcing the other player to play {}.

In this example, P2 made a mistake. by playing [] instead of [{}], {[]}, or [[]] he sentenced himself to losing as it gave P1 the winning strategy above.

Another winning strategy is to play [] after () and {{}} have been played as it forces the opponent to play {} and lose.
or {} after () and [[]] have been played to force the other player to play []. This means that if P1 plays (), your only options are to play [{}] or {[]}.

so here's a better game.

P1: ()
P2: [{}]
P1: {[]}
P2: [[]]
P1: [] <-fatal blunder
P2: {{}}
P1: {}

NEVER EVER make that mistake. If you play [] after () has been played, but not {{}}, your opponent wins by playing {{}} and forcing you to play {}, leaving them with no legal moves.


Note that any game is equivalent -- has the same outcome -- if you swap a pair or parentheses/brackets/braces (how about we call they openy-closies).

for instance, swapping brackets with braces, you get:
P1: ()
P2: {[]}
P1: [{}]
P2: {{}}
P1: {} <- fatal blunder
P2: [[]]
P1: []

this is because our symbols are rather arbitrary. you could use fore/backslashes -- /\ -- as well (anyone up for a game of TREEgame(4)?)
or angle brackets: <>
we have at least five symbols on the qwerty keyboard, so we can play TREEgame(5):

1: () -- parentheses
2: [] --brackets
3: {} --braces
4: /\ -- slashes
5: <> -- angle brackets

Of course, playing these games won’t give TREE(n) -- after all, we’re not trying to optimize the length of the game but rather are trying to make the parity of the length of the game even for one player and odd for the other.

EDIT:
In fakeTREE, playing [{()}] after [()] is legal— it’s not in actual tree but it makes the game more fun.

{}

A bold first move; how will his/her opponent react?
(Also, isn't it that you lose if you have to make a tree that (homeomorphically) contains another, rather than winning?)

toroidalet wrote: (Also, isn't it that you lose if you have to make a tree that (homeomorphically) contains another, rather than winning?)

I fee the winner is whoever has no legal moves (but you can’t just make a tree that contains another, because you might have legal moves). Otherwise you would win just by playing () after [] and {} have been played, which seems easier.

It’s like miser chess this way.

toroidalet wrote:{}

A bold first move; how will his/her opponent react?

I love it!
Clearly I must do this
Toroidalet: {}
Moosey: ([])

Of course, we can do this with more players.

And while we're playing a game of TREEgame(3), I'll open fakeTREEgame(4)

<>

Hmm, only 2 players are allowed for the game, so I'll have to do something in TREEgame(4).
Moosey: <>
PkmnQ: [{}]
I think I'm playing it a little bit too safe here. What are legal moves?

PkmnQ wrote:Hmm, only 2 players are allowed for the game, so I'll have to do something in TREEgame(4).
Moosey: <>
PkmnQ: [{}]
I think I'm playing it a little bit too safe here. What are legal moves?

You have legal moves as long as:
Your tree does not contain any past tree
Your tree has at most n nodes, where n is the turn.

Moosey: <>
PkmnQ: [{}]
Moosey:[({})]
You might want to read calcyman’s blog post about it.

Moosey: <>
PkmnQ: [{}]
Moosey: [({})]
PkmnQ: ([])

Moosey: <>
PkmnQ: [{}]
Moosey: [({})]
PkmnQ: ([])
Moosey: []


I have a poor concept of how to play this, given that this is probably the first time ever that this game has been played between two real people. I think nobody yet has a good strategy beyond the first three moves, if even that. I think I have a basic strategy for starting TREEgame(3) but nothing else.

I believe Moosey's second move is illegal because you can contract the () node to get PkmnQ's move.

fluffykitty wrote:I believe Moosey's second move is illegal because you can contract the () node to get PkmnQ's move.

Not, because my move was
2->1->3 which I believe does not contain 2->3 (cuz there’s a 1 in between)
I think I need apg to clarify to me because no doubt he knows better

Contracting a node with one child is one of the actions you can do for homeomorphic embedding (see the example in the blog post)

Okay, let’s rename my version “faketree” —It’s less of a hassle and might be more fun anyways.

If you're deviating from the blog post's rules, you need to specify exactly what the rules are.
Also, while we're waiting for the players to play, how about people try to make long TREE(3) sequences? I'll submit {},(),[],empty to get things started.

fluffykitty wrote:Also, while we're waiting for the players to play, how about people try to make long TREE(3) sequences? I'll submit {},(),[],empty to get things started.

Is there anything wrong with this?

That seems to work

Moosey: <>
PkmnQ: [{}]
Moosey: [({})]
PkmnQ: ([])
Moosey: []
PkmnQ: {()[()]}

Someone might as well start a game of actual TREE(4).
And also, was my move even allowed?
Edit: Neglected my own move.

No, again because of your first move.

New game, anyone?
[]

fluffykitty wrote:If you're deviating from the blog post's rules, you need to specify exactly what the rules are.
Also, while we're waiting for the players to play, how about people try to make long TREE(3) sequences? I'll submit {},(),[],empty to get things started.

Difference 1:
[{()}] does not contain [()] like it would usually (more possibilities)
I believe this is Difference 2:
[()] does not contain ([])

hdjen wrote:New game, anyone?
[]

What rules apply to this one?
Presumably no “Moosey instantly wins”

({})

A continuation of the TREE(3) game:

toroidalet wrote:A continuation of the TREE(3) game:

Code: Select all

{},
([]), and now
[[()]]

I’d be glad to let someone else play for me.

Moosey wrote:
What rules apply to this one?
Presumably no “Moosey instantly wins”

({})

(())

Shouldn't the player with no legal moves be the loser? That's how it is in the original article, anyway. Otherwise, there are only a few ways the game can play out. For TREE(3), there's a fairly simple winning (losing?) strategy for P1:

P1 plays (). P2 then has a choice:

• []: P1 plays {{}}, P2 must play {}, P1 wins.
• [[]]: P1 plays {}, P2 must play [], P1 wins.
• {}: P1 plays [[]], P2 must play [], P1 wins.
• {{}}: P1 plays [], P2 must play {}, P1 wins.
• [{}]: P1 should then play {[]}. P2 will have to play repeating {{...}} or [[...]] (up to 4 deep), P1 should respond with the same number of [[...]] or {{...}}. If P2 plays [[]], {{}}, [], or {}, P1 should respond as above.

I'll write a small Javascript applet that can validate TREE(k) games, to make analyzing these a little easier.

ishanpm wrote:Shouldn't the player with no legal moves be the loser? That's how it is in the original article, anyway. Otherwise, there are only a few ways the game can play out. For TREE(3), there's a fairly simple winning (losing?) strategy for P1:

P1 plays (). P2 then has a choice:

• []: P1 plays {{}}, P2 must play {}, P1 wins.
• [[]]: P1 plays {}, P2 must play [], P1 wins.
• {}: P1 plays [[]], P2 must play [], P1 wins.
• {{}}: P1 plays [], P2 must play {}, P1 wins.
• [{}]: P1 should then play {[]}. P2 will have to play repeating {{...}} or [[...]] (up to 4 deep), P1 should respond with the same number of [[...]] or <<...>>. If P2 plays [[]], {{}}, [], or {}, P1 should respond as above.

I'll write a small Javascript applet that can validate TREE(k) games, to make analyzing these a little easier.

Well, I personally like it the misère way, though we can obviously play both kinds here, just like with the fakeTREE vs the purists’ actual TREE.

As per your list of permitted moves, excellent! It proves P1 can win the purist way (of the misère game) all the time (making the fake way a bit more fun).

Likewise with the JavaScript applet Idea.

Tree game validator! Let me know if you see any bugs.

Doesn't support fakeTREE at the moment. Later, I'll add a feature to list legal moves.

https://jsfiddle.net/ishanpm/s45w7ouj/

ishanpm wrote:Tree game validator! Let me know if you see any bugs.

Doesn't support fakeTREE at the moment. Later, I'll add a feature to list legal moves.

https://jsfiddle.net/ishanpm/s45w7ouj/

I was gonna say,
“Nice”
A while ago but felt that was unproductive.
But, I still provide my complements.
Perhaps you could have a basic strategy guide as some output.
Also, not to @ishanpm specifically,
Would anyone be able to explain how the weak tree function (tree(n)) works? Has nobody calculated tree(3) yet? Wikipedia’s lower bound (tree(3) > 262140) seems ridiculously low— it should be possible to calculate (based on my poor knowledge) with a upper bound, using trial and error (can I play a longer game than x) though I suppose it wouldn’t be super super easy to do— but finding a number with a lower bound that’s less than a million and probably an upper bound (just by that we probably don’t have one that’s more than a few orders of magnitude larger) that’s likely less than (10-100?) million seems easier than finding those huge primes that people find, mersenne or not.

Finally, a question:
Would it be possible to approximate a value of TREE(n) for any positive n which is not an integer? Obviously, TREE(n) is undefined for all non-[positive integer] numbers, but could we somehow approximate it. Since it always grows, we know that 1<“approxTREE(1.5)”<3 since TREE(1) is 1 and TREE(2) is 3.
Obviously, given the fact that TREE(n) grows very fast for n>2, approxTREE(1.5) is probably closer to 1 than 3, so I think that, most likely, 1<approxTREE(1.5)<2. (Actually, this depends on the exact behavior of approx TREE(n). If it’s a bit like an exponential function at the start then approxTREE(1.5) is about 1, while if it’s more like a linear function then it’s about 2.)

Another nice thing is that we can also make bounds on approxTREE’(n) increases, for n>=2.
We know it’s less than approxTREE(n+1), for larger n. This can be proven this way:
If TREE(n) is a negligible compared to TREE(n+1), (which it is for integer n>1) the average rate of change over 1 unit is about ((TREE(n+1)-0)/1, or just about TREE(n+1). I’m just doing more or less what newton did when he did his calculus—getting rid of the stuff that’s practically zero. Now, since approxTREE’’(n)>0 for all n>0, we know that TREE’(n) < the average rate of change over n, n+1. Plug in TREE(n+1) = about the avg rate of change over [n,n+1] and you get your proof:
TREE’(n) < TREE(n+1) for integer n >1. Since approxTREE(n) should behave more or less the same (the only difference being that it’s defined for nonintegers too) as TREE(n), (drumroll please)
approxTREE’(n) < approxTREE(n+1) for n ≥ 2.



I guess if this hasn’t been discovered yet it will be called Moosey’s theorem. It almost certainly has though— please tell me what it’s called.

In more general terms, what it states is that if f(x) is a twice differentiable really fast-growing function over [n,n+1] (i.e. f(n)/f(n+1) is practically 0), f’(n) < f(n+1) given f’’(x) > 1 over [n,n+1]