Dominion Strategy Forum

Please login or register.

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

Author Topic: Introducing DominionSim  (Read 4083 times)

0 Members and 1 Guest are viewing this topic.

Chris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 24
  • Respect: +77
    • View Profile
Introducing DominionSim
« on: March 10, 2015, 03:17:31 am »
+31

Hello!

My future wife and I are huge Dominion fans. We’ve played several games a day over the last few years, and only recently decided to take a break.  :) During that time, I’ve learned I’m a better engineer than Dominioner and devised a secret scheme to program my way out of losing more often than not. I was quickly discovered and that began a journey of building a program that could take any situation or any set of cards and produce an optimal outcome. “Should only take a couple days”.

That was quite a while ago, but today I feel it’s in a state that it needs feedback from someone who isn’t in my head.

DominionSim is a WPF app with a C++ core. It’s built to be multi-threaded and with a UI that’s easy to describe game situations. It will run best on a high end, multi-core PC.

Internally, each turn has its action possibilities enumerated and by cloning the game, the action can be played and new possibilities can be enumerated. It doesn’t cheat by knowing the cards of the opponent or what exactly it will draw. But it does track cards it’s played and can reasonably guess what draw will come next to decide on what to play.

How is it different from Geronimoo’s simulator? There is no hard coded action or trash priority list. There are some hard coded responses to cards (like trashing opponents cards with Thief), but most situations are dealt by enumerating possibilities and choosing the one which gives the best result according to the player’s code.

My goal with DominionSim is to explore interaction of cards which will generate human usable results. It's not there yet, but the essence is coming along.

So what stuff can it do?
-   Solve a turn for likely best play.
-   Analyze a game outcome from beginning, or any point in between
-   Analyze a turn for possible outcomes
-   Flexible language for coding priority gain, trash and play action lists with code complete.
-   Everything is customizable. Change any pile content to anything. No limits on player count, starting cards, cards on the board, etc.
-   Live output. Quickly iterate on games and use links to jump between states and tools.
-   Undo, redo, save and restore all state or individual brains using XML.
-   (FUTURE) Generate a new strategy that beats existing ones using genetic algorithms
-   (FUTURE) Provide great turn prediction for what to do next (without actually playing the turn)
-   (FUTURE) Flexible graphing

Stuff in progress:
-   Only the first set of cards at this moment.
-   Some cards generate large number of choices (Cellar) and can hang the game in extreme situations.
-   Borrowed some strategies from Geronimoo’s simulator to seed the brains, but long way off from a robust set.
-   It’s not done, this is beta, find the bugs.

Issues can be posted here or on git hub. Here's where to get it:
https://github.com/ChrisDS1/DominionSim/releases

Thanks to anyone who gives it a try and gives feedback! This has been fun to build and I hope can be more than a science experiment that I've filled my free time with. Thanks to Geronimoo’s simulator for the inspiration to make this one.

Analyzing game outcomes:


Flexible language with code complete. Priority list can value Play-ing a card or Trash-ing a card over Gain-ing one.


Play Witch to win the game instead of gaining Province:


Analyze turns to find possible outcomes from drawing:


Find great results from complicated hands. Here it finds a way to play cards to get enough actions, then generate Silvers with Woodcutter, then draw them with Witch.
« Last Edit: March 30, 2015, 12:06:29 am by Chris »
Logged

Seprix

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5451
  • Shuffle iT Username: Seprix
  • luck is a glitch
  • Respect: +3393
    • View Profile
    • The Border Village
Re: Introducing DominionSim
« Reply #1 on: March 11, 2015, 11:42:17 am »
0

Incredible. Hope it works for Macs, I'd love to tinker with strategies.
Logged
WOWIE I GUESS I HAVE TO DO EVERYTHING AROUND HERE
Join Dominion Discord

Fergesser

  • Thief
  • ****
  • Offline Offline
  • Posts: 95
  • Respect: +14
    • View Profile
Re: Introducing DominionSim
« Reply #2 on: March 11, 2015, 02:33:14 pm »
0

Very interesting. Props for doing that.
Logged

werothegreat

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 8029
  • Shuffle iT Username: werothegreat
  • Prepare to be boarded!
  • Respect: +9282
    • View Profile
Re: Introducing DominionSim
« Reply #3 on: March 11, 2015, 09:51:35 pm »
0

First, a round of applause for you.  *claps in a circle*

Second, maybe change CountOf(Gold, Dominion) to CountOf(Gold, Deck)?  At first I thought it was counting how many Golds were in the entire game.

Third, how many cards do you have coded, and how are you going about coding them?
Logged
Contrary to popular belief, I do not run the wiki all on my own.  There are plenty of other people who are actively editing.  Go bother them!

Check out this fantasy epic adventure novel I wrote, the Broken Globe!  http://www.amazon.com/Broken-Globe-Tyr-Chronicles-Book-ebook/dp/B00LR1SZAS/

Burning Skull

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1122
  • Shuffle iT Username: Burning Skull
  • See you in the Outpost
  • Respect: +1764
    • View Profile
Re: Introducing DominionSim
« Reply #4 on: March 12, 2015, 07:46:44 am »
+1

Is it in your plans to reveal the source code at some point?

Chris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 24
  • Respect: +77
    • View Profile
Re: Introducing DominionSim
« Reply #5 on: March 12, 2015, 12:40:04 pm »
+1

It will only run on Windows, but you can run it on a VM or with Boot Camp on a Mac.

For CountOf(Gold, Dominion), I debated this a lot because the term "Deck" is overloaded and am open to suggestions. The Dominion rules refer to "Deck" as the pile you draw from. At the end of the game, you put all cards in your deck and calculate VP.  There isn't a term for "all your cards" so I thought your "Dominion" was the appropriate term. Also what's missing is an enum for describing the draw pile deck to count of cards in there (I just didn't get around to implementing it yet).

So options could be:
  1. Dominion for "all cards" and Deck for draw pile during game.
  2. Deck for "all cards", DrawPile for draw pile during game.
  3. AllCards for "all cards" and Deck for draw pile during game.
  4. ??

I'm about a 3rd of the way through the Intrigue cards. Goal is to get to them all eventually. There's some that I will likely procrastinate on (Possession). But I also want to focus on getting the tools right too. The tools decide how the cards are authored and I've re-authored the cards like 3 times since starting. So I didn't want to accumulate a huge set of cards I would have to redo again. I think the architecture is pretty good right now, so I'm going to get Intrigue done and go from there.

Yes, I want to release the source code. One step at a time...
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 310
  • Shuffle iT Username: Ephesos
  • Respect: +262
    • View Profile
Re: Introducing DominionSim
« Reply #6 on: March 12, 2015, 01:01:37 pm »
0

Don't know exactly how you've coded this, but may I suggest Player.Cards for all of a player's cards? I guess then Cards would be an attribute of a player object, I tend to think in object oriented terms though.

Also, on a related note, is it possible to specify your opponent's Cards or Deck? I mean, you can write in protections so the strategy can't cheat, but I would reasonably, as a player, know the CountOf(Province, Opponent.Cards), and I could definitely imagine wanting to know this in a strategy.
Logged

werothegreat

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 8029
  • Shuffle iT Username: werothegreat
  • Prepare to be boarded!
  • Respect: +9282
    • View Profile
Re: Introducing DominionSim
« Reply #7 on: March 12, 2015, 01:49:44 pm »
0

It will only run on Windows, but you can run it on a VM or with Boot Camp on a Mac.

For CountOf(Gold, Dominion), I debated this a lot because the term "Deck" is overloaded and am open to suggestions. The Dominion rules refer to "Deck" as the pile you draw from. At the end of the game, you put all cards in your deck and calculate VP.  There isn't a term for "all your cards" so I thought your "Dominion" was the appropriate term. Also what's missing is an enum for describing the draw pile deck to count of cards in there (I just didn't get around to implementing it yet).

So options could be:
  1. Dominion for "all cards" and Deck for draw pile during game.
  2. Deck for "all cards", DrawPile for draw pile during game.
  3. AllCards for "all cards" and Deck for draw pile during game.
  4. ??

I'm about a 3rd of the way through the Intrigue cards. Goal is to get to them all eventually. There's some that I will likely procrastinate on (Possession). But I also want to focus on getting the tools right too. The tools decide how the cards are authored and I've re-authored the cards like 3 times since starting. So I didn't want to accumulate a huge set of cards I would have to redo again. I think the architecture is pretty good right now, so I'm going to get Intrigue done and go from there.

Yes, I want to release the source code. One step at a time...

I'd vote for option 2, with ephesos' suggestion of marking Player1.Deck, Player2.Deck, etc.
Logged
Contrary to popular belief, I do not run the wiki all on my own.  There are plenty of other people who are actively editing.  Go bother them!

Check out this fantasy epic adventure novel I wrote, the Broken Globe!  http://www.amazon.com/Broken-Globe-Tyr-Chronicles-Book-ebook/dp/B00LR1SZAS/

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1263
    • View Profile
Re: Introducing DominionSim
« Reply #8 on: March 12, 2015, 04:06:57 pm »
+1

It will only run on Windows, but you can run it on a VM or with Boot Camp on a Mac.

For CountOf(Gold, Dominion), I debated this a lot because the term "Deck" is overloaded and am open to suggestions. The Dominion rules refer to "Deck" as the pile you draw from. At the end of the game, you put all cards in your deck and calculate VP.  There isn't a term for "all your cards" so I thought your "Dominion" was the appropriate term. Also what's missing is an enum for describing the draw pile deck to count of cards in there (I just didn't get around to implementing it yet).

So options could be:
  1. Dominion for "all cards" and Deck for draw pile during game.
  2. Deck for "all cards", DrawPile for draw pile during game.
  3. AllCards for "all cards" and Deck for draw pile during game.
  4. ??

I'm about a 3rd of the way through the Intrigue cards. Goal is to get to them all eventually. There's some that I will likely procrastinate on (Possession). But I also want to focus on getting the tools right too. The tools decide how the cards are authored and I've re-authored the cards like 3 times since starting. So I didn't want to accumulate a huge set of cards I would have to redo again. I think the architecture is pretty good right now, so I'm going to get Intrigue done and go from there.

Yes, I want to release the source code. One step at a time...

Since deck is ambiguous, why not just avoid using it entirely? So AllCards, and DrawPile
Logged
"All advice is awful"
 —Count Grishnakh

Chris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 24
  • Respect: +77
    • View Profile
Re: Introducing DominionSim
« Reply #9 on: March 14, 2015, 01:55:23 am »
+3

I went with option 2 for now. So back to what everyone is familiar with: CountOf(Province, Deck) for how many Provinces you own overall.

Opponent's cards are tricky. First, you don't know how many opponents you have or your brain is only good for one kind of game. So any function has to account for all opponents, or the one winning or something else. Second, you can't always calculate what cards they have. Masquerade in a 3+ player will mean one player passes another player a card you can't see.  You can calculate the difference between your cards and the supply, yielding how many all of your opponents have. AllOpponentsCountOf(Province). This is what Geronimoo's simulator offers.

https://github.com/ChrisDS1/DominionSim/releases/tag/0.1.1.0.beta

Also:
Added Courtyard, Pawn, SecretChamber, GreatHall, ShantyTown, Steward, Conspirator, Ironworks, Baron, Scout, Duke, Harem and Nobles
Additional output while playing actions, ex: "+2 Actions"
Fixed ambiguity with Trash keyword, location is now TrashPile


« Last Edit: March 14, 2015, 02:01:50 am by Chris »
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 310
  • Shuffle iT Username: Ephesos
  • Respect: +262
    • View Profile
Re: Introducing DominionSim
« Reply #10 on: March 14, 2015, 02:45:30 am »
0

Does AllOpponentsCountOf(Province) take the TrashPile into consideration? I would think that it should; I'm not sure about officially, but I know you can always look through the trash on Goko.

Also, it would be nice to just know how many cards my opponents have in total; e.g. AllOpponentsCountOf(*), where * will match any card. Either that, or maybe LeftOpponentCountOf(*), though that has issues in solitaire. I remember having to code Dominate to just outlast all possible opposition when playing the Masq pin by going for 100 turns, and it took forever to analyze.
Logged

Sparafucile

  • Salvager
  • ****
  • Offline Offline
  • Posts: 67
  • Respect: +122
    • View Profile
Re: Introducing DominionSim
« Reply #11 on: April 02, 2015, 11:32:58 am »
0

Very nice!   Implementing all of the cards takes quite a bit of time.  I had the same thought process as you - but a couple years later, I still have 3 cards left to implement.

Have you considered building on top of an existing engine?  It may not be easy on top of the more popular ones, but Dominulator should have the infrastructure you need.   You'll find references to it in this forum.   It's a c# backend which has separated the rules of the game from the choices players make.   Just about all of the cards (excluding Adventures) have been implemented.  (though unit tests are minimal).   On my PC, it can simulate a turn from rules similar to Geronimos in about 2 microseconds.  A whole game takes about 83 microseconds. 

Theoretically, you would just have to implement this interface to get all of the cards working:

Code: [Select]
public interface IPlayerAction
{       
        int GetCountToReturnToSupply(Card card, GameState gameState);
        Card BanCardToDrawnIntoHandFromRevealedCards(GameState gameState);
        Card BanCardForCurrentPlayerPurchase(GameState gameState);       
        Card ChooseCardToPlayFirst(GameState gameState, Card card1, Card card2);       
        Card GetTreasureFromHandToPlay(GameState gameState, CardPredicate acceptableCard, bool isOptional);
        Card GetCardFromSupplyToEmbargo(GameState gameState);
        Card GetCardFromSupplyToPlay(GameState gameState, CardPredicate acceptableCard);
        Card GetCardFromSupplyToBuy(GameState gameState, CardPredicate acceptableCard);
        Card GetCardFromSupplyToGain(GameState gameState, CardPredicate acceptableCard, bool isOptional);
        Card GuessCardTopOfDeck(GameState gameState);
        Card NameACard(GameState gameState);
        Card GetCardFromTrashToGain(GameState gameState, CardPredicate acceptableCard, bool isOptional);       
        Card GetCardFromPlayToTopDeckDuringCleanup(GameState gameState, CardPredicate acceptableCard, bool isOptional);
        Card GetCardFromDiscardToTopDeck(GameState gameState, bool isOptional);
        Card GetCardFromRevealedCardsToTopDeck(GameState gameState, bool isOptional);
        Card GetCardFromRevealedCardsToTrash(GameState gameState, CardPredicate acceptableCard);
        Card GetCardFromRevealedCardsToPutOnDeck(GameState gameState);
        Card GetCardFromRevealedCardsToDiscard(GameState gameState);
        Card GetCardFromHandToDeferToNextTurn(GameState gameState);
        Card GetCardFromHandToDiscard(GameState gameState, CardPredicate acceptableCard, bool isOptional);
        Card GetCardFromHandToIsland(GameState gameState);
        Card GetCardFromHandToPassLeft(GameState gameState);       
        Card GetCardFromHandToPlay(GameState gameState, CardPredicate acceptableCard, bool isOptional);
        Card GetCardFromHandToReveal(GameState gameState, CardPredicate acceptableCard); // always optional
        Card GetCardFromHandToTopDeck(GameState gameState, CardPredicate acceptableCard, bool isOptional);       
        Card GetCardFromHandToTrash(GameState gameState, CardPredicate acceptableCard, bool isOptional, CollectionCards cardsTrashedSoFar);       
        Card GetCardFromHandOrDiscardToTrash(GameState gameState, CardPredicate acceptableCard, bool isOptional, out DeckPlacement deckPlacement);
        Card GetCardFromOtherPlayersHandToDiscard(GameState gameState, PlayerState otherPlayer);
        Card GetCardFromOtherPlayersRevealedCardsToTrash(GameState gameState, PlayerState otherPlayer, CardPredicate acceptableCard);
        int GetNumberOfCoppersToPutInHandForCountingHouse(GameState gameState, int maxNumber);
        bool ShouldPlayerDiscardCardFromDeck(GameState gameState, PlayerState player, Card card);
        bool ShouldPlayerDiscardCardFromHand(GameState gameState, Card card);
        bool ShouldRevealCardFromHandForCard(GameState gameState, Card card, Card cardFor);
        bool ShouldRevealCardFromHand(GameState gameState, Card card);
        bool ShouldPutCardInHand(GameState gameState, Card card);
        bool WantToResign(GameState gameState);       
        bool ShouldPutDeckInDiscard(GameState gameState);
        bool ShouldPutCardOnTopOfDeck(Card card, GameState gameState);
        bool ShouldTrashCard(GameState gameState, Card card);
        bool ShouldGainCard(GameState gameState, Card card);
        PlayerActionChoice ChooseBetween(GameState gameState, IsValidChoice acceptableChoice);
        DeckPlacement ChooseBetweenTrashAndTopDeck(GameState gameState, Card card);
        DeckPlacement ChooseBetweenTrashTopDeckDiscard(GameState gameState, Card card);
        string PlayerName { get; }       
        int GetCoinAmountToOverpayForCard(GameState gameState, Card card);
        int GetCoinAmountToSpendInBuyPhase(GameState gameState);
        int GetCoinAmountToUseInButcher(GameState gameState);
        void ChooseLocationForStashAfterShuffle(GameState gameState, int[] locations);
    }

And you could watch what happens during a game using this interface

Code: [Select]
public interface IGameLog
        : IDisposable
    {
        void PushScope();
        void PopScope();
        void BeginRound(PlayerState playerState);
        void EndRound(GameState gameState);
        void BeginPhase(PlayerState playerState);
        void EndPhase(PlayerState playerState);
        void BeginTurn(PlayerState playerState);
        void EndTurn(PlayerState playerState);
        void PlayerNamedCard(PlayerState playerState, Card card);
        void PlayerRevealedCard(PlayerState playerState, Card card, DeckPlacement source);
        void PlayerBoughtCard(PlayerState playerState, Card card);       
        void PlayedCard(PlayerState playerState, Card card);
        void CardWentToLocation(DeckPlacement deckPlacement);
        void ReceivedDurationEffectFrom(PlayerState playerState, Card card);
        void PlayerGainedCard(PlayerState playerState, Card card);
        void PlayerDiscardCard(PlayerState playerState, Card card, DeckPlacement source);
        void PlayerTrashedCard(PlayerState playerState, Card card);
        void PlayerPutCardInHand(PlayerState playerState, Card card);
        void PlayerTopDeckedCard(PlayerState playerState, Card card);
        void PlayerSetAsideCardFromHandForNextTurn(PlayerState playerState, Card card);
        void PlayerReturnedCardToHand(PlayerState playerState, Card card);
        void PlayerReturnedCardToPile(PlayerState playerState, Card card);
        void DrewCardIntoHand(PlayerState playerState, Card card);
        void DiscardedCard(PlayerState playerState, Card card);
        void ReshuffledDiscardIntoDeck(PlayerState playerState);
        void StartGame(GameState gameState);
        void EndGame(GameState gameState);
        void PlayerGainedPotion(PlayerState playerState, int potionCount);
        void PlayerGainedCoin(PlayerState playerState, int coinAmount);
        void PlayerGainedCoinToken(PlayerState playerState, int coinAmount);
        void PlayerGainedActions(PlayerState playerState, int actionAmount);
        void PlayerGainedBuys(PlayerState playerState, int actionAmount);
        void PlayerOverpaidForCard(Card boughtCard, int overPayAmount);
        void PlayerGainedVictoryTokens(PlayerState playerState, int amount);
        void PlayerChoseLocationForStash(PlayerState playerState, int[] positions);
    }

Logged

Chris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 24
  • Respect: +77
    • View Profile
Re: Introducing DominionSim
« Reply #12 on: April 04, 2015, 01:03:35 am »
0

I was not aware of Dominulator, it looks awesome! Someone should update the simulator page with all the options. :) What license is the Dominulator source released under?

Why write a new engine? That's a long answer. Some reasons:
1. Search turn space for best play, zero to little hard coded priority lists.
2. Use multi-threading to speed up analysis
3. Quickly iterate on strategy in UI (without recompiling)

All together these require some special attention. Also because I like modern C++ programming and no one's done this kind of tool yet. :)

So, for example, to do #1 take a look a the source for Mine:



The key part here is "view.Continuation(...)". This allows the engine to re-enter this code to try different options. It simulates each combination by cloning the game it can see and measures the result. From there it picks the best after a certain recursion rate (5 right now) and then makes the actual play. This means it can (in theory) make better decisions based on the behavior of the cards instead of a list. These continuations are recursive within cards. ThroneRoom can result in a large chain of nested Continuations and the game will plug in different decisions at each level to get the best result.

With this model, I don't need to think of how cards get played, it will figure them out:


Logged

Sparafucile

  • Salvager
  • ****
  • Offline Offline
  • Posts: 67
  • Respect: +122
    • View Profile
Re: Introducing DominionSim
« Reply #13 on: April 05, 2015, 07:45:44 pm »
0

I like the style of your code.  Very nice :).  I can understand your motivation for wanting to write it in your fav language.   I made similar choices of course when choosing to begin my simulator.   It does also run multi threaded - and the core game engine itself makes 0 decisions on behalf of the player.  One has to build up strategy code on top of the core engine. I do have a UI I have coded up which dynamically allows one to tune a strategy without recompiling.   I'll have to make an updated post on this thread I think

I like the approach of your declaration language for DiminonSim.  I will be keeping an eye on it to see if I can borrow any ideas ;)

For convenience, here's what my implementation of Mine ended up looking like.  Thought it's kind of cheating showing this code.  It's obviously just special casing a helper method.  (as the pattern of trashing and gaining another card is common - and I like code reuse ;) )   

Code: [Select]
public class Mine
        : Card
    {
        public static Mine card = new Mine();

        private Mine()
            : base("Mine", Expansion.Base, coinCost: 5, isAction: true)
        {
        }

        public override void DoSpecializedAction(PlayerState currentPlayer, GameState gameState)
        {
            currentPlayer.RequestPlayerTrashCardFromHandAndGainCard(
                        gameState,
                        card => card.isTreasure,
                        CostConstraint.UpTo,
                        3,
                        CardRelativeCost.RelativeCost,
                        isOptionalToTrash: false,
                        isOptionalToGain: false,
                        defaultLocation: DeckPlacement.Hand);
        }
    }

One interesting differentiation I see in the approach you are taking is the "try all permuation" approach to evaluating strategies.   I considered this approach, but I was worried that the branching factor would become too high.   For example, a hand with cellar and a bunch of pawns has quite a high branching factor for searching the entire space.   I have a friend who also advocated for the approach you are taking - but he never implemented it.  I'm looking forward to seeing more of your results.

It's an interesting approach you are taking with continuations.   Unfortunately modifying dominulator to use continuations would require revisiting each card.  I likely won't have time to do that.    However, I always considered that if I wanted to employ a solution that requires iterating the permutations of all available actions - would I would do is clone the gamestate at key points (probably the beginning of each players turn), and then build up a description of actions the user would take during that turn.    One description might cellar one set of cards, and a second and third description might cellar different sets.    With this approach, one would be able to look at the set of descriptions as a whole, and perhaps remove obviously uninteresting, or repetitive permutations.  I'm just musing now.   
Logged

Sparafucile

  • Salvager
  • ****
  • Offline Offline
  • Posts: 67
  • Respect: +122
    • View Profile
Re: Introducing DominionSim
« Reply #14 on: April 05, 2015, 07:49:08 pm »
0

Forgot to answer your question.   The license on dominulator is pretty loose.   I would prefer for people not to fork the code base for the purpose of taking it a different direction, but I welcome any non-profit use of it, and encourage people to contribute back into it.  It's all open source for people to play with.

Here's a quick link to the source:

https://github.com/NathanTeeuwen/Dominulator

Look through the forum for more posts on this simulator.  I've made quite a few - but not a lot since last summer

But the readme is sorely out of date.  I should update that I think.
Logged
Pages: [1]
 

Page created in 0.11 seconds with 20 queries.