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 ... 100
1
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.

2
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.

3
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.

4
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?

5
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".

6
What were the other four?

7
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!

8
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.

9
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".

10
General Discussion / Re: Maths thread.
« on: July 24, 2017, 04:53:48 pm »
Yeah, (1,x,x^2,...) is a really intuitive basis, but the point is that you HAVE to choose it. Any finite-dimensional vector space will be isomorphic to F^n for some field F, so any example I give would be easily interpreted as coordinates; I would just be obfuscating to make the basis hard to see. But the vectors in F^n itself are literally coordinates, so you might not think to translate to a basis. Faust's diagram is really instructive, and can even be generalized for any finite-dimensional F-vector spaces V,W (they both need to have the same base field). Then if f: V --> W is linear, f = iV(g(iW-1))) with

     iV            g             iW-1
V ---> F^n  ---> F^m  ---> W

iV and iW are the isomorphisms from V to F^n and W to F^m specified by bases, and then g is the transformation specified by some n-by-m matrix.

At this point I'm not sure anyone is confused, but I just think these diagrams are pretty cool.

11
General Discussion / Re: Maths thread.
« on: July 23, 2017, 08:34:52 pm »
The class I took was very careful to be precise about this matter. Let V,W be finite-dimensional vector spaces and f: V --> W a linear map between them. Then f is completely determined by how it transforms some basis for V. Say B = (v_1,v_2,...,v_n) is a basis for V, and C = (w_1,w_2,...,w_m) is a basis for W. Then let M be the m-by-n matrix where the i-th column is f(v_i) written with respect to the basis C in W. Then we can say that f(v) = Mv for all vectors v in V - when v is written in the basis B and f(v) is written in the basis C. In particular, we would frequently write f = B[M]C to emphasize that the matrix transforms from the basis B to the basis C.

One other minor thing here is that R3 is special in that is it literally the set of ordered triples of real numbers, and so there are naturally "coordinates". But if we took, say, R[ x ]<3, the vector space of real-valued polynomials in x with degree less than three, there aren't really "coordinates". (1,x,x^2) is a simple basis for the space, but the vectors themselves do not have coordinates. 4x^2 + 2x + 7 is a vector in this space, and with respect to that basis it is (7,2,4). Then if you apply a linear transformation to this vector, you can instead use a matrix with respect to this basis and apply it to (7,2,4); it doesn't make any sense to multiply a matrix by 4x^2 + 2x + 7. In fact, R[ x ]<3 is isomorphic to R3, but here it's more clear that the vectors need to be written with respect to a basis.

12
Simulation / Re: Confusion over setting Kingdoms
« on: July 21, 2017, 10:12:38 pm »
Well, I think the reason that the simulations aren't very useful is at least partially because there is no actual kingdom. Joejoe probably realizes that a good simulator would need to take more things into account and so is surprised that they don't have a kingdom.

13
Did you win 12-6 or something? That's pretty sweet.

14
Still haven't done the math on if this is even a good idea or not but whatever.
You got 2 actions and a coin for , so it's like you added a villa to your deck for without spending a buy. Although you can normally do that for just , without diadem or other action cards in your hand.

15
General Discussion / Re: Maths thread.
« on: July 13, 2017, 11:35:17 pm »
Ok wow yeah that bit was just nonsense. If A,B,C satisfied the previous equation they would automatically satisfy the triangle inequality though, so we didn't need to worry about that.

Say x <= y <= z. Say x >= 4, then let x = 4 + i, y = 4 + j, and z = 4 + k for non-negative j,k. Then:

 xyz = (4 + i)(4 + j)(4 + k) >= (16 + 4j + 4i)(4 + k) >= 64 + 16i + 16j + 16k > 48+4i +4j+4k = 4(4+i + 4+j + 4+k) = 4(x + y + z)

Which means no solutions. Then we can just check all x in {0.5, 1, 1.5, 2, 2.5, 3, 3.5} like I did before and get those solutions.

Showing that x < 4 was more messy than it really needed to be. The intuition is just that (x,y,z) = (4,4,4) already has LHS < RHS and increasing x,y, or z will increase the RHS at least as much as the LHS.

16
General Discussion / Re: Maths thread.
« on: July 13, 2017, 12:44:08 am »
I asked some other people with experience with contest math and they solved it pretty quickly. There are   5  triangles.

A hint that should help unblock things: Given any triangle with side lengths a, b, c, you can find positive x, y, z such that a = x+y, b = y+z, and c = x+z. Try working in (x,y,z) space instead.
Huh. I guess that's vaguely motivated by the triangle inequality/the appearance of (A+B+C)/2 in Heron's?

Well, it does really simplify things:

4S^2 = S(S-A)(S-B)(S-C)
4S = (S-A)(S-B)(S-C)
4(x + y + z) = xyz

At least one of x,y,z must divide 4 (and so is either 1,2, or 4). WOLOG say it is x. Now:

xyz - 4(y + z) = 4x
yz - (4/x)(y + z) = 4
(y - 4/x)(z - 4/x) = 4 + 16/x2

If x = 1:

(y - 4)(z - 4) = 20
Solution pairs are (5,24), (6,14), and (8,9)

If x = 2:

(y - 2)(z - 2) = 8
Solution pairs are (3,10) and (4,6)

If x = 4:
(y - 1)(z - 1) = 5
The only pair is (2,6) and we already have this triple above.

The 5 solutions for x,y,z given above result in the triangles:

(6,25,29),(7,15,20),(9,10,17),(5,12,13),(6,8,10)

17
Puzzles and Challenges / Re: Best Asymptotic Point Scoring
« on: July 10, 2017, 02:45:23 pm »
OK, I think I now see what you were saying before, so the below version doesn't bother with foragers. Hopefully I've re-phrased it well enough that it's now more clear why it doesn't matter what fraction of the deck is city quarters. I believe we can add ferry and royal carriage to the kingdom without allowing unbounded gain. The kingdom is now:

KC, stonemason, city quarter, fortress, royal carriage, bridge, travelling fair, training, ferry, inheritance.

The only draw is city quarter and fortress, and it's still not possible to gain either mid-turn. Ferry on royal carriage, inheritance on KC so that we can gain them from stonemasoning fortress. Training on stonemason. The bridge is just so that we can inherit KC in the first place. Choose some large constant C, and say that we have d stonemasons/estates. Every iteration, gain C royal carriages on the side, and only keep d/2C-1 KC/stonemasons in hand. This gains 4d(1 - 1/2C-1) estates/stonemasons. Then play C royal carriages, and use them to play a city quarter C+1 times to draw everything again. Repeat for as many iterations as city quarters. Now if there were x city quarters going into this turn, then now we have O(d(4 - 1/2C-3)x - log(x + d)) coins which we use to buy city quarters. The new number of estates/stonemasons in our deck is also on the order of this quantity, so we can say d = O(x) and x = O(d). Therefore the new number of city quarters is:

O(d(4 - 1/2C-3)x - log(x + d))
= O(x(4 - 1/2C-3)x - log(x))
= O((4 - 1/2C-3)x)
~O(4x)

Since the number of points is within a constant factor of the number of city quarters, in the long run we can get (4 - ε) ↑↑ n points in n turns for any ε > 0.

18
Puzzles and Challenges / Re: Best Asymptotic Point Scoring
« on: July 10, 2017, 01:52:20 pm »
If we wanted more gardens, we wouldn't even need to set them aside; it would be no trouble to keep drawing them. But that really wouldn't even increase the base of the tetration.
Perhaps there is something I misunderstand, but here is how I understand what you are doing:
In turn n you can increase the deck size of your deck by a factor f^n, so that the total deck size in turn n is f^n^n. Now if we would just replace some gains to double the number of gardens each iteration, your factor f gets replaced by g with g < f. On the other hand you have now g^(2n) points. So if there is a spot where g^2 > f, you would improve the result.
luser is right... if the deck size is d on turn n, then the deck size at the end of the turn will be f^d for some constant f. Then after n turns the deck size is f^f^f^...^f, or f ↑↑ n.


If we wanted more gardens, we wouldn't even need to set them aside; it would be no trouble to keep drawing them. But that really wouldn't even increase the base of the tetration. Also I think ghost is right - it doesn't seem to cause infinite draw?
You shouldn't think, you should know. With stonemason example its 2kc, 2nv, stonemason loop
Oh, right - we can't have any gainable draw at all. Then we also can't have KC-workshop-watchtower, which would break your second method but it looks like you can just replace watchtower with royal seal.

Quote
You are right, Kc-cq cubes the base of the tetration. So now if we get almost all of our starting cards to be city quarter, then we have 3.455675... ↑↑ n points.

We don't want a constant number of cq though; we want almost all of our cards to be cq because the number of iterations is what limits our growth. The initial log_2 (d) plays of cq become meaningless. I think you may be right, there is a slight error in my analysis though... that I don't feel like looking into.

No, problem that makes analysis worthless is that result would depend on having constant number of cq more or less. By first getting 20 cq and playing them for 20 fifty more iterations you would get thousand times more coins and if you plug it into calculation you would get bigger exponent. And log d cq factor where you have cards from previous iteration would outgrow any constant.

Also its easy to see that you want to play only 1 cq per iteration if you use more you made mistake. For contradiction find last cq play where you didn't draw whole deck. You could instead of playing  on previous turn play them this turn to gain same cards for undrawn portion and have better drawing capabilities in previous turn.
I still don't see what you are saying at all. The number of iterations is O(d) >> log d, so the vast majority of the cq will be spent re-drawing cards mid-turn. Multiplying the number of cq by a constant multiplies the exponent by a constant. The log d just subtracts from the exponent, which gets dominated.

Since we're using KC-cq anyway, we'll want to play 7/11ths of our cards each time so that 3 plays of cq take us from 4/11 to 32/11. That means we're really getting (almost) 32/11 ↑↑ n VP.

19
Puzzles and Challenges / Re: Best Asymptotic Point Scoring
« on: July 09, 2017, 05:16:24 pm »
Native village with kc would cause infinite draw. I doubt that you could get triple arrow because of deck composition where you use limited number of one action as counter.

Second problem is that you didn't use kc-cq which increases draw to 8x instead to 2x.

Dependence of function on tfair/cq cost is just wrong from the first glance. It couldn't change asymptotic behaviour. Having constant number of cq more increases coins by bigger constant factor and initial log (d) cq plays exceed any constant factor.

But now I realized how to use scrying pool which I couldn't before as I didn't know how to deal with potions. Its again with city quarter.

Kingdom with cq, kc, bridge, workshop, spool, watchtower.

At start of turn use topdecked pool to draw all actions bought last turn and with one kc-cq draw rest of deck. Play kc-bridge. Now repeat playing kc-workshops gaining more kc and workshops and redrawing with scrying pool while you have pools.

At last iteration use half of kc and workshops that you have to gain potions, kc and bridges and use kc-cq to draw them. Buy and topdeck kc, cq and as many scrying pools as potions.
If we wanted more gardens, we wouldn't even need to set them aside; it would be no trouble to keep drawing them. But that really wouldn't even increase the base of the tetration. Also I think ghost is right - it doesn't seem to cause infinite draw?

You are right, Kc-cq cubes the base of the tetration. So now if we get almost all of our starting cards to be city quarter, then we have 3.455675... ↑↑ n points. EDIT: Somewhat wrong.

We don't want a constant number of cq though; we want almost all of our cards to be cq because the number of iterations is what limits our growth. The initial log_2 (d) plays of cq become meaningless. I think you may be right, there is a slight error in my analysis though... that I don't feel like looking into.

Your new solution also results in double-arrow points... the base of the tetration might be better when optimized but I also don't feel like calculating it.

I'm working on another idea right now, possibly involving hermit...

20
General Discussion / Re: Maths thread.
« on: July 08, 2017, 08:31:17 pm »
Well, here a few more thoughts...

If (A,B,C) are positive integers satisfying 16(A + B + C) = (-A + B + C)(A - B + C)(A + B - C), then they must make a valid triangle. For if they violated the triangle inequality somehow, then exactly one term on the RHS would be negative while the LHS is positive. So we don't need to worry about that at all.

If the area A divides the perimeter P, say P = Ak, then after scaling sides of the triangle by k we have P' = Pk and A' = Ak^2 = Pk, so P' = A' in the new triangle. This doesn't really help with the above equations though.

Building on Tables' parity argument:

Let's look at the possibilities modulo 4. At least one of the RHS terms must be divisible by 4. Then if A,B,C are all even, then either one is divisible by 4 or all 4 are. In the case that only 1 is even we can't determine anything. Hmmm, not so helpful...

What if we looked at it modulo one of the side lengths. For example we have 16(B + C) = -(B + C)(B - C)^2 modulo A. That looks nicer but probably isn't actually too helpful... if gcd(A,B+C) = 1 it gets even simpler, (B - C)^2 = -16 modulo A... for example in the case (13,12,5) = (A,B,C) we have 7^2 = 10 = -16 modulo 13. Still not sure where this would go.

I'm guessing there are only finitely many solutions and most of them aren't right triangles.

21
General Discussion / Re: Maths thread.
« on: July 08, 2017, 03:35:25 pm »
A fun (and tricky) problem I came up with at work about triangles is:

How many triangles satisfy the following properties:
1. All of the side lengths are integers.
2. The area of the triangle is equal to its perimeter.
Funny you would ask... my first inclination is to use... Heron's formula! Let S be half the perimeter. Heron's formula states that the area of the triangle is sqrt(S(S-A)(S-B)(S-C)) where the sides are A, B, and C. That's equal to 2S, apparently. Then:

4S^2 = S(S-A)(S-B)(S-C)
4S = (S-A)(S-B)(S-C)
16(A + B + C) = (-A + B + C)(A - B + C)(A + B - C)

Uh, then we need all integer solutions to this, and I suppose we also need to be able to make a triangle out of it (so if A < B < C, we need A + B > C). Not really sure where to go from here though...

22
Puzzles and Challenges / Re: Best Asymptotic Point Scoring
« on: July 08, 2017, 01:38:40 am »
I was kinda assuming perfect shuffle luck, so we draw the city quarters at the start of every turn. I forgot that tfair topdecks and was just using it for buys. But sure, get a royal seal. I like the idea of forager but not totally sure how it works? We would have to gain a lot of them, like O(d) of them - then we have fewer stonemasons and estates. Also I guess it's just a constant factor.

If p is the fraction of the cards we play each iteration, then we end up with (1 - p) of the cards in hand and 4p cards to draw. In order to end up with them all (1 + 3p) in hand we need to play ceil(log2(1 + 3p/(1-p))) = k city quarters. If the fraction of the deck that is city quarters is x, then the final deck size will be multiplied by (1 + 3p)xd/k. Then we want to maximize (1 + 3p)1/ceil(log2((1 + 3p)/(1-p))). Wolfram says the optimal value for p is actually 3/7 here, which is kind of surprisingly low. That makes the final base of our tetration (16/7)x/2. If x = 1/22 like it did before this is less than 1.02, but maybe we can do better with forager...

We would actually be thrilled if 99% of our starting cards each turn were city quarter or something; the deck size reached at the end of the turn would only be decreased a constant amount compared to several more iterations. So I think you are right; we can make all of our gains in the final iteration forager. Each forager will give at least 18 coins easily, which is enough for two city quarters. Since k = 2 this is enough for another iteration (multiply by 16/7), so definitely will always be better than taking a stonemason or something. We'll still want to keep travelling fair around for the buys, since each forager play only gives 1 buy but enough coins for two city quarters. In any case we'll be losing a constant factor every turn, possibly a lot, but x will be pretty darn close to 1. If we use the final 4p cards for just KC-forager then we get 8p forager plays for 16p city quarters, and the rest of the deck is just 1-p other stuff. Then x = 16p/(1 + 15p) = 0.923... we could include this in the optimization of p but I have a hunch that we could actually make x arbitrarily close to 1. Anyway, we now have 1.464544...  ↑↑ n points.

If we let x = 1 we get 1.51... instead, so slightly better. Anyway, not sure I feel like trying to optimize this technique further... I made enough mistakes while writing this post.

23
General Discussion / Re: Maths thread.
« on: July 07, 2017, 06:58:24 pm »
Alternate solution:

We are counting unordered partitions of 180 into three parts. First we'll count the number of ordered partitions, adjust a few times to just count distinct ones.

Line up 180 dots in a line. To partition into three parts, draw two vertical lines in two of 179 spots to separate them. There are 89*179 ways to do this.

The equilateral triangle was counted exactly once.

Isosceles triangles can be made in three different ways. How many of these are there that aren't equilateral? 88, one for every even integer between 2 and 178 inclusive, except for 60.

Therefore there were 89*179 - 88*3 - 1 drawings that resulted in scalene triangles. Each of these was drawn 6 times, so after dividing by six we get that there were 2611 distinct scalene triangles. Add back the 89 other triangles to get 2700 total triangles.

I suspect that there may be an even simpler way still to count this...

24
General Discussion / Re: Random Stuff Part III
« on: July 07, 2017, 06:15:01 pm »
Oh hey, anyone live in Louisville Kentucky?

Yeah, someone lives there. Quite a lot of people actually, around 760 000. Hope this helps!

The context is that someone from here would live in Louisville Kentucky.

Given that there are approximately 7,347,000,000 people in this world, 5,244 total members, and 760,000 people in Louisville, what is the statistical probability of a user from F.DS being located within this section of the world?

1 – {Product: i = 0 to 759999 of [(7347000000 – i – 5244) / (7347000000 – i)]}

I think. This is confusing me slightly.

Alternatively, the probability is at least 1 - (1 - 76/737400)5244 = 0.4175429... and at most 1 - (1 - 76/737399)5244 = 0.4175433...

Close enough for you?

25
On the other hand, if it's a card that actually does have a when-trashed effect (rats, fortress, squire, catacombs, sir vander, wow these are all from dark ages) then you DO get that effect. You could also then discard a market square for a gold.

EDIT: sniped by singletee's edit, and he thought of another card (feodum) with such an effect, also from dark ages; almost like trashing was a theme of that expansion.

EDIT2: Oh, and hunting grounds. There are more of these than I thought...

Pages: [1] 2 3 ... 100

Page created in 0.207 seconds with 18 queries.