Print

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

[rrenaud]

Has anyone seen/played with this?

http://graphics.stanford.edu/~mdfisher/DominionAI.html

[Schneau]

That looks really cool! I remember seeing something similar here, but this new one looks more well-formed and explained. I haven't read the whole thing yet, but I'm excited to, since I do research in evolutionary algorithms.

[timchen]

Looks pretty much like an automated Geronimoo's simulator.

The author is amazing however! So many interesting projects!

[werothegreat]

Glancing through, I'm rather staggered that the leading strategy in a kingdom with Goons, City and Nobles, is to buy all the Cities and all the Nobles, but only one Goons.  Now that's just a waste of Actions.

[dondon151]

Glancing through, I'm rather staggered that the leading strategy in a kingdom with Goons, City and Nobles, is to buy all the Cities and all the Nobles, but only one Goons.  Now that's just a waste of Actions.

That's only the leading strategy at one point in the AI evolutionary process.

[blueblimp]

Interesting, but the example strategies in the write-up aren't convincing. The 2nd kingdom obviously wants a KC-Bridge megaturn, which the AI didn't find. The 3rd kingdom is complex, but the bot's strategy doesn't seem like one of the good options available.

I also wish the bot's isotropic name were given, so that I can see its rating.

[meandering mercury]

I know of the author personally (although I probably only talked to him once or twice). He was something of a minor legend. His roommate was my TA for a class once and he told me that the author had some video game (Warcraft 3?) AI that would play against other humans and was ranked quite well on the leaderboard (better than most hobby players).

I have a feeling that there is an AI player rampaging on Isotropic, feeding on hapless human victims. You can download the executable and play against the AI using the built-in interface.

If you read over the documentation you'll find that there is some sophistication here, including the ability to know when to remodel Gold into Province or knowing what to Salvage. Also of note is that the fact that it sounds like the author is *capable* of writing more powerful ("classic" machine learning) AI engines but *chooses* not to in order to make the results useful to human players.

I'm a level 35 player. I played 3 games with the AI:

Game 1: Won 34 pts to 28 pts the first game: mostly a Bishop game that it seemed to play well.

Game 2: Won 27 to 24, using Chapel, Bazaar, Courtyard, 1 Explorer + 1 Expand against a Courtyard/BM? strategy (hard to tell exactly what AI is doing because log isn't as pretty) -- felt pretty close though. I think I only won because I Expanded Province -> Province to deplete the pile, but then again because the UI is more clumsy I didn't realize I had overtrashed my deck until it was too late, and then had to spend some time rebuilding.

Game 3: Won 83 to 47 last game. Key cards: Throne Room, Gardens, Village, Monument, Council Room, Loan. I used a draw your deck + play zillions of Monuments strategy and beat the AI's BM-like strategy fairly solidly.

Overall, quite impressive for an AI although I don't expect it to beat good players on engine boards. I get the impression that the AI buys a province every time it has $8+ so it just isn't setup for megaturns. I think it would play BM-style boards quite well, however.

[Dsell]

If I read correctly, it will basically always buy one of the most expensive cards it can afford, which is often going to be a mistake (unless this was just when testing optimal strategies for a particular kingdom). That would explain always buying Province with $8+.

[timchen]

You didn't read it correctly.

[lespeutere]

I was curious whether it was a f.ds member doing this stuff so I checked the forum member map and there is one guy based in Palo Alto: WrathOfGlod (presumably better known by his iso handle Michael Harris). So maybe.. ;-)

[DG]

This does seem to be an interesting AI since it is learning and evaluating before a game is played, in order to decide a purchasing strategy that it will execute in the coming game. So a limitation immediately arises that the predetermined strategy does not account for draws, the deck contents, and the opponent's strategy. It offers instead a purchasing strategy that has suited a variety of draws and decks in the past. The Goko bots seem to have an awareness of the game state but only a general purchasing strategy that applies to all kingdoms.

As with Geronimoo's simulator, the results seem heavily dependent upon good card play rules that are hard written into the software. Again big advantages can be gained over the Goko bots if these play rules exclude trashing golds with transmute, for example. The author states however that the buy and play rules are largely disconnected, and that good play strategies rarely understand long term behavior of the AI. This is true up to a point, but that point becomes a large barrier as the AI gets better. Good play should buy cards to support card play, card play that provides the right coins needed for purchasing.

If the author is reading this then I'd suggest running a lot of tests on Base set + Hinterlands kingdoms. These have a lot of treasure based decks with limited trashing that might suit AI analysis. The Goko bots can play this combination quite well (compared to other expansions). It would also be a good test of the learning process to see if the AI can find heavy investment in highways or fool's gold.

[dondon151]

Interesting, but the example strategies in the write-up aren't convincing. The 2nd kingdom obviously wants a KC-Bridge megaturn, which the AI didn't find.

I don't quite follow. I think its biggest problem is definitely prioritizing Bridge and FV over Chapel, but the rest of its buy strategy looks fit for a KC-Bridge megaturn.

[techmatt]

The important thing to remember about the AI is that it is mostly focused on finding good purchasing strategies.  To keep training times reasonable, it only uses deterministic strategies when deciding how to play cards.  After it determines what its general buy strategies are, it *should* switch to a more advanced strategy for playing cards that resembles the techniques used for say, Chess and Go AIs, but I haven't implemented this yet.  Consequently, it will not be as effective at playing against humans as it could be.

I haven't really spent enough time generating interesting strategies.  In cases where there is a classic strategy such as king's court + bridge, it will typically converge to it; for example http://graphics.stanford.edu/~mdfisher/Images/Dominion/KCBridge.png
In cases where it doesn't, remember that sometimes the "megaturn" strategy is not always the best one.

The "greedily buy provinces" can be easily changed.  See for example http://graphics.stanford.edu/~mdfisher/Images/Dominion/ProvinceBuys.png where it buys a Wharf and two Gold before its first Province.  The only reason I don't default to this behavior is that it makes the visualizations even larger and consequently harder to read.

As far as playing on Isotropic goes, it is currently around level 23 but really hasn't played as many games as it needs to for this to be a good evaluation.  There are a lot of challenges to getting it to play well, and it is greatly hindered by the fact that it can't train for as long as it needs to, so converges to sub-optimal strategies.  I will focus more on this once I implement more adaptive card play behavior.

One of the hardest challenges for the AI is how to handle things that mix buy and play strategies.  Sometimes, in response to how you or your opponent's buys are going, it makes sense to change what you are purchasing.  For example, if you go through your 2nd shuffle without a 5-coin turn, you might re-evaluate what you are purchasing.  This is a very difficult behavior to encode.

[Axxle]

Interesting, but the example strategies in the write-up aren't convincing. The 2nd kingdom obviously wants a KC-Bridge megaturn, which the AI didn't find. The 3rd kingdom is complex, but the bot's strategy doesn't seem like one of the good options available.

Read again, I think it did find it: " For many kingdoms, the AI will have no trouble capturing "classic" strategies in a reasonable number of generations. For example, the canonical "king's court + bridge" game: "

[WrathOfGlod]

I was curious whether it was a f.ds member doing this stuff so I checked the forum member map and there is one guy based in Palo Alto: WrathOfGlod (presumably better known by his iso handle Michael Harris). So maybe.. ;-)

Lol, not me. I wish I was this gosu

[Axxle]

One of the hardest challenges for the AI is how to handle things that mix buy and play strategies.  Sometimes, in response to how you or your opponent's buys are going, it makes sense to change what you are purchasing.  For example, if you go through your 2nd shuffle without a 5-coin turn, you might re-evaluate what you are purchasing.  This is a very difficult behavior to encode.

My first thought is that it sounds like what it needs is a feel for "how long is this game going to last" and adapt strategy that way.  It does sound like a very hard problem to solve though.

[techmatt]

My first thought is that it sounds like what it needs is a feel for "how long is this game going to last" and adapt strategy that way.  It does sound like a very hard problem to solve though.

Predicting the end of the game is pretty easy.  It's just a supervised learning problem that can be solved with fairly standard techniques such as a support vector machine: http://en.wikipedia.org/wiki/Support_vector_machine

The more challenging problem is changing what you're going to purchase in response to an event besides the end of the game.  For example, consider a kingdom with Witch.  The naive thing to do, which is what the AI is currently doing, is to say you want to buy either 0, 1, or 2 witches.  But this is pretty poor play in some situations.  If you got unlucky in your 2nd shuffle and got no 5-coin turns, you won't be able to buy a Witch until fairly late in the game.  In this case, you might not want to buy a 2nd witch because the curses might be essentially depleted before you get to play it.  Likewise, your opponent might want to take advantage of your unluckiness and make sure to get a 2nd witch.  In either case, the players are adapting their buy strategy to an event besides the end of the game (in this case, the # of curses remaining).  It's possible to try and encode all these features, but there are such a huge # of situations this isn't likely to be feasible or effective.

[DG]

Has the AI separate purchasing rules for 3/4 and 5/2 starts? Quite often an initial purchase of a terminal action on turns 3 or 4 will dictate the nature of a deck. For example a 4/3 start might suggest a militia but if you have a 5/2 start you can look to skip militia entirely (and buy goons later, say).

[rrenaud]

Have you considered hard coding some of the human learned rspeer/gerinomoo bots as competitors?  Presumably playing against a better baseline would help speed up the learning.

[techmatt]

For example a 4/3 start might suggest a militia but if you have a 5/2 start you can look to skip militia entirely (and buy goons later, say).

The AI does condition its build on 2-5 vs. 3-4 splits.  See for example http://graphics.stanford.edu/~mdfisher/Images/Dominion/Game34vs25.png
The top line for each game shows whether it's training on a 3-4 or 2-5 split.  In this case it skips Militia in the 2-5 game.

Have you considered hard coding some of the human learned rspeer/gerinomoo bots as competitors?  Presumably playing against a better baseline would help speed up the learning.

I did do some brief tests for this.  There is pretty high variance; naturally, everything depends on the kingdom, and Dominion has a high variance game, but unless a specific combination of cards has been encoded into rspeer's AI, the kingdom-specific trained builds will do significantly better (typically somewhere between 70-30 on most kingdoms).
At first glance it would seem like a good idea to train against a strong baseline.  This would definitely help with the initial generations when the AI is proposing a lot of very random and consequently terrible builds until it finds a plausible one.  The problem with training against a stronger baseline is that it tends to bias the AI towards taking advantage of the weaknesses in the baseline.  For example, the baseline might always purchase 2 militias, causing the AI to bias itself towards getting extra libraries.  This might work well versus the baseline but result in poor performance once played against humans or un-biased AIs that don't make the same mistakes the baseline does.

[rrenaud]

Shouldn't the hard coded strategies eventually get out competed, and then fall out of the opponent pool?

Do you have a measure of how many distinct kingdom cards dominant strategies tend to use?

If it tends to be low, you could imagine saving dominant strategies into a database, and then finding historical dominant strategies as initial candidates for a given set.  If it's not low, you can imagine optimizing to prune cards out of a strategy so that it uses only 3 distinct and still maximizes its chances against the full strategies.  These would then be good initial candidate strategies to any applicable sets.

[blueblimp]

Interesting, but the example strategies in the write-up aren't convincing. The 2nd kingdom obviously wants a KC-Bridge megaturn, which the AI didn't find.

I don't quite follow. I think its biggest problem is definitely prioritizing Bridge and FV over Chapel, but the rest of its buy strategy looks fit for a KC-Bridge megaturn.

Whoops, I got my kingdom numbering off and actually meant the kingdom with KC + Rabble + Bridge, where the bot only buys 1 each of KC and Bridge (and prefers Silver over Lighthouse), and I'm pretty sure early greening sans-Lighthouse will be absolutely crushed by KC-Rabble into megaturn.

[techmatt]

Whoops, I got my kingdom numbering off and actually meant the kingdom with KC + Rabble + Bridge, where the bot only buys 1 each of KC and Bridge (and prefers Silver over Lighthouse), and I'm pretty sure early greening sans-Lighthouse will be absolutely crushed by KC-Rabble into megaturn.

It's true that this is probably an inferior strategy, as the image you're talking about is just showing the chain of strategies the AI goes through.  In the case of this particular kingdom, the AI hasn't converged yet since it takes a while to discover the KC+Bridge strategy.  If you let the AI run for longer it will converge to something close to the mega-turn strategy:
http://graphics.stanford.edu/~mdfisher/Images/Dominion/KCBridge.png

[DG]

Of course if you let other people play with it they are bound to find bugs - throned cards are not being cleaned up at end of turn and I'm not convinced they are correctly applied either. I don't know if this applies to the AI generally or just the human player.

[techmatt]

throned cards are not being cleaned up at end of turn

Most of this is a problem with visualizing the cards, although it's possible the internal state machine used by the AI is also wrong in this regard.  The user interface is not really meant for anything more than basic testing of the AI; ideally people would just be playing through a Goko or Isotropic interface instead as those are better tested and more user-friendly.  I'll look into the throned card problem; there are also any manner of fairly bizarre corner cases involving KC -> TR -> duration cards.

[Polk5440]

A natural question to ask is what is the ratio of complex to simple kingdoms. It turns out that complex kingdoms are definitely the exception and the vast majority of kingdoms are simple, converging directly to a very good strategy in a small number of iterations. Out of a thousand kingdoms, I was only able to find about five with non-dominating behavior.

Even if finding the best strategy is difficult more often, this makes me a little sad.

[Polk5440]

Also, Matt, if you are fixing bugs, I noticed that Talisman does not actually gain you a copy of a card. (The instance I had was play Talisman, buy Treasure Map, and I only gained only one Treasure Map.)

[techmatt]

Shouldn't the hard coded strategies eventually get out competed, and then fall out of the opponent pool?

Except in very weird circumstances, they will (likely) eventually get weeded out as you suspect.  I did something like this with big-money variants, but those are fairly simple so don't really have much impact.  Using well-trained AIs could definitely help improve training times, although it already trains reasonably fast.

Do you have a measure of how many distinct kingdom cards dominant strategies tend to use?

Averaged over a few hundred games, it's typically 4-6 cards, although sometimes it's just a simple "if you have exactly 2$, buy a cellar" sort of thing.

If it tends to be low, you could imagine saving dominant strategies into a database, and then finding historical dominant strategies as initial candidates for a given set.  If it's not low, you can imagine optimizing to prune cards out of a strategy so that it uses only 3 distinct and still maximizes its chances against the full strategies.  These would then be good initial candidate strategies to any applicable sets.

Current plans are along these lines.  At present the initial seed for the 1st generation is just random mutations of big money.  Instead, it could be the X-best strategies from the Y-most similar kingdoms in the training set.  That way, if we had say, Wharf or Mountebank, the initial pool will be flooded with these cards.  Might quash some good/interesting strategies that manage to avoid these cards, but more likely than not it would converge to something similar with fewer generations.

[Rabid]

Thanks for posting about this techmatt, really interesting AI you have made.
Would you mind sharing it isotropic user name by any chance?
I would be interested in seeing some of its old games on Council Room.
http://councilroom.com/

[techmatt]

Even if finding the best strategy is difficult more often, this makes me a little sad.

I'll admit I was a bit surprised myself.  The reason I made the big "tournament matrix" on the right was mostly because I expected it to actually be rare that a single strategy dominated.  Naturally, there might be some difference between this AI and a near-optimal player, but I suspect that even in the case of a very good player there is still typically a single dominant strategy that cleverly balances offense vs. defense (and any other compromise that needs to be made).

More concretely, if you look at the tournament matrix in these two kingdoms:
http://graphics.stanford.edu/~mdfisher/Images/Dominion/simpleGameA.png
http://graphics.stanford.edu/~mdfisher/Images/Dominion/simpleGameB.png
They all have the same "strictly dominating" structure; A > B > C > D > E, and not something more "rock-paper-scissors" like A > B > C > A.

[techmatt]

Also, Matt, if you are fixing bugs, I noticed that Talisman does not actually gain you a copy of a card. (The instance I had was play Talisman, buy Treasure Map, and I only gained only one Treasure Map.)

I am fixing bugs, thanks for pointing this one out.  Sometimes when I change things to accommodate new cards something I've already implemented/tested gets broken and I only find out because the AI refuses to pick the card (which is a pretty wise choice, when talisman does nothing).

Would you mind sharing it isotropic user name by any chance?

At the moment I don't have a very good interface to Isotropic, and just have to manually copy+paste the entire webpage *each decision* into a special "Isotropic dominion state machine extractor" program, that then parses the page and spits out the AIs decision, which I have to manually translate back into the Isotropic interface.  It's pretty hilariously inefficient, which is why I haven't run many games, and I decided to just use the username of one of my friend's; I'll poke him while I decide on if I want to work out a more clean Isotropic interface (which I suspect won't be worth the effort, both as Isotropic is going down and an AI isn't as interesting as human opponents).

[rrenaud]

It doesn't surprise me that most games of dominion have one dominant strategy.  Dominion gets a lot of its replayability from the variable kingdom set selection, I doubt it would be a good a game with a fixed set of 10 kingdom cards (see the 'A few acres of snow' balance debacle for evidence).

Have you considered sending goko a mail and working with integrating your AI into their system? 

[soulnet]

an AI isn't as interesting as human opponents).

I strongly disagree, having an AI that plays incredibly fast let you test things that is hard to do with humans. If there were an AI on Iso I would have played it a lot when I don't have a lot of time to spend or want to have the hability to cancel games in the middle without annoying a fellow player. The only reason I play several games I have on my computer instead of playing on Iso all the times is this flexibility that computers give as I don't feel a need to consider their feelings (please refrain from making comments with Matrix/Terminator/other sci-fi induced jokes).

EDIT: Is also great when you are new and are trying to learn all the cards at once, which was my case as I went into Iso only having played Base IRL a few times. Reading and understanding all the cards before a game can be annoying to other players who want a fast casual game.

[techmatt]

Have you considered sending goko a mail and working with integrating your AI into their system?

I've thought about it but haven't contacted them yet.  Toying around with the goko code, integration seems like it would be fairly straightforward.  Getting wider playability is also nice for any statistical approach (I'm naturally familiar with councilroom's data-mining, but it's still difficult or impossible to fully reconstruct the state at each time-step).  However I was planning on finishing implementing the rest of the cards and switching to non-copyrighted versions of the artwork before I contact them.

I don't have a lot of time to spend or want to have the hability to cancel games in the middle without annoying a fellow player

Is also great when you are new and are trying to learn all the cards at once

These are good reasons, although it's unfortunate (but understandable) that Isotropic is going down as writing an "API interceptor" for that would be simpler than integrating with Goko.  Of course Goko already has an AI; the main point would be making playing the AI actually challenging.  Provincial isn't as good as it could be yet, but integrating its "pre-game buy analysis" with Goko's "mid-game card play awareness" is likely to be fairly effective.  Although a few of the AIs advantages are a bit brutal (wishing well, for example, it can just pick the most likely card left in its deck, which it can always know precisely).

[Toskk]

Although a few of the AIs advantages are a bit brutal (wishing well, for example, it can just pick the most likely card left in its deck, which it can always know precisely).

Even brutal would be better than Goko's current AI implementation of Wishing Well, though.. I've watched that AI play Scout.. followed by Wishing Well.. and fail to pick the card on top.

[Donald X.]

These are good reasons, although it's unfortunate (but understandable) that Isotropic is going down as writing an "API interceptor" for that would be simpler than integrating with Goko.  Of course Goko already has an AI; the main point would be making playing the AI actually challenging.  Provincial isn't as good as it could be yet, but integrating its "pre-game buy analysis" with Goko's "mid-game card play awareness" is likely to be fairly effective.  Although a few of the AIs advantages are a bit brutal (wishing well, for example, it can just pick the most likely card left in its deck, which it can always know precisely).

Of course sometimes you want to make sure you don't draw the card, and sometimes you only want to draw the card if it's dead, and sometimes you want to gamble on something more helpful than the most common card.

Goko has said that they will let people write bots for them. Dunno when that will happen.

It has always seemed to me, and this seems obvious but why not say it, that the best approach to tactics is to have two algorithms. One is full of ad hoc logic and just makes each decision as best it can, like what Goko has. The other algorithm considers each possible move, and for each move it plays out the rest of the game however many times you can do quickly enough, with each player using the ad hoc logic, and then it picks the move that did the best. This will let you do clever things that would normally be wrong, but won't find a combination of two normally wrong things.

Strategy seems much harder, since it necessarily involves combinations, and you only have so much time between turns. Pick-order seems good for the early game; obv. the endgame has important factors missing there, and sometimes the game can end any moment on a huge turn that runs out piles. You might just want an unrelated endgame algorithm. And then it seems great to re-evaluate your strategy as of turn 4, with where your initial buys ended up being the major factor but obv. endless other things about the specific state contributing.

@Toskk: They know about the Scout/Wishing Well thing; obv. they simply don't track their knowledge of the top cards.

[Schneau]

It has always seemed to me, and this seems obvious but why not say it, that the best approach to tactics is to have two algorithms. One is full of ad hoc logic and just makes each decision as best it can, like what Goko has. The other algorithm considers each possible move, and for each move it plays out the rest of the game however many times you can do quickly enough, with each player using the ad hoc logic, and then it picks the move that did the best. This will let you do clever things that would normally be wrong, but won't find a combination of two normally wrong things.

You are essentially describing a version of the minimax algorithm adjusted for nondeterministic games. The main problem here is that the branching grows exponentially for each decision, as well as exponentially for each random event (like what cards you draw). So, you can only look so far into the future in a short period of time.

[Donald X.]

It has always seemed to me, and this seems obvious but why not say it, that the best approach to tactics is to have two algorithms. One is full of ad hoc logic and just makes each decision as best it can, like what Goko has. The other algorithm considers each possible move, and for each move it plays out the rest of the game however many times you can do quickly enough, with each player using the ad hoc logic, and then it picks the move that did the best. This will let you do clever things that would normally be wrong, but won't find a combination of two normally wrong things.

You are essentially describing a version of the minimax algorithm adjusted for nondeterministic games. The main problem here is that the branching grows exponentially for each decision, as well as exponentially for each random event (like what cards you draw). So, you can only look so far into the future in a short period of time.

No, not what I am describing. We consider each possible move, and for each possible move we play out the rest of the game. However! When playing the rest of the game we *do not* consider each possible move - we use the ad hoc logic there to make decisions. It's not recursive.

[Schneau]

It has always seemed to me, and this seems obvious but why not say it, that the best approach to tactics is to have two algorithms. One is full of ad hoc logic and just makes each decision as best it can, like what Goko has. The other algorithm considers each possible move, and for each move it plays out the rest of the game however many times you can do quickly enough, with each player using the ad hoc logic, and then it picks the move that did the best. This will let you do clever things that would normally be wrong, but won't find a combination of two normally wrong things.

You are essentially describing a version of the minimax algorithm adjusted for nondeterministic games. The main problem here is that the branching grows exponentially for each decision, as well as exponentially for each random event (like what cards you draw). So, you can only look so far into the future in a short period of time.

No, not what I am describing. We consider each possible move, and for each possible move we play out the rest of the game. However! When playing the rest of the game we *do not* consider each possible move - we use the ad hoc logic there to make decisions. It's not recursive.

Ah, I see. The thing is, this doesn't gain you much (or anything) over just using the ad hoc logic, since the future-looking part of it assumes that the ad hoc logic will be used, but when that point in the actual game happens, the look-forward search will happen. I could see it gaining a little, but using the ad hoc logic for the forward-looking search makes the process highly dependent on the quality of the ad hoc logic - and if your ad hoc logic is that good, you might as well use that instead!

[Donald X.]

Ah, I see. The thing is, this doesn't gain you much (or anything) over just using the ad hoc logic, since the future-looking part of it assumes that the ad hoc logic will be used, but when that point in the actual game happens, the look-forward search will happen. I could see it gaining a little, but using the ad hoc logic for the forward-looking search makes the process highly dependent on the quality of the ad hoc logic - and if your ad hoc logic is that good, you might as well use that instead!

I don't agree with your argument at all. This could turn into one of those things I regret pouring time into, so so much for that.

[Schneau]

Ah, I see. The thing is, this doesn't gain you much (or anything) over just using the ad hoc logic, since the future-looking part of it assumes that the ad hoc logic will be used, but when that point in the actual game happens, the look-forward search will happen. I could see it gaining a little, but using the ad hoc logic for the forward-looking search makes the process highly dependent on the quality of the ad hoc logic - and if your ad hoc logic is that good, you might as well use that instead!

I don't agree with your argument at all. This could turn into one of those things I regret pouring time into, so so much for that.

That's fine - I could very well be wrong! I do research in artificial intelligence, but do not have much background in game AI.

[GwinnR]

I've played with this some times yet and now I want to make an Simulation-tournament, but I don'T get, how it works.
I go to "game options" and write the required cards down, but when I want to "run tournament" he doesn't take the cards I wrote.
Can someone tell me what I'm doing wrong?

[techmatt]

No, not what I am describing. We consider each possible move, and for each possible move we play out the rest of the game. However! When playing the rest of the game we *do not* consider each possible move - we use the ad hoc logic there to make decisions. It's not recursive.

Donald's argument is fine and is a pretty good algorithm for Dominion.  The more general version of this strategy is called Monte-Carlo tree search, and is what's used for games with really deep branching factors like Go.  The main advantage in the case of Dominion is that you can avoid the need to try and define a "state value function", that will numerically decide how good each of the many trade-offs in the game is (what is the relative value of getting the "discard down to 3" Militia effect vs. depleting 3 victory cards from the top of your deck for a better next turn?)  Since Dominion games aren't that long, Donald is just suggesting running simulations that go the end of the game directly, after making a single decision, and choosing the option with the best expected value.

If you look at the top-right figure of http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf -> this algorithm is just skipping the expansion phase.  Select -> Simulate -> Backpropogate and repeat until you feel confident enough about your choice.

A simple extension to the algorithm would be to consider branching out slightly deeper (probably just to depth 2 or 3), and having certain decisions where the heuristic is just called directly (example: generally when playing treasure cards, all this simulation work is just going to be wasted).  The real complication is when deciding what to buy -- this could work, but it's equally likely to result in some really weird (and probably bad) purchases; there isn't a clear "heuristic choice" for buys.  For that (I'd argue) you need to use a much more sophisticated engine (which is the part I was focusing on, for this reason).

You might just want an unrelated endgame algorithm

You probably would, but even this can do reasonably well.  For example, to answer the end-game question of "I have 5 coins; should I buy a lab or a duchy"?  This algorithm will give you the ad-hoc expectation of which is more likely to win you the game.  I'd bet this is pretty well correlated with the "correct" answer.  Naturally for things like buying out a 3rd pile to force an early end, you'd need something more specialized.

[techmatt]

I go to "game options" and write the required cards down, but when I want to "run tournament" he doesn't take the cards I wrote.
Can someone tell me what I'm doing wrong?

Click on "New Kingdom Cards" after you enter the required cards.  This will update the current game (you should see it reflected back in the "Main" window), then click Run Tournament.

[GwinnR]

I go to "game options" and write the required cards down, but when I want to "run tournament" he doesn't take the cards I wrote.
Can someone tell me what I'm doing wrong?

Click on "New Kingdom Cards" after you enter the required cards.  This will update the current game (you should see it reflected back in the "Main" window), then click Run Tournament.

Thanks! Works now! Very cool job you've done there!

Edit: But there are not all cards required, do they?

[Donald X.]

The real complication is when deciding what to buy -- this could work, but it's equally likely to result in some really weird (and probably bad) purchases; there isn't a clear "heuristic choice" for buys.  For that (I'd argue) you need to use a much more sophisticated engine (which is the part I was focusing on, for this reason).

Yes, I would do the thing I said for short-term "tactics," more specifically decisions on how to play out turns, other than what to buy/gain; but it doesn't work for long-term "strategy," more specifically buys/gains, again because for strategy you need to consider combinations of decisions, which this doesn't.

[techmatt]

Edit: But there are not all cards required, do they?

If you specify fewer than 10 cards, it will just pick the new ones randomly.  Although it doesn't currently have every card in every published expansion.
You could also go into data/parameters.txt and set useCustomCards to true, if you want more variety.  You can browse the custom cards in data/custom, although they're disabled by default.

[GwinnR]

Although it doesn't currently have every card in every published expansion.

Ok, that was that, what I ment. I was a little astonished, because I wanted to try a set and it only always only got three cards of it.

[Tables]

If this were implemented into Goko, could the algorithm be sped up by say starting off using Lord Bottington's rules, then running the learning stuff?

[techmatt]

If this were implemented into Goko, could the algorithm be sped up by say starting off using Lord Bottington's rules, then running the learning stuff?

Yes, although the simpler solution is just to instead "pre-train" it in on 10,000+ randomly sampled kingdoms.  Then training would only take a few seconds, as you run the best AIs of nearby kingdoms against each other to decide which are the best.  In this case, you wouldn't really need to run the learning phase.

[PitzerMike]

Do you rank the cards by how much of a game-changing effect they have in order to help select nearby kingdoms?

[techmatt]

Do you rank the cards by how much of a game-changing effect they have in order to help select nearby kingdoms?

At present no, I just look at the percentage of overlap in kingdom cards, which is pretty discrete (either 4/10 or 5/10 but never 4.6/10, for example).  But as you suggest it would probably be better to weight them according to how important they were, which could likely be estimated from councilroom data of "+win%" from people who have bought at least 1 of the card.

[GwinnR]

Are you going to implement all cards?

[Matt_Arnold]

This is great! But how do you play with the custom cards? I tried to type them into the card requirements field and they were ignored.

Also, is it possible to program my own custom cards?

Sorry if this has been covered elsewhere, but I couldn't find it in this thread or on the webpage about Provincial.

[Maveric78f]

I played a bit with the soft. It's pretty good. I'm not familiar with the interface yet, but it should come. I just noticed a bug : lighthouse does not protect from minion draw 4.

[Maveric78f]

There is another bu with grand market remaining in play as if it was a duration card.

Actually, the false duration card bug seems to be linked with King's Court.