[GAME] TREE function games

A forum where anything goes. Introduce yourselves to other members of the forums, discuss how your name evolves when written out in the Game of Life, or just tell us how you found it. This is the forum for "non-academic" content.
Post Reply
User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

[GAME] TREE function games

Post by Moosey » April 9th, 2019, 5:41 pm

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.
Last edited by Moosey on April 10th, 2019, 7:13 pm, edited 2 times in total.
not active here but active on discord

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: [GAME] TREE function games

Post by toroidalet » April 9th, 2019, 6:17 pm

{}

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?)
Any sufficiently advanced software is indistinguishable from malice.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » April 9th, 2019, 6:43 pm

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)

<>
Last edited by Moosey on April 10th, 2019, 7:13 pm, edited 1 time in total.
not active here but active on discord

User avatar
PkmnQ
Posts: 1137
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: [GAME] TREE function games

Post by PkmnQ » April 10th, 2019, 8:21 am

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?

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » April 10th, 2019, 9:13 am

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.
Last edited by Moosey on April 10th, 2019, 7:10 pm, edited 2 times in total.
not active here but active on discord

User avatar
PkmnQ
Posts: 1137
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: [GAME] TREE function games

Post by PkmnQ » April 10th, 2019, 9:21 am

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

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » April 10th, 2019, 11:18 am

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.
not active here but active on discord

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: [GAME] TREE function games

Post by fluffykitty » April 10th, 2019, 1:44 pm

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

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » April 10th, 2019, 2:30 pm

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
not active here but active on discord

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: [GAME] TREE function games

Post by fluffykitty » April 10th, 2019, 3:33 pm

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

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » April 10th, 2019, 7:11 pm

:oops: :oops: :oops: :oops: Okay, let’s rename my version “faketree” —It’s less of a hassle and might be more fun anyways.
not active here but active on discord

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: [GAME] TREE function games

Post by fluffykitty » April 10th, 2019, 8:40 pm

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.

User avatar
BlinkerSpawn
Posts: 1992
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: [GAME] TREE function games

Post by BlinkerSpawn » April 10th, 2019, 10:25 pm

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?

Code: Select all

{}
([])
[[][]]
[[[[]]]]
[[[(())]]]
[[[()()()]]]
[[[()()](())]]
[[[()()]()()()]]
[[[()()]()()](())]
[[[()()]()()]()()()]
[[[()()]()()]()()]
[[[()()]()()]()]
[[[()()]()]((((((()))))))]
Last edited by BlinkerSpawn on April 10th, 2019, 10:34 pm, edited 2 times in total.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: [GAME] TREE function games

Post by fluffykitty » April 10th, 2019, 10:29 pm

That seems to work

User avatar
PkmnQ
Posts: 1137
Joined: September 24th, 2018, 6:35 am
Location: Server antipode

Re: [GAME] TREE function games

Post by PkmnQ » April 10th, 2019, 10:55 pm

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.
Last edited by PkmnQ on April 11th, 2019, 6:25 am, edited 1 time in total.

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: [GAME] TREE function games

Post by fluffykitty » April 10th, 2019, 11:04 pm

No, again because of your first move.

User avatar
Hdjensofjfnen
Posts: 1742
Joined: March 15th, 2016, 6:41 pm
Location: re^jθ

Re: [GAME] TREE function games

Post by Hdjensofjfnen » April 14th, 2019, 10:48 pm

New game, anyone?
[]

Code: Select all

x = 5, y = 9, rule = B3-jqr/S01c2-in3
3bo$4bo$o2bo$2o2$2o$o2bo$4bo$3bo!

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » April 22nd, 2019, 12:59 pm

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”

({})
not active here but active on discord

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: [GAME] TREE function games

Post by toroidalet » April 25th, 2019, 11:05 pm

A continuation of the TREE(3) game:

Code: Select all

{},
([]), and now
[[()]]
Any sufficiently advanced software is indistinguishable from malice.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » April 26th, 2019, 9:19 am

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.
not active here but active on discord

User avatar
Hdjensofjfnen
Posts: 1742
Joined: March 15th, 2016, 6:41 pm
Location: re^jθ

Re: [GAME] TREE function games

Post by Hdjensofjfnen » April 26th, 2019, 11:33 pm

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

({})
(())

Code: Select all

x = 5, y = 9, rule = B3-jqr/S01c2-in3
3bo$4bo$o2bo$2o2$2o$o2bo$4bo$3bo!

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
ishanpm
Posts: 27
Joined: September 28th, 2017, 9:54 pm
Contact:

Re: [GAME] TREE function games

Post by ishanpm » April 27th, 2019, 10:19 pm

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.
Last edited by ishanpm on April 28th, 2019, 9:36 am, edited 1 time in total.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » April 28th, 2019, 8:48 am

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.
not active here but active on discord

User avatar
ishanpm
Posts: 27
Joined: September 28th, 2017, 9:54 pm
Contact:

Re: [GAME] TREE function games

Post by ishanpm » April 28th, 2019, 11:48 am

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/

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: [GAME] TREE function games

Post by Moosey » May 23rd, 2019, 4:02 pm

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]
not active here but active on discord

Post Reply