Dominion Strategy Forum

Please login or register.

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

Author Topic: Dominion Evolutionary Algorithm - Finding the optimum strategy on a given board  (Read 1520 times)

0 Members and 1 Guest are viewing this topic.

BeXXsoR

  • Pawn
  • **
  • Offline Offline
  • Posts: 3
  • Respect: +9
    • View Profile
+9

Hi everyone,

this is my first post on this forum, so first of all I'd like to say Hello to all of you.

I have used Geronimoos Simulator a lot lately, and its an amazing tool to test the effect of cards and strategies on a given board. What I have in mind now is to extend its functionality to not only let fixed strategies play against each other, but to figure out the optimal (or near-optimal) strategy on a given board on its own!

I want to use an Evolutionary Algorithm (EA) to achieve this. An EA is a heuristic algorithms that tries to solve optimization problems by imitating nature's behaviour of evolution.

Here's a quick roundup of how an EA works:
An EA starts with a random population of possible solutions (in our case, random strategies), and applies the following steps:
  • Reproduction: Two selected strategies are combined to create a new solution, meaning that the new solutions takes some parameters of the first and some of the second strategy.
  • Mutation: A random subset of the population is mutated, meaning that a random parameter of their strategy is altered randomly.
  • Evaluation: Each solution is assigned a fitness value that acts as a measure of its quality.
  • Selection: Out of all of the strategies of the starting population and the ones created in steps 2 and 3, a new population is formed by kicking out as many strategies as needed to get the population down to a given size. Strategies with a lower fitness value are more likely to be kicked out.
  • These steps are iterated until a given stopping condition is reached.
The crucial parts of implementing a good Dominion EA are:
a) The representation of Dominion strategies by as few parameters as possible, and
b) The definition of a quick to evaluate fitness function to measure the quality of a strategy


Here are my thoughts on these points:
a) The representation of Dominion strategies by as few parameters as possible
To define a strategy, I like to use Geronimoos buying rules. But these can get as complex as you like, so I have to make some restrictions:
  • Engines vs. BM are so different that it's hard to define a template that may generate both types of strategies. But as these are the two main strategies used in todays games, I like to focus on them first and ignore Slogs, Rushes, Combos for the time being.
  • I like to ignore Alt-VP cards for the time being, because they would make the template even more complex. I might add them later when the base EA works.
  • I like to ignore tax, debt, events, landmarks and some special cards as well for the same reason
My representation of a strategie looks like this:
Each strategy assigns values to 17 parameters k_1 to k_17, which are:
  • k_1, k_2, ... , k_10: Maximum number of copies the strategy wants to gain of board card 1, 2, ..., 10, resp. Valid values are 0, 1, 2 and no restriction
  • k_11: Same as k_1 to k_10 for the bane card if its in play
  • k_12, k_13: Same as k_1 to k_10 for Gold and Silver
  • k_14: Card that is check for start of greening. Valid choices are "Most-expensive card with k_i = no restriction" and "Gold"
  • k_15: Number of copies of k_14 to have in deck before greening starts. Valid values are 1, 2, 3, 4
  • k_16: Number of Provinces left in the supply before buying Duchys. Valid values are 4, 5, 7
  • k_17: What to go for if the greening condition is fulfilled, but the player doesnt have enough money to buy the next desired green card. Valid values are "Follow your usual strat" or "Treasure"
The Buy strategy with these parameters looks like this:
  • Buy Provinces if [Count in Deck(k_14) >= k_15]
  • Buy Duchys if [Count in Supply(Provinces) <= k_16]
  • Buy Estates if [Count in Supply(Provinces) <= 2]
  • Buy Gold and Silver respecting the values k_12 and k_13 if [Count in Deck(k_14) >= k_15 AND k_17 = "Treasure"]
  • Buy the most expensive kingdom card you can afforf respecting the values of k_1 to k_11. If you have the choice between two or more cards with the same cost, buy the one you have less copies of in your deck.
  • Buy Gold or Silver respecting the values k_12 and k_13
So for example a simple Big Money strategy without any actions would look like this:
  • k_1 to k_11 = 0
  • k_12 to k_13 = No Restrictions
  • k_14 = "Gold"
  • k_15 = 2
  • k_16 = 5
  • k_17 = "Treasure"
And Festival/Smithy without any treausre would look this way (lets say Festival is k_1 and Smithy is k_4):
  • k_1 and k_4 = No restrictions
  • k_2, k_3, k_5 to k_13 = 0
  • k_14 = "Festival"
  • k_15 = 4
  • k_16 = 7
  • k_17 = "Follow your strategy"

b) The definition of a quick to evaluate fitness function to measure the quality of a strategy
The hard part in this statement is the "quick to evaluate". By nature, strategies are there to compete against each other, so you cant measure their quality in a solitaire game, but have to let them play real (i.e. simulated) games vs. other strategies. I though about letting all current strategies play a littel tournament, but that would consume way to much CPU time. Therefore I came up with the idea of letting the user define 1 to 4 benchmark strategies that the new strategies have to play against. For example, these strategies could be Smithy BM ("How good is new strategy against BM), Witch & Militia ("How good does it stand against attacks) and Village & Smithy ("How does it perform vs. a base engine). The sum of the win rates against all benchmark strategies defines the fitness value of a strategy.


Before I start the implementation, I lilke to hear your opinions on this. How can i optimize the representation of a strategy? How can I generate a better and/or quicker fitness function?

And last but not least, I want to thank you, Geronimoo, for creating such a great simulator and making it open source for the community! I only can imagine how much time and energy you have invested in this tool!

Regards
BeXXsoR
Logged

JW

  • Minion
  • *****
  • Offline Offline
  • Posts: 558
  • Shuffle iT Username: JW
  • Respect: +913
    • View Profile
+1

Have you seen the Provincial AI for dominion? The write-up for that may contain useful ideas. https://graphics.stanford.edu/~mdfisher/DominionAI.html
Logged

DG

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3838
  • Respect: +2307
    • View Profile
0

If you dig back through the forums you might also find a thesis which used Dominion as a basis for AI development using mathematical methods. I'm assuming that was theoretical whereas you will be looking for practical results.
Logged

ben_king

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 132
  • formerly grsbmd
  • Respect: +483
    • View Profile
+4

Before I start the implementation, I lilke to hear your opinions on this. How can i optimize the representation of a strategy? How can I generate a better and/or quicker fitness function?

Ultimately any fitness function is going to be an approximation.  The best approximation is going to be simulating playouts, probably at least a few thousand games.  Using a simulator like Geronimoo's that has fixed rules for how each card is played, this can actually be pretty fast to do.

Testing it against a number of benchmark strategies might be an okay approximation, but it will fail miserably in some cases.  Suppose that your kingdom has (among other cards), Enchantress and Hunting Grounds.  Maybe one of your candidates likes to play something that resembles Hunting Grounds-BM.  That might play really well against all the benchmarks, but it will fail big-time against anyone who knows to pick up Enchantress.  Sure you can over-terminal to try to fight that, but the benchmarks aren't likely to select a candidate that over-terminals.  The point, I guess, is that there are way too many possible scenarios (especially in post-Empires Dominion) for the benchmarks to select good strategies.  More than ever, it depends on the board.

Unfortunately, I think even with the best genetic algorithm and fitness function, this type of approach will not come close to being able to beat good humans.  Maybe on some weak big money boards, it could get good shuffle luck and sometimes win.  But deciding what cards to buy is at best only half the skill in Dominion.  I don't know if a human-level AI is what you're aiming for, but the proposed AI will probably fall short.

If you are looking to build something human-level, you might want to look into Monte-Carlo tree search.  This is more or less what AlphaGo, plus a number of other top AIs for other games use.
Logged

trivialknot

  • Duke
  • *****
  • Offline Offline
  • Posts: 362
  • Respect: +451
    • View Profile
+1

Good luck with the evolutionary algorithm!  Even if it isn't the best AI ever, it could be a fun project, and I hope to hear more about it.

A few comments on the strategy representation:

I don't understand k_17.  For the simple Big Money strategy, it seems like k_17 doesn't matter, since either "follow your strategy" or "treasure" both lead to buying treasure.  For the Engine strategy, it doesn't usually make sense for the Engine strategy to suddenly veer into treasure during the greening phase.

One problem with your strategy parameters is that it doesn't handle card priorities well. A strategy that wants to buy Chapel may never get around to buying it because it's given lowest priority.  I'm also not sure how multiple buys are handled.  Provincial offers some ideas on how to handle card priorities, but Provincial's method is imperfect too.  You could probably go a bit crazier with the number of parameters.
Logged

dedicateddan

  • Apprentice
  • *****
  • Offline Offline
  • Posts: 291
  • Shuffle iT Username: dan brooks
  • Respect: +433
    • View Profile
+2

Well, really, there are two types of decks in dominion. Money (and to a certain extent slogs) are looking to rush VP. Engines, on the other hand, are looking to build up as big as possible before ending the game.

Consider the simple board of Village, Smithy, Market, and Chapel.

Money:
The strategy here is clear - open Smithy/Silver, pick up some treasures and then buy Provinces early and often.

Engine:
The engine wants to draw deck and then build exponentially. Here's an example of the concepts an engine might consider. Please forgive any typos I may have made.

To this end, let's define a series of concepts:
Cards to draw deck:
Terminals:
Villages:
Coins in deck:
Buys:
VP in supply:
VP deficit:
Coins/Buys to end game:
Estimated opposing coins/buys:

On turn 1 with a deck of 7 copper/3 estate, this evaluates to:
Cards to draw deck: 5
Terminals: 0
Villages: 0
Coins in deck: 7
Buys: 1
VP in supply: 80
VP deficit: 0
Coins/Buys to end game: 64/8
Estimated opposing coins/buys: 3.5/1
Since drawing deck is the early game priority, the clear opening is chapel, paired with either Market, Silver, or Village.

On turn 6, the deck might look like 4 Copper, 1 Estate, 1 Silver, 1 Market, 1 Village, 1 Chapel
Cards to draw deck: 2
Terminals: 1
Villages: 1
Coins in deck: 7
Buys: 2
VP in supply: 80
VP deficit: -2
Coins/Buys to end game: 64/8
Estimated opposing coins/buys: 6/1
Here, a Smithy would be a high priority in order to get to the point of drawing deck

On turn 10, the deck might look like 1 Copper, 3 Silver, 2 Gold, 2 Market, 2 Village, 1 Smithy, 1 Chapel
Cards to draw deck: 0
Terminals: 2
Villages: 2
Coins in deck: 15
Buys: 3
VP in supply: 74
VP deficit: -9
Coins/Buys to end game: 56/7
Estimated opposing coins/buys: 7/1
There's still plenty of time left in the game, so building more with Market/Smithy/Gold looks good

On turn 12, the deck might look like 3 Silver, 4 Gold, 3 Market, 3 Village, 2 Smithy, 1 Chapel
Cards to draw deck: -1
Terminals: 3
Villages: 3
Coins in deck: 21
Buys: 4
VP in supply: 62
VP deficit: -21
Coins/Buys to end game: 40/5
Estimated opposing coins/buys: 7/1
With VP running low, it's time to start looking at greening. Something like Province/Village/Smithy/Gold looks solid

On turn 13, the deck might look like 3 Silver, 5 Gold, 3 Market, 4 Village, 3 Smithy, 1 Chapel, 1 Province
Cards to draw deck: -1
Terminals: 4
Villages: 4
Coins in deck: 24
Buys: 4
VP in supply: 53
VP deficit: -18
Coins/Buys to end game: 32/4
Estimated opposing coins/buys: 6.5/1
Now it's really time to take points, while defending against a possible province. Buy: Province/Province/Village/Smithy

On turn 13, the deck might look like 3 Silver, 5 Gold, 3 Market, 5 Village, 4 Smithy, 1 Chapel, 3 Province
Cards to draw deck: -1
Terminals: 5
Villages: 5
Coins in deck: 24
Buys: 4
VP in supply: 35
VP deficit: -12
Coins/Buys to end game: 8/1
Estimated opposing coins/buys: 6/1
With 1 province left, the engine takes the win with Province/Duchy/Duchy/Estate
« Last Edit: April 24, 2017, 07:55:07 pm by dedicateddan »
Logged

Titandrake

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1953
  • Respect: +2052
    • View Profile
+1

If I remember right, Provincial is an evolutionary algorithm. It represents strategies by an ordered list of cards and counts. Each turn it buys the leftmost card it can afford, then decreases the count by 1.

As a word of warning, evolutionary methods sound really cool, but they tend to take a lot of compute time, and it can be hard to tune them properly (evolutionary methods are inherently pretty black box, so if they don't work right away it can be very difficult to figure out what to do next.) Still, best of luck.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

BeXXsoR

  • Pawn
  • **
  • Offline Offline
  • Posts: 3
  • Respect: +9
    • View Profile
0

I've taken a look into Provincial AI, and it is indeed very close to what I want to implement. Its buying rules follow the same main principles ("buy the most desired card that you can afford"), and it has parameters to control how many copies of each card are desired and when to start greening. Furthermore, it even considers the buying priority of cards and allows cards to be split across the buying rule, so that some copies are bought earlier and others later in the game. Thats seems like a very well designed buying template.

You could probably go a bit crazier with the number of parameters.
After reading about Provincial AI, I agree to this. I'm going to do some tests on the runtime of Geronimoos sim on my PC and adjust the number of parameters.

I don't understand k_17.  For the simple Big Money strategy, it seems like k_17 doesn't matter, since either "follow your strategy" or "treasure" both lead to buying treasure.  For the Engine strategy, it doesn't usually make sense for the Engine strategy to suddenly veer into treasure during the greening phase.
This is for engine decks without enough virtual coins to start greening. These need an option to strengthen their buying power only after they have picked up all their desired engine components. So you would choose k_17 = "Treasure" in that case.
If I increase the number of parameters, this one will probably be replaced by a combination of new ones.
Logged

JThorne

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +380
    • View Profile
+1

One thing I can recommend is to play a few hundred games against Provincial yourself just to get a feel for how well that program works.

What's interesting is that there are some BM kingdoms and slogs where it's hard to beat the AI consistently because that really is the best strategy, and the AI counts and deck tracks perfectly, so the result is almost a coin flip. In fact, some of them the AI wins more often if there's no really good complex strategy.

However, there a LOT of kingdoms where proper play will repeatedly destroy the AI.

It can't play a Gardens rush at all, and there are a number of Ironworks/Gardens kingdoms.

It can't play a megaturn. It'll settle for double Provinces, or even triples, not "getting" that you can easily build to a turn where you buy six or seven Provinces, or even three Provinces and five or more Duchies to overwhelm the rest of the Provinces.

It can't play Goons or any other VP-chip strategy, and you can beat it by hundreds of points, because it never tries building an engine that buys and trashes copper or curses for handfuls of chips at a time. Heck, you can even beat it with a KC/Monument starvation deck (my nickname for a deck which, if both players play it, results in an infinite loop of players gaining points and no cards. The official ruling from Donald X is that the loser is whoever starves to death first.)

And that program was written well before the game got REALLY complex with Dark Ages/Adventures/Empires. Not to mention all of the incredible subtle issues that players have enumerated since then that have appeared in the forum, such as thinking of progress in terms of shuffles instead of turns, tracking issues like cards missing the shuffle, or triggering a reshuffle at the wrong time. So many cards now reward careful play as well as buying strategy.

I think you have a much, much longer road ahead of you than you imagine. But it's certainly an interesting one!
Logged

BeXXsoR

  • Pawn
  • **
  • Offline Offline
  • Posts: 3
  • Respect: +9
    • View Profile
0

I played a couple games vs Provincial AI. Its an interesting bot that plays quite well on a lot of kingdoms, but plays quite bad on others. For example, I tried a kingdom containing chapel, and Provinvial AI never considered bying one in the first round, so i beat it with ease.

So i spent some time thinking how to optimize such an evolutionary algorithm, and i thought about the factors that good players include in their decision making, both at the beginning at the game and during play. That lead me to the idea of building an assessment algorithm by defining a set of factors that are important for different dominion strategies and weighting them according to the given kingdom. At any decision point in a game, the algorithm assesses each option and chooses the one with the highest score.

Of course, the weighting of a factor changes during a game. Trashing, for example, is more important at the beginning as at the end. On the other hand, victory points are best at the end of the game but generally bad at the beginning. So instead if defining a weight per factor, you have to define a function of the weight of each factor over the course of the game.

For this to work I need to identify the factors that determine the strength of a deck and the weighting functions of these on a given board. The second task can be done via evolutionary algorithms. For the first one, I need your help.
These are the factors that came to my mind:
  • Money Potential: How much money does the deck generate on average per turn?
  • Drawing Potential: Which percentage of the deck is drawn on average per turn?
  • Terminal-Collision Potential: What is the probability of a terminal collision on average per turn?
  • Trashing Potential: How many cards can the deck trash on average per turn? How many turns does the deck need to get rid of all "bad" cards (i.e. copper, curse, estate, ...). Maybe include Sifting Potential in this as well.
  • Buying Potential: How much extra buys does the deck generate on average per turn?
  • Attacking Potential: How many attacks can the deck play on average per turn?
  •   Differentiate this potential per types of attack: cursing, junking, discarding, ...
  •   Consider the counter potential that the board allwos (e.g. library as a counter to discarding attacks)
  • Counter Potential: How well can the deck counter the attacks that the board allows?
  • Victory Point Potential: How many victory points does the deck have in comparison to the opponents deck?
  • Quick-Ending-Potential: How many turns does the deck need to end the game?
  • Gaining Potential: How many cards can the deck gain on average per turn?
  • Flexibility Potential: I dont quite know yet how to measure this. I want to take into account cards like steward that allow to play them one way or another, whtaever fits best in the given situation
What do you think of these factors? What other factors do you consider in your games?
Logged

JThorne

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +380
    • View Profile
0

I hate to be that guy, but I'm not even that guy. I'm not a ranked on-line player, just an avid student of the game who probably enjoys beating the snot out of people IRL more than he should, based on reading literally every page of the wiki followed by almost every thread in this forum, digging for deep analysis and wisdom about the game.

First, you need to take every thing on your list that ends with "per turn" list and change it to "per shuffle." (per Stef.) The Shuffle is the defining boundary in decision-making (partly because your deck doesn't get better or worse when you buy cards. It only changes when you shuffle it.)

Next, you need to take the "per shuffle" thinking process and even expand THAT to "per game."

The reality is that BM is usually the wrong play, and is primarily used as a yardstick against which other strategies are measured in simulators when testing out combos. An evolutionary algorithm for the modern game is simply going to have to know how to build and play an engine from start to finish.

Engines are almost always built with a combination of trashing and gaining; trashing down, then building up. I don't see the word "payload" anywhere in your list of considerations. I don't see any reference to cost reduction. I think with the "quick ending potential" you're referring to "pile control." I don't see any reference to tempo. Or opportunity cost. Or OVER-drawing your deck. There's a lot of already-established terminology you should probably incorporate somewhere along the line.

I'd say you should perhaps start by just trying experiments with the base set, but even that is far, far more complex than you're probably imagining.

Check out this thread:

http://forum.dominionstrategy.com/index.php?topic=17171.0

Watch the video for a clinic on base set engine-building and listen to the commentary (if you can get past the music) and try to imagine how you would build those sorts of considerations into an algorithm. How is your algorithm going to figure out that it's preferable to open two terminals, and which one to play if they collide? How is it going to figure out when it makes sense to buy the single Bandit, which is emphatically not an early-game card? Is it going to be sophisticated enough to do even simple tricks like gaining cards (like Bandit Golds) and drawing them on the same turn by ordering the play of actions correctly? Is it going to figure out when to stop playing Bandit altogether so that you're not gaining Golds that will gum up the engine?

Then, once you've pondered that and have some free time, read through the neat interactions thread. Will an evolutionary algorithm "see" any of those? Why or why not? AI has to focus on playing strategies as well as buying strategies. The cans of worms just keep opening.

Logged

DG

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3838
  • Respect: +2307
    • View Profile
0

Here's a link for the old Puerto Rico evolving AI spreadsheet https://boardgamegeek.com/filepage/8766/pr-030205zip. This records the success rates of strategies then uses that data to play against you. If you haven't seen it then it may give you some new ideas.
Logged

dedicateddan

  • Apprentice
  • *****
  • Offline Offline
  • Posts: 291
  • Shuffle iT Username: dan brooks
  • Respect: +433
    • View Profile
0

I played a couple games vs Provincial AI. Its an interesting bot that plays quite well on a lot of kingdoms, but plays quite bad on others. For example, I tried a kingdom containing chapel, and Provinvial AI never considered bying one in the first round, so i beat it with ease.

So i spent some time thinking how to optimize such an evolutionary algorithm, and i thought about the factors that good players include in their decision making, both at the beginning at the game and during play. That lead me to the idea of building an assessment algorithm by defining a set of factors that are important for different dominion strategies and weighting them according to the given kingdom. At any decision point in a game, the algorithm assesses each option and chooses the one with the highest score.

Of course, the weighting of a factor changes during a game. Trashing, for example, is more important at the beginning as at the end. On the other hand, victory points are best at the end of the game but generally bad at the beginning. So instead if defining a weight per factor, you have to define a function of the weight of each factor over the course of the game.

For this to work I need to identify the factors that determine the strength of a deck and the weighting functions of these on a given board. The second task can be done via evolutionary algorithms. For the first one, I need your help.
These are the factors that came to my mind:
  • Money Potential: How much money does the deck generate on average per turn?
  • Drawing Potential: Which percentage of the deck is drawn on average per turn?
  • Terminal-Collision Potential: What is the probability of a terminal collision on average per turn?
  • Trashing Potential: How many cards can the deck trash on average per turn? How many turns does the deck need to get rid of all "bad" cards (i.e. copper, curse, estate, ...). Maybe include Sifting Potential in this as well.
  • Buying Potential: How much extra buys does the deck generate on average per turn?
  • Attacking Potential: How many attacks can the deck play on average per turn?
  •   Differentiate this potential per types of attack: cursing, junking, discarding, ...
  •   Consider the counter potential that the board allwos (e.g. library as a counter to discarding attacks)
  • Counter Potential: How well can the deck counter the attacks that the board allows?
  • Victory Point Potential: How many victory points does the deck have in comparison to the opponents deck?
  • Quick-Ending-Potential: How many turns does the deck need to end the game?
  • Gaining Potential: How many cards can the deck gain on average per turn?
  • Flexibility Potential: I dont quite know yet how to measure this. I want to take into account cards like steward that allow to play them one way or another, whtaever fits best in the given situation
What do you think of these factors? What other factors do you consider in your games?

That looks about right. It would be interesting to see a bot that tries to draw 100% of deck and build up until the piles are low.
Logged

JThorne

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +380
    • View Profile
0

I had another thought about this recently as I was helping someone with a development project.

I wonder how much help a neural network would be in devising optimal buying/playing strategies? Neural networks work best when they can be fed a vast amount of data, but I started wondering: How many full games are now stored in the servers? Does the server have all of the old Isotropic games, Making Fun games, and the new server?

A neural network works by being fed lots of data and eventually building up knowledge that's useful for pattern recognition. If you feed it the game state for every single turn of every single game ever played online, with the goal of avoiding things that lead to losses and doing things that lead to wins, I wonder if there's enough data for an NN to learn from that?

Part of the reason that I thought about that was that when developing a genetic algorithm, you're still pre-programming it with certain strategies and playing bot generations against each other. It will essentially only learn to beat itself, and it will only be as good as the strategies and play styles that you anticipate using.

That said, even a NN might need a little help; some sort of "starter" that looked at a kingdom and tried to recognize "engine" or "BM" or "slog" or "rush" just from the kingdom contents, then looked at what the players actually played and what the final score was. An NN should, at the very least, be able to learn to recognize that from existing data. It would also learn to recognize certain patterns; cards that synergize or anti-synergize, based purely on buying patterns of winners and losers, or even just buying patterns in general.

The one thing I wonder is whether there's enough data to defeat the pairing system; beginners play beginners, advanced players play advanced players, meaning that terrible play can still win the low-ranked games and great play will still lose the high-ranked games. With enough data, though, that gets overwhelmed.

Of course, it may be that only the developers have access to all that data. If so, I wonder if they've played around with that concept.
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1613
  • Shuffle iT Username: faust
  • Respect: +2077
    • View Profile
0

Well, Dominion online things have been around for less than 10 years.

Let's assume that 10000 games were played each day. That is probably generous. 10 years are about 4000 days, i.e. we probably have less than 4 billion games played. I don't have the eact number in my head, but there are at least 250 Dominion cards I think. Thus, there are more than (250 choose 10) = 2*10^17 possble games.

Roughly speaking, out of 100 million possible boards, less than 1 has been played on average. You'd need to put some serious work in to make a neural network work under these circumstances.

Logged
Since the number of points is within a constant factor of the number of city quarters, in the long run we can get (4 - ε) ↑↑ n points in n turns for any ε > 0.

Holger

  • Duke
  • *****
  • Offline Offline
  • Posts: 395
  • Respect: +183
    • View Profile
0

Well, Dominion online things have been around for less than 10 years.

Let's assume that 10000 games were played each day. That is probably generous. 10 years are about 4000 days, i.e. we probably have less than 4 billion games played. I don't have the eact number in my head, but there are at least 250 Dominion cards I think. Thus, there are more than (250 choose 10) = 2*10^17 possble games.

Roughly speaking, out of 100 million possible boards, less than 1 has been played on average. You'd need to put some serious work in to make a neural network work under these circumstances.

10,000 games times 4,000 days is 40 million, not 4 billion, so the odds are even worse.
Logged

JThorne

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +380
    • View Profile
0

Quote
Roughly speaking, out of 100 million possible boards, less than 1 has been played on average. You'd need to put some serious work in to make a neural network work under these circumstances.

But a neural network doesn't need to see every possible combination. That's the whole point. How many images of faces does an NN need to be fed before it develops the patterns necessary for facial recognition, where it can pick a face or multiple faces out of an image? Likewise, How many games of Dominion do you think it would need to be fed in order to look at a kingdom and be able to simply say "engine" or "BM" or "slog" reliably? I'm betting it would be pretty accurate given the database that exists right now.

Using similar technology to tune playstyles could also be done with targeted data analysis, but it would be a fascinating experiment just to start with the above and see what you get.
Logged

ben_king

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 132
  • formerly grsbmd
  • Respect: +483
    • View Profile
+1

Quote
Roughly speaking, out of 100 million possible boards, less than 1 has been played on average. You'd need to put some serious work in to make a neural network work under these circumstances.

But a neural network doesn't need to see every possible combination. That's the whole point. How many images of faces does an NN need to be fed before it develops the patterns necessary for facial recognition, where it can pick a face or multiple faces out of an image? Likewise, How many games of Dominion do you think it would need to be fed in order to look at a kingdom and be able to simply say "engine" or "BM" or "slog" reliably? I'm betting it would be pretty accurate given the database that exists right now.

Using similar technology to tune playstyles could also be done with targeted data analysis, but it would be a fascinating experiment just to start with the above and see what you get.

The real issue is how cards and the game state are represented.  Does the representation somehow encode that Village is +1 card +2 actions, or is it just a card called Village?  If it's seen Village and Smithy played together, can it know that Worker's Village + Avanto also work together?  And even if you can represent the vanilla bonuses in features, how do you represent Enchantress's attack or Possession's interaction?  Representation is the key issue here and in my experience non-trivial.
Logged
Pages: [1]
 

Page created in 0.111 seconds with 20 queries.