Dominion Strategy Forum

Please login or register.

Login with username, password and session length

Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - liopoil

Filter to certain boards:

Pages: [1] 2 3 ... 384
1
Puzzles and Challenges / Re: Best Asymptotic Point Scoring
« on: November 23, 2018, 02:15:19 am »
Very nice! This is some good progress. It got me thinking about the Busy Beaver amount of Coin thread again, where we also achieved triple-up-arrow. The question there is, how many coins can be generated by an n-card deck which can't generate arbitrarily many coins? Coins and VP are mostly synonymous, and with f(n) coins you can pretty much get whatever f(n)-size deck you want. This suggests that if there is a solution for the coin problem achieving the growth rate, then there should be a solution to this VP problem which achieves a fn(2) growth rate, where fn() is f() iterated n times and 2 is a constant.

This suggests that there should be a quadruple-up-arrow solution to the VP problem, arising from the triple-up-arrow solution to the coin problem. However, we don't quite yet have this: the current triple-up-arrow solution for the coin problem involves gaining arbitrarily many cards costing <6, which isn't an issue for that problem because the number of actions (and so the amount of draw) is bounded. But for this problem, we could gain arbitrarily many estates for unbounded VP. The converse seems to be true in this case, though: bitwise's triple-up-arrow solution does give a double-up-arrow solution for the coin problem too.

That said, maybe we can still use this. Suppose we add the landmark wall to the kingdom, so that the estates aren't worth a point anymore. Then as long as we have another way of getting points (I think obelisk on an expensive card or palace both work), it may be possible to use that solution. I'll go see how well that works...

EDIT: the way we gained arbitrarily many cards in the coin solution was to inherit estate as catacombs, trash them with watchtower gaining hunting grounds (reduced cost to zero), trash the hunting grounds for 3x estate, repeat. However, we could gain arbitrarily many duchies in this way, so wall doesn't fix that. Still, maybe we can find another way to gain arbitrarily many cards in a way that excludes duchy and province (and at least one of gold, a potion-cost, or a debt-cost)

2
Puzzles and Challenges / Re: Best Asymptotic Point Scoring
« on: November 14, 2018, 06:42:09 pm »
The growth rate to beat is currently double-up-arrow, first introduced here:

I have better f(n)= 2^2^2^(O(n) times) kingdom kc, workshop, city quarter, training, tfair, bridge, gardens.  Deck contains starting cards one gardens, rest are action. Training on workshop

Turn starts by drawing deck with log(d) cq where d is deck size, play kc-bridge. Then you start multiplying workshops/kc. Assume that deck has k kc and k workshops. play k/2 kc on k/2 workshops to gain 3/4k workshops and 3/4k kc then play cq to draw these and repeat by number of cq in deck. If you start with 3 kc and 3 workshops and l cq you will end with 2^l workshops. Coins from training allow you to buy 2^l/10 cq which shows that f(n+1)>=2^f(n) and bound follows.

and explained in more detail here:
I think what luser originally wrote works but tim's suggestion is more clear and is technically better (improves the base of the exponent, pretty much). A more explicit (but still not totally optimized) description of luser's solution with additions (it took me a bit of work to decipher exactly what was happening):

Kingdom:  KC, stonemason, city quarter, fortress, gardens, training, travelling fair, inheritance (3 events, oh well). Training on stonemason, inheritance on KC (okay add a cost-reducer to the kingdom). When our deck has size d: Deck has 1 gardens, 1 fortress, ~7d/22 estates, ~14d/22 Stonemasons, ~d/22 City Quarters where x = o(d).

Turn:
Play ~log2(d) City Quarters to draw the deck
Play the estates as d/4 KC on d/2 stonemasons for 3d gains, make them d estates and 2d stonemasons.
We have d/4 cards left in hand, so play 4 city quarters to draw everything again.
Play 3d/4 estates on 3d/2 stonemasons for 9d gains, which are 3d estates and 6d stonemasons...
Repeat like before until we run out of city quarters. We now have over d' = 3d/88d cards in our deck, and the number of stonemason plays a bit over half of that. From training we could buy d'/20 city quarters, but just buy d'/22 instead (using travelling fair for buys).

Each turn d' = (31/88)d, so we end up with around 31/88 ↑↑ n points.

I wouldn't be surprised at all if three arrows is possible though... I'll think about it...

the rest of the thread just improves the number of set up turns by a constant, as bitwise pointed out. So the next step requires a new level of method, and it would surely involve these newfangled expansions I'm hearing about...

3
I've been asking (Math and CS) friends this question for a while now. In particular some variant of question 2.

Being able to embed a turing machine (which is not a totally well defined notion) doesn't seem to (necessarily) have any implication for the undecidability for the game.

Dominion with finite piles is really complicated (i.e. question 2 and variants i.e. winning in 1, getting from 1 state to another presumably these are all the same computability strength). . It seems that the win in turn one question is likely decidable (though proving this seems ferociously hard). But I have no idea about infinite pile dominion.
I've also talked about this question with some friends before; in fact, I suspect that we have some mutual friends. The simplest way of stating my question is: Is the decision problem "is there a way to get at least n points this turn?" decidable for any game state? I do not know the answer for finite piles OR infinite piles. In the case of infinite piles, game states must still have a finite description. My suspicion is that the answers are yes and no, respectively, but it's possible that new card could make the finite piles case undecidable as well. It's also possible that the infinite case is decidable; I do not have a proof

4
Puzzles and Challenges / Re: Best Asymptotic Point Scoring
« on: October 29, 2018, 04:18:00 am »
Sorry for the necro.

Note that if we're already willing to subtract a constant number of turns from n (e.g. to set up the deck), it doesn't really matter what number you have as the base of the tetration. Here's a proof that 2 ↑↑ (n+2) >= 4 ↑↑ n.

Lemma 1: If x >= 4y and y >= 1, then 2^x >= 4*4^y.
Proof: x => 4y implies 2^x >= 2^(4y) = 4^(2y) = (4^y)*(4^y) >= 4*(4^y).

Now we can show that 2 ↑↑ (n+2) >= 4 * (4 ↑↑ n) for all n with induction. For n=1, both sides equal 16. If 2 ↑↑ (k+2) >= 4 * (4 ↑↑ k), then by Lemma 1, 2^(2 ↑↑ (k+2)) >= 4 * 4 ^ (4 ↑↑ k), or 2 ↑↑ (k+3) >= 4 * (4 ↑↑ (k+1)).

The same idea can be extended to show that for any A,B, there's a constant c such that A ↑↑ (n+c) >= B ↑↑ n for all n.

In summary, all of the c ↑↑ n solutions are about as good as each other for this question.
Oh, yes, you are right. Wow, it's been a while.

I'm kinda surprised that this and the busy beaver question (maximize coins in single turn, iirc) have different answers (two up arrows v. three up arrows). Also a couple expansions have come out since I last thought about this, and I don't know all the cards anymore. Still, would be interesting to see if it's possible to do better now.

5
Non-Mafia Game Threads / Re: The Necro Wars
« on: July 13, 2018, 09:34:14 pm »
Sometimes I feel like I'm the only one playing
Is this post the current longest necro?

6
Other Games / Re: Splendor
« on: May 16, 2018, 04:39:38 am »
My friends and I have been playing a fair bit of Splendor, and for the most part have settled upon a meta of play that is similar to the strategy Awaclus describes. Today we tried to answer the following question:

In a four-player game (so, 7 chips in each pile) with perfect luck for yourself and your opponent staying out of the way, what is the shortest possible game?

I found a little article with statistics on over 7000 games of splendor played online, and 3 games took 19 turns with none being shorter. However, it's not that hard to come up with a way that someone might get to 15 points faster than that with no opposition and perfect luck.

After a few hours of puzzling, the shortest game we could come up with was 15 turns to 15 points, which we managed to achieve in three essentially different ways. How many turns can you get to 15 points in? I think there is still a fair bit of unexplored space for solutions and possibly improvements and would be interested to see what the forum comes up with.

I'll add that we don't really have much idea how to show that a given solution is the best possible. We think we've pretty much proven that a game of splendor must take at least 11 turns, but that is almost surely not tight and it's unclear how to improve that bound with certainty.

7
Dominion General Discussion / Re: Right way to play when you canít win?
« on: January 29, 2018, 07:30:34 pm »
The utility function I and my friends use for this and other multiplayer games is:

Let epsilon be a positive number that is way smaller than any conceivable positive probability of any particular event occurring in a game of dominion.

Winning is worth 1 point
2nd place is worth epsilon points
3rd place is worth epsilon squared points
The game ending one turn earlier is worth epsilon cubed points

Maximizing your expected points always leads to playing solely for the topmost uncertain outcome. This is equivalent to what most people are saying in this thread. Also, this makes it so that you play for a shorter game as soon as your placement is assured, no matter what it is. e.g., always taking the three-pile win if it's there.

8
Non-Mafia Game Threads / Re: The Necro Wars
« on: October 31, 2017, 12:26:33 pm »
this thread is far too active right now

9
Non-Mafia Game Threads / Re: The Necro Wars
« on: October 07, 2017, 11:57:12 am »
Oh wow things are changing fast now

10
General Discussion / Re: Random Stuff Part III
« on: October 01, 2017, 07:11:37 pm »
I know how run-time works in general, just not sure precisely what quantity n is referring to in this context. If it's the size of the list, I guess my question is exactly how the list is structured. Before I assumed that the list was infinite and it just started being periodic after some point and the period was around n or something. So now I don't have any real idea what a "linearly linked list" is. If it's like, each element points to its successor, or something, I'm not sure what stops you from just like going down the list until you get somewhere you've already been. If it's just a graph shaped like a P or something, then you're just looking for the vertex with degree three. I'm just trying to guess what this structure is at this point... I guess that's what I meant by "What information exactly are you given" - as in what's the data structure.

11
General Discussion / Re: Random Stuff Part III
« on: October 01, 2017, 05:54:16 pm »
I'm not sure I understand the question. What exactly is n supposed to be? What information exactly are you given and what does each query or whatever tell you?

12
Puzzles and Challenges / Re: Best Asymptotic Point Scoring
« on: October 01, 2017, 05:52:22 pm »
Yeah, there are lots of foolproof ways to set your starting deck up, especially because of donate. I didn't really feel the need to flesh that part of it out because that's not really the hard. I suppose the true statement of the final result here is:

For any ε > 0, there exists a positive constant integer c, such that for any positive integer n we can get (4 - ε) ↑↑ (n - c) points within n turns.

Again it doesn't make much sense to use big-O notation when the rate of growth is hyper-exponential like this. Really the answer is "we can pretty much make our score grow at the same general rate as 4 ↑↑ n does".

13
Non-Mafia Game Threads / Re: The Necro Wars
« on: September 21, 2017, 08:13:43 pm »
I would have taken it tonight too :/ I blame the necro game thread for prompting you

That is what did it!
It's okay, the necro game thread prompted me several times back in the day...

14
Non-Mafia Game Threads / Re: The Necro Wars
« on: September 21, 2017, 07:21:18 pm »
I would have taken it tonight too :/ I blame the necro game thread for prompting you

15
Non-Mafia Game Threads / Re: The Necro Wars
« on: September 07, 2017, 01:37:29 pm »
Post
darn I was hoping you wouldn't bother

16
Non-Mafia Game Threads / Re: The Necro Wars
« on: August 30, 2017, 12:40:02 am »
Muhahahahahaha
Oh no I accidentally moved away to college :(

17
Forum Games / Re: BM26 Cryptography Mafia (3 spots left!)
« on: August 21, 2017, 03:38:45 pm »
If this doesn't start soon I should probably out too :/
I have to /out :(

20
What were the other four?

21
Forum Games / Re: BM26 Cryptography Mafia
« on: August 07, 2017, 02:19:51 am »
If this doesn't start soon I should probably out too :/

23
General Discussion / Re: Random Stuff Part III
« on: August 04, 2017, 02:27:07 pm »
Not strictly speaking "almost all," though, because there are infinite real numbers which are not normal.
I'm assuming that liopoil meant almost all with respect to Lebesgue measure. 

Which, I imagine that's true, though I don't know for sure.
This is what I meant. I read somewhere that it'd been proven, though I have no idea how. Seems plausible though!

24
General Discussion / Re: Random Stuff Part III
« on: August 04, 2017, 04:18:06 am »
Yeah, but like, how stupid would it be if pi weren't normal? Almost all real numbers are normal.

25
General Discussion / Re: Evolution of Trust
« on: August 03, 2017, 08:45:45 pm »
I played this a little while ago and it was pretty cool, and obviously makes a good point. I did have one issue with it though...

The game only considers a small finite set of strategies, from which the best performing strategy against the others over time was the "cheat only after you're pretty sure that you're opponent is a cheater" strategy. The game makes it seem like that strategy is some sort of "long term equilibrium". And I'm sure that in the real world where we play similar games, it may be. But for this specific game, it isn't actually. The rules of the game state:

Quote
you'll play anywhere between 3 to 7 rounds. (You won't know in advance when the last round is)

(this later became any variable number of rounds, but for now we'll assume that the game lasts at most 7 rounds).

Then if a game gets to a 7th round, you know that it's the last round. So if I take the copycat strategy and modify it to "copy what your opponent did in the previous round, unless this is the 7th round, in which case, cheat no matter what", then I will beat the copycat strategy in the long run. Similar for all of the modified strategies that sometimes cooperate. And then we can go further: once all of the strategies cheat in the 7th round, it becomes pointless to cooperate in the 6th round... and so on.

So I think that the game needs to be modified further to truly get the desired outcome. Maybe something like: "after each round, roll a 6-sided die, and if it's not a 6, play again".

Pages: [1] 2 3 ... 384

Page created in 0.147 seconds with 19 queries.