Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Toskk]

Hello everyone,

Well, coming from a background in video game theorycrafting, I was surprised to find that while there are several excellent Dominion simulators, there aren't any Dominion models.. calculators that quickly evaluate the strength of Dominion cards relative to each other and to the deck without simulation. So, I've been endeavoring to create one, as usual using javascript. I've finally finished a prototype version of the calculator, and would love some feedback and debugging on it. The interface is currently very simplistic, and includes only a very limited selection of Dominion cards.. this is still a work in progress..

In brief, the calculator does the following:

1). It evaluates the purchasing power of the averaged hand (and card) in your deck.
2). Using the above as a baseline, it evaluates the relative purchasing power value of adding specific cards to the deck.

Note: To reset your deck to turn 1, simply refresh the page.

At a basic level, the calculator is quite simple. For example, it is pretty trivial to calculate the value of something like Smithy if you haven't purchased anything for your deck yet (or have purchased only Treasure).. with a brand new deck, the purchasing power of a Smithy would be 0.7 (7 Coppers in 10 total cards) * 3 draws = 2.1.. or very slightly better than if the Smithy were instead a Silver. This all gets more complicated as you add more action cards to the deck, however, particularly terminal actions. Thanks to some formulas appropriated from AdamH's thread over in the Articles forum, however, the calculator is for the most part able to correctly compensate for chaining actions and terminal collisions, altering the relative value of each card based on the probability of these events occurring.

Strengths of the Calculator

Unlike a Simulator, the calculator is theoretically able to evaluate the relative value of a huge number of cards/strategies at any point in the development of the deck, and executes instantly. All cards are constantly ranked by their relative purchasing power value, and re-updated with every purchase or trash.

Limitations of the Calculator

I don't think I need to tell anyone that there are lots of limitations to modeling Dominion.. not the least of which being that in some cases the underlying mathematics and probabilities are simply too complex to model (at least for me). Some mechanics are simply not going to be 100% accurate, and some cards may not ever be possible to model properly. So please take any result from the Calculator with a 'grain of salt'. While I am fairly confident that for the most part the relative values are accurate, in many cases the results are not very intuitive or easy to utilize. Beyond this, though, there are several very important limitations to the Calculator:

1). The relative values of each card are entirely based on the purchasing power of the deck/hand/card.. i.e. 'Big Money'. In short, this Calculator only optimizes for treasure-based strategies. It also will not ever recommend purchasing Victory cards. By definition, these are likely to hurt the purchasing power of the deck (with the rare exceptions of possibly Nobles, Harem, etc.). Theoretically, the Calculator *could* suggest when it is optimal to start 'going green'.. for example, from simulation of the Big Money strategy, it is typically optimal to start purchasing Provinces once your deck reaches ~18 total treasure, or a per-hand purchase power of ~6 and per-card purchase power of ~1.2.

2). The Calculator isn't actually playing your deck, and doesn't understand the concept of a deck, hand, and discard pile. In short, it is evaluating the purchasing power of your entire deck as a single object, rather than as a discrete number of hands. While this is not exactly 'incorrect', the implications of this method are not entirely intuitive. For example, from simulation of the Big Money + Smithy strategy, it appears optimal to try to purchase a second Smithy sometime just after turn 7 or so. The Calculator, by contrast, will typically suggest that the relative value of a second Smithy surpasses the relative value of Silver at somewhere around turn 13. These results are not actually at odds with each-other. The Calculator isn't taking into account how many turns it might be between when the second Smithy is purchased and when it might actually first be played. So while it might not be optimal to purchase a Smithy at turn 7, based on your current deck at turn 7, by the time it comes around to actually playing that Smithy your deck might be 2-3 Silver heavier, and at that point it *might* be optimal to have a Smithy in the deck. To quickly summarize the issue.. the Calculator cannot anticipate your future (in the turns after the current one) purchases, nor does it know just how soon any purchased card is going to be played. So best use of the Calculator often requires adding several cards to the deck, to evaluate the future purchasing power of the deck several turns out, based on a prediction of what your next few draws might be.. not the easiest thing in the world to do.

3). There are several mechanics that the Calculator currently does not support at all, including the effect of +buys, +2 actions, and Attack cards. While I believe that I can eventually figure out the probabilities for modeling cards like Vault, Warehouse, Salvager, etc.. I'm currently not positive about +2 action cards.. the probabilities involved with determining when they might allow for +card/+action chains are very complex. I could also possibly give an estimate for the value of Attack cards, however it would only be directly applicable to a specific opponent deck (I could probably use either a mirror deck or a Big Money deck as the opponent). I also am not positive that Duration cards are currently being modeled 100% correctly..

4). As is probably obvious given the above limitations, the Calculator is not an AI that will tell you how to win at Dominion.. it still requires a fair amount of knowledge, prediction, and decision-making to utilize (and even then Dominion is subject to a lot of random variation). Theoretically, it might be possible to use it to create an actual Dominion AI, however that would require two additional components: A). an actual understanding of deck, hand, and discard pile, and B). a method of applying the same deck evaluation calculations out into the future, examining the potential impact on the deck at some future point based on all possible purchases up to that point.

Whew.. sorry for the wall of text.. anyway, I am very interested in feedback on the Calculator. I'm definitely going to continue developing it, and would very much appreciate any testing or troubleshooting anyone would be willing to do. If there's enough interest in it, I'll also eventually find a host for the program somewhere.

Thanks,

Toskk

[popsofctown]

If it's just going to run big money, it seems like the full game bots are better.

I would expect the value of this to be investigating engine optimization.

[Toskk]

If it's just going to run big money, it seems like the full game bots are better.

I would expect the value of this to be investigating engine optimization.

Well, technically most engines actually *are* just doing Big Money.. just doing it with +draws (which can be evaluated by the average coin value they return) instead of pure treasures. Theoretically, once I figure out how to implement +2 Action cards, the Calculator should be able to evaluate any engine that is still primarily attempting to purchase high-cost Victory cards. Engines that instead attempt to 3-pile or just gain VP chips, however, are not possible to evaluate using this method.

[Geronimoo]

Well it's fun to see the average value of a hand go up or down immediately when buying/trashing a card, but I'm afraid the practical use of this is going to be limited because modeling all the card interactions will be impossible.
If you're having fun with it, please continue and we might learn something from your efforts that might be helpful to incorporate in the simulators.

[Qvist]

I tried to model this for myself (for a basic AI). So I'm glad to see that someone has the same idea.
But I dropped that because I realised that this is nearly impossible to model.
A few thoughts...

+2 Action Cards: I don't know what your intention is. If it is to get exact mathematic results, then ignore my post. But you can approach it very well.
I hope my English is understandable. If you calculate the sum of all +actions subtracted by 1 it should be greater than -1 (so terminal action cards have a value of -1, and villages of +1). One terminal action is fine. If you add another terminal action you should add a +2 action card as well to raise the sum to at least -1. So the approach would be to include the effects of all action cards if the sum is greater than -1 and otherwise to get a percentual penalty.

Avg Value per Hand: I think there's an error in your application that should be fixed. Test it with a deck of 4 Laboratories and one Gold. Of course you have an avg value of 3 per hand. But your application seems to assume an infinite deck so you draw more Golds. So a Lab has still the effect of 0.5 and a Gold of -1.6. Please take that into account.

Another approach: In my application I calculated the total value of the deck which is the total of all treasures and coins (minus the penalty) and then I calculated the number of turns to get through my deck. So 7 Coppers and 3 Estates is 2 turns (10/5). Adding a Smithy would be 11 cards, but one card draws 3 more cards, so the # turns would be (11-3)/5=1.6
I called it "turn rate". If you have a turn rate of <1, then you have the max, that means the total value of your deck. If you have a second Smithy, I calculated it against my turn rate. So if turn rate + action sum is < 0 (a approximated value for possibility of collisions), then I have a penalty. Here I have a penalty of 2-(12-6)/5=-0.8 so basically it means I can play the second Smithy about 20% of all time (I don't know if it's near the real mathematical value, but I think it's close). Maybe these thoughts help you...

Coming back to +2 Actions: So if you have an penalty, obviously the simulator could evaluate an addition of a village in your deck. So for me that was no big problem.

Further problems: But later I realised other issues. As you already mentioned +Buy is very difficult to evaluate. The maximum I can think of is: If the avg value of your deck exceeds the cost of the best card in the supply, then the simulator could recommend buying a card with +Buy. But how would recommending be valuated in numbers? I have no idea. Same goes with "Gainers" like Ironworks or Smugglers. But it gets more difficult with more complex cards. Can somebody tell me how to evaluate the mathematic possibility of a card that needs another specific card in hand to be played, like Moneylender of Baron? You want it more complicated? Obviously trashing Coppers and Estates raises the avg value of your deck. But how would you rate a card like Chapel to be buyed? Basically you need a list of cards that you want to trash, so maybe always add Copper, Curse and Estate. But maybe you also want to trash Moneylender because the possibility to draw a Copper is now too low... Next step would be choice cards: How would you rate choice cards like Steward for example? We need a comparable value of all 3 benefits (+2 cards, trash 2 cards, +$2), so the value of that card would be the highest value of the 3 choices I assume... Until here, I think it's still possible to evaluate with mathematic knowledge.

Going into the impossible: I have no idea how to evaluate Victory cards. Or let's say Goons and Bishop... Evaluating Attack cards would require knowledge of the opponents' decks. But still if we would have the data, how would we get a value of an attack card that is comparable to a value in coins? The same goes with reaction cards. Another problem you already mentioned is looking into the future. An AI would not recommend buying a Tournament if you have no provinces in your deck. Or buying a Treasure Map would give no benefit to your deck.

I like to help you in this process if I have enough time. But I think that it would be a big undertaking to get reasonably results.

[Toskk]

Hi Qvist,

Thanks for the feedback! Yes, I agree that in some areas modeling is just not going to be possible. I'm still working on trying to figure out how to model +2 action cards.. so I can't say to much about that one yet at all. I'm not sure if anything is really going to work or not.

That error you found, though.. *bleh* I hadn't even thought about the case of overdrawing the entire deck. That's going to require some significant recoding. I'll get to work on it. I really like your method of evaluating 'turns to draw the deck', too. I may actually need to switch to that mechanic if I can't fix the bug with the existing method.

I do actually have an idea for cards like Moneylender, though.. although there is one critical problem. Basically, the value of Moneylender relies on Copper being present, and we know how many Copper we have and the size of our deck. So we can directly determine the probability of drawing Moneylender and no Copper.. as long as we know how many cards are with Moneylender.. and that's the catch. The probability of drawing zero copper along with Moneylender in a 5-card hand is:

non_copper_card_# * (non_copper_card_# - 1) * (non_copper_card_# - 2) * (non_copper_card_# - 3) / (deck_size * (deck_size - 1) * (deck_size - 2) * (deck_size - 3))

However I'm not sure what to do about cases where we're drawing cards before playing Moneylender.

I'll think more on this..

[ghostofmars]

I wrote a small AI once, which was based on a similar deck evaluation. I went in a slightly different direction, as I wanted to make buy choices before implementing cards. My goal was to write a big money bot which can compete with the BMU strategy without manually setting the cutoffs.
Perhaps a short description of the program may help you (or someone else) to develop a better AI. The concept was the following:
The deck quality is the number of victory points, which will be achieved until the end of the game, if I switch to full greening at a certain point.

To illustrate this idea a little bit:
Suppose it is early in the game and I draw 8 coins. Is it better to buy gold or a province? If I buy gold, my buying power will increase and I will get more provinces later on, however I have less victory points now, which I have to compensate for in later rounds. So if my current score + the points I will get on average when buying gold is larger than my current score + 6 + the points I will get on average with the province buy, I should prefer gold to province.

Details of the implementation:
As I limited my study to BM strategy, the average coin value of the deck is trivial to determine. To calculate the chance with which I can buy a province, I made the following assumptions:
1) consider always the full deck
2) the propability distribution is gaussian
3) the deck quality is constant after this buy
4) consider only province endings
All assumptions drastically simplify the calculations, though one could image more advanced schemes, which get rid of them. The variation of the distribution is simply determined under the 2nd assumption.
To decide, which card to buy, we compare all possible resulting decks (which are few for BM) and check their deck quality, which is given as the average points they will score till the end of the game.
The propability to draw x coins is
p(x) = 0.5 * erfc( (x - avg)/sqrt(2*sigma^2) )
so that the chances for province p_P = p(8), duchy p_D = p(5)-p(8), and estate p_E = p(2)-p(5) are easiliy evaluated. The game will end when all provinces are gone, so in average after
t = province left / sum over p(8) of all players
turns. My final score is my current score + t * ( 6*p_P + 3*p_D + p_E ). I chose the buy with the largest final score.

I've tested this bot against BMU and it loses 42:54, which is propably reasonable result considering all the approximations made.

[Qvist]

So, I started a whole new retry for my AI and I need some help.

Let's say I have a 10 card deck with 1 Village and 2 Smithies and the rest are treasures and victory cards. I need the mathematical possibilities for drawing a Village and for drawing a Smithy dead ... I mean with no actions left.
How would you calculate that?
For simplicity the deck gets not reshuffled if no cards are left in the deck.
Can anyone help me?

[DStu]

http://forum.dominionstrategy.com/index.php?topic=552.0 ?

Edit: Probably not exactly what you want, but I also don't really understand what you want:

Say you have a Smithy in hand and want to play it. There are now a number of (slightly different) possible things you might want to know:
a) the probability that you draw at least one card dead
b) the average number of cards you draw dead

b) is probably the easiest. Say you draw d cards. You have t terminals and c cards in total in your discard. The average number of drawn dead cards should be just
E = d*t/c.
a) is more or less the same, you have to acount for the fact that you draw 2 or more cards dead, but this usually is small (if t is much smaller than c).

So if you have 10 cards, your first 5 cards contain a Smithy, and the second 5 contain a Village and a Smithy, the probability that you draw a Village dead is 3/5, the probability that you draw a Smithy dead is also 3/5, on average you draw 6/5>1 cards dead. The probability to draw at least one dead is of course smaller than 6/5, as this is larger than 1. To draw nothing dead, Smithy and Village have to be cards 4 and 5 in the discard, the probability for that is 1/10, so the probability to draw at least one card dead is 9/10.

[ghostofmars]

I think what Qvist is going for is the average value of a hand, probably also the average amount of cards drawn (which determines the cycling).

Assuming this I start with the no memory approximation, i.e., all cards start as completely random draw pile before drawing a new hand. The chances to draw a particular hand are

#possible permutations x product( #individual cards ) x 5! / ( total number of cards in the deck )!

Example for the 2 Smithy, 1 Village, 7 Victory/Treasure deck:

draw 4(Vi/Tr) cards and 1 Smithy:
5 possible permutations
* 2 (Smithy) * 7 * 6 * 5 * 4 (Vi/Tr)
* 5!/10! = 27.78%

draw 3(Vi/Tr) cards a Smithy and a Village:
20 possible permutations
* 2 (Smithy) * 1 (Village) * 7 * 6 * 5 (Vi/Tr)
* 5!/10! = 27.78%

here's the complete list (X = Vi/Tr, S = Smithy, V = Village)
A) X X X X X =  8.33%
B) S X X X X = 27.78%
C) V X X X X = 13.89%
D) S V X X X = 27.78%
E) S S X X X = 13.89%
F) S S V X X =  8.33%

Now I determine the average value
A trivial = 5*X
B simple: 4*X + 3*(3*X+2*0)/5 (village and smithy are dead cards)
D I will always draw all X -> 7*X
E simple: 3*X + 0 + 3*(4*X+1*0)/5
F simple: 7*X (it would be larger, but there are no more cards)

this leaves C - two cases:
1) 40% draw second smithy -> 7*X
2) 60% draw X -> 5*X

Now you just have to multiply the chances for a particular starting hand with the associated gain to predict the average hand of this deck:
[ 8.33% * 5 + 27.78% * 5.8 + 13.89% * (0.6*7 + 0.4*5) + 27.78% * 7 + 13.89% * 5.4 + 8.33% * 7 ] * X = 6.17 * X
So if all X were copper, I'd have in average 6.17 coins.

Note the importance of the 'no memory' approximation: If you want to go beyond, you'd have to keep track of which cards have been played already. E.g., the case A and C2 which both give 5*X this turn have a significant difference in the outcome for the next turn! An advanced scheme could expand the probability tree until the next reshuffle...

[Qvist]

Wow, thx ghostofmars.
That's exactly what I meant. I will analyze this and hopefully can implement this in my AI.