Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: [1]

Author Topic: The quest for a Nash Equilibrium  (Read 4017 times)

0 Members and 1 Guest are viewing this topic.

Geronimoo

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1059
  • Respect: +868
    • View Profile
    • Geronimoo's Dominion Simulator
The quest for a Nash Equilibrium
« on: August 19, 2011, 06:31:19 am »
+1

Just now I was messing around with my Simulator and the 3- and 4-player strategies. I thought I had found a Nash equilibrium for the 4-player game where players can only buy Witches, Moats and the common cards (Silver, Gold, Province, Duchy and Estates).

When I chose 3 players playing the built-in 3/4P - BM - Witch/Moat, the fourth player would always lose more if he played a different strategy. So I figured I had found the Nash Equilibrium for that game, but then I created the following bot that broke the equilibrium:

Code: [Select]
<player name="3/4P - BM - Moat/Moat/Witch/Witch">
   <buy name="Province">
      <condition>
         <left type="countCardsInDeck" attribute="Gold"/>
         <operator type="greaterThan" />
         <right type="constant" attribute="0.0"/>
      </condition>
   </buy>
   <buy name="Duchy">
      <condition>
         <left type="countCardsInSupply" attribute="Province"/>
         <operator type="smallerOrEqualThan" />
         <right type="constant" attribute="7.0"/>
      </condition>
   </buy>
   <buy name="Estate">
      <condition>
         <left type="countCardsInSupply" attribute="Province"/>
         <operator type="smallerOrEqualThan" />
         <right type="constant" attribute="3.0"/>
      </condition>
   </buy>
   <buy name="Gold"/>
   <buy name="Witch">
      <condition>
         <left type="countCardsInDeck" attribute="Witch"/>
         <operator type="smallerThan" />
         <right type="constant" attribute="2.0"/>
      </condition>
   </buy>
   <buy name="Silver">
      <condition>
         <left type="countCardsInDeck" attribute="Silver"/>
         <operator type="equalTo" />
         <right type="constant" attribute="0.0"/>
      </condition>
   </buy>
   <buy name="Moat">
      <condition>
         <left type="countCardsInDeck" attribute="Moat"/>
         <operator type="smallerThan" />
         <right type="constant" attribute="2.0"/>
      </condition>
   </buy>
   <buy name="Silver"/>
</player>

I toyed around a bit more but wasn't able to make a bot that would create a Nash Equilibrium for the specified game.

Can you??? (If you don't know what a Nash Equilibrium is : http://en.wikipedia.org/wiki/Nash_equilibrium)
Logged

Geronimoo

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1059
  • Respect: +868
    • View Profile
    • Geronimoo's Dominion Simulator
Re: The quest for a Nash Equilibrium
« Reply #1 on: August 19, 2011, 06:50:51 am »
0

This is probably (close to) the Nash Equilibrium for the 2 player version of this game:

Code: [Select]
<player name="BM - 2 Witch/1 Moat">
   <buy name="Province">
      <condition>
         <left type="countCardsInDeck" attribute="Gold"/>
         <operator type="greaterThan" />
         <right type="constant" attribute="0.0"/>
      </condition>
   </buy>
   <buy name="Duchy">
      <condition>
         <left type="countCardsInSupply" attribute="Province"/>
         <operator type="smallerOrEqualThan" />
         <right type="constant" attribute="5.0"/>
      </condition>
   </buy>
   <buy name="Estate">
      <condition>
         <left type="countCardsInSupply" attribute="Province"/>
         <operator type="smallerOrEqualThan" />
         <right type="constant" attribute="2.0"/>
      </condition>
   </buy>
   <buy name="Witch">
      <condition>
         <left type="countCardsInDeck" attribute="Witch"/>
         <operator type="smallerThan" />
         <right type="constant" attribute="1.0"/>
      </condition>
   </buy>
   <buy name="Gold"/>
   <buy name="Witch">
      <condition>
         <left type="countCardsInDeck" attribute="Witch"/>
         <operator type="smallerThan" />
         <right type="constant" attribute="2.0"/>
      </condition>
   </buy>
   <buy name="Silver">
      <condition>
         <left type="countCardsInDeck" attribute="Silver"/>
         <operator type="equalTo" />
         <right type="constant" attribute="0.0"/>
      </condition>
   </buy>
   <buy name="Moat">
      <condition>
         <left type="countCardsInDeck" attribute="Moat"/>
         <operator type="equalTo" />
         <right type="constant" attribute="0.0"/>
      </condition>
   </buy>
   <buy name="Silver"/>
</player>

It buys the first Witch over Gold and also buys a single Moat.
Logged

pst

  • Minion
  • *****
  • Offline Offline
  • Posts: 584
  • Respect: +906
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #2 on: August 19, 2011, 06:54:13 am »
0

It seems like three of your "3/4P - BM - Moat/Moat/Witch/Witch" are beaten by a variant that waits a little longer with buying Duchy if it can buy Gold instead.

(The values maybe aren't optimal, but seem to be enough for this task. It's close though, so you need several "Accurate Simulations" to see it. I would love to be able to name an arbitrary number of games.)

(Edit: In the included file I've unnecessarily copied the Estate buying rule. I thought of fiddling with those numbers too, but didn't.)
Logged

Geronimoo

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1059
  • Respect: +868
    • View Profile
    • Geronimoo's Dominion Simulator
Re: The quest for a Nash Equilibrium
« Reply #3 on: August 19, 2011, 07:43:37 am »
0

@pst: The point of this exercise isn't really to fine tune a certain bot, but to find a strategy that if played by 3 people has a higher win rate than any other strategy played by the fourth player. For instance one of this bot beats 3 of yours:

Code: [Select]
<player name="3/4P - BM - Four Moats">
   <buy name="Province">
      <condition>
         <left type="countCardsInDeck" attribute="Gold"/>
         <operator type="greaterThan" />
         <right type="constant" attribute="0.0"/>
      </condition>
   </buy>
   <buy name="Duchy">
      <condition>
         <left type="countCardsInSupply" attribute="Province"/>
         <operator type="smallerOrEqualThan" />
         <right type="constant" attribute="7.0"/>
      </condition>
   </buy>
   <buy name="Estate">
      <condition>
         <left type="countCardsInSupply" attribute="Province"/>
         <operator type="smallerOrEqualThan" />
         <right type="constant" attribute="3.0"/>
      </condition>
   </buy>
   <buy name="Gold"/>
   <buy name="Silver">
      <condition>
         <left type="countCardsInDeck" attribute="Silver"/>
         <operator type="equalTo" />
         <right type="constant" attribute="0.0"/>
      </condition>
   </buy>
   <buy name="Moat">
      <condition>
         <left type="countCardsInDeck" attribute="Moat"/>
         <operator type="smallerThan" />
         <right type="constant" attribute="4.0"/>
      </condition>
   </buy>
   <buy name="Silver"/>
</player>

This bot is really stupid because it buys 4 moats and if played by 3 players can easily be beaten.
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #4 on: August 19, 2011, 07:53:01 am »
0

"Beat" is defined as >25% winchance?
Logged

Geronimoo

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1059
  • Respect: +868
    • View Profile
    • Geronimoo's Dominion Simulator
Re: The quest for a Nash Equilibrium
« Reply #5 on: August 19, 2011, 08:00:43 am »
0

"Beat" is defined as >25% winchance?

Yes... and why not... if this game were repeated for a very large number of times and each player payed $1 to participate and the winner got $4, the ">25% win rate" player would be very very rich indeed...
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #6 on: August 19, 2011, 08:08:34 am »
0

You're right, just wanted to revert my question because when you think 1 second about it the answer is obvious.

So to be a little bit more constructive I want to stress that maybe you are looking for the Nash-equilibrium from the wrong side. I would conjecture that there will be none if you assume that 3 players play the same strategy and 1 player plays another, because you can always tune the 1 player to counter what the others do. So if they go heavy witch, play for defense, where you are less effected by the curses then them. Additionally, the moats draw the same number of cards as the witches and are less expensive. So you should be on advantage.
On the other hand, if 3 players go for defense you can easily beat them by just not attacking.

But there might be a Nash-equilibrium in the regime where each 2 players play the same strategy. Because if 2 attack and 2 defense, if you join the attackers as defender you might  end up in a worse position, and if you switch from attack to defense there is not enough attack left that defense is usefull. But of course this is all not really one-dimensional nor linear, but at least there is  more freedom with this approach than fixing the 3 vs 1.

Edit2:
For example. if you let P1 and P2 play your Moat/Moat/Witch/Witch, and P3,P4 play 4xMoat, the winchances are 26:26:22:22. If you switch one of them to {M/M/W/W,BM,4xM}, his winchance will drop.

Edit3:
3xMoat seems to behave slightly better than 4xMoat, but the effect seems to be stable. Interestingly, when you go down to 2 Moats, it is no equilibrium anymor because joining the attacking team will improve one of the defenders. But luckily, the 2xMoat is also worse than 3x Moat when played against 2xMMWW+3M, so that does not contradict the equilibrium.
« Last Edit: August 19, 2011, 08:39:14 am by DStu »
Logged

DsnowMan

  • Bishop
  • ****
  • Offline Offline
  • Posts: 122
  • Respect: +26
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #7 on: August 19, 2011, 09:08:31 am »
0

I've said it before and I'll say it again: I don't think there will be many boards where you can find Nash eq, in 2,3 or 4 player games. The strategy-set is too wide and the opportunities to react too numerous (even without attacks) that I think we'll be stuck in a big ring of near-degenerate RPS.

That being said, it will still be fun to look... I just think you could be tweaking for a long time
Logged

Razzishi

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 216
  • Shuffle iT Username: Eye Urn
  • Respect: +121
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #8 on: August 19, 2011, 11:02:12 am »
0

I've said it before and I'll say it again: I don't think there will be many boards where you can find Nash eq, in 2,3 or 4 player games. The strategy-set is too wide and the opportunities to react too numerous (even without attacks) that I think we'll be stuck in a big ring of near-degenerate RPS.

That being said, it will still be fun to look... I just think you could be tweaking for a long time

Nash's proof that such an equilibrium exists relies on there being mixed (that is, probabilistic) strategies available, which the simulator does not inherently provide.  Despite the relative lack of hidden information, exactly how much treasure your opponent had might be quite important; when someone plays 2 Copper and buys a Chapel turn 1 you really have no clue whether they'll have $5, $4, or $3 next turn.  You might have to adopt a mixed strategy because your best purchase might depend on what exactly they'll have available next turn.  Additionally, with in a game where it is feasible to play a hand size attack and follow it with Masquerade (or even Mountebank or Tournament) you may need to probabilistically determine what cards to keep when your opponent makes you discard with an action still available.  To do this optimally you would need to determine whether it's even possible that he has a Masq in hand (or can draw one later), and any such programming would be completely unavailable to users.  Thus, if my interpretation of the theory is right, it might be possible that there is no programmable Nash equilibrium.  The likelihood of this happening might be fairly low, but when combined with the fact that the simulator is not particularly good at determining the better of strategies that go 48/48/4 it seems like a hopeless task.

However, we're not being asked to look at those complicated scenarios, we're looking specifically at Witch + Moat games.  If an opponent buys Moat turn 1 one can probably assume they're going to buy a Witch (or at least have $5) turn 2, and there's nothing difficult to decide in the play of the cards.  However, when it comes to 3/4 player games and looking at opponents' decks, I'm not sure if there are really enough options available in the simulator to truly make all possible strategies available.  I guess if you make an assumption of there being exactly 4 players you can get nearly everything relevant by using "count in all opponent's decks" (that's where the apostrophe is in the simulator; it should actually be " opponents' "), and so I might expect that the result would depend on exactly how many players there are.  The only thing you can't really look at is where you're seated, and the count in other players' decks could easily be skewed based on where in the turn order you go and it's certainly possible that how your purchases are affected by the existence of cards in the opponents' decks depend on where you're sitting.  Nevertheless, by taking a count of the total number of cards or Silver or treasure you might be able to determine how many turns you've taken which when combined with the information on the opponents' decks likely provides every single piece of pertinent information.

All that said, going to the detail that the above discussion suggests might be necessary is certainly well beyond the amount of effort I'm willing to put into this.
Logged
Stop reading my signature.

WanderingWinder

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5275
  • ...doesn't really matter to me
  • Respect: +4386
    • View Profile
    • WanderingWinder YouTube Page
Re: The quest for a Nash Equilibrium
« Reply #9 on: August 19, 2011, 11:11:33 am »
0

I don't think there's (necessarily, and likely in this case specifically) a programmable NE mostly because you can actually react to your opponent - you don't have to make the decision at the same time they do, second player gets an advantage like that.

Razzishi

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 216
  • Shuffle iT Username: Eye Urn
  • Respect: +121
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #10 on: August 19, 2011, 11:36:57 am »
0

I don't think there's (necessarily, and likely in this case specifically) a programmable NE mostly because you can actually react to your opponent - you don't have to make the decision at the same time they do, second player gets an advantage like that.

Presumably the strategy would include responding to what the opponents have done, using the ability to check what's in your opponents' decks to guide those responses.  If you also used information from what's in your deck you could work out where you stand in effective turn order.  However it would be exceedingly complicated with pages of buy conditions given the limitations we have.
Logged
Stop reading my signature.

Geronimoo

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1059
  • Respect: +868
    • View Profile
    • Geronimoo's Dominion Simulator
Re: The quest for a Nash Equilibrium
« Reply #11 on: August 19, 2011, 01:33:54 pm »
0

Some people are trying to complicate things too much. The strategies are announced before the game starts and then neither player will change it in the middle of the game because of other player's actions/buys. At least that was my intention.
Logged

HiveMindEmulator

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2222
  • Respect: +2118
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #12 on: August 19, 2011, 02:20:41 pm »
0

I don't think there's (necessarily, and likely in this case specifically) a programmable NE mostly because you can actually react to your opponent - you don't have to make the decision at the same time they do, second player gets an advantage like that.
It's not really possible to solve the best way to play using this technique, but it's still at least potentially a mathematically interesting question to consider the modified game where players must specify their buy rules at the same time at the start of the game, and see if there exists a nash equilibrium for this modified game.

EDIT: oops, this is exactly what the post above me says... i guess i fail at scrolling all the way to the bottom...
Logged

pst

  • Minion
  • *****
  • Offline Offline
  • Posts: 584
  • Respect: +906
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #13 on: August 19, 2011, 05:37:25 pm »
0

@pst: The point of this exercise isn't really to fine tune a certain bot, but to find a strategy that if played by 3 people has a higher win rate than any other strategy played by the fourth player. For instance one of this bot beats 3 of yours:

I've never thought anything else. My point was to point out that your robot wasn't a nash eq, because I hastily misread your post to believe you said so. Sorry about that. I guess you did the same thing with my post.
Logged

Razzishi

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 216
  • Shuffle iT Username: Eye Urn
  • Respect: +121
    • View Profile
Re: The quest for a Nash Equilibrium
« Reply #14 on: August 20, 2011, 11:08:11 am »
0

Some people are trying to complicate things too much. The strategies are announced before the game starts and then neither player will change it in the middle of the game because of other player's actions/buys. At least that was my intention.

But part of the equilibrium strategy probably is that what you buy depends on what your opponent buys.
Logged
Stop reading my signature.
Pages: [1]
 

Page created in 0.086 seconds with 20 queries.