Print

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

[ecq]

I'd like to put together and participate in a competition where people write scripts to play fixed sets of kingdom cards optimally.

My main goal is to capture what optimal play looks like.  On the whole, our simulations are good at assessing big-picture strategies, but they lack the nuance and adaptation present in a real game.  Some examples:

• You're buying a key engine card this turn and want to avoid triggering a shuffle.
• It becomes obvious that your opponent is going for Duke/Duchy.
• You're going for Conspirator and have several available cantrips.
• The Kingdom makes Fairgrounds or Menagerie viable.
• Your opponent pulled Lighthouse from the Black Market on turn 3.
• Embargo is available.  Perhaps your opponent has even used it.

My thinking is that optimizing simulated players against fixed Kingdoms will bring out some of these nuances, and that will hopefully produce meaningful improvements to our current simulators and to our understanding of optimal play.  As a side-effect, we'd also end up with some really thorough board analysis.

First question: Would anyone participate in such a thing?

Now let's talk mechanics.  I'm open to any and all ideas of how this should work or why my thinking is wrong.

Firstly, it seems like we'd almost have to use Dominiate rather than Geronimoo's simulator.  Geronimoo's simulator is already excellent about hard-coding many of the game nuances (massive thanks for his dedication to this), but Dominiate's openness and extensibility are completely compelling.  As far as I can tell, it's possible to program any decision in the game in Dominiate, using a fully-featured programming language.  It also seems better suited to a server-side environment.

It's difficult to rank bots.  There are two problems: (1) Three bots may all beat each other in rock-paper-scissors fashion, and (2) it should not be possible to beat the current first-place bot using a functionally identical strategy.  I was thinking each bot could play each other bot 100 times and its score would be its total number of wins.  This would resolve the first problem but not the second.  I'm not sure what to do about the second, but I'm betting the answer has the words "Standard Deviation" in it.

I do think it's important to make the bots publicly viewable for educational reasons.  I also think people should be encouraged to tweak and tune the best bots to make them even better.  It'd be nice if there were some meaningful way to give credit to the authors of previous iterations.

Finding a good source of Kingdoms is tough, too.  The 2011 Championship finals seems like one good place.  We could just let people submit Kingdoms at will.  Presumably the more interesting Kingdoms would get played more.  This could also be a way to involve people who are interested in Dominion but not in simulation.

That's a long enough post for now.  Thoughts?

[DStu]

I haven't understood exactly what you are trying to do.

So we already had some informal "Simulation Challanges" here, sometimes started on a game log, sometimes on a combo. Someone post a say kingdom, posts a bot and others try to beat it. I always felt like they were great fun, at least for the some people who participated, and would love to do more of them. Or are you thinking of something more formal like a league?

I also think that Dominiate would be more fun, but before we get any reasonable results there for a competition like that 'someone' should implement the "don't kill yourself rule". I realized in "Simulation Challange: Yaron's claims" or however I called it that this rule greatly changes the results compared to Geronimoo, and writing it from hand for every bot is also a little bit distracting from the goal.

Geronimoo, any hints how you implemented it? I mean, "if VP with this buy < max op. VP OR  .. <= ... with more turns]" is quite clear, but did you do something with multiple buys?

[Davio]

I think any AI challenge is entirely different from using simulators and quite a lot harder.

Simulators are programmed by humans and then just do whatever the humans decided to do, they make no real decisions on their own.
What you'd want for an AI is when he comes across a hand like Salvager-Silver-Copper-Copper-Copper to try 3 options: Don't play Salvager, trash Silver to buy Gold and trash Copper and buy Silver. The AI has to try all of these options and decide what is best.

So you get advanced branching and pruning and eventually, the AI makes a decision.

If I had enough time, I would certainly be interested, but alas, real life demands too much of it.

It's hard to make a good AI, due to the randomness of the shuffles. How certain are you that Salvaging the Silver was better after 10 playthroughs of a couple of extra turns? How many times do you have to simulate those couple of turns to get a good idea?

It's also hard to accurately judge game state, which is critical for a good AI. A chessbot can look at how many pieces every player has and the one with the better pieces will usually have a better chance of winning. In Dominion, those parameters are more murky. One player could dive into Gardens and the other may be hammering the Provinces. Which is better? Only time would tell... One player may be building an engine that reliably gets 2 Provinces every turn, but if the Provinces are already gone, it's no use.

[DStu]

I think any AI challenge is entirely different from using simulators and quite a lot harder.

If we are really talking about an "general Domninion AI", I firstly think that we are not so far to get this going with enough people to compete against each other, and secondly that we should restrict us to the Base set (or any other collection of 25 cards excluding some hard cases), cause there are way too many special cases to capture.

And probably we should work together on one bot (maybe against special Bots) and not competing against each other.

[DG]

Having put some time into some one or two simulations I'd recommend against making this a competition

- clear advantage can be gained from improving vp purchasing rules but it's laborious and not often insightful
- as script complexity rises it becomes more difficult to measure small improvements and rare advantages
- as script complexity rises any changes will require amendments, become more time consuming, and more likely to fail through poor coding
- the best integration of play rules and purchasing rules will still go beyond the current capabilities of the simulators

[ecq]

I'm definitely not talking about a general Dominion AI.

The idea was that there would be a fixed Kingdom, so you'd be writing a script to play that particular Kingdom.  Strategies would be fairly narrow.

I guess "AI" was a bad way of putting it, because it's too big of an umbrella.  I'd consider many AI approaches cheating and strongly discourage them (probably with CPU time limits).  In a perfect world, scripts would contain decisions that a human is capable of making.  "If my Courtyard draws my Witch, put my Witch back on deck, unless the Curse pile has run out and I have a spare Gold in-hand."

To use an old AI buzzword, I was thinking of something more along the lines of expert systems.  Initially the scripts would probably look a lot like the scripts we currently write.  The winning scripts would probably contain a few optimizations of play rules.  Hopefully some of those optimizations, especially things like VP purchasing rules, could be incorporated into the simulator code.  Perhaps other scripts would explore interesting buy decisions because people would be playing with a real, full Kingdom, rather than one or two engine cards. 

- the best integration of play rules and purchasing rules will still go beyond the current capabilities of the simulators

First of all, I'm not sure this is completely true, insofar as Dominiate allows you to override essentially any decision in the game.  However, many play strategies would require some programming knowledge.  The fact that these strategies require a fair amount of programming is one of my core motivations for setting this up.  Many strategies should be easier for non-programmers to specify.  The competition would be a way to discover these strategies and motivate people to write some code to implement them.

[DG]

First of all, I'm not sure this is completely true, insofar as Dominiate allows you to override essentially any decision in the game.  However, many play strategies would require some programming knowledge.  The fact that these strategies require a fair amount of programming is one of my core motivations for setting this up.

The difficulty is that computer logic likes sequential decisions. If we take my favourite example playing a hand with {upgrade, moneylender, copper, silver, duchy} there are many choices on offer. The decision changes when we consider
- the cards in the draw deck
- managing the timing of your next shuffle
- overall quality of the deck (ventures, no other copper)
- the scores (will taking two duchies just lose you the game quicker or be the only way to overtake an opponent with a big lead?)
- the cards left in the supply and game end proximity
- other kingdom cards (farmland, cities)
- opponent's cards (smugglers)

Let's suppose we can consider all that for our simple bit of card play, and prioritise it, and square it with the unknown sequence of the draw deck. As soon as we move to more complex examples such as {upgrade, menagerie, throne, moneylender, copper, copper, duchy} the AI will be unable to play a single card in a practical amount of time since the logic required becomes immense and intractable for home developed software.

[rrenaud]

The perfect is the enemy of the good!

Sure, we'll never have a perfect Dominion bot.  That shouldn't get in the way of people trying to make a good dominion bot.

Of course, maybe it will get the state that if we gave the bot 100x more time, it will be play slightly, and then we have to evaluate a speed/quality tradeoff.  But deal with that if it becomes with a problem.

[ecq]

As soon as we move to more complex examples such as {upgrade, menagerie, throne, moneylender, copper, copper, duchy} the AI will be unable to play a single card in a practical amount of time since the logic required becomes immense and intractable for home developed software.

Most humans would struggle to know what's right in that circumstance, and the optimal answer very likely depends on chance (the next card on the deck).  We try to make good guesses based on a set of heuristics.  There's no reason we couldn't program a bot to do the same.  It also becomes much, much easier to program the bot when the Kingdom is fixed.  You told the bot to buy every one of those cards. 

Menagerie is probably a worst-case scenario for bots.  Maybe it's too complicated to handle with currently-available code.  That doesn't mean it needs to stay that way forever or that we should throw our hands up.  With the right set of helper functions, the problem could become more manageable.

[DStu]

First of all, I'm not sure this is completely true, insofar as Dominiate allows you to override essentially any decision in the game. 

I also don't really see the problem given we just optimze on one kingdom. That's more or less what we did in ~10 Simulation Challanges already, just that we now take it to Dominiate, which gives more freedom because we can't just specify buyrules, but also playrules.

And, given that we take the sets from the final, that we get theory-approved sets which should feature >1 way to the winning.

[DG]

Most humans would struggle to know what's right in that circumstance, and the optimal answer very likely depends on chance (the next card on the deck).  We try to make good guesses based on a set of heuristics.  There's no reason we couldn't program a bot to do the same.

Computers don't guess. You can start to make computer decisions by weighting probable events and their benefits but that's a big step froward from where the simulators are right now. The simulators are currently making a series of discrete decisions based on the cards in hand (or do simple counting to predict wishing wells say).

[ecq]

Computers can absolutely guess and act upon heuristics.

It's trivial to write a bot that buys, say, Gold 60% of the time when it has at least one Gold, and Harem the other 40%.

Similarly, they can weight the values of various circumstances.  It's simple to write a bot that, say, buys a cantrip with $3 if the expected value of each card in the deck is > $2 and buys a Silver otherwise.  Maybe you value actions more than Silver in your deck, though.  So you change the weights.  You guess that it's best to buy a silver if the expected value of each card is around $1.5.

It's not hard to build more complicated examples.  The hard part is knowing what value to assign different scenarios.