Recommend
8 
 Thumb up
 Hide
47 Posts
1 , 2  Next »   | 

Dominion» Forums » Strategy

Subject: Against "expected number of turns" rss

Your Tags: Add tags
Popular Tags: [View All]
Guy Srinivasan
United States
Kirkland
Washington
flag msg tools
Avatar
mbmbmbmbmb
Every time I see a simulation done to gauge a Dominion strategy's strength, or the marginal value of +1 Smithy, or how broken the Chapel is, or whatever, and the reported number is "Expected number of turns to buy 4 Provinces" or similar, I cringe. How can we do better without incurring a large coding cost?

Why are we trying to get to 4 Provinces? Because for many mainline strategies, whoever can get to 4 Provinces first will likely also win. Sounds fine enough. There are some other goals, like with Gardens, but they all come down to "who can get to X points first, where X means the remaining points likely to be bought, split up among the remaining players, won't win?"

How do we tell who gets to 4 Provinces first? Measuring average number of turns works whenever all strategies involved have similar variance characteristics. So Big Money vs Big Money + Smithy is probably fine, and in fact any time we're looking at the marginal value of one extra card (besides Chapel) to a strategy, average number of turns is probably good enough.

When doesn't it work? When variance characteristics are very different. Such as Big Money vs All Treasure Maps. If the TM player hits on turn 5-6, she's going to just win, and we don't much care how fast she does it. If she hits first on turn 10, she's going to just lose, and we don't much care how slow she would have reached 4 Provinces.

What can we do about it? IMO the simplest change that accomplishes the most is whenever you code up a simulation, don't just keep a total-turns-taken counter and divide it by the number of trials at the end. Instead, keep an array of trials-taking-X-turns counters and divide each by the number of trials at the end. The output of a simulation that ends when the 4th Province is bought should look like this (warning: made-up numbers):
11 Turns: 1%
12 Turns: 3%
13 Turns: 8%
14 Turns: 22%
15 Turns: 31%
16 Turns: 17%
17 Turns: 10%
18 Turns: 5%
19 Turns: 2%
20 Turns: 1%

After that? Sure, go ahead and compute the expected number of turns if you like. But with the more detailed, just-as-easy-to-gather information, we can FAR more effectively compare two results. Suppose (haha) Treasure Map turned out to look like:
11 Turns: 2%
12 Turns: 12%
13 Turns: 7%
14 Turns: 14%
15 Turns: 17%
16 Turns: 8%
17 Turns: 1%
...
23 Turns: 39%

Then its Expected Turns is much worse than the first strategy, but when all its opponents are playing the first strategy, it wins:
2er: 41.7% (baseline 50% = -8.3%)
3er: 32.7% (baseline 33.3% = -1.6%)
4er: 27.6% (baseline 25% = +2.6%)
5er: 24.3% (baseline 20% = +4.3%)
6er: 22.0% (baseline 16.6% = +5.4%)

Hopefully information like this will help avoid the bias these simulations have toward inaccurate 3+ player games by correctly rewarding high-variance strategies in games with more players.

What about attack cards, chaining Festivals and Moats, strategy 17.2b, etc? Incorporating these incurs a large coding cost, so it's outside the scope of the request.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jason Woolever
United States
Mountain View
California
flag msg tools
mbmbmbmbmb
I also cringe at expected time to buy 4 provinces, for many of the reasons you described. In my simulations, I've just ran with n players and when a game ending condition is reached, it stops. It's not much more complicated to simulate n players buying 8/12 Provinces (or even exhausting three piles), than doing a single player run. Then the reported value is win percentage. To compare two strategies, you have them compete many times.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Rob Neuhaus
United States
New York
NY
flag msg tools
Avatar
mbmbmbmbmb
Is there enough talent and interest in a Dominion AI server? Are there any pair/triple of people who are interested in writing a general Dominion AI and are willing to code in the same language?

In late December/early January, I am going to have a bit of free time for coding things.

I am considering implementing a generic Dominion server focused on AI play, where you can connect with your own AI and play over RPCs.

Alternatively, if there are some people willing to code in say, Python (or maybe it would be an excuse to learn Ruby), I'd be happy to eschew the server idea and just write a coupled game logic + AI in it.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Guy Srinivasan
United States
Kirkland
Washington
flag msg tools
Avatar
mbmbmbmbmb
Unless something unexpected comes up I plan to work on a Dominion AI after Thanksgiving until New Years Ish, and see how hard/unworkable/unexpectedly-perfect? my ideas for an AI turn out to be. I was going to use C#.
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt Sargent
United States
Portland
Oregon
flag msg tools
Avatar
mb
I think an AI server would be lots of fun. I started writing a Dominion program to play against but I haven't gotten back to it in a while. Writing an AI to compete against other people's AIs sounds wonderfully motivating. As far as languages go, Java is my language of choice.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ian Kelly
United States
Longmont
Colorado
flag msg tools
Allow me to introduce myself. I am Hexachlorophene J. Goodfortune, Kidnapper-At-Large, and Devourer of Tortoises par Excellence, at your service.
badge
If you can read this, then this sentence is false.
Avatar
mbmbmbmbmb
Okay, here's a pair of actual simulations using that format.

Smithy
10 Turns: 0.10%
11 Turns: 1.66%
12 Turns: 4.62%
13 Turns: 14.84%
14 Turns: 20.58%
15 Turns: 21.99%
16 Turns: 18.85%
17 Turns: 10.16%
18 Turns: 4.50%
19 Turns: 1.95%
20 Turns: 0.58%
21 Turns: 0.14%
22 Turns: 0.02%
23 Turns: 0.01%
Num = 10000
Tot = 10000
Min = 10
Med = 15.000000
Max = 23
Avg = 14.931700
StD = 1.739235
Avg Score = 27.000000

Treasure Map (4)
10 Turns: 0.04%
11 Turns: 0.41%
12 Turns: 2.10%
13 Turns: 4.30%
14 Turns: 7.69%
15 Turns: 11.28%
16 Turns: 13.93%
17 Turns: 14.59%
18 Turns: 13.98%
19 Turns: 11.58%
20 Turns: 8.14%
21 Turns: 5.27%
22 Turns: 3.45%
23 Turns: 1.77%
24 Turns: 0.84%
25 Turns: 0.30%
26 Turns: 0.18%
27 Turns: 0.08%
28 Turns: 0.04%
29 Turns: 0.01%
30 Turns: 0.01%
31 Turns: 0.01%
Num = 10000
Tot = 10000
Min = 10
Med = 17.000000
Max = 31
Avg = 17.320400
StD = 2.677323
Avg Score = 27.000000



And since I like to do both types of simulations, here's the result of a set of full games.

Num = 10000
Tot = 10000
Smithy 8144 0.8144
Treasure Map 2844 0.2844


Frankly, I don't see how that extra output is going to be significantly more useful than just reporting mean and standard deviation, since the distributions are close to normal.

Edit: Changed the full game simulation to a better one with fewer draws.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ian Kelly
United States
Longmont
Colorado
flag msg tools
Allow me to introduce myself. I am Hexachlorophene J. Goodfortune, Kidnapper-At-Large, and Devourer of Tortoises par Excellence, at your service.
badge
If you can read this, then this sentence is false.
Avatar
mbmbmbmbmb
And for those who are noticing that Treasure Map is remarkably bad without support from other Action cards, here's a follow-up simulation:

Num = 10000
Tot = 10000
Big Money 6078 0.6078
Treasure Map 5132 0.5132
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Rob Neuhaus
United States
New York
NY
flag msg tools
Avatar
mbmbmbmbmb
any interest in posting code or at least telling the treasure map strategy? Are you getting a 3rd and 4th treasure map?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Guy Srinivasan
United States
Kirkland
Washington
flag msg tools
Avatar
mbmbmbmbmb
Peristarkawan wrote:
Frankly, I don't see how that extra output is going to be significantly more useful than just reporting mean and standard deviation, since the distributions are close to normal.

If they're close to normal, mean and stddev is plenty! But people don't seem to post the stddev. And they don't seem to post whether or not it's normal. And I kind of assumed that the distributions weren't normal, that they were skewed towards a fatter tail on one end or the other, or possibly even two humped for Treasure Map.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
John Anderson
United States
Minnesota
flag msg tools
mbmbmbmbmb
rrenaud wrote:
any interest in posting code or at least telling the treasure map strategy? Are you getting a 3rd and 4th treasure map?
I interpret the "Treasure Map (4)" notation to mean they're buying a total of 4 treasure maps, but I could be wrong.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ian Kelly
United States
Longmont
Colorado
flag msg tools
Allow me to introduce myself. I am Hexachlorophene J. Goodfortune, Kidnapper-At-Large, and Devourer of Tortoises par Excellence, at your service.
badge
If you can read this, then this sentence is false.
Avatar
mbmbmbmbmb
puck71 wrote:
rrenaud wrote:
any interest in posting code or at least telling the treasure map strategy? Are you getting a 3rd and 4th treasure map?
I interpret the "Treasure Map (4)" notation to mean they're buying a total of 4 treasure maps, but I could be wrong.


That's correct. 4 was what I found to be optimal.

However, I discovered a bug. It was still buying up to 4 Treasure Maps even after it had already cashed them in (whoops!). I made it stop buying Treasure Maps once it matches a pair, and in this case it's actually optimal, in terms of minimizing the average number of turns, to buy as many as are available until a pair is matched, and then stop.

In terms of actual games against Big Money, it seems to be optimal to buy no more than 3 Treasure Maps. 3 is enough to give you a decent chance of going off early, and stopping there helps you cut your losses when you don't. Here's the distribution:

Treasure Map (3)
10 Turns: 0.03%
11 Turns: 0.64%
12 Turns: 3.05%
13 Turns: 5.14%
14 Turns: 8.35%
15 Turns: 12.82%
16 Turns: 13.85%
17 Turns: 14.18%
18 Turns: 13.26%
19 Turns: 9.36%
20 Turns: 6.25%
21 Turns: 4.34%
22 Turns: 3.07%
23 Turns: 2.06%
24 Turns: 1.38%
25 Turns: 0.92%
26 Turns: 0.61%
27 Turns: 0.40%
28 Turns: 0.17%
29 Turns: 0.08%
30 Turns: 0.03%
31 Turns: 0.01%
32 Turns: 0.00%
33 Turns: 0.00%
36 Turns: 0.00%
Num = 100000
Tot = 100000
Min = 10
Med = 17.000000
Max = 36
Avg = 17.213600
StD = 3.004431
Avg Score = 27.000000


And here's the result of games against various numbers of Big Money opponents:

Num = 10000
Tot = 10000
Big Money 1 5972.0 0.5972
Treasure Map 4028.0 0.4028

Num = 10000
Tot = 10000
Big Money 1 3419.83333333 0.341983333333
Big Money 2 3328.83333333 0.332883333333
Treasure Map 3251.33333333 0.325133333333

Num = 10000
Tot = 10000
Big Money 1 2470.5 0.24705
Big Money 2 2452.66666667 0.245266666667
Big Money 3 2494.0 0.2494
Treasure Map 2582.83333333 0.258283333333

Num = 10000
Tot = 10000
Big Money 1 1950.4 0.19504
Big Money 2 1940.65 0.194065
Big Money 3 1846.65 0.184665
Big Money 4 1922.06666667 0.192206666667
Treasure Map 2340.23333333 0.234023333333

Num = 10000
Tot = 10000
Big Money 1 1523.78333333 0.152378333333
Big Money 2 1580.88333333 0.158088333333
Big Money 3 1639.1 0.16391
Big Money 4 1583.06666667 0.158306666667
Big Money 5 1530.28333333 0.153028333333
Treasure Map 2142.88333333 0.214288333333
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Alex Rockwell
United States
Lynnwood
Washington
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
GreedyAlgorithm wrote:
Unless something unexpected comes up I plan to work on a Dominion AI after Thanksgiving until New Years Ish, and see how hard/unworkable/unexpectedly-perfect? my ideas for an AI turn out to be. I was going to use C#.


Cool! I hope your project is successful.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Alex Rockwell
United States
Lynnwood
Washington
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
JovenShadowcaster wrote:
My idea is to just friggin' play. Let the eggheads figure out which strategies are best -- if I do the same, it'll suck the fun right out of Dominion.


Yeah, we're nerds.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Freelance Police
United States
Palo Alto
California
flag msg tools
designer
Avatar
mbmbmbmbmb
rrenaud wrote:
Is there enough talent and interest in a Dominion AI server?


Even if you could code a "dumb" Dominion flash app that plays the Silver Strategy (and can interact with other players), I'd appreciate it. It *would* be amusing for the human players to play Dominion focusing on screwing the AI!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Joseph
United States
Ankeny
Iowa
flag msg tools
because it's all I ever wanted to be..
badge
Cloning gamers since 2003
Avatar
mbmbmbmbmb
JovenShadowcaster wrote:
My idea is to just friggin' play. Let the eggheads figure out which strategies are best -- if I do the same, it'll suck the fun right out of Dominion.


Best Post Today.

Thank You,Sir!
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jon
United States
Redmond
Washington
flag msg tools
Plaatsvervangende Schaamte
badge
Avatar
mbmbmb
Peristarkawan wrote:
Num = 10000
Tot = 10000
Big Money 1 5972.0 0.5972
Treasure Map 4028.0 0.4028

Num = 10000
Tot = 10000
Big Money 1 3419.83333333 0.341983333333
Big Money 2 3328.83333333 0.332883333333
Treasure Map 3251.33333333 0.325133333333

Num = 10000
Tot = 10000
Big Money 1 2470.5 0.24705
Big Money 2 2452.66666667 0.245266666667
Big Money 3 2494.0 0.2494
Treasure Map 2582.83333333 0.258283333333

Num = 10000
Tot = 10000
Big Money 1 1950.4 0.19504
Big Money 2 1940.65 0.194065
Big Money 3 1846.65 0.184665
Big Money 4 1922.06666667 0.192206666667
Treasure Map 2340.23333333 0.234023333333

Num = 10000
Tot = 10000
Big Money 1 1523.78333333 0.152378333333
Big Money 2 1580.88333333 0.158088333333
Big Money 3 1639.1 0.16391
Big Money 4 1583.06666667 0.158306666667
Big Money 5 1530.28333333 0.153028333333
Treasure Map 2142.88333333 0.214288333333


It amuses me that a thread entitled Against "expected number of turns" has turned into a thread about the expected number of turns Treasure Map yields Provinces.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Guy Srinivasan
United States
Kirkland
Washington
flag msg tools
Avatar
mbmbmbmbmb
jcaraway wrote:
JovenShadowcaster wrote:
My idea is to just friggin' play. Let the eggheads figure out which strategies are best -- if I do the same, it'll suck the fun right out of Dominion.


Best Post Today.

Thank You,Sir!

You might want to avoid reading posts in the Strategy section, if there's a chance they'll suck the fun right out of your game. It seems like the best strategy to me.
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Guy Srinivasan
United States
Kirkland
Washington
flag msg tools
Avatar
mbmbmbmbmb
JonPrud wrote:
Peristarkawan wrote:
Num = 10000
Tot = 10000
Big Money 1 5972.0 0.5972
Treasure Map 4028.0 0.4028

Num = 10000
Tot = 10000
Big Money 1 3419.83333333 0.341983333333
Big Money 2 3328.83333333 0.332883333333
Treasure Map 3251.33333333 0.325133333333

Num = 10000
Tot = 10000
Big Money 1 2470.5 0.24705
Big Money 2 2452.66666667 0.245266666667
Big Money 3 2494.0 0.2494
Treasure Map 2582.83333333 0.258283333333

Num = 10000
Tot = 10000
Big Money 1 1950.4 0.19504
Big Money 2 1940.65 0.194065
Big Money 3 1846.65 0.184665
Big Money 4 1922.06666667 0.192206666667
Treasure Map 2340.23333333 0.234023333333

Num = 10000
Tot = 10000
Big Money 1 1523.78333333 0.152378333333
Big Money 2 1580.88333333 0.158088333333
Big Money 3 1639.1 0.16391
Big Money 4 1583.06666667 0.158306666667
Big Money 5 1530.28333333 0.153028333333
Treasure Map 2142.88333333 0.214288333333


It amuses me that a thread entitled Against "expected number of turns" has turned into a thread about the expected number of turns Treasure Map yields Provinces.

Hardly! Those quoted numbers are how often Treasure Map beats Big Money, and contain no "expected turns" at all! The point is that comparing expected number of turns 'til Provinces doesn't necessarily yield how often Treasure Map beats Big Money.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jon
United States
Redmond
Washington
flag msg tools
Plaatsvervangende Schaamte
badge
Avatar
mbmbmb
GreedyAlgorithm wrote:
JonPrud wrote:
It amuses me that a thread entitled Against "expected number of turns" has turned into a thread about the expected number of turns Treasure Map yields Provinces.

You missed the point, it seems. Those quoted numbers are how often Treasure Map beats Big Money, and contain no "expected turns" at all! The point is that comparing expected number of turns 'til Provinces doesn't necessarily yield how often Treasure Map beats Big Money.


On the contrary. I didn't feel the need to quote the entirity of Peristarkawan's analysis. A few lines above my snippet the average time to 4 provinces was declared to be 17. My appologies for not including that fragment in my reply.

I think the analysis is interesting. Other threads have talked about how the time to 4 prov is not necessarily equal to time to winning, but can give some insight to how fast they can opperate.

It still amuses me, however.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Guy Srinivasan
United States
Kirkland
Washington
flag msg tools
Avatar
mbmbmbmbmb
JonPrud wrote:
It still amuses me, however.

Fair enough.

I guess a better thread title would be Against just "expected number of turns", since I'm not against the metric, I'm against computing that metric without the other pieces necessary to answer the question I perceive actually being asked.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jon
United States
Redmond
Washington
flag msg tools
Plaatsvervangende Schaamte
badge
Avatar
mbmbmb
Peristarkawan wrote:
Treasure Map (3)
10 Turns: 0.03%
11 Turns: 0.64%
12 Turns: 3.05%
13 Turns: 5.14%
14 Turns: 8.35%
15 Turns: 12.82%
16 Turns: 13.85%
17 Turns: 14.18%
18 Turns: 13.26%
19 Turns: 9.36%
20 Turns: 6.25%
21 Turns: 4.34%
22 Turns: 3.07%
23 Turns: 2.06%
24 Turns: 1.38%
25 Turns: 0.92%
26 Turns: 0.61%
27 Turns: 0.40%
28 Turns: 0.17%
29 Turns: 0.08%
30 Turns: 0.03%
31 Turns: 0.01%
32 Turns: 0.00%
33 Turns: 0.00%
36 Turns: 0.00%
Num = 100000
Tot = 100000
Min = 10
Med = 17.000000
Max = 36
Avg = 17.213600
StD = 3.004431
Avg Score = 27.000000


And here's the result of games against various numbers of Big Money opponents:

Num = 10000
Tot = 10000
Big Money 1 5972.0 0.5972
Treasure Map 4028.0 0.4028

Num = 10000
Tot = 10000
Big Money 1 3419.83333333 0.341983333333
Big Money 2 3328.83333333 0.332883333333
Treasure Map 3251.33333333 0.325133333333

Num = 10000
Tot = 10000
Big Money 1 2470.5 0.24705
Big Money 2 2452.66666667 0.245266666667
Big Money 3 2494.0 0.2494
Treasure Map 2582.83333333 0.258283333333

Num = 10000
Tot = 10000
Big Money 1 1950.4 0.19504
Big Money 2 1940.65 0.194065
Big Money 3 1846.65 0.184665
Big Money 4 1922.06666667 0.192206666667
Treasure Map 2340.23333333 0.234023333333

Num = 10000
Tot = 10000
Big Money 1 1523.78333333 0.152378333333
Big Money 2 1580.88333333 0.158088333333
Big Money 3 1639.1 0.16391
Big Money 4 1583.06666667 0.158306666667
Big Money 5 1530.28333333 0.153028333333
Treasure Map 2142.88333333 0.214288333333


I am not familiar with your "Big Money X" notation. Does it indicate different strategies, or is it just enumerating the different positions relative to TM around a table?

Also, do your Big Money strategies buy other VPs? If not, I would be interested in knowing how tightly correlated average time to 5 Provinces is to winning in a more than 2er game. I would expect those results to be close.

Edit:
If none of the strategies in your simulation are adaptive or interactive, these numbers surprise me. Why would Treasure Map be more likely to win in games with more players? Does your simulation randomize start position? (Please forgive me if you have covered your methodology indepth on another thread.)

Edit 2:
How are fractions of games won? Are you counting draws as fractional results?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt Sargent
United States
Portland
Oregon
flag msg tools
Avatar
mb
Wait, Treasure Map's win rate goes up as you add more players? How does that work exactly?
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jon
United States
Redmond
Washington
flag msg tools
Plaatsvervangende Schaamte
badge
Avatar
mbmbmb
noon wrote:
Wait, Treasure Map's win rate goes up as you add more players? How does that work exactly?


Yeah, I just noticed that, too. I would not have guessed that result.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Guy Srinivasan
United States
Kirkland
Washington
flag msg tools
Avatar
mbmbmbmbmb
noon wrote:
Wait, Treasure Map's win rate goes up as you add more players? How does that work exactly?

Its win rate goes down, but its relative win rate compared to how often you'd expect it to win if it was equally as good as every other strategy goes up.

Picture the following card: Cost 5. Roll a standard 6-sided die. If it lands on a 5 or a 6, you win the game. Otherwise you lose the game and skip the rest of your turns.

If you bought that card turn 1 in a 2-player game, you would lose more often than if you did not buy it. If you bought that card turn 1 in a 6-player game, you would win way more often than if you did not buy it. In one you're trying to beat the best performing deck among 1 other deck. In the other you're trying to beat the best performing deck among 5 other decks, which is harder, so riskier strategies with large payoffs if they go off are more useful.

ETA: This is what I'm talking about when I say expected number of turns doesn't give you a good picture of how the strategy performs!
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jon
United States
Redmond
Washington
flag msg tools
Plaatsvervangende Schaamte
badge
Avatar
mbmbmb
Peristarkawan wrote:
And for those who are noticing that Treasure Map is remarkably bad without support from other Action cards, here's a follow-up simulation:

Num = 10000
Tot = 10000
Big Money 6078 0.6078
Treasure Map 5132 0.5132


There is somthing fishy going on here. 6078 + 5132 > 10000, the total number of trials...
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2  Next »   | 
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.