[GAME] TREE function games
[GAME] TREE function games
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.
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
- toroidalet
- Posts: 1514
- Joined: August 7th, 2016, 1:48 pm
- Location: My computer
- Contact:
Re: [GAME] TREE function games
{}
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?)
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.
Re: [GAME] TREE function games
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.toroidalet wrote: (Also, isn't it that you lose if you have to make a tree that (homeomorphically) contains another, rather than winning?)
It’s like miser chess this way.
I love it!toroidalet wrote:{}
A bold first move; how will his/her opponent react?
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
Re: [GAME] TREE function games
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?
Moosey: <>
PkmnQ: [{}]
I think I'm playing it a little bit too safe here. What are legal moves?
Re: [GAME] TREE function games
You have legal moves as long as: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?
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
Re: [GAME] TREE function games
Moosey: <>
PkmnQ: [{}]
Moosey: [({})]
PkmnQ: ([])
PkmnQ: [{}]
Moosey: [({})]
PkmnQ: ([])
Re: [GAME] TREE function games
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.
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
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: [GAME] TREE function games
I believe Moosey's second move is illegal because you can contract the () node to get PkmnQ's move.
Re: [GAME] TREE function games
Not, because my move wasfluffykitty wrote:I believe Moosey's second move is illegal because you can contract the () node to get PkmnQ's move.
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
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: [GAME] TREE function games
Contracting a node with one child is one of the actions you can do for homeomorphic embedding (see the example in the blog post)
Re: [GAME] TREE function games
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
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: [GAME] TREE function games
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.
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.
- BlinkerSpawn
- Posts: 1992
- Joined: November 8th, 2014, 8:48 pm
- Location: Getting a snacker from R-Bee's
Re: [GAME] TREE function games
Is there anything wrong with this?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.
Code: Select all
{}
([])
[[][]]
[[[[]]]]
[[[(())]]]
[[[()()()]]]
[[[()()](())]]
[[[()()]()()()]]
[[[()()]()()](())]
[[[()()]()()]()()()]
[[[()()]()()]()()]
[[[()()]()()]()]
[[[()()]()]((((((()))))))]
Last edited by BlinkerSpawn on April 10th, 2019, 10:34 pm, edited 2 times in total.
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: [GAME] TREE function games
That seems to work
Re: [GAME] TREE function games
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.
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.
-
- Posts: 1175
- Joined: June 14th, 2014, 5:03 pm
- Contact:
Re: [GAME] TREE function games
No, again because of your first move.
- Hdjensofjfnen
- Posts: 1743
- Joined: March 15th, 2016, 6:41 pm
- Location: re^jθ
Re: [GAME] TREE function games
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!
Re: [GAME] TREE function games
Difference 1: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.
[{()}] does not contain [()] like it would usually (more possibilities)
I believe this is Difference 2:
[()] does not contain ([])
What rules apply to this one?hdjen wrote:New game, anyone?
[]
Presumably no “Moosey instantly wins”
({})
not active here but active on discord
- toroidalet
- Posts: 1514
- Joined: August 7th, 2016, 1:48 pm
- Location: My computer
- Contact:
Re: [GAME] TREE function games
A continuation of the TREE(3) game:
Code: Select all
{},
([]), and now
[[()]]
Any sufficiently advanced software is indistinguishable from malice.
Re: [GAME] TREE function games
I’d be glad to let someone else play for me.toroidalet wrote:A continuation of the TREE(3) game:Code: Select all
{}, ([]), and now [[()]]
not active here but active on discord
- Hdjensofjfnen
- Posts: 1743
- Joined: March 15th, 2016, 6:41 pm
- Location: re^jθ
Re: [GAME] TREE function games
(())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!
Re: [GAME] TREE function games
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 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.
Last edited by ishanpm on April 28th, 2019, 9:36 am, edited 1 time in total.
Re: [GAME] TREE function games
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.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:
I'll write a small Javascript applet that can validate TREE(k) games, to make analyzing these a little easier.
- []: 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.
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
Re: [GAME] TREE function games
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/
Doesn't support fakeTREE at the moment. Later, I'll add a feature to list legal moves.
https://jsfiddle.net/ishanpm/s45w7ouj/
Re: [GAME] TREE function games
I was gonna say,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/
“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