Print

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

[Thinkaman]

Now that we have super cool simulators by the super cool Geronimoo and now also rspeer, we could potentially get something really crazy going.

Here's a novel flash "game" you might have seen before: http://boxcar2d.com/

It generates random cars and races them.  After so many, it creates a new generation of cars constructed with properties weighted according the the results of the last batch.  In theory, each generation gets better and better, converging to an optimal state.  The algorithm defines how many cars are in each batch, how many and what magnitude of "mutations" occur, and

It's not much of a stretch to see how this applies to Dominion simulation.  Take n strategies, play them all against each other 100/1k/10k times, and then do it again with random mutations of the winners.

I'm pretty sure this could find the optimized Big Money buy pattern consistently--and possibly even find finer grained tuning than we are aware of.  The algorithm would just endlessly add, change, and reorder purchase conditions until it find something better than the old best.  We can further use this to investigate optimal base strategies for any given card (given a defined play logic of course) or combination of cards, such as a full set of 10.

Of course, as the complexity space widens combinatorically by adding more mutation options, it will take longer to converge in any meaningful way. (A 10-card set would take ages to investigate all important combinations.) However, we are talking about a program that could be left to run freely, and one whose work is easily and informally distributable. (The RAM requirements would not scale, and the partial results could be shared just like any other existing simulator templates.)

Now, unless the mutation degree is set excessively high, a genetic algorithm would never make the simultaneous intuitive leaps to find a strategy like Workshop-Gardens from scratch; it would continually find that Workshop is bad incrementally and that Gardens is bad incrementally, and never evolve a good deck with both.  To investigate that sort of strategy, we would have to give it Workshop/Gardens as a starting point.  The key is that the point of this wouldn't be to "solve Dominion", just investigate optimal behavior in given sub-fields we define.

Any interest in this sort of thing?  Especially among super cool people?

[rrenaud]

Someone already wrote an AI for base dominion.  Though it's quality is hard to gauge and its code is not available.

http://boardgamegeek.com/thread/647682/masters-thesis-on-dominion-ai

I am generally skeptical of genetic algorithms, and I am biased towards trying to learn from the existing isotropic log data rather than 'from scratch'.

[Geronimoo]

Maybe if you're able to create a fitness function that is calculated by evaluating the contents of a deck instead of fitness(strategy) = #wins

The first will converge A LOT faster not needing to play out a few hundred games to determine the fitness.

[Davio]

Someone already wrote an AI for base dominion.  Though it's quality is hard to gauge and its code is not available.

http://boardgamegeek.com/thread/647682/masters-thesis-on-dominion-ai

I am generally skeptical of genetic algorithms, and I am biased towards trying to learn from the existing isotropic log data rather than 'from scratch'.

I wonder if that AI ever Workshopped Gardens.
That must be the Turing test of Dominion AIs.

I also noticed that only cards from the base game were used, meaning the AI hardly ever had to make a difficult decision like we have to do with Ambassador, Pawn, Steward and Such. And of course we know through experience that the base game is mainly about BMU+ or WS/WC/Gardens.

[Lhurgoyf]

As long as you don't try out Genetic Algorithms in the restaurant, I think it is ok.

http://xkcd.com/720/

;-)

[guided]

I wonder if that AI ever Workshopped Gardens.
That must be the Turing test of Dominion AIs.

Wellllll... an AI that can recognize when Gardens and Workshop (or Woodcutter) are both on the board and play a 100% scripted and easy-to-describe strategy will win games with those combos. I would say Workshop/Gardens is one of the very easiest winning strategies to teach to a bot.

[popsofctown]

Genetic algorithms are cool.  Thumbs up.

I have better things to do than write one though, and my processor has better things to do than run one.

[Brando Commando]

I'm not "super cool" in that I don't code, but I'm curious, like you. The closest thing I could find to an expert on the matter was a friend of mine who did his Ph.D. at MIT in AI, and he thought it was worth a shot...but was totally uninterested in giving it a shot himself.

I think by "genetic algorithm" you're talking about what I discussed with him -- essentially, making every choice the AI makes a question of its genetic code.

It seems to me this would be most interesting with a given "kingdom" set-up of 10 (or 11 with Young Witch) cards, since then you might be able (in theory) to approximate the "best player" of that given set-up.

Maybe you've already worked this out, but this is the way I imagine it going, using the choice of what to buy in the regular buy phase as an example:

Let's say I have played $2, so I only have enough money to buy a Lighthouse, a Hamlet, a Curse, a Copper, or nothing. Each of these 5 options is attached to its own distinct set of coefficients, ranging from, say, 0 to 1. The coefficients would be given, for example, for every variable that might be important -- the number of Coppers in my discard, for example, or the number of buys I have left, or the number of actions I've played this turn, or the total number of victory points in my deck, or the number of victory points in my opponent's deck.

By averaging all these coefficients for one option, I can come up with a metric for my desire to buy, say, a Lighthouse, and find it's 0.75. Then I do the same for the other 4 options, and I get, maybe, 0.65, 0.05, 0.10, and 0.30, and so my desire to by a Lighthouse is greater than my desire to buy anything else (including buying nothing), so I do that.

You could do this too for yes/no decisions or pretty much any decision in the game, I think (I haven't thought over everything).

I'm excited about this, but have no ability to implement it, so...

[ftl]

Commando, you may be thinking of a neural network instead of a genetic algorithm. Though they can go together, I suppose.

They are similar in that they are both proposed as solutions to all sorts of various problems; the problems are similar only in that we don't know how to do them. "Neural Network" and "Genetic Algorithm" are imagined as little magic bullets which you can throw at a problem of unknown complexity with unknown solutions which you don't understand, and still get out a winning answer.

I don't think it works that way.

In my humble opinion, talking about genetic algorithms is putting the cart before the horse, just a little.

They're a good way of finding local maxima in a search space. But to do that, you have to define the search space first. You have to figure out how to represent a "strategy" in dominion as a set of "genes" that can be "mutated" or can do "crossover" and so on and so forth, in such a way that it's expressive enough to capture the various ways Dominion could be played, without overly broadening it to include the vastly, vastly larger number of ways that the Dominion rules can be used to go nowhere.

And that's just as hard if not harder. Look at your own example. "The coefficients would be given, for example, for every variable that might be important..." ...but defining what variables are important is the crux of the problem in the first place. On a board, you have what, 17 piles? So if you have a variable for how many of each are in [your deck, opponent's deck, your discard, opponent's discard,  the trash, various mats] that's already overwhelming. Some of them are interchangeable in some ways (if there's more than one village around) but not for all purposes (trash-for-benefit). They interact in various ways - sometimes you want to make a buy decision based on some complex function numbers of cards in your deck (do I have enough villages to support my card-drawing engine cards in my engine deck? If I get an extra terminal, how likely is it to collide with a current one in my money deck?). And those have to be calculated separately for buying and trashing (and discarding in response to attacks) and so on. If you put in variables and coefficients for even a fraction of the different possible interactions, you've got an exponential explosion, especially as you're trying to find the best ones by essentially a biased random walk.

If you figure that out - how to represent a Dominion strategy in a compact and yet expressive way, that can be modified by a genetic algorithm or by any other form of machine learning - yeah, you're well on your way. But that's the hard part. Not coding the learning algorithm itself. Saying "genetic algorithm!" brings you little closer to an actual solution.

The original post was more possible - use something like that for incrementally modifying a predefined strategy. On the other hand, such a limited problem space makes any sort of fancy tech just not worth it  - look, if you want to know when's the optimal time to start buying duchies, there's a limited number of options, just try them all in the simulator.

There's such a narrow range between "trivial enough  that's it's not worth getting fancy" and "complex enough that even a fancy solution gets nowhere", unless you're more sophisticated about what you're doing than just throwing a generic machine learning technique at the problem. 

[rspeer]

Yeah, it's common to throw around the phrase "genetic algorithms" when one doesn't have a good plan of how to actually design the AI. People see biological evolution as a compelling example, and they forget that it takes millions of years. Watch boxcar2d for a while and reflect on the fact that 90% of the cars utterly fail at driving.

I do have a project called Golem (http://github.com/rspeer/golem) that's attempting to learn a "winningness" value for every deck by reading the isotropic game logs and fitting a function to them. It does kind of okay so far, but I believe I still have not defined the search space correctly.

For one thing, I have separate variables for every turn number, which is ridiculously expanding the space and causing strange discontinuities in its strategy. What I should really have is some linear combination of "this combo is worth X in the early game" and "this combo is worth X in the late game", for example. Two things are slowing me down: the fact that it takes about a day of solid computation time to retrain, and the fact that even once it's done I can't really evaluate whether it's smart because it doesn't know how to play a hand.

And that's one reason I started working on Dominiate, a JavaScript Dominion simulator (http://github.com/rspeer/dominiate): to implement the rules of Dominion and put together good plans for how to play a hand.

[Davio]

I wonder if that AI ever Workshopped Gardens.
That must be the Turing test of Dominion AIs.

Wellllll... an AI that can recognize when Gardens and Workshop (or Woodcutter) are both on the board and play a 100% scripted and easy-to-describe strategy will win games with those combos. I would say Workshop/Gardens is one of the very easiest winning strategies to teach to a bot.

Yeah, but that would be cheating.

The idea is that the AI just tries random things until some strategies evolve which are clearly better than others.
And to judge how good a strategy is, is hard for an AI, because it has to look at the big picture.

If it just counts VPs, it may find this combo, but also start hammering the Estates every game and lose to basic players.
However, if it focuses on getting a decent amount of $$$, it will surely fail to find it, since the average WS/Gardens deck doesn't have much more than 10 Coppers over 40+ cards...

Such a strategy is why human brains are so wonderful, it's intuitive and beautifully simple.
I very much admire our human capabilities of pattern recognition and creativity.

[rspeer]

Notwithstanding my and others' complaints about genetic algorithms, I actually think a sort of genetic algorithm would be a good way to tune an existing strategy.

A typical simulator strategy has a whole lot of numbers in it that you just have to choose based on what seems right, and try several combinations against each other. As the strategies get more complex, you won't really be able to examine the whole space of strategies like it. But you could automate a process that tries random mutations of them in the simulator, and uses the ones that win more often.

[Slow Dog]

[] you have to define the search space first. You have to figure out how to represent a "strategy" in dominion as a set of "genes" that can be "mutated" or can do "crossover" and so on and so forth, in such a way that it's expressive enough to capture the various ways Dominion could be played, without overly broadening it to include the vastly, vastly larger number of ways that the Dominion rules can be used to go nowhere.
[]
If you figure that out - how to represent a Dominion strategy in a compact and yet expressive way, that can be modified by a genetic algorithm or by any other form of machine learning - yeah, you're well on your way. But that's the hard part. Not coding the learning algorithm itself. Saying "genetic algorithm!" brings you little closer to an actual solution.

Here's a strategy representation, as used by Geronimoo's bot:

Big Money:

Code: [Select]

<player name="Big Money">
   <buy name="Province">
      <condition>
         <left type="getTotalMoney"/>
         <operator type="greaterThan" />
         <right type="constant" attribute="18.0"/>
      </condition>
   </buy>
   <buy name="Duchy">
      <condition>
         <left type="countCardsInSupply" attribute="Province"/>
         <operator type="smallerOrEqualThan" />
         <right type="constant" attribute="4.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="Gold"/>
   <buy name="Duchy">
      <condition>
         <left type="countCardsInSupply" attribute="Province"/>
         <operator type="smallerOrEqualThan" />
         <right type="constant" attribute="6.0"/>
      </condition>
   </buy>
   <buy name="Silver"/>
</player>


It doesn't appear to me that it would be difficult to represent that as some sort of sequence that's usable by a genetic algorithm, not that I've actually ever done such a thing. It would be a genetic algorithm for finding winning strategies for Dominon as played by Gerinmoos bot. Ok, it's as limited as the simulators is, and it's clear that the simulator rules don't cover the full scope of Dominion play. But there are already many threads of the form "find a winning set of simulator rules for <some board/strategy>", and this would work for those.

[guided]

Yeah, but that would be cheating.

Your Turing test isn't very robust if it can be easily cheated

(FWIW, a Workshop/Gardens strategy that fails to hammer the Estates will lose. A lot.)

[DG]

I read sections of the AI thesis http://gameprogrammer.dk/data/Developing_an_Agent_for_Dominion_using_modern_AI-approaches.pdf and it does highlight a number of the high level problems in evolutionary development. I didn't have anywhere near enough specialist mathematics to understand their solutions.


One difficulty that I hadn't realised before reading that document was the need to maintain a pool of strategies to measure other strategies against. You can't just play a new generation against itself or else the genes might become narrow and focussed, ending the evolution quickly but with a dead end. Maintaining a strong and varied gene pool for both the cross-breeding and the competition was something that I hadn't considered. It did not seem like something an amateur approach would resolve easily.