Print

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

[Samuel]

I noticed this adage: There is no such thing as optimal play.

Now, in games where you have complete information such as Tic-Tac-Toe or Chess, there is optimal play (even though it may be too complicated for you to calculate it).

On the other hand, in a game like rock-paper-scissors, there is no optimal play like "always play rock", because the best play depends on what your opponent is doing: If he plays "paper", you should have played "scissors". You need what is called a mixed strategy.

Now how about Dominion? It is a card game, you don't have complete information - but this hardly ever matters, so there should be optimal play in most situations.

One exception may be Masquerade: You have to pass a card to your opponent and the best card may depend on what card your opponent is passing to you - which you don't know.

Example: In a two-player-game, my opponent has just played a Masquerade. I know (from deck-tracking and because he has just emptied his draw-pile), that he has a curse, a copper and a Mountebank in hand (and an action left to play it).
He knows (for similar reasons) that I have one curse and a copper in hand.

Should I pass him my curse or not?
In this particular situation there is no optimal play; it depends on what my opponent is doing (which I can only guess.)

Now my questions: Have you ever met such a situation with no optimal play?
Can you think of other examples - maybe even without Masquerade?

[liopoil]

One could construct such a scenario with endgame pile-dancing for sure. Possibly also with early-game decisions on what deck to go for. Or with a card like governor. Even though the decisions aren't simultaneous, a mixed strategy could be optimal because of different possible hands which can take advantage of each other in different ways.

[xyz123]

Interesting idea.

I suppose every game of Dominion has a finite (but large enough to it cannot be calculated) number of ways the game can work out. Every decision a player makes is from a finite number of options. Every time a player shuffles their deck there is a finite number of ways your deck can be ordered.

With enough computing power, you could have a theoretical brute-force AI that knows the current game state, has calculated all the ways the game could pan out and how many of those result in a win. Whenever it makes a decision it goes with which ever option leads to the greatest percentage of wins.

[Ankenaut]

The optimal play at any given time is the move that maximizes the expected value of the expectiminimax tree: https://en.m.wikipedia.org/wiki/Expectiminimax_tree

Since there is a random element to the game, even optimal play doesn't necessarily guarantee you will beat suboptimal play, so perhaps that is what is meant by this adage.

Also, it's not usually feasible to actually compute the whole tree, but that's true of most interesting games.

[Awaclus]

The optimal play at any given time is the move that maximizes the expected value of the expectiminimax tree: https://en.m.wikipedia.org/wiki/Expectiminimax_tree

Since there is a random element to the game, even optimal play doesn't necessarily guarantee you will beat suboptimal play, so perhaps that is what is meant by this adage.

Also, it's not usually feasible to actually compute the whole tree, but that's true of most interesting games.

What I believe was meant by the adage is that since you can't compute the whole tree, you never know if a play is optimal or not.

[Limetime]

Lets see if celestial chameleon can build a optimal bot in 4 days.

[qmech]

The optimal play at any given time is the move that maximizes the expected value of the expectiminimax tree: https://en.m.wikipedia.org/wiki/Expectiminimax_tree

It's not clear that Dominion can be put into this form, because of the simultaneous decisions.  (If this is in fact always possible for some clever reason I'd love to hear it!)

[liopoil]

The optimal play at any given time is the move that maximizes the expected value of the expectiminimax tree: https://en.m.wikipedia.org/wiki/Expectiminimax_tree

It's not clear that Dominion can be put into this form, because of the simultaneous decisions.  (If this is in fact always possible for some clever reason I'd love to hear it!)

The main issue is hidden information - from simultaneous decisions and that your opponent know things you don't. So I agree that this doesn't quite work, which is OP's point - that situations exist where the optimal play is to throw a weighting die between some choices, like in the scenario detailed in the OP.

[Ankenaut]

I think you can adapt expectiminimax to deal with hidden information. For instance, see https://en.m.wikipedia.org/wiki/Partially_observable_Markov_decision_process

For simultaneous moves, a mixed strategy can indeed be the optimal strategy. So in either case I'd still take issue with the adage. But help me out here: Where in Dominion do you make simultaneous moves? The only case I can think of is masquerade, and I have to think about that, but my gut reaction is that you could come up with an equivalent non-simultaneous way to express what you do there.

[Samuel]

One could construct such a scenario with endgame pile-dancing for sure.

Sounds cool. Of course, there has to be some information-hiding; otherwise it's no mixed-strategy-situation. Gear could do that information-hiding.

[eHalcyon]

One could construct such a scenario with endgame pile-dancing for sure.

Sounds cool. Of course, there has to be some information-hiding; otherwise it's no mixed-strategy-situation. Gear could do that information-hiding.

There's hidden information in the game without needing a specific card.  Even if you perfectly track the contents of your opponent's deck, you usually won't know the exact contents of their hand.  Also note that you can't always perfectly track your opponent's deck anyway, because the contents of the discard pile (other than the top card) are also hidden information.  If you haven't seen me play my Militia this shuffle, you won't know whether it's because I haven't drawn it or because I discarded it earlier without playing it.

[liopoil]

One could construct such a scenario with endgame pile-dancing for sure.

Sounds cool. Of course, there has to be some information-hiding; otherwise it's no mixed-strategy-situation. Gear could do that information-hiding.

Here is an example without using any kingdom cards. Suppose my deck and hand combined consist of 5 Gold, 1 Silver, and 3 Estates(we both know this), there are 3 provinces and 2 colonies left in the supply, and I have 3 Gold, Silver, Estate in hand (8 coins next turn, 11 this turn). We are tied on points, but you went first and you have a deck with +buy but no attacks. I reason that you have a really good chance of being able to get a colony, and a decent shot at being able to pick up an estate with it. No chance of double province, high chance of double duchy.

If I buy a colony: You have a decent shot at winning with colony/estate
If I buy province, not playing a gold: You can get a colony, taking a commanding lead, but may reason that I am likely to have a colony hand and so settle for double duchy.

If I always buy the province in this scenario, then I do poorly because you are likely to get the colony anyway. If I always buy the colony, you will always correctly get double duchy when in this scenario. You, seeing that I kept a card or two un-played, will have to adopt a mixed strategy to avoid me being able to take advantage of you; and I will also take a mixed strategy in this case. The example here isn't perfect, but hopefully you can see the potential.

As you can see, the information hiding is built-in by having hands and not being able to search through opponent's discards.

I think you can adapt expectiminimax to deal with hidden information. For instance, see

https://en.m.wikipedia.org/wiki/Partially_observable_Markov_decision_process

For simultaneous moves, a mixed strategy can indeed be the optimal strategy. So in either case I'd still take issue with the adage. But help me out here: Where in Dominion do you make simultaneous moves? The only case I can think of is masquerade, and I have to think about that, but my gut reaction is that you could come up with an equivalent non-simultaneous way to express what you do there.

In this case it is effectively simultaneous because you make your decision without knowing what decision I made, that is, whether I chose to not play a gold or whether I didn't have one.

This is also why the real pros don't play all their coppers on the opening when they aren't going to use them. Note that this is completely false; nobody actually does this and it never actually matters even slightly. In theory it totally could though!

[A Drowned Kernel]

nobody actually does this and it never actually matters even slightly

I mean the second part is true.

[Donald X.]

This is also why the real pros don't play all their coppers on the opening when they aren't going to use them. Note that this is completely false; nobody actually does this and it never actually matters even slightly. In theory it totally could though!

I typically do not play extra Coppers when buying a $2.

On turn one a big reason is just for the joy of threatening to open with a $5. It's fun and I'm not hurting anybody.

On later turns, or sometimes turn one, I may just not want to let on that I personally think this $2 this game is worth whatever I'm paying. I would like you to think that it's something to only buy when you have exactly $2; a consolation prize. So really it's just a minor tool for being mirrored less often by weaker players. I do it though.

[LastFootnote]

I play all my Treasures at once online because it's the thing to do; there's a big Play Treasures button and it is conceivably bad etiquette to play Treasures one by one, especially when you play with animations on, as I do.

In real life, I often only play the Treasures I need to buy what I'm buying, because why not?

[Watno]

The main problem with not playing all your treasures online is that your opponent can see that you did't play all your treasures. So to get the full effect out of this, you need to play all your treasures individually every turn.
I still do it in the opening and lategame sometimes.

[GendoIkari]

The main problem with not playing all your treasures online is that your opponent can see that you did't play all your treasures. So to get the full effect out of this, you need to play all your treasures individually every turn.
I still do it in the opening and lategame sometimes.

Online has other similar issues. When they play an attack, they get to know when you have a reaction in hand even if you don't want to reveal that reaction.

[werothegreat]

I'm still not getting what "mixed strategy" is supposed to be.

[liopoil]

I'm still not getting what "mixed strategy" is supposed to be.

A 'pure' strategy is one where in any given gamestate, you would make the same decision every time. In a mixed-strategy, you decide what to do based on a random variable of some sort. In rock-paper-scissors, playing rock every time is bad; the best strategy is to play randomly. In the case of RPS, uniform random is best, but usually it will be weighted somehow. So, 73% of the time I buy a Remake, 22% of the time I buy a Sea Hag, 1% of the time I buy a scout. That strategy is bad; just buy Remake 100% of the time in that scenario, but where there is relevant hidden information that you don't want the other player to know (like when you don't want your opponent to know you will always play rock), mixing it up is best.

This is also why the real pros don't play all their coppers on the opening when they aren't going to use them. Note that this is completely false; nobody actually does this and it never actually matters even slightly. In theory it totally could though!

I typically do not play extra Coppers when buying a $2.

On turn one a big reason is just for the joy of threatening to open with a $5. It's fun and I'm not hurting anybody.

On later turns, or sometimes turn one, I may just not want to let on that I personally think this $2 this game is worth whatever I'm paying. I would like you to think that it's something to only buy when you have exactly $2; a consolation prize. So really it's just a minor tool for being mirrored less often by weaker players. I do it though.

Yeah, I too actually do it occasionally. The idea behind it is fine, but it doesn't actually give any strategic advantage unless the opening buy decision is so razor-thin close that it depends on what your opponent can get. This would not be an example of a mixed-strategy anyway, because you would just always conceal it. It only works when you might prefer something costing more but decide concealing something is worth the downgrade.

[Donald X.]

In rock-paper-scissors, playing rock every time is bad; the best strategy is to play randomly.

This is a common myth.

You have an opponent! If your opponent is playing randomly... it doesn't matter what you do, the outcome is already random. If your opponent is not playing randomly... you can hope to do better than them. It's a history analysis problem (if you play more than once) or a psychology / culture analysis problem (if you play just once).

Playing randomly is only the best strategy when you know your opponent is better than you.

And of course people are bad at playing randomly. Someone trying to play randomly against you may be beatable.

[liopoil]

In rock-paper-scissors, playing rock every time is bad; the best strategy is to play randomly.

This is a common myth.

You have an opponent! If your opponent is playing randomly... it doesn't matter what you do, the outcome is already random. If your opponent is not playing randomly... you can hope to do better than them. It's a history analysis problem (if you play more than once) or a psychology / culture analysis problem (if you play just once).

Playing randomly is only the best strategy when you know your opponent is better than you.

And of course people are bad at playing randomly. Someone trying to play randomly against you may be beatable.

I am aware of this. The implicit assumption is that you should play a nash equilibrium - where the only one is full random. Any non-full random strategy can be beaten by another, so full-random is the only way to guarantee you don't lose (and you have no hope of winning against a good player).

In practice, sure, try to mind-game them, since generating random numbers is hard.

[Donald X.]

I am aware of this. The implicit assumption is that you should play a nash equilibrium - where the only one is full random. Any non-full random strategy can be beaten by another, so full-random is the only way to guarantee you don't lose (and you have no hope of winning against a good player).

In practice, sure, try to mind-game them, since generating random numbers is hard.

You mean, the only way to guarantee that the outcome is *random*. You randomly win or lose or tie. There is no way to guarantee you don't lose. And guaranteeing that the outcome is random is only good if you know you're outgunned.

Generating random numbers is easy if it's something you want to be good at; it's just hard for normal people who haven't prepared. It's much easier than the history analysis problem or psychology / culture problem. Those are how you win this game though.

That little chart where you point at a "nash equilibrium" does not, for example, include that early episode of the Simpsons. "Good old rock. Nothing beats that." You know? It's missing information that happens to be important to this game.

[liopoil]

I am aware of this. The implicit assumption is that you should play a nash equilibrium - where the only one is full random. Any non-full random strategy can be beaten by another, so full-random is the only way to guarantee you don't lose (and you have no hope of winning against a good player).

In practice, sure, try to mind-game them, since generating random numbers is hard.

You mean, the only way to guarantee that the outcome is *random*. You randomly win or lose or tie. There is no way to guarantee you don't lose. And guaranteeing that the outcome is random is only good if you know you're outgunned.

Generating random numbers is easy if it's something you want to be good at; it's just hard for normal people who haven't prepared. It's much easier than the history analysis problem or psychology / culture problem. Those are how you win this game though.

That little chart where you point at a "nash equilibrium" does not, for example, include that early episode of the Simpsons. "Good old rock. Nothing beats that." You know? It's missing information that happens to be important to this game.

I meant because generating random numbers is hard for your opponent who either doesn't have a good method in mind or doesn't even want to be random. So get in their head, remember that Simpson's episode, whatever. I don't think we actually disagree. Personally I pretty much always lead with Rock, because all the cool kids play scissors so nobody plays paper and I play a lot of cool kids.

[Donald X.]

I meant because generating random numbers is hard for your opponent who either doesn't have a good method in mind or doesn't even want to be random. So get in their head, remember that Simpson's episode, whatever. I don't think we actually disagree. Personally I pretty much always lead with Rock, because all the cool kids play scissors so nobody plays paper and I play a lot of cool kids.

Yes. Most people will just automatically be bad at randomness. Even when focusing on it.

[Samuel]

the contents of the discard pile (other than the top card) are also hidden information.

I didn't know this! We always just drop our cards on the discard pile and everyone sees everything.

Here is an example without using any kingdom cards...

I think I get what you mean. A good example. Thank you.

One more example:
I have just played a gear and now I have 8 coins in hand including a Counterband (and you know this).
If you automatically block Province, I can set aside a Silver with gear and buy a Gold instead.
So, assuming that I have set aside a Silver, you might prefer to block Gold.